# Biconvex optimization problems

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

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.

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