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.

**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}$$

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:

- A quadratic program minimizes a convex quadratic function over a polyhedral set.
- 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$.
- Quadratic programming with one negative eigenvalue is NP-hard.
- A QCQP minimizes a convex quadratic function over an intersection of ellipsoids.

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}$$

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}$$

Suppose the $p$ equality constraints define 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.)

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$.)

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.)

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$.

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 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.