Biconvex optimization

Last updated March 14, 2019

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]

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Whereas many classes of convex optimization problems admit polynomial-time algorithms, mathematical optimization is in general NP-hard.

A set $B\subset X\times Y$ is called a biconvex set on $X\times 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 \mathbb {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.^[1]

The generalization to functions of more than two arguments is called a block multi-convex function. A function $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]

Related Research Articles

Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

In mathematics, computer science and operations research, mathematical optimization or mathematical programming is the selection of a best element from some set of available alternatives.

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function $is obviously equivalent to the minimization of the function .$

Multi-task learning (MTL) is a subfield of machine learning in which multiple learning tasks are solved at the same time, while exploiting commonalities and differences across tasks. This can result in improved learning efficiency and prediction accuracy for the task-specific models, when compared to training the models separately. Early versions of MTL were called "hints"

Interior-point methods are a certain class of algorithms that solve linear and nonlinear convex optimization problems.

The Frank–Wolfe algorithm is an iterative first-order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method, reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in 1956. In each iteration, the Frank–Wolfe algorithm considers a linear approximation of the objective function, and moves towards a minimizer of this linear function.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a finite number of steps.

In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form $is a convex set. For a function of a single variable, along any stretch of the curve the highest point is one of the endpoints. The negative of a quasiconvex function is said to be quasiconcave .$

A geometric program (GP) is an optimization problem of the form

Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function. When the objective function is differentiable, sub-gradient methods for unconstrained problems use the same search direction as the method of steepest descent.

Multi-objective optimization is an area of multiple criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective optimization has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives.

Coordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, then exactly or inexactly minimizes over the corresponding coordinate hyperplane while fixing all other coordinates or coordinate blocks. A line search along the coordinate direction can be performed at the current iterate to determine the appropriate step size. Coordinate descent is applicable in both differentiable and derivative-free contexts.

In applied mathematics, Graver bases enable iterative solutions of linear and various nonlinear integer programming problems in polynomial time. They were introduced by Jack E. Graver. Their connection to the theory of Gröbner bases was discussed by Bernd Sturmfels. The algorithmic theory of Graver bases and its application to integer programming is described by Shmuel Onn.

Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set". The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.

Proximal gradient methods are a generalized form of projection used to solve non-differentiable convex optimization problems. Many interesting problems can be formulated as convex optimization problems of form

Proximal gradientmethods for learning is an area of research in optimization and statistical learning theory which studies algorithms for a general class of convex regularization problems where the regularization penalty may not be differentiable. One such example is $regularization of the form$

Derivative-free optimization is a discipline in mathematical optimization that does not use derivative information in the classical sense to find optimal solutions: Sometimes information about the derivative of the objective function f is unavailable, unreliable or impractical to obtain. For example, f might be non-smooth, or time-consuming to evaluate, or in some way noisy, so that methods that rely on derivatives or approximate them via finite differences are of little use. The problem to find optimal points in such situations is referred to as derivative-free optimization, algorithms that do not use derivatives or finite differences are called derivative-free algorithms . Derivative-free optimization is closely related to black-box optimization.

Multi-objective linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objection linear programming is also a subarea of Multi-objective optimization.

References

1 2 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.
↑ Floudas, Christodoulos A. (2000). Deterministic global optimization : theory, methods, and applications. Dordrecht [u.a.]: Kluwer Academic Publ. ISBN 978-0-7923-6014-8.
↑ Chen, Caihua (2016). ""The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent"". "Math. Prof.". 155: 57–59. doi:10.1007/s10107-014-0826-5.

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[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"". "Math. Prof.". 155: 57–59. doi:10.1007/s10107-014-0826-5.