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


1 Answer 1


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.

  • $\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, 2013 at 13:57
  • $\begingroup$ The reference I gave you has more to say than I do :P $\endgroup$ Apr 19, 2013 at 14:05
  • $\begingroup$ Hi Michael, could you give an example of biconvex function that has multiple local minima? Thanks. $\endgroup$
    – chaohuang
    May 6, 2013 at 2:33

Your Answer

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

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