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 [math]\displaystyle{ B \subset X\times Y }[/math] is called a biconvex set on [math]\displaystyle{ X\times Y }[/math] if for every fixed [math]\displaystyle{ y\in Y }[/math], [math]\displaystyle{ B_y = \{x \in X: (x,y) \in B\} }[/math] is a convex set in [math]\displaystyle{ X }[/math] and for every fixed [math]\displaystyle{ x\in X }[/math], [math]\displaystyle{ B_x = \{y \in Y: (x,y) \in B\} }[/math] is a convex set in [math]\displaystyle{ Y }[/math].

A function [math]\displaystyle{ f(x, y): B \to \mathbb{R} }[/math] is called a biconvex function if fixing [math]\displaystyle{ x }[/math], [math]\displaystyle{ f_x(y) = f(x, y) }[/math] is convex over [math]\displaystyle{ Y }[/math] and fixing [math]\displaystyle{ y }[/math], [math]\displaystyle{ f_y(x) = f(x, y) }[/math] is convex over [math]\displaystyle{ X }[/math].

A common practice for solving a biconvex problem (which does not guarantee global optimality of the solution) is alternatively updating [math]\displaystyle{ x, y }[/math] 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 [math]\displaystyle{ f(x_1,\ldots,x_K) \to \mathbb{R} }[/math] is block multi-convex iff it is convex with respect to each of the individual arguments while holding all others fixed.