Convex Optimization - Standard Form

Standard form is the usual and most intuitive form of describing a convex minimization problem. It consists of the following three parts:

A convex function to be minimized over the variable
Inequality constraints of the form, where the functions are convex
Equality constraints of the form, where the functions are affine. In practice, the terms "linear" and "affine" are often used interchangeably. Such constraints can be expressed in the form, where is a column-vector and a real number.

A convex minimization problem is thus written as

$\begin{align} &\underset{x}{\operatorname{minimize}}& & f(x) \\ &\operatorname{subject\;to} & &g_i(x) \leq 0, \quad i = 1,\dots,m \\ &&&h_i(x) = 0, \quad i = 1, \dots,p. \end{align}$

Note that every equality constraint can be equivalently replaced by a pair of inequality constraints and . Therefore, for theoretical purposes, equality constraints are redundant; however, it can be beneficial to treat them specially in practice.

Following from this fact, it is easy to understand why has to be affine as opposed to merely being convex. If is convex, is convex, but is concave. Therefore, the only way for to be convex is for to be affine.

Read more about this topic: Convex Optimization

Famous quotes containing the words standard and/or form:

“... the meanest life, the poorest existence, is attributed to God’s will, but as human beings become more affluent, as their living standard and style begin to ascend the material scale, God descends the scale of responsibility at a commensurate speed.”
—Maya Angelou (b. 1928)

“Upon the whole, necessity is something, that exists in the mind, not in objects; nor is it possible for us ever to form the most distant idea of it, consider’d as a quality in bodies. Either we have no idea of necessity, or necessity is nothing but that determination of thought to pass from cause to effects and effects to causes, according to their experienc’d union.”
—David Hume (1711–1776)