Constrained Optimization Problem and Dual Problem.
本文目录：
- 约束优化问题
- 最大最小不等式(max-min inequality)与弱对偶关系
- 极小极大定理(minimax theorem)与强对偶关系
1. 约束优化问题 Constrained Optimization Problem
约束优化问题的一般形式：
\[\begin{aligned} \mathop{\min}_{x \in \Bbb{R}^p} \quad & f(x) \\ \text{s.t. } \quad & m_i(x) \leq 0,i=1,2,\cdots,M \\& n_j(x) = 0,j=1,2,\cdots,N \end{aligned}\]构建约束优化问题的拉格朗日函数：
\[\mathcal{L}(x,\lambda, \eta) = f(x) + \sum_{i=1}^M \lambda_im_i(x) + \sum_{j=1}^N \eta_jn_j(x)\]则可以将原问题转化为关于$x$的无约束形式：
\[\begin{aligned} \mathop{\min}_{x \in \Bbb{R}^p} \mathop{\max}_{\lambda, \eta} \quad & \mathcal{L}(x,\lambda, \eta) \\ \text{s.t. } \quad & \lambda_i \geq 0,i=1,2,\cdots,M \end{aligned}\]该形式隐式地包含对$x$的约束，考虑将可行域\(\Bbb{R}^p\)划分为$x$的约束区域\(\Bbb{D}_1\)和未约束区域\(\Bbb{D}_2\)，则上述目标等价于：
\[\begin{aligned} & \mathop{\min}_{x \in \Bbb{R}^p} \mathop{\max}_{\lambda, \eta} \mathcal{L}(x,\lambda, \eta) \\ =& \mathop{\min}_{x \in \Bbb{R}^p} [\mathop{\max}_{\lambda, \eta,x \in \Bbb{D}_1} \mathcal{L}(x,\lambda, \eta) , \mathop{\max}_{\lambda, \eta,x \in \Bbb{D}_2} \mathcal{L}(x,\lambda, \eta)] \\ =& \mathop{\min}_{x \in \Bbb{R}^p} [\mathop{\max}_{\lambda, \eta,x \in \Bbb{D}_1} \mathcal{L}(x,\lambda, \eta) , + \infty ] \\ =& \mathop{\min}_{x \in \Bbb{R}^p} \mathop{\max}_{\lambda, \eta,x \in \Bbb{D}_1} \mathcal{L}(x,\lambda, \eta) \end{aligned}\]2. 最大最小不等式与弱对偶关系
(1) 最大-最小不等式 max-min inequality
最大-最小不等式是指对任意函数\(f:X \times Y \to \Bbb{R}\)，有：
\[\mathop{\sup}_{y \in Y} \mathop{\inf}_{x \in X} f(x,y) \leq \mathop{\inf}_{x \in X} \mathop{\sup}_{y \in Y} f(x,y)\]⚪ 最大-最小不等式的证明
已知函数$f(x,y)$必定不大于其关于$y$的上确界supremum，且不小于其关于$x$的下确界infimum：
\[\mathop{\inf}_{x \in X} f(x,y) \leq f(x,y) \leq \mathop{\sup}_{y \in Y} f(x,y)\]左式不大于右式，则一定不大与右式关于$x$的下确界infimum：
\[\mathop{\inf}_{x \in X} f(x,y) \leq \mathop{\inf}_{x \in X} \mathop{\sup}_{y \in Y} f(x,y)\]右式不小于左式，则一定不小于左式关于$y$的上确界supremum：
\[\mathop{\sup}_{y \in Y} \mathop{\inf}_{x \in X} f(x,y) \leq \mathop{\inf}_{x \in X} \mathop{\sup}_{y \in Y} f(x,y)\]⚪ 最大-最小不等式的几何解释
假设函数函数$f(x,y)$表示一片土地（不必是矩形），考虑横纵两个方向（不必是正交的），$x$或$y$分别代表了横纵两个方向的坐标，而函数值$f(x,y)$代表了在该坐标的海拔。
假设把这片土地分别沿横纵两个方向切成了细条，在每个横条的最低海拔处放一个红色的鹅卵石作标记，在每个纵条的最高海拔处放一个蓝色色的鹅卵石作标记。则不会出现红卵石比蓝卵石海拔更高的情况。
假设有一块红卵石比蓝卵石的海拔高，那就意味着这块红卵石所在横条的最低点比那块蓝卵石所在竖条的最高点还高。现在想象一下从蓝卵石所在处出发，沿着纵条方向向着横竖条的交叉点走，因为蓝卵石是纵条最高点，所以一定是在走下坡。当走到红卵石所在的横条时，海拔会比蓝卵石低，而蓝卵石又比红卵石低，所以所处位置的海拔一定低于红卵石。然而红卵石是该横条上的海拔最低点，由此推出矛盾，证明不可能有红卵石高于任何一块蓝卵石。
(2) 对偶问题 Dual Problem
根据原问题的无约束形式：
\[\begin{aligned} \mathop{\min}_{x \in \Bbb{R}^p} \mathop{\max}_{\lambda, \eta} \quad & \mathcal{L}(x,\lambda, \eta) \\ \text{s.t. } \quad & \lambda_i \geq 0,i=1,2,\cdots,M \end{aligned}\]可以写出原问题的对偶问题：
\[\begin{aligned} \mathop{\max}_{\lambda, \eta} \mathop{\min}_{x \in \Bbb{R}^p} \quad & \mathcal{L}(x,\lambda, \eta) \\ \text{s.t. } \quad & \lambda_i \geq 0,i=1,2,\cdots,M \end{aligned}\]对偶问题具有如下对偶性(duality)：
- 原问题是关于$x$的函数；对偶问题是关于$\lambda, \eta$的函数。
- 原问题与对偶问题存在弱对偶性(weak duality)，根据最大-最小不等式：
⚪ 对偶性的几何解释
为简化讨论，假设原问题具有单一约束条件$m(x)\leq 0$。则原问题、原问题的无约束形式以及对偶问题如下：
\[\begin{aligned} \mathop{\min}_{x} & f(x) \\ \text{s.t. } & m(x) \leq 0 \end{aligned} \leftrightarrow \begin{aligned} \mathop{\min}_{x} \mathop{\max}_{\lambda} & f(x) + \lambda m(x) \\ \text{s.t. } & \lambda \geq 0 \end{aligned} \leftrightarrow \begin{aligned} \mathop{\max}_{\lambda}\mathop{\min}_{x} & f(x) + \lambda m(x) \\ \text{s.t. } & \lambda \geq 0 \end{aligned}\]记原问题和对偶问题取得最优解时对应的目标函数值分别为：
\[\begin{aligned} p^* &= \mathop{\min}_{x} f(x) \\ d^* &= \mathop{\max}_{\lambda}\mathop{\min}_{x} f(x) + \lambda m(x) \end{aligned}\]下面考虑以$(u,t) = (m(x),f(x))$为坐标系的空间$uot$，所有满足$x$可行域的点在区域$G$中。则上述目标函数值进一步表示为：
\[\begin{aligned} p^* &= \inf \{t\mid (u,t) \in G,u \leq 0\} \\ d^* &= \mathop{\max}_{\lambda} \inf \{t+\lambda u \mid (u,t) \in G,\lambda \geq 0\} \end{aligned}\]对应到图像中，$p^{*}$为区域$G$在$u \leq 0$的半平面内最小的$t$。做一系列$d=t+\lambda u$直线(斜率为$-\lambda$)与区域$G$相交，$d^{*}$为通过调整$\lambda$后获得的$d$最大值。对于一般的对偶关系，恒有$p^{*} \geq d^{*}$。
3. 极小极大定理与强对偶关系
(1) 极小极大定理 Minimax Theorem
von Neumann极小极大定理是指令\(X \subset \Bbb{R}^n\)和\(Y \subset \Bbb{R}^m\)是紧凸集，如果函数\(f:X \times Y \to \Bbb{R}\)是一个连续的凸凹(convex-concave)函数：
- \(f(\cdot,y):X \to \Bbb{R}\)是$x$的凸函数
- \(f(x,\cdot):Y \to \Bbb{R}\)是$y$的凹函数
则有：
\[\mathop{\max}_{y \in Y} \mathop{\min}_{x \in X} f(x,y) = \mathop{\min}_{x \in X} \mathop{\max}_{y \in Y} f(x,y)\]该定理指出，如果函数$f(x,y)$沿着一个变量变化的方向是凸的，沿着另一个变量变化的方向是凹的（这可以视为一个马鞍面），则在鞍点(saddle point)时上式成立。
(2) 强对偶关系 Strong Duality
根据Minimax定理，如果min问题和max问题的参数可行域都是凸集，并且目标函数是关于min问题参数的凸函数、是关于max问题参数的凹函数，则min和max的次序可以交换：
\[\mathop{\min}_{x \in \Bbb{R}^p} \mathop{\max}_{\lambda, \eta} \mathcal{L}(x,\lambda, \eta) = \mathop{\max}_{\lambda, \eta} \mathop{\min}_{x \in \Bbb{R}^p} \mathcal{L}(x,\lambda, \eta)\]此时原问题和对偶问题是等价的，称为强对偶关系(strong duality)。
对于原问题，需要首先考虑\(\mathop{\max}_{\lambda, \eta}\)算符，这是一个约束优化问题，通常不容易处理；通过强对偶关系转换为首先处理\(\mathop{\min}_{x \in \Bbb{R}^p}\)算符，这是一个无约束优化问题，可以通过取极值进行处理，从而简化问题的求解。
(3) 强对偶关系的一个充分条件：Slater条件
Slater Condition是指，在$x$的可行域的相对区域(relative interior, 即可行域的开区域)内存在一点$\hat{x}$，使得：
\[\forall i=1,2,\cdots,M, \quad m_i(\hat{x}) \lt 0\]- 对于大多数凸优化问题，Slater条件成立，且强对偶关系成立。
- 放松的Slater条件：若$M$个约束$m_i(x)$中有$K$个仿射函数，则只需验证其余$M-K$个约束满足$m_i(\hat{x}) \lt 0$即可。如凸二次规划问题满足Slater条件。
- Slater条件的几何意义是，在$(u,t) = (m(x),f(x))$组成的区域$G$中存在$u < 0$的点。
(4) 强对偶关系的一个充要条件：KKT条件
KKT条件(Karush–Kuhn–Tucker condition) 是强对偶关系的一个充要条件，给出了在强对偶关系下计算原问题和对偶问题的最优解$x^{*},\lambda^{*},\eta^{*}$的方法。
KKT条件包括：
- 可行域条件：
- 互补松弛(complementary slackness)条件：
- 梯度条件：
下面简单介绍互补松弛条件和梯度条件的推导过程。记原问题和对偶问题的最优解$x^{*},\lambda^{*},\eta^{*}$，且最优解对应的目标函数值分别为：
\[\begin{aligned} p^* &= \mathop{\min}_{x} f(x) \\ d^* &= \mathop{\max}_{\lambda, \eta}\mathop{\min}_{x} \mathcal{L}(x,\lambda, \eta) \\ \mathcal{L}(x,\lambda, \eta) &= f(x) + \sum_{i=1}^M \lambda m_i(x) + \sum_{j=1}^N \eta n_j(x) \end{aligned}\]则可写出如下过程：
\[\begin{aligned} d^* &= \mathop{\max}_{\lambda, \eta}\mathop{\min}_{x} \mathcal{L}(x,\lambda, \eta) = \mathop{\min}_{x} \mathcal{L}(x,\lambda^*, \eta^*) \\ & \leq \mathcal{L}(x^*,\lambda^*, \eta^*) = f(x^*) + \sum_{i=1}^M \lambda^* m_i(x^*) + \sum_{j=1}^N \eta^* n_j(x^*) \\ & = f(x^*) + \sum_{i=1}^M \lambda^* m_i(x^*) \quad (\text{根据可行域条件} n_j(x^*)= 0) \\ & \leq f(x^*) = \mathop{\min}_{x} f(x) = p^* \end{aligned}\]根据强对偶关系有$p^{*} = d^{*}$，则上述过程的两个不等式应取等号。
对第一个不等式取等号：
\[\mathop{\min}_{x} \mathcal{L}(x,\lambda^*, \eta^*) = \mathcal{L}(x^*,\lambda^*, \eta^*)\]则$x^{*}$应为函数\(\mathcal{L}(x,\lambda^*, \eta^*)\)的极小值点，即导出梯度条件：
\[\nabla_x \mathcal{L}(x,\lambda^*, \eta^*) |_{x=x^*} = 0\]对第二个不等式取等号：
\[f(x^*) + \sum_{i=1}^M \lambda^* m_i(x^*) = f(x^*)\]可得\(\sum_{i=1}^M \lambda^* m_i(x^*)=0\)。而根据可行域条件有\(m_i(x^*) \leq 0\), \(\lambda_i^* \geq 0\)，则导出互补松弛条件：
\[\lambda_i^* \cdot m_i(x^*) = 0\]
