Convex optimization is a subfield of
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
that studies the problem of minimizing
convex functions over
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
s (or, equivalently, maximizing
concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms,
whereas mathematical optimization is in general
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
.
Convex optimization has applications in a wide range of disciplines, such as automatic
control systems, estimation and
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
, communications and networks, electronic
circuit design, data analysis and modeling,
finance,
statistics (
optimal experimental design
In the design of experiments, optimal designs (or optimum designs) are a class of experimental designs that are optimal with respect to some statistical criterion. The creation of this field of statistics has been credited to Danish statistic ...
), and
structural optimization, where the approximation concept has proven to be efficient.
With recent advancements in computing and
optimization algorithms, convex programming is nearly as straightforward as
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
.
Definition
A convex optimization problem is an
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
in which the objective function is a
convex function and the
feasible set is a
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
. A function
mapping some subset of
into
is convex if its domain is convex and for all
Standard form
A convex optimization problem is in ''standard form'' if it is written as
:
\begin
&\underset& & f(\mathbf) \\
&\operatorname
& &g_i(\mathbf) \leq 0, \quad i = 1, \dots, m \\
&&&h_i(\mathbf) = 0, \quad i = 1, \dots, p,
\end
where:
[
* \mathbf \in \mathbb^n is the optimization variable;
* The objective function f: \mathcal D \subseteq \mathbb^n \to \mathbb is a convex function;
* The inequality constraint functions g_i : \mathbb^n \to \mathbb, i=1, \ldots, m, are convex functions;
* The equality constraint functions h_i : \mathbb^n \to \mathbb, i=1, \ldots, p, are ]affine transformation
In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.
More generall ...
s, that is, of the form: h_i(\mathbf) = \mathbf\cdot \mathbf - b_i, where \mathbf is a vector and b_i is a scalar.
This notation describes the problem of finding \mathbf \in \mathbb^n that minimizes f(\mathbf) among all \mathbf satisfying g_i(\mathbf) \leq 0, i=1, \ldots, m and h_i(\mathbf) = 0, i=1, \ldots, p. The function f is the objective function of the problem, and the functions g_i and h_i are the constraint functions.
The feasible set C of the optimization problem consists of all points \mathbf \in \mathcal satisfying the constraints. This set is convex because \mathcal is convex, the sublevel sets of convex functions are convex, affine sets are convex, and the intersection of convex sets is convex.
A solution to a convex optimization problem is any point \mathbf \in C attaining \inf \. In general, a convex optimization problem may have zero, one, or many solutions.
Many optimization problems can be equivalently formulated in this standard form. For example, the problem of maximizing a concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap, or upper convex.
Definition
A real-valued function f on an ...
f can be re-formulated equivalently as the problem of minimizing the convex function -f. The problem of maximizing a concave function over a convex set is commonly called a convex optimization problem.
Properties
The following are useful properties of convex optimization problems:[
* every local minimum is a global minimum;
* the optimal set is convex;
* if the objective function is ''strictly'' convex, then the problem has at most one optimal point.
These results are used by the theory of convex minimization along with geometric notions from ]functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defined ...
(in Hilbert spaces) such as the Hilbert projection theorem, the separating hyperplane theorem, and Farkas' lemma.
Applications
The following problem classes are all convex optimization problems, or can be reduced to convex optimization problems via simple transformations:[
]
*Least squares
The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems (sets of equations in which there are more equations than unknowns) by minimizing the sum of the squares of the r ...
*Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
* Convex quadratic minimization with linear constraints
* Quadratic minimization with convex quadratic constraints
* Conic optimization
* Geometric programming
*Second order cone programming
A second-order cone program (SOCP) is a convex optimization problem of the form
:minimize \ f^T x \
:subject to
::\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m
::Fx = g \
where the problem parameters are f \in \mathbb^n, ...
* Semidefinite programming
* Entropy maximization with appropriate constraints
Convex optimization has practical applications for the following.
* Portfolio optimization.
* Worst-case risk analysis.[
* Optimal advertising.][
* Variations of statistical regression (including regularization and ]quantile regression
Quantile regression is a type of regression analysis used in statistics and econometrics. Whereas the method of least squares estimates the conditional ''mean'' of the response variable across values of the predictor variables, quantile regress ...
).[
* Model fitting][ (particularly multiclass classification]).
* Electricity generation
Electricity generation is the process of generating electric power from sources of primary energy. For utilities in the electric power industry, it is the stage prior to its delivery ( transmission, distribution, etc.) to end users or its stor ...
optimization.[
* ]Combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
.[
* Non-probabilistic modelling of ]uncertainty
Uncertainty refers to Epistemology, epistemic situations involving imperfect or unknown information. It applies to predictions of future events, to physical measurements that are already made, or to the unknown. Uncertainty arises in partially ...
.
* Localization using wireless signals
Lagrange multipliers
Consider a convex minimization problem given in standard form by a cost function f(x) and inequality constraints g_i(x)\leq 0 for 1 \leq i \leq m. Then the domain \mathcal is:
:\mathcal = \left\.
The Lagrangian function for the problem is
:L(x,\lambda_,\lambda_1, \ldots ,\lambda_)=\lambda_ f(x) + \lambda_ g_ (x)+\cdots + \lambda_ g_ (x).
For each point x in X that minimizes f over X, there exist real numbers \lambda_,\lambda_1, \ldots, \lambda_, called Lagrange multipliers
In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied ...
, that satisfy these conditions simultaneously:
# x minimizes L(y,\lambda_,\lambda_,\ldots ,\lambda_) over all y \in X,
# \lambda_,\lambda_,\ldots ,\lambda_ \geq 0, with at least one \lambda_ > 0,
# \lambda_g_(x)=\cdots = \lambda_g_(x) = 0 (complementary slackness).
If there exists a "strictly feasible point", that is, a point z satisfying
:g_(z), \ldots, g_(z)<0,
then the statement above can be strengthened to require that \lambda_=1.
Conversely, if some x in X satisfies (1)–(3) for scalars \lambda_,\ldots,\lambda_ with \lambda_=1 then x is certain to minimize f over X.
Algorithms
Unconstrained convex optimization can be easily solved with gradient descent (a special case of steepest descent) or Newton's method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real ...
, combined with line search for an appropriate step size; these can be mathematically proven to converge quickly, especially the latter method. Convex optimization with linear equality constraints can also be solved using KKT matrix techniques if the objective function is a quadratic function
In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomi ...
(which generalizes to a variation of Newton's method, which works even if the point of initialization does not satisfy the constraints), but can also generally be solved by eliminating the equality constraints with linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matric ...
or solving the dual problem.[ Finally, convex optimization with both linear equality constraints and convex inequality constraints can be solved by applying an unconstrained convex optimization technique to the objective function plus logarithmic barrier terms.][ (When the starting point is not feasible - that is, satisfying the constraints - this is preceded by so-called ''phase I'' methods, which either find a feasible point or show that none exist. Phase I methods generally consist of reducing the search in question to yet another convex optimization problem.][)
Convex optimization problems can also be solved by the following contemporary methods:
* Bundle methods (Wolfe, Lemaréchal, Kiwiel), and
* Subgradient projection methods (Polyak),
* ]Interior-point methods
Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems.
An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...
,[ which make use of self-concordant barrier functions and self-regular barrier functions.]
*Cutting-plane methods
In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed ''cuts''. Such procedures are commonly used ...
* Ellipsoid method
*Subgradient method 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 funct ...
* Dual subgradients and the drift-plus-penalty method
Subgradient methods can be implemented simply and so are widely used.[Bertsekas] Dual subgradient methods are subgradient methods applied to a dual problem
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. If the primal is a minimization problem then t ...
. The drift-plus-penalty method is similar to the dual subgradient method, but takes a time average of the primal variables.
Implementations
Convex optimization and related algorithms have been implemented in the following software programs:
Extensions
Extensions of convex optimization include the optimization of biconvex, pseudo-convex, and quasiconvex functions. Extensions of the theory of convex analysis and iterative methods for approximately solving non-convex minimization problems occur in the field of generalized convexity
A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set theory, set of elements, as well as one or more commo ...
, also known as abstract convex analysis.
See also
* Duality
Duality may refer to:
Mathematics
* Duality (mathematics), a mathematical concept
** Dual (category theory), a formalization of mathematical duality
** Duality (optimization)
** Duality (order theory), a concept regarding binary relations
** Dual ...
* Karush–Kuhn–Tucker conditions
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be ...
* Optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
* Proximal gradient method
Notes
References
*
*
*
*
*
* Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). ''Fundamentals of Convex analysis''. Berlin: Springer.
*
*
*
*
*
* Nesterov, Yurii. (2004).
Introductory Lectures on Convex Optimization
', Kluwer Academic Publishers
*
*
* Schmit, L.A.; Fleury, C. 1980: ''Structural synthesis by combining approximation concepts and dual methods''. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260
External links
EE364a: Convex Optimization I
an
EE364b: Convex Optimization II
Stanford course homepages
6.253: Convex Analysis and Optimization
an MIT OCW course homepage
* Brian Borchers
An overview of software for convex optimization
Convex Optimization Book by Lieven Vandenberghe and Stephen P. Boyd
{{Convex analysis and variational analysis
Convex analysis
Mathematical optimization