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.[1][2]

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

A function ${\displaystyle f(x,y):B\to \mathbb {R} }$ is called a biconvex function if fixing ${\displaystyle x}$, ${\displaystyle f_{x}(y)=f(x,y)}$ is convex over ${\displaystyle Y}$ and fixing ${\displaystyle y}$, ${\displaystyle f_{y}(x)=f(x,y)}$ is convex over ${\displaystyle X}$.

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

The generalization to functions of more than two arguments is called a block multi-convex function. A function ${\displaystyle f(x_{1},\ldots ,x_{K})\to \mathbb {R} }$ is block multi-convex iff it is convex with respect to each of the individual arguments while holding all others fixed.[3]

References

1. Gorski, Jochen; Pfeuffer, Frank; Klamroth, Kathrin (22 June 2007). "Biconvex sets and optimization with biconvex functions: a survey and extensions" (PDF). Mathematical Methods of Operations Research. 66 (3): 373–407. doi:10.1007/s00186-007-0161-1. S2CID 15900842.
2. Floudas, Christodoulos A. (2000). Deterministic global optimization : theory, methods, and applications. Dordrecht [u.a.]: Kluwer Academic Publ. ISBN 978-0-7923-6014-8.
3. Chen, Caihua (2016). ""The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent"". Mathematical Programming. 155 (1–2): 57–59. doi:10.1007/s10107-014-0826-5. S2CID 5646309.