1
$\begingroup$

The goal is to approximate some function u known at some values s as a sum of function of the form $( x - K)_{+}$

Given $(K_{i})_{1 \le i \le N_{k}} \in R^{+}$ , $(u_{i},s_{i})_{1 \le i \le N} \in R$ ( can be restricted to some compact of the form $]-S;S[$ ) I want to solve the following problem $\min_{\alpha \in R^{N_{k}}} || \sum_{i=1}^{N}(u_{i}-\sum_{j=1}^{N_{k}}\alpha_{j}(s_{i}-K_{j})_{+}||^{2}$ under the N constraints $ u_{1} \le g(s_{1}) , u_{2} \le g(s_{2}) ,....,u_{n} \le g(s_{n})$ where $g(x)= \sum_{j=1}^{N_{k}}\alpha_{j}(x-K_{j})_{+}$ ( I want my approximation to be at least always superior to my fonction u in each point )

Is there a solution to this problem ? Is it unique ? And if the solution can't be found analytically , what algorithm should i use?

$\endgroup$
2
  • $\begingroup$ $u_i, s_i$ are given, i.e., inputs? What is $u(s_i)$? What is $g(s_i)$? Those are highly relevant to assessing the properties of this problem and how to solve it. If everything in the objective function (i.e., function being minimized) is given (i.e.. input), the objective function is linear least squares. As to what the constraints are? That depends on the answers to my questions. $\endgroup$ Aug 29, 2020 at 22:50
  • $\begingroup$ I have edited , i hope its more clear , but I want my approximation in terms of sums to be always equal or greater than my fonction u in each point ( recall i dont know u , i only know some values at each point $s_{i}$) $\endgroup$
    – Kupoc
    Aug 30, 2020 at 8:03

1 Answer 1

0
$\begingroup$

This is a linearly constrained linear least squares problem. There are many available solvers for this class of problems.

In lieu of a linearly constrained linear least squares solver, this can be solved with any Quadratic Programming solver, because a linearly constrained linear least squares problem is a convex Quadratic Programming (QP) problem.

The objertive function (i.e., the function being minimized) is the square of the 2-norm of the summands. So an alternative to the QP formulation, and which is more robust numerically because ti avoids squaring the condition number, is to not square the 2-norm, which results in a Second Order Cone problem (SOCP), for which there are several solvers.

In general, it is not possible to say whether the solution will be unique. Depending on the input data, it is possible that the problem could be infeasible, i.e., no solution exists which satisfies all the constraints.

If you say what computing environment you would like to use, I can suggest solvers and'/or modeling systems within that environment.

I will also note that rather than having the objective function being the 2-norm (squared) of the summands, you might want to use the L-1 norm, i.e., sum of absolute values. That can be transformed into a Linear Programming (LP) problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .