4
$\begingroup$

Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?

$\endgroup$
7
$\begingroup$

For the general audience: a biconvex optimization problem is a problem of the form: $$\begin{array}{ll} \text{minimize} & f(x,y) \\ \text{subject to} & (X,Y)\in\mathcal{B} \end{array}$$ which is convex in $X$ for any fixed $Y$, convex in $Y$ for any fixed $X$, but is not convex in both $(X,Y)$ jointly.

No, biconvex problems are not polynomially solvable. They may have lots of local minima, so without knowing more about a special case, global optimization is the only alternative.

I suspect that the standard, obvious heuristic for a biconvex problem is to fix $X$ and minimize over $Y$, then fix $Y$ and minimize over $X$, and repeat.

Here is a reference you might find useful. I used this reference here. EDIT: the heuristic I describe above is called "Alternate Convex Search" in this reference; Algorithm 4.1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer, Michael. ACS is an iterative approach and it gives a convergent sequence of objective function but not necessarily convergent sequence of feasible points. The later is held when the sets X and Y are compact. In my case, X is not bounded. I am asking for another approach except GOP and ACS. $\endgroup$ – Star Apr 19 '13 at 13:57
  • $\begingroup$ The reference I gave you has more to say than I do :P $\endgroup$ – Michael Grant Apr 19 '13 at 14:05
  • $\begingroup$ Hi Michael, could you give an example of biconvex function that has multiple local minima? Thanks. $\endgroup$ – chaohuang May 6 '13 at 2:33

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.