Biconvex optimization explained

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

B \subset X x Y is called a biconvex set on X x 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 R 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 argumentsis called a block multi-convex function.A function

f(x _{1,\ldots,x} _{K)} \to R is block multi-convexiff it is convex with respect to each of the individual argumentswhile holding all others fixed.^[3]

Notes and References

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