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:

    “There is a certain standard of grace and beauty which consists in a certain relation between our nature, such as it is, weak or strong, and the thing which pleases us. Whatever is formed according to this standard pleases us, be it house, song, discourse, verse, prose, woman, birds, rivers, trees, room, dress, and so on. Whatever is not made according to this standard displeases those who have good taste.”
    —Blaise Pascal (1623–1662)

    “Freedom of religion, freedom of the press, and freedom of person under the protection of habeas corpus, and trial by juries impartially selected. These principles form the bright constellation which has gone before us, and guided our steps through an age of revolution and reformation.”
    —Thomas Jefferson (1743–1826)