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 B⊂X×Y is called a biconvex set on X×Y if for every fixed y∈Y, By={x∈X:(x,y)∈B} is a convex set in X and for every fixed x∈X, Bx={y∈Y:(x,y)∈B} is a convex set in Y.

A function f(x,y):B->ℝ is called a biconvex function if fixing x, fx(y)=f(x,y) is convex over Y and fixing y, fy(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.[1]

The generalization to functions of more than two arguments is called a block multi-convex function. A function f(x1,…,xK)->ℝ is block multi-convex iff it is convex with respect to each of the individual arguments while holding all others fixed.[3]

## References

1. ↑ 1.0 1.1 Gorski, Jochen; Pfeuffer, Frank; Klamroth, Kathrin (22 June 2007). "Biconvex sets and optimization with biconvex functions: a survey and extensions". Mathematical Methods of Operations Research 66 (3): 373–407. doi:10.1007/s00186-007-0161-1. http://www2.math.uni-wuppertal.de/~klamroth/publications/gopfkl07.pdf.
2. ↑ Floudas, Christodoulos A. (2000). Deterministic global optimization : theory, methods, and applications. Dordrecht [u.a.]: Kluwer Academic Publ.. ISBN 978-0-7923-6014-8. https://www.springer.com/mathematics/book/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.

* v
* t
* e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

| … functions|

* Golden-section search
* Interpolation methods
* Line search
* Nelder–Mead method
* Successive parabolic interpolation

|

… and gradients|

| Convergence|

* Trust region
* Wolfe conditions

|

Quasi–Newton|

* Berndt–Hall–Hall–Hausman
* Broyden–Fletcher–Goldfarb–Shanno and L-BFGS
* Davidon–Fletcher–Powell
* Symmetric rank-one (SR1)

Other methods|

* Gauss–Newton
* Gradient
* Levenberg–Marquardt
* Conjugate gradient
* Truncated Newton

… and Hessians|

* Newton's method

Optimization computes maxima and minima.

Constrained nonlinear

| General|

* Barrier methods
* Penalty methods

|

Differentiable|

* Augmented Lagrangian methods
* Sequential quadratic programming
* Successive linear programming

Convex optimization

| Convex
minimization|

* Cutting-plane method
* Reduced gradient (Frank–Wolfe)
* Subgradient method

|

Linear and
quadratic|

| Interior point|

* Affine scaling
* Ellipsoid algorithm of Khachiyan
* Projective algorithm of Karmarkar

|

Basis-exchange|

* Simplex algorithm of Dantzig
* Revised simplex algorithm
* Criss-cross algorithm
* Principal pivoting algorithm of Lemke

Combinatorial

| Paradigms|

* Approximation algorithm
* Dynamic programming
* Greedy algorithm
* Integer programming
* Branch and bound/cut

|

Graph
algorithms|

| Minimum
spanning tree|

* Borůvka
* Prim
* Kruskal

|

* Bellman–Ford
* Dijkstra
* Floyd–Warshall

Network flows|

* Dinic
* Edmonds–Karp
* Ford–Fulkerson
* Push–relabel maximum flow

Metaheuristics

* Evolutionary algorithm
* Hill climbing
* Local search
* Simulated annealing
* Tabu search

* Software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Biconvex optimization. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Biconvex_optimization&oldid=307393"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template