本讲我们将介绍优化问题中的另一个重要概念——对偶性（duality）。利用对偶性可以将优化问题转化为对偶问题，不仅可以为原始问题的最优值提供下界，还能将非凸问题的求解转化为凸问题的求解。

对偶性（Duality）

拉格朗日函数（Lagrangian）

  • 在阐述对偶性理论之前，我们需要先定义拉格朗日函数。考虑下述原始优化问题： P:min⁡x⃗∈Rnf0(x⃗)s.t.fi(x⃗)≤0,i=1,2,⋯ ,mhj(x⃗)=0,j=1,2,⋯ ,p\begin{aligned} \mathcal{P}:\quad \min_{\vec{x}\in\R^n}\quad &f_0(\vec{x})\\ \text{s.t.}\quad &f_i(\vec{x})\leq 0,\quad i=1,2,\cdots,m\\ &h_j(\vec{x})=0,\quad j=1,2,\cdots,p \end{aligned} 我们希望将约束条件融入进目标函数中。对此，设约束条件对应的可行域为Ω\Omega，我们考虑引入示性函数： 1{C(x⃗)}={0,C(x⃗)为真+∞,C(x⃗)为假\mathbf{1}_{\{C(\vec{x})\}}=\begin{cases} 0, &C(\vec{x})\text{为真}\\ +\infty,&C(\vec{x})\text{为假} \end{cases} 那么目标函数就可以转化为 min⁡x⃗∈Ωf0(x⃗)=min⁡x⃗∈Rn{f0(x⃗)+1{x⃗∈Ω}}=min⁡x⃗∈Rn{f0(x⃗)+∑i=1m1{fi(x⃗)≤0}+∑j=1p1{hj(x⃗)=0}}.\begin{aligned} \min_{\vec{x} \in \Omega} f_0(\vec{x})&= \min_{\vec{x} \in \mathbb{R}^n} \bigl\{ f_0(\vec{x}) + \mathbf{1}_{\{\vec{x} \in \Omega\}} \bigr\} \\ &= \min_{\vec{x} \in \mathbb{R}^n} \left\{ f_0(\vec{x}) + \sum_{i=1}^m \mathbf{1}_{\{f_i(\vec{x}) \le 0\}} + \sum_{j=1}^p \mathbf{1}_{\{h_j(\vec{x}) = 0\}}\right\}. \end{aligned} 将转化后的目标函数记作F0(x⃗)F_0(\vec{x})，那么当x⃗∉Ω\vec{x}\not\in\Omega时，F0(x⃗)=∞F_0(\vec{x})=\infty。
  • 这样我们就将约束优化问题转化为了无约束优化问题。然而，由于示性函数不可微，我们仍然无法直接使用无约束优化方法（如梯度下降）求解。于是我们考虑使用可微函数近似表示示性函数。具体而言，我们使用以下转换： 1{fi(x⃗)≤0}=max⁡λi∈R+λifi(x⃗)1{hj(x⃗)=0}=max⁡νj∈Rνjhj(x⃗)\begin{aligned} \mathbf{1}_{\{f_i(\vec{x}) \le 0\}}&=\max_{\lambda_i\in\R^+}\lambda_if_i(\vec{x})\\ \mathbf{1}_{\{h_j(\vec{x}) = 0\}}&=\max_{\nu_j\in\R}\nu_jh_j(\vec{x}) \end{aligned} 为什么这个转换成立呢？以第一个式子为例：若fi(x⃗)>0f_i(\vec{x})>0，因为λifi(x⃗)\lambda_i f_i(\vec{x})要尽量大，所以λi\lambda_i会趋向+∞+\infty；若fi(x⃗)≤0f_i(\vec{x})\leq 0，要让λifi(x⃗)\lambda_if_i(\vec{x})尽量大，λi\lambda_i最终会取00。【第二个式子同理】
    • 这样我们就可以将上述问题进一步转化为 min⁡x⃗∈Ωf0(x⃗)=min⁡x⃗∈Rn{f0(x⃗)+∑i=1mmax⁡λi∈R+λifi(x⃗)+∑j=1pmax⁡νj∈Rνjhj(x⃗)}=min⁡x⃗∈Rn{f0(x⃗)+max⁡λ⃗∈R+m∑i=1mλifi(x⃗)+max⁡ν⃗∈Rp∑j=1pνjhj(x⃗)}=min⁡x⃗∈Rnmax⁡λ⃗∈R+mν⃗∈Rp{f0(x⃗)+∑i=1mλifi(x⃗)+∑j=1pνjhj(x⃗)}.\begin{aligned} \min_{\vec{x} \in \Omega} f_0(\vec{x})&= \min_{\vec{x} \in \mathbb{R}^n} \left\{ f_0(\vec{x}) + \sum_{i=1}^m \max_{\lambda_i \in \mathbb{R}_+} \lambda_i f_i(\vec{x}) + \sum_{j=1}^p \max_{\nu_j \in \mathbb{R}} \nu_j h_j(\vec{x}) \right\} \\ &= \min_{\vec{x} \in \mathbb{R}^n} \left\{ f_0(\vec{x}) + \max_{\vec{\lambda} \in \mathbb{R}_+^m} \sum_{i=1}^m \lambda_i f_i(\vec{x}) + \max_{\vec{\nu} \in \mathbb{R}^p} \sum_{j=1}^p \nu_j h_j(\vec{x}) \right\} \\ &= \min_{\vec{x} \in \mathbb{R}^n} \max_{\substack{\vec{\lambda} \in \mathbb{R}_+^m\\[3pt]\vec{\nu} \in \mathbb{R}^p}} \left\{ f_0(\vec{x}) + \sum_{i=1}^m \lambda_i f_i(\vec{x}) + \sum_{j=1}^p \nu_j h_j(\vec{x}) \right\}.\\ \end{aligned} 这便得到了拉格朗日函数L:Rn×Rm×Rp→RL:\R^n\times\R^m\times\R^p\to\R： L(x⃗,λ⃗,ν⃗)=f0(x⃗)+∑i=1mλifi(x⃗)+∑j=1pνjhj(x⃗)L(\vec{x},\vec{\lambda},\vec{\nu})=f_0(\vec{x}) + \sum_{i=1}^m \lambda_i f_i(\vec{x}) + \sum_{j=1}^p \nu_j h_j(\vec{x}) 其中λi,νj\lambda_i,\nu_j也称为拉格朗日乘子。
    • 拉格朗日函数相比原来带指示函数的目标函数更容易处理（虽然增加了两个优化参数，稍后我们会介绍如何处理）。实际上，拉格朗日乘子的引入相当于对超出约束的解进行惩罚，但相比示性函数这种“硬边界”更加柔和。
  • 拉格朗日函数具有下述性质：对任意给定x⃗∈Rn\vec{x}\in\R^n，(λ⃗,ν⃗)(\vec{\lambda},\vec{\nu})到L(x⃗,λ⃗,ν⃗)L(\vec{x},\vec{\lambda},\vec{\nu})的函数是仿射函数，进而也是凹函数。【这会在后续对偶性理论中起到重要作用】

btw，关于拉格朗日函数，也可以参考国内《数学分析》或类似课程的多元微积分条件极值相关内容。

弱对偶性（Weak Duality）

  • 我们对对偶性的讨论从下述拉格朗日函数优化问题开始： p∗=min⁡x⃗∈Rnmax⁡λ⃗∈R+mν⃗∈RpL(x⃗,λ⃗,ν⃗)p^*=\min_{\vec{x} \in \mathbb{R}^n} \max_{\substack{\vec{\lambda} \in \mathbb{R}_+^m\\[3pt]\vec{\nu} \in \mathbb{R}^p}}L(\vec{x},\vec{\lambda},\vec{\nu}) 将上式中的min⁡\min和max⁡\max对调，就得到了对偶问题形式： d∗=max⁡λ⃗∈R+mν⃗∈Rpmin⁡x⃗∈RnL(x⃗,λ⃗,ν⃗)d^*=\max_{\substack{\vec{\lambda} \in \mathbb{R}_+^m\\[3pt]\vec{\nu} \in \mathbb{R}^p}}\min_{\vec{x} \in \mathbb{R}^n}L(\vec{x},\vec{\lambda},\vec{\nu}) 其正式定义如下：考虑上述原始优化问题P\mathcal{P}，那么它的对偶问题D\mathcal{D}定义为 D:d∗=max⁡λ⃗∈Rmν⃗∈Rp  g(λ⃗,ν⃗)s.t.λi≥0,i=1,2,⋯ ,m\begin{aligned} \mathcal{D}:\quad d^*=\max_{\substack{\vec{\lambda} \in \mathbb{R}^m\\[3pt]\vec{\nu} \in \mathbb{R}^p}}\;&g(\vec{\lambda},\vec{\nu})\\ \text{s.t.}\quad &\lambda_i\geq 0,\quad i=1,2,\cdots,m \end{aligned} 其中g:R+m×Rp→Rg:\R_+^m\times\R^p\to\R为对偶函数，表达式为g(λ⃗,ν⃗)=min⁡x⃗∈RnL(x⃗,λ⃗,ν⃗)g(\vec{\lambda},\vec{\nu})=\displaystyle\min_{\vec{x} \in \mathbb{R}^n}L(\vec{x},\vec{\lambda},\vec{\nu})。
    • 由此可知gg函数的解可由一个无约束优化问题得到，且由上述拉格朗日函数性质可知，gg函数一定是凹函数（gg可看作一系列拉格朗日函数的逐点最小值）。
    • 也就是说，无论原始问题P\mathcal{P}的形式如何，对偶问题D\mathcal{D}一定是一个凸优化问题。
  • 接下来我们将讨论对偶问题的解与原始问题解的关系，以说明将原始问题转化为对偶问题求解的策略是可行的。
    • 具体而言，函数f0,gf_0,g与最优解p∗,d∗p^*,d^*之间具有如下不等式关系：设x⃗∈Ω,λ⃗∈R+m,ν⃗∈Rp\vec{x}\in\Omega,\vec{\lambda}\in\R^m_+,\vec{\nu}\in\R^p，那么有 f0(x⃗)≥p∗,  g(λ⃗,v⃗)≤d∗f0(x⃗)≥L(x⃗,λ⃗,v⃗)≥g(λ⃗,v⃗)f0(x⃗)≥d∗,  g(λ⃗,v⃗)≤p∗\begin{align} &f_0(\vec{x}) \geq p^*,\; g(\vec{\lambda}, \vec{v}) \leq d^* \tag{a} \\ &f_0(\vec{x}) \geq L(\vec{x}, \vec{\lambda}, \vec{v}) \geq g(\vec{\lambda}, \vec{v}) \tag{b} \\ &f_0(\vec{x}) \geq d^*,\; g(\vec{\lambda}, \vec{v}) \leq p^* \tag{c} \end{align} 推导如下： p∗=min⁡x⃗′∈Ωf0(x⃗′)≤f0(x⃗)d∗=max⁡λ⃗′∈R+mν⃗′∈Rpg(λ⃗′,ν⃗′)≥g(λ⃗,ν⃗)g(λ⃗,v⃗)=min⁡x⃗′∈ΩL(x⃗′,λ⃗,v⃗)≤L(x⃗,λ⃗,v⃗)≤max⁡λ⃗′∈R+mν⃗′∈RpL(x⃗,λ⃗′,v⃗′)=f0(x⃗)f0(x⃗)≥g(λ⃗,ν⃗)∀λ⃗∈R+m,  ∀ν⃗∈Rp⟹f0(x⃗)≥max⁡λ⃗′∈R+mg(λ⃗′,ν⃗′)=d∗f0(x⃗)≥g(λ⃗,ν⃗)∀x⃗∈Ω⟹p∗=min⁡x⃗′∈Ωf0(x⃗′)≥g(λ⃗,ν⃗).\begin{align*} p^* &= \min_{\vec{x}' \in \Omega} f_0(\vec{x}') \leq f_0(\vec{x}) \\ d^* &= \max_{\substack{\vec{\lambda}' \in \mathbb{R}^m_+\\[3pt]\vec{\nu}' \in \mathbb{R}^p}} g(\vec{\lambda}', \vec{\nu}') \geq g(\vec{\lambda}, \vec{\nu}) \tag{a}\\ g(\vec{\lambda}, \vec{v}) &= \min_{\vec{x}' \in \Omega} L(\vec{x}', \vec{\lambda}, \vec{v}) \leq L(\vec{x}, \vec{\lambda}, \vec{v})\leq \max_{\substack{\vec{\lambda}' \in \mathbb{R}^m_+\\[3pt]\vec{\nu}' \in \mathbb{R}^p}} L(\vec{x}, \vec{\lambda}', \vec{v}') =f_0(\vec{x}) \tag{b}\\ f_0(\vec{x}) &\geq g(\vec{\lambda}, \vec{\nu}) \quad \forall \vec{\lambda} \in \mathbb{R}_+^m,\; \forall \vec{\nu} \in \mathbb{R}^p \Longrightarrow f_0(\vec{x}) \geq \max_{\vec{\lambda}' \in \mathbb{R}_+^m} g(\vec{\lambda}', \vec{\nu}') = d^* \\ f_0(\vec{x}) &\geq g(\vec{\lambda}, \vec{\nu}) \quad \forall \vec{x} \in \Omega \Longrightarrow p^* = \min_{\vec{x}' \in \Omega} f_0(\vec{x}') \geq g(\vec{\lambda}, \vec{\nu}). \tag{c} \end{align*}
  • 由上述关系可知，g(λ⃗,ν⃗)≤{p∗,d∗}≤f0(x⃗)g(\vec{\lambda}, \vec{\nu})\leq\{p^*,d^*\}\leq f_0(\vec{x})，然而p∗,d∗p^*,d^*之间的大小关系仍未确定。实际上，它们之间的关系与对偶性本身密切相关。具体而言：
    1. 若上述问题中p∗≥d∗p^*\geq d^*，我们称其满足弱对偶性（weak duality）；
    2. 若上述问题中p∗=d∗p^*= d^*，我们称其满足强对偶性（strong duality）；
    3. 定义p∗−d∗p^*-d^*为对偶间隙（duality gap）。
  • 接下来我们给出一个重要命题：对于任意优化问题，弱对偶性总是成立，即对偶间隙一定非负。
    • 实际上这一命题可看作下述极大极小不等式（minimax inequality）的一个推论：设XX与YY为任意集合，F:X×Y→RF:X\times Y\to\R为任意函数，那么有 min⁡x∈Xmax⁡y∈YF(x,y)≥max⁡y∈Ymin⁡x∈XF(x,y)\min_{x\in X}\max_{y\in Y}F(x,y)\geq \max_{y\in Y}\min_{x\in X}F(x,y) 简单证明如下：因为 F(x,y)≥min⁡x′∈XF(x′,y)F(x,y)\geq \min_{x'\in X}F(x',y) 两边对yy取最大值得 max⁡y∈YF(x,y)≥max⁡y∈Ymin⁡x∈XF(x,y)\max_{y\in Y}F(x,y)\geq \max_{y\in Y}\min_{x\in X}F(x,y) 由于上式右边为常数，故对左侧关于xx取最小值不等号仍然成立，原命题得证。

      注：上式两边对yy取最大值时取的yy可能不同，但不影响不等式结果。

    • 那么如何理解这个不等式呢？可以用玩家博弈的先后手理解：
      • 设玩家XX希望对函数FF最小化，而玩家YY希望对FF最大化。
      • 他们分别选择对变量xx和yy操作，而min⁡\min和max⁡\max的先后顺序对应了先后手（靠左侧为先手，靠右侧为后手，因为函数变量从左到右进行固定）。
      • 对于玩家XX，选择后手（先max⁡\max后min⁡\min）比先手（先min⁡\min后max⁡\max）得到的结果更好（即函数更小）。【玩家YY视角同理】
  • 那么如何利用弱对偶性呢？根据上述推导，我们可得对于任意x⃗∈Ω,(λ⃗,ν⃗)∈R+m×Rp\vec{x}\in\Omega,(\vec{\lambda}, \vec{\nu})\in\R^m_+\times\R^p，有 f0(x⃗)≥p∗≥d∗≥g(λ⃗,ν⃗)  ⟹  f0(x⃗)−g(λ⃗,ν⃗)≥f0(x⃗)−p∗.f_0(\vec{x}) \geq p^* \geq d^* \geq g(\vec{\lambda}, \vec{\nu}) \implies f_0(\vec{x}) - g(\vec{\lambda}, \vec{\nu}) \geq f_0(\vec{x}) - p^*. 于是，我们就能通过解函数与对偶函数之差得到解与最优解之间差距的上界。这可以作为优化算法迭代停止的依据。【这也被称作最优性证书（certificate of optimality）】

强对偶性（Strong Duality）

  • 上面介绍的弱对偶性虽然具有普遍性，但只依赖弱对偶性无法精确计算最优解。此时我们就需要借助强对偶性，虽然它并不总是成立。
  • 强对偶性成立的条件有很多，下面我们介绍一种简单且广泛适用的条件：Slater条件。其具体表述如下：
    • 设原始问题的可行域为Ω\Omega，考虑原始问题约束条件中的函数f1,⋯ ,fmf_1,\cdots,f_m（均为凸函数）和h1,⋯ ,hph_1,\cdots,h_p（均为仿射函数）。如果存在x⃗∈relint(Ω)\vec{x}\in\text{relint}(\Omega)（即严格可行），使得对于任意fi,i∈{1,2,⋯ ,m}f_i,i\in\{1,2,\cdots,m\}，当fif_i为仿射函数时fi(x⃗)≤0f_i(\vec{x})\leq 0，不是仿射函数时fi(x⃗)<0f_i(\vec{x})< 0，那么就称原始问题P\mathcal{P}具有强对偶性，即对偶间隙为00。

      注：这个条件实际上是精细Slater条件，与标准Slater条件的唯一区别在于后者对所有不等式约束函数都要求严格小于00。

    • 关于Slater条件的证明在此作略，可参见Boyd的《凸优化》5.3.2节或知乎文章。【使用了分离超平面定理】
    • 从直观上理解，Slater条件的本质是如果可行域的内部具有一个严格可行解，那么强对偶性就成立。
  • 下面我们给出两个用对偶问题求解原问题最优解的具体示例：

    1. 最小范数问题（可参见Chapter 1）：原始问题形式为

      P:p∗=min⁡x⃗∈Rn∥x⃗∥22s.t.Ax⃗=y⃗\begin{aligned} \mathcal{P}:\quad p^*=\min_{\vec{x}\in\R^n}\|\vec{x}\|_2^2\\ \text{s.t.}\quad A\vec{x}=\vec{y} \end{aligned}

      其中A∈Rp×nA\in\R^{p\times n}。由于问题只有等式约束，因此拉格朗日函数为

      L(x⃗,ν⃗)=∥x⃗∥22+∑j=1pνj(Ax⃗−y⃗)j=∥x⃗∥22+ν⃗⊤(Ax⃗−y⃗).L(\vec{x},\vec{\nu})=\|\vec{x}\|_2^2+\sum_{j=1}^p\nu_j(A\vec{x}-\vec{y})_j=\|\vec{x}\|_2^2+\vec{\nu}^\top(A\vec{x}-\vec{y}).

      从而得到对偶函数

      g(ν⃗)=min⁡x⃗∈RnL(x⃗,ν⃗)=min⁡x⃗∈Rn{∥x⃗∥22+ν⃗⊤(Ax⃗−y⃗)}g(\vec{\nu})=\min_{\vec{x}\in\R^n}L(\vec{x},\vec{\nu})=\min_{\vec{x}\in\R^n}\left\{\|\vec{x}\|_2^2+\vec{\nu}^\top(A\vec{x}-\vec{y})\right\}

      因为拉格朗日函数为凸函数，所以直接将其对x⃗\vec{x}求偏导取零值：

      ∇x⃗L(x⃗,ν⃗)=2x⃗+A⊤ν⃗=0⃗⟹x⃗∗=−12A⊤ν⃗\nabla_{\vec{x}}L(\vec{x},\vec{\nu})=2\vec{x}+A^\top\vec{\nu}=\vec{0}\Longrightarrow \vec{x}^*=-\frac{1}{2}A^\top\vec{\nu}

      代回拉格朗日函数得到

      g(ν)=(−12A⊤ν⃗)2−12ν⃗⊤AA⊤ν⃗−ν⃗⊤y⃗=−14ν⃗⊤AA⊤ν⃗−ν⃗⊤y⃗g(\nu)=\left(-\frac{1}{2}A^\top\vec{\nu}\right)^2-\frac{1}{2}\vec{\nu}^\top AA^\top\vec{\nu}-\vec{\nu}^\top\vec{y}=-\frac{1}{4}\vec{\nu}^\top AA^\top\vec{\nu}-\vec{\nu}^\top\vec{y}

      于是对偶问题即为

      d∗=max⁡ν∈Rp{−14ν⃗⊤AA⊤ν⃗−ν⃗⊤y⃗}=min⁡ν∈Rp{14ν⃗⊤AA⊤ν⃗+ν⃗⊤y⃗}d^*=\max_{\nu\in\R^p}\left\{-\frac{1}{4}\vec{\nu}^\top AA^\top\vec{\nu}-\vec{\nu}^\top\vec{y}\right\}=\min_{\nu\in\R^p}\left\{\frac{1}{4}\vec{\nu}^\top AA^\top\vec{\nu}+\vec{\nu}^\top\vec{y}\right\}

      这同样是一个凸优化问题，依旧使用求偏导取零点得到

      ∇g(ν⃗)=12AA⊤ν⃗+y⃗⟹ν⃗∗=−2(AA⊤)−1y⃗\nabla g(\vec{\nu})=\frac{1}{2}AA^\top\vec{\nu}+\vec{y}\Longrightarrow \vec{\nu}^*=-2(AA^\top)^{-1}\vec{y}

      由于原始问题是凸优化问题且约束函数是仿射函数，因此只要约束条件Ax⃗=y⃗A\vec{x}=\vec{y}有解，问题就满足强对偶性。此时

      x⃗∗=−12A⊤ν⃗∗=A(AA⊤)−1y⃗\vec{x}^*=-\frac{1}{2}A^\top\vec{\nu}^*=A(AA^\top)^{-1}\vec{y}

      便是原始问题的全局最优解。

    2. 影子价格问题（拉格朗日乘子的经济学解释）：假设我们有两种原料AA和BB，分别有200200千克和300300千克，将它们混合制作成商品，有两种方案：

      • 取44千克原料AA和11千克原料BB，加工成一份价值2020的商品；
      • 取22千克原料AA和33千克原料BB，加工成一份价值1515的商品；

      我们希望总销售额最大。具体而言，假设两种商品分别制作q1q_1份和q2q_2份，对应的优化问题即为

      p∗=max⁡q1,q2∈R20q1+15q2s.t.4q1+2q2≤200q1+3q2≤300q1≥0q2≥0.\begin{aligned} p^* = \max_{q_1, q_2 \in \mathbb{R}} \quad & 20q_1 + 15q_2 \\ \text{s.t.} \quad & 4q_1 + 2q_2 \leq 200 \\ & q_1 + 3q_2 \leq 300 \\ & q_1 \geq 0 \\ & q_2 \geq 0. \end{aligned}

      这实际上可以看作一个线性规划（linear programming）问题（虽然最终参数解一般取整数）。我们考虑包含前两个约束条件的拉格朗日函数

      max⁡q1,q2∈R+{20q1+15q2+λ1(200−4q1−2q2)+λ2(300−q1−3q2)}=max⁡q1,q2∈R+{(20−4λ1−λ2)q1+(15−2λ1−3λ2)q2+200λ1+300λ2}.\begin{aligned} \max_{q_1, q_2 \in \mathbb{R}_+} \bigl\{ 20q_1 + 15q_2 + \lambda_1 (200 - 4q_1 - 2q_2) + \lambda_2 (300 - q_1 - 3q_2) \bigr\} \\ = \max_{q_1, q_2 \in \mathbb{R}_+} \bigl\{ (20 - 4\lambda_1 - \lambda_2)q_1 + (15 - 2\lambda_1 - 3\lambda_2)q_2 + 200\lambda_1 + 300\lambda_2 \bigr\}. \end{aligned}

      其中λ1\lambda_1和λ2\lambda_2可以理解为11千克原料AA和BB的“内部估值”。接着我们可以再考虑下述原料总估值的最小化问题：

      min⁡λ1,λ2∈R+200λ1+300λ2s.t.20−4λ1−λ2≤015−2λ1−3λ2≤0\begin{aligned} \min_{\lambda_1,\lambda_2\in\R_+}&200\lambda_1+300\lambda_2\\ \text{s.t.}\quad &20 - 4\lambda_1 - \lambda_2\leq 0\\ &15 - 2\lambda_1 - 3\lambda_2\leq 0 \end{aligned}

      其中约束条件可以理解为每种商品的售价都不超过其所耗原料的内部估值。

      • 实际上，这也是上述优化问题的对偶问题，且显然满足强对偶性条件。【给全部原料给出的最小总估值，恰好等于原问题能够达到的最大总销售额】
      • λi\lambda_i也被称为影子价格（shadow prices），反映了我们愿意为违反约束条件付出的代价。

Karush-Kuhn-Tucker（KKT）条件

下面我们再介绍另一个与强对偶性有关的重要条件，即KKT条件。其具体形式如下：

  • 设(x⃗,λ⃗,v⃗)∈Rn×Rm×Rp(\vec{x}, \vec{\lambda}, \vec{v}) \in \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p为决策变量和拉格朗日乘子，目标函数f0f_0以及约束函数f1,…,fm,h1,…,hpf_1, \ldots, f_m, h_1, \ldots, h_p均可微。若(x⃗,λ⃗,v⃗)(\vec{x}, \vec{\lambda}, \vec{v})满足：

    1. x⃗\vec{x}为原始问题P\mathcal{P}的可行解，即 fi(x⃗)≤0,i=1,2,⋯ ,mhj(x⃗)=0,j=1,2,⋯ ,p\begin{aligned} f_i(\vec{x}) \leq 0, \quad i=1,2,\cdots,m\\ h_j(\vec{x}) = 0, \quad j=1,2,\cdots,p \end{aligned}
    2. (λ⃗,v⃗)(\vec{\lambda}, \vec{v})为对偶问题D\mathcal{D}的可行解，即 λ⃗i≥0,i=1,2,⋯ ,m\vec{\lambda}_i \geq 0, \quad i=1,2,\cdots,m
    3. 互补松弛条件：【实际上，这个条件可理解为筛选出活跃约束（将非活跃约束乘子取00）】 λ⃗ifi(x⃗)=0,i=1,2,⋯ ,m\vec{\lambda}_i f_i(\vec{x}) = 0, \quad i=1,2,\cdots,m
    4. 平稳性（也称一阶条件）： 0⃗=∇x⃗L(x⃗,λ⃗,v⃗)=∇f(x⃗)+∑i=1mλ⃗i∇fi(x⃗)+∑j=1pv⃗j∇hj(x⃗)\vec{0} = \nabla_{\vec{x}} L(\vec{x}, \vec{\lambda}, \vec{v}) = \nabla f(\vec{x}) + \sum_{i=1}^m \vec{\lambda}_i \nabla f_i(\vec{x}) + \sum_{j=1}^p \vec{v}_j \nabla h_j(\vec{x})

    则称其满足KKT条件。

  • 实际上，如果原始问题P\mathcal{P}满足强对偶性，且对应的目标函数与约束函数可微，(x⃗∗,λ⃗∗,ν⃗∗)(\vec{x}^*,\vec{\lambda}^*,\vec{\nu}^*)为原始问题与对偶问题的最优解，那么它就满足KKT条件。【KKT条件是强对偶性的必要条件】

    • 简单证明：由上述前提可知

      λi∗fi(x⃗∗)≤0,i=1,2,⋯ ,mνj∗hj(x⃗∗)=0,j=1,2,⋯ ,p\begin{aligned} \lambda_i^*f_i(\vec{x}^*)\leq 0,\quad i=1,2,\cdots,m\\ \nu_j^*h_j(\vec{x}^*)=0,\quad j=1,2,\cdots,p \end{aligned}

      而根据之前对弱对偶性的推导可知：

      d∗=g(λ⃗∗,ν⃗∗)=min⁡x⃗∈RnL(x⃗,λ⃗∗,ν⃗∗)≤L(x⃗∗,λ⃗∗,ν⃗∗)=f0(x⃗∗)+∑i=1mλi∗fi(x⃗∗)+∑j=1pνj∗hj(x⃗∗)≤f0(x⃗∗)=p∗d^* = g(\vec{\lambda}^*, \vec{\nu}^*) = \min_{\vec{x} \in \mathbb{R}^n} L(\vec{x}, \vec{\lambda}^*, \vec{\nu}^*) \leq L(\vec{x}^*, \vec{\lambda}^*, \vec{\nu}^*) = f_0(\vec{x}^*) + \sum_{i=1}^m \lambda_i^* f_i(\vec{x}^*) + \sum_{j=1}^p \nu_j^* h_j(\vec{x}^*) \leq f_0(\vec{x}^*) = p^*

      又根据强对偶性，d∗=p∗d^*=p^*，故中间所有不等号都可去等。于是：

      • 第一个不等号取等：x⃗∗\vec{x}^*为拉格朗日函数关于x⃗\vec{x}的最小值点，故∇x⃗L(x⃗,λ⃗,v⃗)=0⃗\nabla_{\vec{x}} L(\vec{x}, \vec{\lambda}, \vec{v})=\vec{0}；
      • 第二个不等号去等：∑i=1mλi∗fi(x⃗∗)\displaystyle\sum_{i=1}^m \lambda_i^* f_i(\vec{x}^*)必须为00，因此λi∗fi(x⃗∗)\lambda_i^* f_i(\vec{x}^*)对任意ii均成立（即互补松弛条件）。

      而前两个条件显然成立，因此KKT条件成立。

  • 那么KKT条件能否推出强对偶性呢？在凸性条件下是可以的。具体而言，设原始问题P\mathcal{P}中目标函数f0f_0与约束函数f1,⋯ ,fm,h1,⋯ ,hpf_1,\cdots,f_m,h_1,\cdots,h_p均可微，f0,f1,⋯ ,fmf_0,f_1,\cdots,f_m为凸函数，h1,⋯ ,hph_1,\cdots,h_p为仿射函数，如果(x⃗~,λ⃗~,ν⃗~)(\tilde{\vec{x}},\tilde{\vec{\lambda}},\tilde{\vec{\nu}})满足KKT条件，那么原始问题就是凸优化问题，满足强对偶性，且(x⃗~,λ⃗~,ν⃗~)(\tilde{\vec{x}},\tilde{\vec{\lambda}},\tilde{\vec{\nu}})就是原始问题和对偶问题的最优解。

    • 也就是说，对于凸优化问题，KKT条件与强对偶性是相互等价的。【同时满足KKT条件的解一定是最优解】

  • 综合上述推导，我们就能得到利用KKT条件解决凸优化问题的策略：

    1. 设原始问题为P\mathcal{P}，验证P\mathcal{P}的目标函数与约束条件函数均满足凸性条件且可微；
    2. 验证P\mathcal{P}满足Slater条件或P\mathcal{P}和D\mathcal{D}满足强对偶性；
    3. 计算P\mathcal{P}和D\mathcal{D}对应的KKT条件，由此得到最优解参数。

    然而，由KKT条件构造方程组得到的解不一定就是全局最优解。此时可以考虑对原始问题进行简化（如引入松弛变量），或者生成多个候选解，再代回KKT条件进行验证。

锥对偶性（Cone Duality）

拉格朗日函数与对偶性还可以推广到约束条件为广义不等式的优化问题中。广义不等式的定义如下：

  • 设K⊆RnK\subseteq\R^n为一个正常锥，int(K)\text{int}(K)为KK的内部。那么对于任意两个向量u⃗,v⃗∈Rn\vec{u},\vec{v}\in\R^n，它们之间的关系可以用KK诱导出的不等关系≻K\succ_K（⪰K\succeq_K）表示。具体而言，

    • 若u⃗−v⃗∈K\vec{u}-\vec{v}\in K，则称u⃗⪰Kv⃗\vec{u}\succeq_K\vec{v}或v⃗⪯Ku⃗\vec{v}\preceq_K\vec{u}；
    • 若u⃗−v⃗∈int(K)\vec{u}-\vec{v}\in \text{int}(K)，则称u⃗≻Kv⃗\vec{u}\succ_K\vec{v}或v⃗≺Ku⃗\vec{v}\prec_K\vec{u}；

    特别地，如果代入0⃗\vec{0}向量，可以得到：

    u⃗∈K⟹u⃗⪰K0⃗−v⃗∈K⟹v⃗⪯K0⃗u⃗∈int(K)⟹u⃗≻K0⃗−v⃗∈int(K)⟹v⃗≺K0⃗\begin{aligned} \vec{u}\in K\Longrightarrow \vec{u}\succeq_K\vec{0}\\ -\vec{v}\in K\Longrightarrow \vec{v}\preceq_K\vec{0}\\ \vec{u}\in \text{int}(K)\Longrightarrow \vec{u}\succ_K\vec{0}\\ -\vec{v}\in \text{int}(K)\Longrightarrow \vec{v}\prec_K\vec{0}\\ \end{aligned}

    注：当u⃗−v⃗∉K\vec{u}-\vec{v}\not\in K时，u⃗,v⃗\vec{u},\vec{v}之间就无法用KK诱导的不等关系表述。

  • 实际上，之前我们已经接触过一些广义不等式。比如，在定义半正定矩阵的时候，使用A⪰0A\succeq 0就是由正常锥S+n\mathbb{S}_+^n诱导出的关系。

  • 对之前的优化问题，我们也可以用广义不等式简化表示。比如，对于下述优化问题

    min⁡x⃗∈Rnf0(x⃗)s.t.fi(x⃗)≤0,i=1,⋯ ,m.\begin{aligned} \min_{\vec{x} \in \mathbb{R}^n} \quad & f_0(\vec{x}) \\ \text{s.t.} \quad & f_i(\vec{x}) \leq 0, \quad i =1, \cdots, m. \end{aligned}

    考虑正常锥K=R+m={x⃗∈Rm∣xi≥0,i=1,⋯ ,m}K=\R^m_+=\{\vec{x}\in\R^m\mid x_i\geq 0,i=1,\cdots,m\}，定义函数f⃗:Rn→Rm\vec{f}:\R^n\to\R^m为

    f⃗(x⃗)=[f1(x⃗)⋮fm(x⃗)]\vec{f}(\vec{x})=\begin{bmatrix}f_1(\vec{x})\\\vdots\\f_m(\vec{x})\end{bmatrix}

    那么这个优化问题可以简写为

    min⁡x⃗∈Rnf0(x⃗)s.t.f⃗(x⃗)⪯K0⃗,i=1,⋯ ,m.\begin{aligned} \min_{\vec{x} \in \mathbb{R}^n} \quad & f_0(\vec{x}) \\ \text{s.t.} \quad & \vec{f}(\vec{x}) \preceq_K \vec{0}, \quad i =1, \cdots, m. \end{aligned}

  • 广义不等式具有传递性：对于指定正常锥KK，若v⃗1⪰Kv⃗2\vec{v}_1\succeq_K\vec{v}_2，v⃗2⪰Kv⃗3\vec{v}_2\succeq_K\vec{v}_3，那么有v⃗1⪰Kv⃗3\vec{v}_1\succeq_K\vec{v}_3。（其他不等号同理）

  • 利用上述定义与推导，我们可以得到广义约束优化问题的形式：

    • 设目标函数f0:Rn→Rf_0:\R^n\to\R，f⃗i:Rn→Rdi,i=1,2,⋯ ,m\vec{f}_i:\R^n\to\R^{d_i},i=1,2,\cdots,m为向量值不等式约束函数，K⊆RdiK\subseteq\R^{d_i}为正常锥（也被称为约束锥），记d=∑i=1mdi\displaystyle d=\sum_{i=1}^md_i。另设hj:Rn→R,j=1,⋯ ,ph_j:\R^n\to\R,j=1,\cdots,p为等式约束函数。那么我们就得到广义约束优化问题： P:p∗=min⁡x⃗∈Rnf0(x⃗)s.t.f⃗i(x⃗)⪯Ki0⃗,i=1,⋯ ,mhj(x⃗)=0,j=1,⋯ ,p.\begin{aligned} \mathcal{P}: \quad p^* = \min_{\vec{x} \in \mathbb{R}^n} \quad & f_0(\vec{x}) \\ \text{s.t.} \quad & \vec{f}_i(\vec{x}) \preceq_{K_i} \vec{0}, \quad i=1,\cdots,m \\ & h_j(\vec{x}) = 0, \quad j =1,\cdots,p. \end{aligned}

  • 下面对这个优化问题的对偶问题进行推导。首先引入示性函数：

    p∗=min⁡x⃗∈Rn[f0(x⃗)+∑i=1m1{f⃗i(x⃗)⪯Ki0⃗}+∑j=1p1{hj(x⃗)=0}].p^* = \min_{\vec{x} \in \mathbb{R}^n} \left[ f_0(\vec{x}) + \sum_{i=1}^m \mathbf{1}_{\{\vec{f}_i(\vec{x}) \preceq_{K_i} \vec{0}\}} + \sum_{j=1}^p \mathbf{1}_{\{h_j(\vec{x}) = 0\}}\right].

    尝试将指示函数替换为拉格朗日乘子，我们得到

    1{f⃗i(x⃗)⪯Ki0⃗}=max⁡λ⃗i∈Rdiλ⃗i⪰Ki∗0⃗λ⃗i⊤f⃗i(x⃗),1{hj(x⃗)=0}=max⁡νj∈Rνjhj(x⃗)\begin{aligned} \mathbf{1}_{\{\vec{f}_i(\vec{x}) \preceq_{K_i} \vec{0} \}} &= \max_{\substack{\vec{\lambda}_i \in \mathbb{R}^{d_i} \\ \vec{\lambda}_i \succeq_{K_i^*}\vec{0}}} \vec{\lambda}_i^\top \vec{f}_i(\vec{x}),\\ \mathbf{1}_{\{h_j(\vec{x}) = 0\}}&=\max_{\nu_j\in\R}\nu_jh_j(\vec{x}) \end{aligned}

    其中Ki∗K_i^*表示KiK_i在Rdi\R^{d_i}上的对偶锥。【可以通过定义证明】

    注：这里的λ⃗i⊤f⃗i(x⃗)\vec{\lambda}_i^\top \vec{f}_i(\vec{x})可以替换为广义内积⟨λ⃗i,f⃗i(x⃗)⟩\langle\vec{\lambda}_i,\vec{f}_i(\vec{x})\rangle。

    由此我们可以得到优化问题的拉格朗日函数形式：

    p∗=min⁡x⃗∈Rn  max⁡λ⃗∈Rdν⃗∈Rpλ⃗i⪰Ki∗0⃗,i=1,⋯,m.[f0(x⃗)+∑i=1mλ⃗i⊤f⃗i(x⃗)+∑j=1pνjhj(x⃗)]p^*= \min_{\vec{x} \in \mathbb{R}^n} \; \max_{\substack{ \vec{\lambda} \in \mathbb{R}^d \\ \vec{\nu} \in \mathbb{R}^p\\ \vec{\lambda}_i \succeq_{K_i^*} \vec{0},\;i=1,\cdots,m. }} \left[ f_0(\vec{x}) + \sum_{i=1}^m \vec{\lambda}_i^\top \vec{f}_i(\vec{x}) + \sum_{j=1}^p \nu_j h_j(\vec{x}) \right]

    其中拉格朗日函数定义为

    L(x⃗,λ⃗,ν⃗)≔f0(x⃗)+∑i=1mλ⃗i⊤f⃗i(x⃗)+∑j=1pνjhj(x⃗)L(\vec{x},\vec{\lambda},\vec{\nu})\coloneqq f_0(\vec{x}) + \sum_{i=1}^m \vec{\lambda}_i^\top \vec{f}_i(\vec{x}) + \sum_{j=1}^p \nu_j h_j(\vec{x})

    因此对偶函数定义为

    g(λ⃗,ν⃗)≔min⁡x⃗∈RnL(x⃗,λ⃗,ν⃗)g(\vec{\lambda},\vec{\nu})\coloneqq\min_{\vec{x} \in \mathbb{R}^n}L(\vec{x},\vec{\lambda},\vec{\nu})

    从而对偶问题可表示为

    D:d∗=max⁡λ⃗∈Rmν⃗∈Rp  g(λ⃗,ν⃗)s.t.λ⃗i⪰Ki0⃗,i=1,2,⋯ ,m\begin{aligned} \mathcal{D}:\quad d^*=\max_{\substack{\vec{\lambda} \in \mathbb{R}^m\\[3pt]\vec{\nu} \in \mathbb{R}^p}}\;&g(\vec{\lambda},\vec{\nu})\\ \text{s.t.}\quad &\vec{\lambda}_i\succeq_{K_i} \vec{0},\quad i=1,2,\cdots,m \end{aligned}

    其弱对偶性仍然满足。

  • 那么广义不等式体系中是否仍然有Slater条件呢？有的，只需要引入广义凸性概念：设f⃗:Rn→Rd\vec{f}: \mathbb{R}^n \to \mathbb{R}^d，且K⊆RdK \subseteq \mathbb{R}^d为一个正常锥，

    • 若对任意α∈[0,1]\alpha \in [0, 1]和x⃗,y⃗∈Rn\vec{x}, \vec{y} \in \mathbb{R}^n，有 f⃗(αx⃗+(1−α)y⃗)⪯Kαf⃗(x⃗)+(1−α)f⃗(y⃗)\vec{f}(\alpha \vec{x} + (1 - \alpha) \vec{y}) \preceq_K \alpha \vec{f}(\vec{x}) + (1 - \alpha) \vec{f}(\vec{y}) 则称f⃗\vec{f}为KK-凸函数。
    • 若对任意α∈(0,1)\alpha \in (0, 1)和x⃗,y⃗∈Rn\vec{x}, \vec{y} \in \mathbb{R}^n且x⃗≠y⃗\vec{x} \neq \vec{y}，有 f⃗(αx⃗+(1−α)y⃗)≺Kαf⃗(x⃗)+(1−α)f⃗(y⃗)\vec{f}(\alpha \vec{x} + (1 - \alpha) \vec{y}) \prec_K \alpha \vec{f}(\vec{x}) + (1 - \alpha) \vec{f}(\vec{y}) 称f⃗\vec{f}为KK-严格凸函数。

    这样我们就能得到广义Slater条件：对于下述优化问题

    P:p∗=min⁡x⃗∈Rnf0(x⃗)s.t.f⃗i(x⃗)⪯Ki0⃗,i=1,⋯ ,mhj(x⃗)=0,j=1,⋯ ,p.\begin{aligned} \mathcal{P}: \quad p^* = \min_{\vec{x} \in \mathbb{R}^n} \quad & f_0(\vec{x}) \\ \text{s.t.} \quad & \vec{f}_i(\vec{x}) \preceq_{K_i} \vec{0}, \quad i=1,\cdots,m \\ & h_j(\vec{x}) = 0, \quad j =1,\cdots,p. \end{aligned}

    如果：

    • f0:Rn→Rf_0 : \mathbb{R}^n \to \mathbb{R}是凸函数；
    • f⃗i:Rn→Rdi,  i=1,⋯ ,m\vec{f}_i : \mathbb{R}^n \to \mathbb{R}^{d_i},\;i =1, \cdots, m是KiK_i-凸函数，其中Ki⊆RdiK_i \subseteq \mathbb{R}^{d_i}是一个正常锥；
    • hj:Rn→R,  j=1,⋯ ,ph_j : \mathbb{R}^n \to \mathbb{R},\;j=1,\cdots,p是仿射函数；
    • 存在某个点x⃗∈relint(Ω)\vec{x} \in \text{relint}(\Omega)是严格可行的，即满足： f⃗i(x⃗)≺Ki0⃗,i=1,⋯ ,mhj(x⃗)=0,j=1,⋯ ,p\begin{aligned} &\vec{f}_i(\vec{x}) \prec_{K_i} \vec{0},\quad i =1, \cdots, m\\ &h_j(\vec{x}) = 0,\quad j=1,\cdots,p \end{aligned}

    那么原问题P\mathcal{P}及其对偶问题D\mathcal{D}满足强对偶性，即对偶间隙为00。