由于凸优化相关内容较多，本文从基础开始，介绍凸优化中的几个主要问题。
首先介绍凸优化中的基础知识：
凸集
集合
**仿射集合 (Affine set)**：如果通过集合 $C\subseteq \mathbb{R}^n$ 中任意两个不同点的直线仍然在集合 $C$ 中，那么称集合 $C$ 是仿射的。是仿射 $C\subseteq \mathbb{R}^n$ 的等价于：对于任意 $x_1, x_2 \in C$ 及 $\theta \in \mathbb{R} $ 有
$$
\theta x_1+(1-\theta)x_2 \in C
$$
凸集 (Convex Set)： 集合 $C$ 被称为凸集，如果 $C$ 中任意两点间的线段仍然在 $ C$ 中，即对于任意 $x_1, x_2 \in C$ 和满足 $0\le \theta \le 1 $ 的 $\theta$, 都有
$$
\theta x_1+(1-\theta)x_2 \in C
$$
凸组合：称点 $ \theta_1x_1 + … + \theta_kx_k$ 为点 $x_1, …, x_k$ 的一个凸组合，其中 $\theta_1 + … + \theta_k = 1$ 并且 $\theta _i \ge 0, i =1 ,…,k$。一个集合是凸集等价于集合包含其中所有点的凸组合。点的凸组合可以看做它们的混合或加权平均， $\theta_i$ 代表混合时 $x_i$ 所占的份数。
凸包：集合 $C$ 中所有点的凸组合的集合为其凸包，记为 $\mathbf{conv} C$
凸锥 (Convex cone)：如果对于任意 $x\in C$ 和 $\theta \ge 0$ 都有 $\theta x\in C $ . 我们称集合 $C$ 是锥。如 果集合 $C$ 是锥，并且是凸的，则称$C$为凸锥，即对于任意 $x_1, x_2\in C$ 和 $\theta_1 ,\theta_2 \ge 0$ 都有 $\theta_1 x_1+\theta_2x_2 \in C $
超平面：超平面是具有 $${x \vert \alpha^T x = b}$$ 形式的集合 , 其中 $\alpha \in \mathbb{R}^n, \alpha \neq 0, b\in \mathbb{R}$。超平面是仿射的 (也是凸的)。
半空间：半空间是具有 $${x \vert \alpha^T x \le b}$$ 形式的集合，即(非平凡的)线性不等式的解空间，其中 $\alpha \neq 0$, 半空间是凸的。
多面体 (Polyhedra): 定义为有限个线性等式和不等式的解集。多面体是有限个半空间和超平面的交集。仿射集合、射线、线段和半空间都是多面体。多面体是凸集。
$$
\cal P = { x \vert \alpha_j^Tx \le b_j, j = 1,…,m, c_j^Tx = d_j, j = 1,…,p }
$$
保凸运算 (Operations that preserve convexity)
交集：如果 $S_1 $ 和 $S_2 $ 是凸集，那么 $S_1 \cap S_2$ 也是凸集
仿射函数：如果函数 $f: \mathbb{R}^n → \mathbb{R}^m$ 具有 $f(x) = Ax + b$ 的形式, 是一个线性函数和一个常数的和，则它是仿射的，其中 $A\in \mathbb{R}^{m\times n}，b \in \mathbb{R}^m$。假设 $S\in\mathbb{R}^n$ 是凸的，是仿射函 $f: \mathbb{R}^n → \mathbb{R}^m$ 数， $S$ 在 f 下的象是凸的。如果 $f: \mathbb{R}^m → \mathbb{R}^n$ 是仿射函数，那么 S 在 f 下的原象是凸的。
透视函数：$ P: \mathbb{R}^{n+1} → \mathbb{R}^n, P(z, t) = z/t $为透视函数，其定义域为 $\mathbf{dom} P = R^n \times R_{++}$, 其中 $R_{++} = {x\in \mathbb{R} \vert x > 0}$
线性分式函数：线性分式函数由透视函数和仿射函数复合而成。设 $g: \mathbb{R}^n → \mathbb{R}^{m+1} $ 是仿射的，即 $$ g(x) = \left[ \begin{array}{} A \c^T \end{array} \right]x + \left[ \begin{array}{} b\d\end{array} \right] $$, 其中 $A\in \mathbb{R}^{m\times n}，b \in \mathbb{R}^m, c\in \mathbb{R}^n, d\in\mathbb{R}$。则由复合 $f =P\circ g$ 给出的函数
$$
f: \mathbb{R}^n → \mathbb{R}^m: f(x) = \frac{Ax + b)}{c^Tx + d}, \mathbf{dom}f={x\vert c^Tx+d>O}
$$
称为线性分式(或投射)函数。如果$ c = 0, d > 0$，则 $f$ 的定义域为 $\mathbb{R}^n$ ， 并且 $f$ 是仿射函数。可以将仿射和线性函数视为特殊的线性分式函数。
线性分式函数可以表示为 $f = \cal P^{-1}(Q\cal P(x))$ 从 $x\in \mathbf{dom}f$ 出发，可以得到 $\mathbb{R}^{n+1}$ 空间的 一条射线 $\cal P(x)$。将线性变换矩阵 $Q$ 作用于这条射线，就可以得到另一条射线 $Q\cal P(x)$。因 为 $x\in \mathbf{dom}f$ . 这条射线的最后一个分量为正,可以通过逆投射变换恢复出 $f(x)$。
平面
**超平面分离定理 (Separating hyperplane theorem)**：假设 $C$ 和 $D$ 是两个不相交的凸 集，即 $C \cap D= \emptyset $，那么存在 $\alpha \neq 0$ 和 $b$ 使得对于所有 $x\in C$ 有 $\alpha^Tx\le b$， 对于所有 $x\in D$ 有 $\alpha^Tx\ge b$。换言之，仿射函数 $\alpha^Tx-b$ 在 $C$ 中非正，而在 $D$ 中非负。超平面 ${x \vert\alpha^Tx = b}$ 称为集合$C$ 和 $D$ 的分离超平面。
支撑超平面(Supporting hyperplane): 设 $C\subseteq \mathbb{R}^n$ 而 $x_0$ 是其边界 $\mathbf{bd} C$ 上的一点，如果 $\alpha \neq 0$ ，并且对任意 $x\in C$ 满足 $\alpha^Tx \le \alpha^Tx_0 $ 那么称超平面 $${x\vert\alpha^Tx =\alpha^Tx_0}$$ 为集合 $C$ 在点 $X_0$ 处的支撑超平面。几何解释是超平面 $${x\vert\alpha^Tx =\alpha^Tx_0}$$ 与 $C$ 相切于点$X_0 $ ，而且半空间 $${x\vert\alpha^Tx \le\alpha^Tx_0}$$ 包含 C。 (图源：《凸优化》，Stephen Boyd等著，王书宁等译)
支撑超平面定理：表明对于任意非空的凸集 $C$ 和任意 $x_0 \in \mathbf{bd}C$，在 $x_0$ 处存在 $C$ 的支撑超平面。
凸函数
定义
函数 $f: \mathbb{R}^n → \mathbb{R}$ 是凸的，如果 $\mathbf{dom}f$ 是凸集，且对于任意$x, y \in \mathbf{dom}f$ 和任意 $0\le \ \theta\le 1$，有
$$
f(\theta x + (1-\theta )y) \le \theta f(x) +(1-\theta)f(y)
$$
从几何意义上看，上述不等式意味着点 $(x, f(x))$ 和 $(y, f(y))$ 之间的线段，即在函数 $f$ 的图像上方。如果不等式当 $x \neq y$ 以及 $0<\theta <1$ 时严格成立称函数 f 是严格凸的。如果函数 $-f$ 是凸的, 称函数 $f$ 是凹的，如果 $-f$ 严格凸称函数 $f$ 是严格凹的。
函数是凸的，当且仅当其在与其定义域相交的任何直线上都是凸的。也就是说，函数 $f$ 是凸的，当且仅当对于任意 $x\in \mathbf{dom} f$ 和任意向量 $v$， 函数 $g(t) = f(x + tv)$ 是凸的 (其定义域为 $${t \vert x + tv\in \mathbf{dom} f}$$)。
这个性质容许我们通过将函数限制在直线上来判断其是否是凸函数。即，即使 $f: \mathbb{R}^n → \mathbb{R}$，我们也可以通过判断 $g: \mathbb{R} → \mathbb{R}$ 来判断它的凹凸性。
一阶条件
假设 $f$ 可微(即其梯度 $\nabla f$ 在开集 $\mathbf{dom}f$ 内处处存在) ，则函数 $f$ 是凸函数的充要条件是 $\mathbf{dom}f$ 是凸集且对于任意 $x, y \in \mathbf{dom}f$ ， 下式成立
$$
f(y) \ge f(x) + \nabla f(x)^T(y-x)
$$
二阶条件
现在假设函数 $f$ 二阶可微，即对于开集 $\mathbf{dom}f$ 内的任意一点，它的 Hessian 矩阵或者二阶导数 $\nabla^2f$ 存在，则函数 $f$ 是凸函数的充要条件是，其 Hessian 矩阵是半正定阵:即对于所有的$x \in\mathbf{dom}f$ 有
$$
\nabla^2 f \succeq 0
$$
对于 $\mathbb{R}$ 上的函数，上式可以简化为一个简单的条件 $f’’\ge 0$, ($\mathbf{dom}f$ 是凸的，即一 个区间)
下水平集(sublevel set)
函数 $f: \mathbb{R}^n → \mathbb{R}$ 的 $\alpha -$下水平集定义为
$$
C_{\alpha} = {x \in \mathbf{dom}f \vert f(x) \le \alpha}
$$
对于任意 $\alpha $ 值，凸函数的下水平集是凸集。反过来不一定正确。
上境图 (Epigraph)
函数 $f: \mathbb{R}^n → \mathbb{R}$ 的图像定义为 $${(x,f(x))\vert x\in \mathbf{dom}f}$$， 它是 $\mathbb{R}^{n+1}$空间的一个子集。函数 $f: \mathbb{R}^n → \mathbb{R}$ 的上境图定义为
$$
\mathbf{epi} f = { (x,t)\vert x\in\mathbf{dom}f, f(x)\le t }
$$
凸集和凸函数的联系可以通过上境图来建立:一个函数是凸函数，当且仅当其上境图是凸集。一个函数是凹函数，当且仅当其亚图 $$\mathbf{hypo} f = { (x,t)\vert x\in\mathbf{dom}f, f(x)\ge t }$$ 是凸集。
保凸运算
- 非负加权求和：凸函数的集合本身是一个凸锥: 凸函数的非负加权求和仍然是凸函数，即函数 $f= \omega_1 f_i + … +\omega_mf_m$， 是凸函数。类似地，凹函数的非负加权求和仍然是凹函数。严格凸(凹)函数的非负，非零加权求和是严格凸(凹)函数。
- 复合仿射映射: 设函数 $f: \mathbb{R}^n → \mathbb{R}, A\in R^{n\times m}, b\in \mathbb{R}^n$， 定义 $g: \mathbb{R}^m → \mathbb{R}$: $ g(x) = f(Ax+b)$, 其中 $\mathbf{dom} g = {x\vert Ax+b\in \mathbf{dom} f}$。若函数 $f$ 是凸函数，则函数 $g$ 是凸函数:如果函数 $f$ 是凹函数，那么函数 $g$ 是凹函数。
- 逐点最大和逐点上确界：如果函数 $f_1$ 和 $f_2$ 均为凸函数，则二者的逐点最大函数 $$f(x) = \max {f_1(x), f_2(x)}$$ , 其定义域为 $\mathbf{dom}f = \mathbf{dom} f_1 \cap \mathbf{dom}f_2$，仍然是凸函数。逐点最大的性质可以扩展至无限个凸函数的逐点上确界。如果对于任意 $y\in \cal A$， 函数 $f(x， y)$ 关于 $x$ 都是凸的，则函数 $g = \sup_{y\in\cal A} f(x,y)$ , 关于 $x$ 亦是凸的。
- 复合
- 最小化：如果函数 $f$ 关于 $(x,y)$ 是凸函数，集合 $C$ 是非空凸集，定义函数 $g(x) = \inf_{y\in C}f(x,y)$,
若存在某个 $x$ 使得到 $g(x) > -\infty$ (即对所有 x， $g(x) > -\infty$) ，则函数 $g$ 关于 $x$ 是凸函数。函数 $g$ 的定义域是 $\mathbf{dom} f$ 在 $x$ 方向上的投影。 - 透视函数：给定函数 $f: \mathbb{R}^n → \mathbb{R}$ ，则 f 的透视函数 $g: \mathbb{R}^{n+1} → \mathbb{R}$ 定义为$g(x,t) = tf(x/t)$, 其定义域为 $$\mathbf{dom}g = {(x,t)\vert x/t\in \mathbf{dom}f, t>0} $$。透视运算是保凸运算: 如果函数 $f$ 是凸函数，则其透视函数 $g$ 也是凸函数。类似地，若 $f$ 是凹函数，则 $g$ 亦是凹函数。
共轭函数
设函数 $f: \mathbb{R}^n → \mathbb{R}$，定义函数 $f$ 的共轭函数 $f^*: \mathbb{R}^n → \mathbb{R}$ 为
$$
f^*(y) = \sup_{x\in \mathbf{dom}f} (y^Tx-f(x))
$$
使上述上确界有限的所有 $y\in \mathbb{R}^n$ 构成了共轭函数的定义域。对于任意的$f$, 共轭函数是凸函数，这是因为它是一系列 $y$ 的凸函数(实质上是仿射函数)的逐点上确界。
所以共轭函数有什么用？遇到再说吧 hhh
凸优化
优化问题
在所有满足约束的 $x$ 中寻找极小化 $f_0(x)$ 的 $x$ 的问题标准形式 :
$$
\min f_0(x)\
\mathbf{s.t.} f_i(x)\le0, i=1,…,m\
h_i(x) = 0, i = 1,…,p
$$
局部最优
称可行解 $x$ 为局部最忧，如果存在 $R>0$ 使得
$$
f_0(x) = \inf {f_0(z\vert f_i(z)\le0, i = 1,…,m,h_i(z) = 0, i=1,…,p, \vert\vert z-x\vert\vert_2 \le R}
$$
凸优化
凸优化问题的标准形式：
$$
\min f_0(x)\
\mathbf{s.t.} f_i(x)\le0, i=1,…,m\
a_i^Tx = b_i, i = 1,…,p
$$
其中 $f_0, …, f_m $ 为凸函数。(且等式约束函数必须是仿射的)
到底什么是凸优化问题？在 《凸优化》，Stephen Boyd等著，王书宁等译 一书中，提出了另一个例子 (4.2节 凸优化)
因此，一个问题是不是凸优化由定义确定。
- 关于凸优化的定义，遇到过一个问题：以下问题
$$
\min y-x\
\mathbf{s.t.} -xy+9 \le 0\
0\le y\le 6\
1\le x\le 2
$$
是不是一个凸优化问题？
事实上我本来希望用上面的例子解释这个例子，但后来发现似乎不太一样。下面是我的一些理解，可以继续讨论。
我们可以求出第一个约束并不是一个凸函数，按照定义应该不是凸优化。但是分歧在哪里呢？如果我们在二维平面上画出它的 “可行域”， 会发现它是一个凸集。
对于这个问题，我们常见 (中学) 的方法是在二维平面上画出 “可行域”，然后对直线 $ y = x + k$ 进行平移，找到最小的 $k$ 使得直线与 “可行域” 有交点，这个时候，直线是一直在变化的。
然而，这种方法并不是在解一个优化问题：一个常规的优化问题，应该是已知目标函数，求目标函数在可行域内的最小值。如果放到二维平面上，应该是给定一个函数，求函数在一个区间内的最小值。因此这个问题的常规解法，应该是在三维空间中找到可行域 (应该是非凸的)，求函数 $f(x,y) = y-x$ 在可行域内的最小值。
顺便提一些上面上境图的概念：我们在二维平面上画出 $-xy + 9 \le 0$ 的范围发现它是凸的，事实上我们画出的是函数 $ y = 9/x$ 的上境图，这个函数是凸函数，验证了上境图的性质。
局部最优解与全局最优解
凸优化问题的一个基础性质是其任意局部最优解也是(全局)最优解。 设 $x$ 是凸优化问题的局部最优解，即 $x$ 是可行的并且对于某些 $R> 0$， 有 $$f_0(x) = \inf {f_0(z\vert z可行, \vert\vert z-x\vert\vert_2 \le R}$$ 。现在假设 $x$ 不是全局最优解，即存在一个可行的 $y$ 使得 $f_0(y)< f_0(x)$。显然 $\vert\vert y-x\vert\vert_2>R$ 。考虑由
$$
z = (1 - \theta )x +\theta y, \theta=\frac{R}{2\vert\vert y-x\vert\vert_2}
$$
给出的点 $z$， 我们有 $\vert\vert z - x\vert\vert_2 = R/2 < R$。根据可行集的凸性， $z$ 是可行的。根据 $f_0$ 的凸性，我们有 $f_0(z)\le (1-\theta)f_0(x)+\theta f_0(y)< f_0(x)$，出现矛盾。因此不存在满足 $f_0(y)< f_0(x)$的可行解 $y$ ，即 $x$ 是全局最优解。
可微函数 $f_0$ 的最优性准则
设凸优化问题的目标函数 $f_0$ 是可微的，对于所有的 $x,y\in \mathbf{dom}f_0$有
$$
f_0(y)\ge f_0(x) + \nabla f_0(x)^T(y-x)
$$
令 X 表示其可行集，那么 ， $x$ 是最优解，当且仅当 $x\in X$ 且
$$
\nabla f_0(x)^T(y-x)\ge 0, \forall y\in X
$$
这个最优性准则可以从几何上进行理解: 如果$\nabla f_0(x)\neq 0$，那么意味着 $\nabla f_0(x)$ 在 $x$ 处定义了可行集的一个支撑超平面。
