Convex optimization is a subfield of
mathematical optimization 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.
Convex optimization has applications in a wide range of disciplines, such as automatic
control systems
A control system manages, commands, directs, or regulates the behavior of other devices or systems using control loops. It can range from a single home heating controller using a thermostat controlling a domestic boiler to large industrial c ...
, 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), 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.
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
In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, poten ...
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