Solving this minimization problem 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?
 A: 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.
