Biconvex optimization

Biconvex optimization is a generalization of convex optimization where the objective function and the constraint set can be biconvex. There are methods that can find the global optimum of these problems.

A set $B\subset X\times Y$ is called a biconvex set on $X\times Y$ if for every fixed $y\in Y$, $B_y=\{x\in X:(x,y)\in B\}$ is a convex set in $X$ and for every fixed $x\in X$, $B_x=\{y\in Y:(x,y)\in B\}$ is a convex set in $Y$.

A function $f(x,y):B\to ℝ$ is called a biconvex function if fixing $x$, $f_x(y)=f(x,y)$ is convex over $Y$ and fixing $y$, $f_y(x)=f(x,y)$ is convex over $X$.

A common practice for solving a biconvex problem (which does not guarantee global optimality of the solution) is alternatively updating $x,y$ by fixing one of them and solving the corresponding convex optimization problem.

The generalization to functions of more than two arguments is called a block multi-convex function. A function $f(x_1,\dots ,x_K)\to ℝ$ is block multi-convex iff it is convex with respect to each of the individual arguments while holding all others fixed.

References

Template:Mathapplied-stub