Conic optimization is a subfield of
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems ...
that studies problems consisting of minimizing a
convex function
In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of a function, graph of the function lies above or on the graph between the two points. Equivalently, a function is conve ...
over the intersection of an
affine subspace
In mathematics, an affine space is a geometry, geometric structure (mathematics), structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance (mathematics), distance ...
and a
convex cone
In linear algebra, a cone—sometimes called a linear cone to distinguish it from other sorts of cones—is a subset of a real vector space that is closed under positive scalar multiplication; that is, C is a cone if x\in C implies sx\in C for e ...
.
The class of conic optimization problems includes some of the most well known classes of convex optimization problems, namely
linear
In mathematics, the term ''linear'' is used in two distinct senses for two different properties:
* linearity of a '' function'' (or '' mapping'');
* linearity of a '' polynomial''.
An example of a linear function is the function defined by f(x) ...
and
semidefinite programming
Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of po ...
.
Definition
Given a
real vector space
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
''X'', a
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
, real-valued
function
:
defined on a
convex cone
In linear algebra, a cone—sometimes called a linear cone to distinguish it from other sorts of cones—is a subset of a real vector space that is closed under positive scalar multiplication; that is, C is a cone if x\in C implies sx\in C for e ...
, and an affine subspace
defined by a set of
affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a Affinity_(law)#Terminology, relative by marriage in law and anthropology
* Affine cipher, a special case of the more general substi ...
constraints
, a conic
optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
is to find the point
in
for which the number
is smallest.
Examples of
include the positive
orthant
In geometry, an orthant or hyperoctant is the analogue in ''n''-dimensional Euclidean space of a quadrant in the plane or an octant in three dimensions.
In general an orthant in ''n''-dimensions can be considered the intersection of ''n'' mutu ...
,
positive semidefinite matrices
, and the second-order cone
. Often
is a linear function, in which case the conic optimization problem reduces to a
linear program
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 and objective are represented by linear relationships. Linear ...
, a
semidefinite program, and a
second order cone program, respectively.
Duality
Certain special cases of conic optimization problems have notable closed-form expressions of their dual problems.
Conic LP
The dual of the conic linear program
:minimize
:subject to
is
:maximize
:subject to
where
denotes the
dual cone
Dual cone and polar cone are closely related concepts in convex analysis, a branch of mathematics.
Dual cone
In a vector space
The dual cone ''C'' of a subset ''C'' in a linear space ''X'' over the real numbers, reals, e.g. Euclidean spac ...
of
.
Whilst
weak duality holds in conic linear programming,
strong duality does not necessarily hold.
Semidefinite Program
The dual of a semidefinite program in inequality form
: minimize
: subject to
is given by
: maximize
: subject to
:
References
External links
* {{cite book, title=Convex Optimization, first1=Stephen P., last1=Boyd, first2=Lieven, last2=Vandenberghe, year=2004, publisher=Cambridge University Press, isbn=978-0-521-83378-3, url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf , accessdate=October 15, 2011
MOSEKSoftware capable of solving conic optimization problems.
Convex optimization