4
$\begingroup$

I need to solve the following inequality-constrained least-squares problem in vector $x$

$$ \min_{Ax \geq 0} \frac{1}{2} \|Ax-b\|_2^2$$

where matrix $A$ and vector $b$ are given.

I am totally stuck. Classical non-negative least-squares problems have $x \geq 0$, not $Ax \geq 0$.

$\endgroup$
  • 1
    $\begingroup$ I am confusing about your statement. If $x$ is a vector, then $Ax$ should be a vector, too. Hence $B$ should be a vector. $\endgroup$ – foxell May 5 '19 at 5:47
  • $\begingroup$ @Rodrigo de Azevedo As you of course know, the Frobenius norm and 2-norm are tow different names for the same thing when the argument is a vector. $\endgroup$ – Mark L. Stone May 5 '19 at 10:42
  • $\begingroup$ @Rodrigo de Azevedo It is not the notation Iwouldl have used, but it is not incorrect. $\endgroup$ – Mark L. Stone May 5 '19 at 10:44
  • $\begingroup$ @RodrigodeAzevedo A vector is a matrix in some sense ;-). But yes, I'll edit for clarity. And thank you to have edited my question $\endgroup$ – MysteryGuy May 5 '19 at 12:08
  • 1
    $\begingroup$ How about using $y := Ax$, solving the instance of classical NNLS, and then solving $A x = y$ for $x$? $\endgroup$ – Rodrigo de Azevedo May 5 '19 at 12:12
5
$\begingroup$

Use a linearly constrained linear least squares solver.

For example: lsqlin in MATLAB https://www.mathworks.com/help/optim/ug/lsqlin.html

lsei in R https://rdrr.io/rforge/limSolve/man/lsei.html

The easiest way might be using CVX https://cvxr.com/cvx under MATLAB. CVXR https://cvxr.rbind.io/ under R, or CVXPY https://www.cvxpy.org/ under Python.

Here is the code for CVX:

cvx_begin
variable x(n)
minimize(norm(A*x-b))
A*x >= 0
cvx_end

which will transform the problem into a Second Order Cone Problem, send it to a solver, and transform the solver results back to the original problem as entered. You can include the factor of 1/2 (harmless) and square the norm, which doesn't affect the solution but needlessly makes the problem solution less numerically robust.

Edit: Extra details as requested in chat:

CVX calls a numerical optimization solver to solve the optimization problem. The solver enforces the specified constraints (within solver tolerance).

As mentioned above, CVX actually transforms this into an SOCP (Second Order Cone Problem) by converting the problem into epigraph formulation. It does this by introducing a new variable, t, and in effect moving the original objective to the constraints. Thus produce the problem.

minimize(t)
subject to
  norm((A*x-b) <= t
  A*x >= 0

There might also be a slight rearrangement of the constraint A*x >= 0. CVX calls a Second Order Cone solver optimization solver such as SeDuMi, SDPT3, Gurobi, or Mosek to solve this problem. It then transforms the results back to the original problem formulation as entered by the user.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I ended up by using cvx but I was wondering if there is way to solve the problem with the KKT conditions and find a closed-form for $x$ with them ? Actually, I started writing KKT conditions but failed to find a closed form for $x$ and the Lagrangian multiplier vector inherent to it . Thank you if you can answer to it $\endgroup$ – MysteryGuy May 5 '19 at 5:43
  • 1
    $\begingroup$ You'd have to numerically solve the KKT conditions. So you are better off using a numerical optimizer, which in effect is also numerically solving the KKT conditions, but likely in a better way that you would do by explicitly forming the KKT solutions. Using CVX also eliminates the possibility of you making a mistake in the formulation of KKT conditions. $\endgroup$ – Mark L. Stone May 5 '19 at 10:35
3
$\begingroup$

Consider matrix $C$ such that: $$Ran(C)=Ran(A)^{\perp}$$ Here $Ran(A)$ is the range of matrix $A$. Then we have: $$x\in Ran(A)\Leftrightarrow C^{T}x=0$$ Thus the primal problem is equivalent to: $$\min_{y}\frac{1}{2}\parallel y-b\parallel^2,\ \ \ \ C^{T}y=0,y\geq0$$ Consider the dual function: \begin{align}L(\lambda)&=\min_{y}\{\frac{1}{2}\parallel y-b \parallel^2+\lambda^TC^Ty:y\geq0\} \\ &=\min\{\frac{1}{2}\parallel y+C\lambda-b \parallel^2-\frac{1}{2}\parallel C\lambda\parallel^2+<C\lambda,b>:y\geq0 \} \end{align} Which clearly has closed-form solution:$$L(\lambda)=\frac{1}{2}\parallel(b-C\lambda)_{-}\parallel^2-\frac{1}{2}\parallel C\lambda-b\parallel^2+\frac{1}{2}\parallel b\ \parallel^2$$ So the dual problem: $$ \max_{\lambda}L(\lambda)$$ The dual is problem is equivalent to:$$\min_{\lambda }\frac{1}{2}\parallel(b-C\lambda)_{+}\parallel^2$$ Here $x_{+}=(max(0,x_1),max(0,x_2)...)$. If you get the solution of the dual problem, then come back to KKT condition of the primal problem and the definition of $y$:\begin{align} y-b+ C\lambda&=0\\ C^Ty&=0 \end{align} The condition $C^Ty=0$ ensures that there is a $x$ such that $Ax=y$, hence this $x$ would be the optimal solution of your problem.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What is Ran ? Thanks $\endgroup$ – MysteryGuy May 5 '19 at 6:42
  • $\begingroup$ I mean the range of matrix $A$ and $C$. $\endgroup$ – foxell May 5 '19 at 6:44
  • $\begingroup$ If I understand your answer, I have no other choice than using a solver ? $\endgroup$ – MysteryGuy May 5 '19 at 6:48
  • $\begingroup$ Thank you for pointing out this mistake, and after correcting this error, the last problem has nice structure. I was wondering if this problem has closed-form solution. $\endgroup$ – foxell May 5 '19 at 6:57
  • 1
    $\begingroup$ I have written how you can get the optimal solution of the primal problem from the optimal solution of the dual problem. I think probably the dual problem don't have a closed-form solution, since it is very similar to Lasso problem. You may solve the dual problem using FISTA (if you know about this algorithm), which could reach the optimal convergence rate $O(\frac{1}{k^2})$ in the theoretical view. $\endgroup$ – foxell May 5 '19 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.