0
$\begingroup$

There is a least-squares problem Ax = b. It can be solved using backslash in Matlab (x = A \ b).
Let's assume that I have the same problem, but all x must be non-negative (>=0). How can I solve this problem by analogy with the previous one (without non-negativity constraints)? I think it can be somehow connected with the active set method.
I know that the non-negative least squares problem can be easily solved with Matlab Optimization toolbox or CVX or in many other ways. But still I'm curious about solving it by analogy with a straight-forward least-squares method. The idea is to make somehow from non-negative least-squares regular least squares.
Could anyone help me please?

$\endgroup$
  • $\begingroup$ Is $A$ full rank? What are the dimensions of $A$? $\endgroup$ – jkn Nov 11 '13 at 20:29
2
$\begingroup$

"Straightforward" least squares cannot include constraints. It has a simple function to optimize, the sum of squared residuals, and that's it.

Exactly because of that, the solution $x$ can be found by means of linear algebra, i.e. it is the result of applying a linear operator to $b$. This linear operator is described by the matrix $(A^T A)^{-1} A^T$ if the system has a unique solution; if not, the pseudo-inverse $A^-$ defines a linear operator that gives the minimum-norm solution. Though it is recommended to use the backslash operator in Matlab for numerical reasons, that doesn't change this basic idea. As soon as you introduce constraints what you are doing is no longer "least squares", and the solution is no longer given by a linear operator applied to $b$.

To my knowledge, the task of optimizing a quadratic function under linear (equality or inequality) constraints is the subject of quadratic programming.

$\endgroup$
0
$\begingroup$

The problem - Non Negative Least Squares is a Convex Optimization problem yet it doesn't have a closed form solution.

Yet, since it is a Convex Optimization problem one could use many methods to solve it efficiently:

  1. Transformation into LP Problem.
  2. Using Interior Point Method.
  3. Using Projected Sub Gradient Method.

The last method can be viewed with connection to the classic Least Squares problem.
Solving regular Least Squares problem using Gradient Descent is easy.
How will it be different with the constraint applied?
Well, you will have to project the solution of each iteration onto the set of the constraints.

Here is the code:

%% Solution by Projected Gradient Descent

vX = zeros([numCols, 1]);

for ii = 1:numIterations
    vX = vX - ((stepSize / sqrt(ii)) * mA.' * (mA * vX - vB));
    vX = max(vX, 0);
end

The full code and validation against CVX is in my Mathematics Q561696 GitHub Repository.

$\endgroup$

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.