凸优化笔记
既凸又凹就是线性. 故等式约束一定是线性约束.
凸优化的任何局部最优为全局最优.
设 $f_0$ 可微. 则 $x∈ D$ 最优当且仅当 $∀ y∈D, ∇f_0(x)⋅(y-x)≥0$.
无约束凸优化问题里面 $∇f_0(x)=0$ 当且仅当 $x$ 是最优解.
对于带有等式约束 $Ax=b$ 的凸优化问题, 最优解 $x$ 满足 $∇f_0(x)⟂\mathrm{Ker}A$. 即存在 $\nu$ 使得 $∇f_0(x)+A^T ν=0$. 这是 KKT 条件的特例.
带约束优化问题基础: KKT 条件
问题形式:
$$\begin{equation} \begin{aligned} \min\quad &f(x)\\ \text{s.t.} &\begin{cases} c_i(x) ≥ 0, \quad i∈\mathcal{I},\\ c_i(x) = 0, \quad i∈\mathcal{E}. \end{cases} \end{aligned} \end{equation}$$
(tangent vector, tangent cone)
tangent vector 就是直接描述的从点 $x$ 出发的可行域中的曲线可能的初始速度方向, 用于刻画局部可行的扰动方向. 即对于 local minimizer, 显然有 $$\begin{equation} ∇ f(x_*)⋅ d≥ 0, ∀ d∈ T_D(x_*). \end{equation}$$
只不过这个定义直接从可行扰动出发, 直观直接, 但是难以处理, 所以我们需要下面的定义. 它给出了在 LICQ 情况下的更好的刻画.
(linearized feasible directions)
$$\begin{equation}
\mathcal{F}(x) = \{ d ∣ ∇c_i(x)⋅d=0, ∀ i∈\mathcal{E}; ∇c_i(x)⋅d≥0, ∀ \mathcal{I}∩\mathcal{A}(x) \}.
\end{equation}$$
一般情况下只有 $T_D(x)⊆\mathcal{F}(x)$. 只有在满足 LICQ 的时候才成立等式.
($T_D(x)$ 是锥但是未必是凸锥; $\mathcal{F}(x)$ 一定是闭凸锥.)
Remark. 我感觉这里的 LICQ 有非常浓的几何意味, 会和流形上局部切空间的分析相关.
另外值得注意的是, 如果记矩阵 $C=[∇c_i]_{i∈\mathcal{E}}, B=[∇c_i]_{i∈\mathcal{I}∩\mathcal{A}(x)}$ (并排放置列向量), 则有 $$\begin{equation} \mathcal{F}(x) = \{d∣ B^Td≥0, C^Td=0\} = K^*. \end{equation}$$
所以在 LICQ 成立的情况下, 对于任何的 $d∈\mathcal{F}(x_*)$, 一定要有 $∇f(x_*)⋅d≥ 0$, 换一个说法就是 $$\begin{equation} ∇f(x_*)∈ (\mathcal{F}(x_*))^* = (K^*)^*. \end{equation}$$ 这里使用了后面会介绍的对偶说法.
拉格朗日函数定义为
$$\begin{equation} \mathcal{L}(x,\lambda) = f(x) - \sum_{i∈ \mathcal{E}∪\mathcal{I}} \lambda_i c_i(x). \end{equation}$$
KKT 条件就是在 LICQ 情况下取局部最小值的一阶必要条件.
假设所有的函数都可微. 令 $x_*$ 是局部最小值点 (local minimizer), 并且假设 LICQ 条件成立. 则存在 $λ_i$ 使得在 $(x,λ)$ 上有下面的 KKT 条件成立 $$\begin{equation} \begin{aligned} & \nabla_x \mathcal{L} = \nabla f(x_*) - \sum_i \lambda_i∇ c_i(x_*) = 0, \\ & c_i(x_*) = 0, ∀ i∈ \mathcal{E},\quad c_i(x_*)≥ 0, ∀ i∈ \mathcal{I}, \\ & \lambda_i ≥ 0, ∀ i∈ \mathcal{I}, \\ & \lambda_i c_i(x_*) = 0, ∀ i∈ \mathcal{I}. \end{aligned} \end{equation}$$
严谨证明这件事情需要用到 Farkas 引理 (虽然 KKT 条件在直观上非常容易理解).
(Farkas 引理)
令 $B$ 和 $C$ 分别是 $n×m$ 和 $n×p$ 的实矩阵. 令 $p\in\mathbb{R}^n$. 这下面两个命题有且仅有一个成立:
(1) $$\begin{equation} g∈ \{By+Cω∣ y≥ 0\} \end{equation}$$
(2) 存在 $d∈ \mathbb{R}^n$ 使得 $$\begin{equation} g⋅d<0, B^Td≥ 0, C^Td=0. \end{equation}$$
Remark. Farkas 引理本身就很有对偶的意味. 我们定义一个闭凸锥 $$\begin{equation} K = \{By+Cω∣ y≥ 0\}, \end{equation}$$ 考虑它的对偶锥 $$\begin{equation} K^* = \{d ∣ d⋅g≥0,∀g∈ K\}. \end{equation}$$ 我们将可以证明 $$\begin{equation} K^* = \{d∣ B^Td≥ 0, C^Td=0\}. \end{equation}$$
所以上面的 Farkas 引理只不过就是两个情况的罗列: 一个向量在锥 $K$ 里面或者不在 $K$ 里面, 只是在表述的时候表述为在 $K$ 里面或者不在 $(K^*)^*$ 里面.
(KKT 条件的证明)
有了 Farkas 引理, 根据取极小值的必要条件 $ ∇f(x_*)∈ (\mathcal{F}(x_*))^*$ 知道没法成立第二个条件, 所以成立第一个条件, 也就是说 $∇ f(x_*)∈ K$. 换句话说就是 $$\begin{equation}
∇ f(x_*) = \sum_{i\in\mathcal{A}}\lambda_i∇ c_i(x_*),
\end{equation}$$ 其中 $\lambda_i≥ 0, ∀ i\in\mathcal{A}∩\mathcal{I}$. 只要定义 $\lambda_i=0, ∀ i∈ \mathcal{I}\backslash \mathcal{A}$ 即可.
对于凸优化而言, KKT 条件(一阶必要条件)也是充分的.