1
$\begingroup$

I want to solve the following optimization problem: $$\min_{A,B,X} \|Y-AX\|_F^2 + \lambda_1 \|Z-BX\|_F^2+ \lambda_2 \|B\|_F^2$$ $$s.t ~~x_{ij}~ \geq 0$$

in which, $Y$ and $Z$ are data matrices and are $d \times n$ and $l \times n$ (the corresponding columns of $Y$ and $Z$ are data samples), and $A,B,X$ are the parameter matrices and are $d \times k$, $l \times k$ and $k \times n$ respectively. $n$ is around 100 and $d,k$ are around 20.

I think this is called a multivariate optimization problem. I tried to solve it using a general solver like Matlab's "fmincon" and it found a good minimum point. I think it uses the sequential programming algorithm.

My question is how can i solve this optimization problem in a systematic way to find a good optimum point comparable to what the Matlab solver found?

$\endgroup$
1
$\begingroup$

Note that this is a nonconvex problem. So expecting to solve the problem to an optimal solution might not be reasonable. But with a good method and good initialization, you might be able to converge to a good solution, although it might be difficult to prove that it is the optimal solution. One method that you can use to solve such a problem is to use block coordinate descent or alternative optimization. There are many of papers on this, e.g. http://www.math.ucla.edu/~wotaoyin/papers/bcu/.

In your case, the blocks would be $X$ and $(A,B)$. So in each iteration of the algorithm, you fix one block and update the other block by directly minimizing the objective with respect to the other block. If this is computationally intractable you can always linearize the objective. This is equivalent to just taking the gradient of the objective with respect to the non-fixed block and project it back to the feasible set.

In case of your problem, in the $X$ iterations, you fix $(A,B)$ and then update $X$ by a gradient step and then project it back to non-negative orthant to keep it feasible. Then, alternatively, you fix $X$ and update $(A,B)$ by a gradient step (or optimizing with $X$ fixed). You perform this update until convergence. Note that you need to be careful with the step-size in each of those steps, if you are using the gradient, in order to make sure you always reduce the objective by each update.

$\endgroup$
  • $\begingroup$ Thank you for the response. I've already tried alternative optimization solution, but it is still sub-optimal comparing to what the matlab non-linear solver achieves. Mainly because in each optimization block (especially A,B) half of the obj. function won't be considered and the update of parameters will not be in the best direction regarding the optimality of the whole cost function. $\endgroup$ – Bob Sep 12 '17 at 9:00
  • $\begingroup$ I don't understand what you mean by half of the objective function won't be considered? Plus the gradient direction is the best descent direction for a small enough step. If you have implemented the method correctly, your objective function should be decreased in each iteration. As I said, this method will only converge to a stationary solution. So, you might need to do multiple random or pre-designed initializations to get good results. You can also check to see if the solution you get from Matlab is at least a stationary solution by initializing the method with it. $\endgroup$ – Maziar Sanjabi Sep 12 '17 at 17:26
0
$\begingroup$

If you care about finding global optimality, your best bet is to use a more advanced MINLP solver such as BARON. Since you're using MATLAB, try checking out the OPTI Toolbox.

$\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.