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

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation 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 Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

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 Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e