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:

    “Any honest examination of the national life proves how far we are from the standard of human freedom with which we began. The recovery of this standard demands of everyone who loves this country a hard look at himself, for the greatest achievments must begin somewhere, and they always begin with the person. If we are not capable of this examination, we may yet become one of the most distinguished and monumental failures in the history of nations.”
    —James Baldwin (1924–1987)

    “So that if you would form a just judgment of what is of infinite importance to you not to be misled in,—namely, in what degree of real merit you stand ... call in religion and morality.—Look,—What is written in the law of God?—How readest thou?—Consult calm reason and the unchangeable obligations of justice and truth;Mwhat say they?”
    —Laurence Sterne (1713–1768)