Convex Optimization-culled from http://en.wikipedia.org/wiki/Convex_programming

Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions(a function whose graph of real values is below the line segment joining two points of this graph) over convex sets. The property that makes an optimization convex can make it in some sense "easier" than the general case - for example, any local minimum must be a global minimum.

Given a real vector space X together with a convex, real-valued function

f:\mathcal{X}\to \mathbb{R}

defined on a convex subset (i.e a set of two points that lie in an object whose straight line segment has points on it that also lie in the object) \mathcal{X} of X. As such the issue is to find any point x^\ast in \mathcal{X} for which the number f(x) is smallest, i.e., a point x^\ast such that

f(x^\ast) \le f(x) for all x \in \mathcal{X}.

Convex optimization case

An optimization case (also referred to as mathematical programming program or minimization problem) of finding some x^\ast \in \mathcal{X} such that

f(x^\ast) = \min \{f(x):x \in \mathcal{X}\},

where \mathcal{X} \subset \mathbb{R}^n is the feasible set and f(x):\mathbb{R}^n \rightarrow \mathbb{R} is the objective, is called convex if \mathcal{X} is a closed convex set and f(x) is convex on \mathbb{R}^n. [1] [2] Alternatively, an optimization problem on the form

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

is called convex if the functions f, g_1 \ldots g_m : \mathbb{R}^n \rightarrow \mathbb{R} are convex.[3]

 Theory

The following statements are true about the convex minimization problem:

 Standard form

Standard form consists of the following three parts:

A convex minimization case 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 h(x) = 0 can be equivalently replaced by a pair of inequality constraints h(x)\leq 0 and -h(x)\leq 0.

Following from this fact, it is easy to understand why h_i(x) = 0 has to be affine(preserved linearly) as opposed to merely being convex. If h_i(x) is convex, h_i(x) \leq 0 is convex, but -h_i(x) \leq 0 is concave. Therefore, the only way for h_i(x) = 0 to be convex is for h_i(x) to be affine.

  Lagrange multipliers

Consider a convex minimization problem given in standard form by a cost function f(x) and inequality constraints g_i(x)\leq 0, where i=1\ldots m. Then the domain \mathcal{X} is:

\mathcal{X} = \left\lbrace{x\in X \vert g_1(x)\le0, \ldots, g_m(x)\le0}\right\rbrace.

The Lagrangian function for the problem is

L(x,λ0,...,λm) = λ0f(x) + λ1g1(x) + ... + λmgm(x).

For each point x in X that minimizes f over X, there exist real numbers λ0, ..., λm, called Lagrange multipliers, that satisfy these conditions simultaneously:

  1. x minimizes L(y, λ0, λ1, ..., λm) over all y in X,
  2. λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0, with at least one λk>0,
  3. λ1g1(x) = 0, ..., λmgm(x) = 0 (complementary slackness).

If there exists a "strictly feasible point", i.e., a point z satisfying

g1(z) < 0,...,gm(z) < 0,

then the statement above can be upgraded to assert that λ0=1.

Conversely, if some x in X satisfies 1-3 for scalars λ0, ..., λm with λ0 = 1, then x is certain to minimize f over X.

Notes

  1. ^ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). Convex analysis and minimization algorithms: Fundamentals. p. 291. http://books.google.de/books?id=Gdl4Jc3RVjcC&printsec=frontcover&dq=lemarechal+convex+analysis+and+minimization&hl=de&sa=X&ei=E602T4GXGMzQsgaPtJ2VDA&ved=0CDUQ6AEwAA#v=onepage&q=convex%20minimization&f=false.
  2. ^ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. pp. 335–336. http://books.google.de/books?id=M3MqpEJ3jzQC&printsec=frontcover&dq=Lectures+on+Modern+Convex+Optimization:+Analysis,+Algorithms,&hl=de&sa=X&ei=26c2T6G7HYrIswac0d2uDA&ved=0CDIQ6AEwAA#v=onepage&q=convex%20programming&f=false.
  3. ^ Boyd/Vandenberghe, p. 7
  4. ^ For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by Ruszczynski and Boyd and Vandenberghe (interior point).
  5. ^ Bertsekas
  6. ^ Hiriart-Urruty & Lemaréchal (1993, Example XV.1.1.2, p. 277) discuss a "bad guy" constructed by Arkadi Nemirovskii.
  7. ^ In theory, quasiconvex programming and convex programming problems can be solved in reasonable amount of time, where the number of iterations grows like a polynomial in the dimension of the problem (and in the reciprocal of the approximation error tolerated):

    Kiwiel, Krzysztof C. (2001). "Convergence and efficiency of subgradient methods for quasiconvex minimization". Mathematical Programming (Series A) (Berlin, Heidelberg: Springer) 90 (1): pp. 1–25. doi:10.1007/PL00011414. ISSN 0025-5610. MR 1819784. Kiwiel acknowledges that Yuri Nesterov first established that quasiconvex minimization problems can be solved efficiently.

  8. ^ Nemirovskii and Judin
  9. ^ Convex maximization is mentioned in the subsection on convex optimization in this textbook: Ulrich Faigle, Walter Kern, and George Still. Algorithmic principles of mathematical programming. Springer-Verlag. Texts in Mathematics. Chapter 10.2, Subsection "Convex optimization", pages 205-206.
  10. ^ Theorem 32.1 in Rockafellar's Convex Analysis states this maximum principle for extended real-valued functions.
  11. ^ Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
  12. ^ Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.

 


                                                              Xgains4keeps Inc