A convex optimization problem is any problem of minimizing a convex function over a convex set. An optimization problem is quasi-convex if its feasible set is convex and its objective function $f_0$ is quasi-convex. Given convex functions $f_i(x), i=0,\dots,m$, the standard form of a convex optimization problem is: $$\begin{align} \min \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \le 0, && i = 1,\dots,m \\ & \langle a_i,x \rangle = b_i, && i = 1,\dots,p \end{align}$$

Properties of convex optimization problems:

  • The domain of a convex optimization problem is convex, because it's the intersection of some $m+1$ convex sets: $D = \cap_i \text{dom}f_i$.
  • The feasible set of a convex optimization problem is convex, because it's the intersection of the domain, some $m$ sub-level sets of convex functions, and some $p$ hyperplanes.
  • The optimal set and $\varepsilon$-suboptimal set of a convex / quasi-convex optimization problem are convex, because sub-level sets of the objective function are convex.
  • For a convex optimization problem, if its objective function is strictly convex, its optimal set has at most one point.
  • For a convex optimization problem, any locally optimal point is also (globally) optimal.

Special Classes of Convex Optimization Problems

Linear Optimization

A linear program (LP) is an optimization problem that minimizes a linear function over a polyhedral set.

General form of LP: $$\begin{align} \min \quad & \langle c, x \rangle \\ \text{s.t.} \quad & G x \preceq h && G \in \mathbb{R}^{m×n} \\ & A x = b && A \in \mathbb{R}^{p×n} \end{align}$$

Standard form of LP: $$\begin{align} \min \quad & \langle c, x \rangle \\ \text{s.t.} \quad & A x = b && A \in \mathbb{R}^{m×n} \\ & x \succeq 0 \end{align}$$

Inequality form LP: $$\begin{align} \min \quad & \langle c, x \rangle \\ \text{s.t.} \quad & A x \preceq b && A \in \mathbb{R}^{m×n} \end{align}$$

Quadratic Optimization

A quadratic program (QP) is an optimization problem with convex quadratic objective function and linear or affine constraint functions: given a real positive semidefinite matrix $P$, $$\begin{align} \min \quad & \langle x, Px/2 + q \rangle \\ \text{s.t.} \quad & G x \preceq h && G \in \mathbb{R}^{m×n} \\ & A x = b && A \in \mathbb{R}^{p×n} \end{align}$$

A quadratically constrained quadratic program (QCQP) is an optimization problem with convex quadratic objective and inequality constraint functions and linear/affine equality constraint functions.

A second-order cone program (SOCP) is an optimization problem with linear objective function, second-order cone constraints on affine transformations of variables, and linear/affine equality constraints. $$\begin{align} \min \quad & \langle f, x \rangle \\ \text{s.t.} \quad & | A_i x + b_i |_2 \le \langle c_i, x \rangle + d_i && A_i \in \mathbb{R}^{n_i×n}, i = 1,\dots,m \\ & F x = g && F \in \mathbb{R}^{p×n} \end{align}$$

Properties of quadratic programs:

  1. A quadratic program minimizes a convex quadratic function over a polyhedral set.
  2. A QP is a least-squares problem if it is unconstrained and the associated quadratic form is positive semi-definite: the solution is $x = A^\dagger b$, where $A^\dagger = (A^\text{T} A)^{-1}A^\text{T}$ is the pseudo-inverse of $A$.
  3. Quadratic programming with one negative eigenvalue is NP-hard.
  4. A QCQP minimizes a convex quadratic function over an intersection of ellipsoids.

Geometric Programming

A monomial is the product of some power functions with positive variables and coefficient: $f(x) = c \prod_i x_i^{a_i}$, where $c>0, x_i>0, a_i \in \mathbb{R}, i = 1,\dots,n$. Monomials are closed under multiplication and division.

A posynomial (正项式) is the sum of some monomials: $f(x) = \sum_k c_k \prod_i x_i^{a_{ik}}$, where $c_k>0, x_i>0, a_{ik} \in \mathbb{R}$, $i = 1,\dots,n, k = 1,\dots,K$. Posynomials are closed under addition, multiplication, and nonnegative scaling.

A geometric program (GP) is an optimization problem whose objective and inequality constraint functions $f_i, i = 0,\dots,m$ are posynomials, and whose equality constraint functions $h_i, i = 0,\dots,p$ are monomials (the constraint $x \succ 0$ is implicit.): $$\begin{align} \min \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \le 1 && i = 1,\dots,m \\ & h_i(x) = 1 && i = 1,\dots,p \end{align}$$

Generalized inequality constraints

Given convex function $f_0$, proper cones $K_i \subseteq \mathbb{R}^{k_i}$, and $K_i$-convex functions $f_i : \mathbb{R}^n \to \mathbb{R}^{k_i}$, standard form of convex optimization problem with generalized inequality constraints is: $$\begin{align} \min \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \preceq_{K_i} 0 && i = 1,\dots,m \\ & A x = b && A \in \mathbb{R}^{p×n} \end{align}$$

