由于凸优化相关内容较多，本文从基础开始，介绍凸优化中的几个主要问题。
首先介绍凸优化中的基础知识：
凸集
集合
仿射集合 (Affine set)：如果通过集合 \(C\subseteq \mathbb{R}^n\) 中任意两个不同点的直线仍然在集合 \(C\) 中，那么称集合 \(C\) 是仿射的。是仿射 \(C\subseteq \mathbb{R}^n\) 的等价于：对于任意 \(x_1, x_2 \in C\) 及 $ $ 有
\[ \theta x_1+(1-\theta)x_2 \in C \]
凸集 (Convex Set)： 集合 \(C\) 被称为凸集，如果 \(C\) 中任意两点间的线段仍然在 $ C$ 中，即对于任意 \(x_1, x_2 \in C\) 和满足 $0 $ 的 \(\theta\), 都有
\[ \theta x_1+(1-\theta)x_2 \in C \]
凸组合：称点 $ _1x_1 + … + _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\) 都有 $xC $ . 我们称集合 \(C\) 是锥。如 果集合 \(C\) 是锥，并且是凸的，则称\(C\)为凸锥，即对于任意 \(x_1, x_2\in C\) 和 \(\theta_1 ,\theta_2 \ge 0\) 都有 $_1 x_1+_2x_2 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: ^{n+1} → ^n, P(z, t) = z/t $为透视函数，其定义域为 \(\mathbf{dom} P = R^n \times R_{++}\), 其中 \(R_{++} = \{x\in \mathbb{R} \vert x > 0\}\)
线性分式函数：线性分式函数由透视函数和仿射函数复合而成。设 $g: ^n → ^{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 D= $，那么存在 \(\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\) 满足 $^Tx ^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\} \]
对于任意 $$ 值，凸函数的下水平集是凸集。反过来不一定正确。
上境图 (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\) 处定义了可行集的一个支撑超平面。
