2
$\begingroup$

What conditions need to be hold for a nonconvex optimization problem to have a unique solution?

Specifically, I have the following minimization problem that I'd like to know whether it has a unique solution or not:

$ \min_{\bf A, B} \| {\bf Y - XAB} \|_2^2 + \lambda_1 \|{\bf A}\|_1 + \lambda_2 \|{\bf B}\|_1$

where ${\bf Y}_{n \times q}$ and ${\bf X}_{n \times p}$ are fixed, and ${\bf A}_{p \times r}$ and ${\bf B}_{r,q}$ are the variables ($r \leq \min(p,q)$).

Also, I know that this minimzation problem is convex if either ${\bf A}$ or ${\bf B}$ are fixed (and so it has a unique solution in that case).

Is there a certain relaxation that transforms this into a convex problem?

$\endgroup$
2
  • $\begingroup$ It would help if you would specify the meaning of the notation $\|\cdot\|_1$, since there are at least three matrix norms which often use that same notation. But, at any rate, at least for the three I have in mind, ... $\endgroup$
    – cardinal
    Nov 20, 2014 at 1:55
  • $\begingroup$ Hint: Think about the set of $r \times r$ permutation matrices. $\endgroup$
    – cardinal
    Nov 20, 2014 at 1:56

2 Answers 2

2
$\begingroup$

In the absence of convexity (or weaker conditions such as quasiconvexity), I doubt that there are simple general conditions that could be stated. When there are multiple local minima, determining whether the objective values at those local minima are distinct might require detailed computation.

$\endgroup$
2
$\begingroup$

There is duality condition for Lagrangian Multipliers. That relaxes the things. If additionally Slater's condition is met (one needs to check), then the duality becomes strong duality where the solution of the dual problem and the primary problem perfectly matches. If however this condition is not met, there is positive gap, but of course a much simpler problem definition, i.e., the dual function is a concave function in the Lagrangian multipliers.

$\endgroup$

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.