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$
  • $\begingroup$ Do you have multiple vectors ${\mathbf w}_j$? If so, is the objective function missing a sum over $j$? $\endgroup$ – Wolfgang Bangerth Feb 14 '14 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$ – user1009091 Feb 14 '14 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$ – user1009091 Feb 14 '14 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$ – user1009091 Feb 14 '14 at 4:53
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$
  • $\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$ – user1009091 Feb 14 '14 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$ – Geoff Oxberry Feb 14 '14 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$ – Brian Borchers Feb 14 '14 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$ – Brian Borchers Feb 14 '14 at 15:23

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.