A conic problem is an optimization problem with linear objective function, one affine generalized inequality constraint, and linear equality constraints: $$\begin{align} \min \quad & \langle c,x \rangle \\ \text{s.t.} \quad & x \succeq_K 0 \\ & A x = b \end{align}$$

A semidefinite program (SDP) is a conic form problem with the cone of positive semidefinite matrices. Given $S^k$ the set of symmetric $k \times k$ matrices, the standard form of SDP is: $$\begin{align} \min \quad & \text{tr}(C X) && C, X \in S^n \\ \text{s.t.} \quad & \text{tr}(A_i X) = b_i && A_i \in S^n, i = 1,\dots,p \\ & X \succeq 0 \end{align}$$ Inequality form of SDP: $$\begin{align} \min \quad & \langle c,x \rangle \\ \text{s.t.} \quad & \sum_i x_i A_i \preceq B && A_i, B \in S^k, i = 1,\dots,n \end{align}$$

Techniques

Eliminating equality constraints

Suppose the $p$ equality constraints defines a $k$-dimensional manifold on the n-dimensional Euclidean space, then we may introduce $k$ generalized coordinates such that a transformation from the generalized coordinates to the manifold exists for some $\phi: \mathbb{R}^k \to \mathbb{R}^n$. For linear equality constraints $Ax=b$, such transformation has the form $\phi(z) = Fz + x_0$, where $x_0$ is a special solution to $Ax=b$ and $F$ is a basis of the null space of $A$.

For a convex optimization problem, eliminating its (linear) equality constraints preserves convexity. (Because composition with an affine function preserves convexity of a function.)

Introducing equality constraints

Inequality constraint $f_i(x) \le 0$ is equivalent to $f_i(x) + s_i = 0, s_i \ge 0$, where we call $s_i$ a slack variable.

Introducing slack variables for linear inequalities preserves convexity of a problem. (Because the objective is linear, and the new constraint $f_0(x)-t$ is convex in $\text{dom}(x) \times R$.)

Minimizing over some variables

If the constraint functions depend on distinct subsets of variables, then you may first optimize the objective over one subset of variables then the other. For example, optimization problem $$\begin{align} \min \quad & f_0(x_1, x_2) \\ \text{s.t.} \quad & f_i(x_1) \le 0 && i = 1,\dots,m_1 \\ & f'_i(x_2) \le 0 && i = 1,\dots,m_2 \end{align}$$ is equivalent to $$\begin{align} \min \quad & f_0(x_1, z(x_1)) \\ \text{s.t.} \quad & f_i(x_1) \le 0 && i = 1,\dots,m_1 \end{align}$$ , where $f_0(x_1,z(x_1)) = \min \{ f_0(x_1, x_2)~|~f'_i(x_2)≤0, i=1,\dots,m_2 \}$.

Minimizing over some variables preserves convexity of an optimization problem. (Because minimizing a convex function over some variables preserves convexity.)

Quasi-convex optimization via convex feasibility problems

The solution of a quasi-convex optimization problem can be approximated by solving a sequence of convex optimization problems. Let $\phi_t$ be a family of convex functions that the $0$-sublevel set of $\phi_t$ is the $t$-sublevel set of $f_0$: $f_0(x) \le t \Leftrightarrow \phi_t(x) \le 0$. If the convex feasibility problem $$\begin{align} \text{find} \quad & s \\ \text{s.t.} \quad & \phi_t(x) \le 0 \\ & f_i(x) \le 0 && i = 1,\dots,m \\ & Ax = b \end{align}$$ is feasible, then $p^* \le t$; if it's unfeasible, then $p^* > t$.

Converting LPs to standard form

With slack variables $s \in \mathbb{R}_{\ge 0}^m$ and nonnegative variables $x^+, x^-$ with $x = x^+ - x^-$, a general linear program can be expressed in standard form: $$\begin{align} \min \quad & \langle c, (x^+, -x^-) \rangle \\ \text{s.t.} \quad & Gx^+ - Gx^- + s = h && G \in \mathbb{R}^{m×n} \\ & Ax^+ - Ax^- = b && A \in \mathbb{R}^{p×n} \\ & (x^+, x^-, s) \succeq 0 \end{align}$$

Geometric program in convex form

Geometric programs can be transformed to convex problems by a change of variables and a transformation of the objective and constraint functions. With transformation $x_i = e^{y_i}$, posynomial $\sum_k c_k \prod_i x_i^{a_{ik}}$ can be expressed as $\sum_k e^{\langle a_k,y \rangle + b_k}$. Thus GPs are equivalent to convex optimization: $$\begin{align} \min \quad & f_0(y) = \log \sum_k \exp( \langle a_{0k},y \rangle + b_{0k}) \\ \text{s.t.} \quad & f_i(y) = \log \sum_k \exp(\langle a_{ik},y \rangle + b_{ik}) \le 0 && i = 1,\dots,m \\ & h_i(y) = \langle g_i,y \rangle + h_i = 0 && i = 1,…,p \end{align}$$

Note the objective and inequality constraint functions $f_i, i = 0,\dots,m$ are convex, because affine functions $\langle a_{ik},y \rangle + b_{ik}$ are convex and log-sum-exp $\log(e^f + e^g)$ preserves convexity.


🏷 Category=Optimization