2
$\begingroup$

I am trying to solve a least squares problem where the objective function has a least squares term along with L1 and L2 norm regularization. I am unable to find which matlab function provides the ability to perform such an optimization in addition to specifying constraints. I looked into the MATLAB optimization toolbox which also does not provide too much freedom to specify own objective functions (although I hope I am wrong in this case!) in the case of leastSquares optimization problems. If anyone knows how to model such an optimization problem in matlab please do help me out. The optimization problem is as follows:

enter image description here

Here aj is an m X 1 vector and A is an mXn matrix , wj is an n x 1 vector. I don't know how to incorporate the two additional regularization terms into the optimization problems as they only accept 2 matrices and perform the least squares operation on them. I would like to know how to implement this objective function and pass it into matlab optimization toolbox leastSquares function. Any help would be appreciated. If not in the optimization toolbox, alternative implementations of this problem in CPLEX using matlab would also be helpful.

thanks in advance!

$\endgroup$
4
  • $\begingroup$ Do you have multiple vectors ${\mathbf w}_j$? If so, is the objective function missing a sum over $j$? $\endgroup$ Feb 14, 2014 at 4:32
  • $\begingroup$ Nope I was planning to run it in a for loop as all wj vectors are independent of each other so it doesn't matter. The problem instance described above in the objective function is the distributed version of the entire objective function where all vectors are replaced by the actual matrix (aj by A and wj by W) $\endgroup$ Feb 14, 2014 at 4:35
  • $\begingroup$ So basically my question is how would I implement exactly this optimization problem in an optimization library like CPLEX (which provided a function for nonnegative Least Squares) using matlab or in Matlab optimization toolbox. $\endgroup$ Feb 14, 2014 at 4:36
  • $\begingroup$ This is presented more clearly in the following paper if anyone is interested glaros.dtc.umn.edu/gkhome/node/774 $\endgroup$ Feb 14, 2014 at 4:53

1 Answer 1

1
$\begingroup$

This isn't a linear least squares problem as it is written. However, the problem does simplify down to a quadratic optimization problem with nonnegativity constraints and you can even write it as a linear least squares problem with nonnegativity constraints. .

First, since $w_{j,j}$ is constrained to be 0, it has no effect on the objective function. Let $\bf{w}$ be the $n-1$ element vector consisting of the elements of $\bf{w}_{j}$ other than $w_{j,j}$. You can simply remove column $j$ from the $A$ matrix and solve for the $n-1$ by $1$ vector $w$. After you've found $\bf{w}$, you can insert the $0$ in the $j$th position. Let $\hat{A}$ be the $A$ matrix with the $j$th column removed.

Second, since $\bf{w}_{j} \geq 0$, $\| \bf{w}_{j} \|_{1}$ is simply the sum of the elements of the $\bf{w}$ vector.

Now, you can write your problem in terms of the $w$ vector as

$\min_{{\bf w}} \;\; \| a_{j} - \hat{A} {\bf w} \|_{2}^{2} + \frac{\beta}{2} \| {\bf w} \|_{2}^{2} + \lambda \sum_{k=1}^{n-1} w_{k}$

subject to

$\bf{w} \geq 0$.

You can rewrite the objective function in quadratic form as

$\min_{{\bf w}} \;\; (a_{j}-\hat{A}{\bf w})^{T}(a_{j}-\hat{A}{\bf w})+\frac{\beta}{2}{\bf w}^{T}{\bf w} + \lambda \sum_{k=1}^{n-1} w_{k}$

subject to

$\bf{w} \geq 0$.

Combining the quadratic parts of the first two terms and combining the linear terms and the constant term gives

$\min_{{\bf w}}\;\; {\bf w}^{T}(\hat{A}^{T}\hat{A}+\frac{\beta}{2}I){\bf w} + (-2\hat{A}^{T}a_{j}+\lambda {\bf 1})^{T}{\bf w} + a_{j}^{T}a_{j}$

subject to

$\bf{w} \geq 0$.

At this point, you could "complete the square" to turn this into a nonnegative least squares problem and then use the MATLAB function lsqnonneg to solve the problem.

A simpler solution (that would probably perform equally well) is to use the Optimization Toolbox function quadprog to solve the problem. CPLEX could also easily solve the quadratic programming problem.

You haven't said anything about the size of the problem- if the problem is particularly large then it may be very important to pay attention to the algorithm used to solve the problem. In particular, if $A$ is sparse, then you will want to make sure that your solver can take advantage of that fact.

$\endgroup$
4
  • $\begingroup$ Well the problem is quite large. There are 36000 rows and 4503 columns in the matrix A. Hence I am trying to run it using CPLEX which is the only optimization package installed on the computer cluster I have access to. And how does the problem change if A is a sparse matrix? $\endgroup$ Feb 14, 2014 at 6:06
  • $\begingroup$ Generally speaking, the problem won't change. If you have the option of setting up the problem using sparse data structures in the MATLAB interface to CPLEX, you should avail yourself of that option to save memory. CPLEX will usually handle the rest; it has good heuristics, and will select a reasonable method for solving the problem. For a problem that large, I would not use a standard MATLAB solver like quadprog unless I had no other option. $\endgroup$ Feb 14, 2014 at 6:11
  • $\begingroup$ I agree with Geoff that CPLEX is probably a better choice for this, even though I wouldn't call a problem of this size "quite large." $\endgroup$ Feb 14, 2014 at 14:52
  • $\begingroup$ To solve this problem using a standard QP solver, you'd need to multiply out $A^{T}A$ and pass that matrix to the solver. If $A$ is sparse, it is likely that $A^{T}A$ will be more dense than $A$ itself. An alternative would be to use an iterative method that only requires matrix-vector multiplications rather than giving the solver the entire matrix. $\endgroup$ Feb 14, 2014 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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