什么是Lagrange Method, KKT Condtions, Dual Problem？

Lagrange Method for Constrained Optimization

• Generic constrained optimization problem:
  • 
  • regional constraint: \(x\in X\), 例如\(x\geq 0\)
  • functional constraint
    • 等式约束：\(g(x)=b\)
    • 不等式约束：不等式的话加个slack variable，就可以转换为等式。\(g(x)\leq b\) to \(g(x)+z^2=b\)。(使用松弛变量的平方是因为，必须得加一个正数才能变成等于，如果只加z，又得引入新的约束\(z>0\))
  • solved by using Lagrangian method.
• Lagrangian: \(L(x, \lambda)=f(x)+\lambda(b-g(x))\),
  • \(\lambda\): Lagrange multiplier
  • if \(L(x, \lambda)\) is a concave function of x, then it has a unique maximum; same with convex function and minimum.
  • 求一阶导，求出最值。代入原来的constraint中消掉\(\lambda\)求出x*。

Lagrange multipliers

• 上述方法其实就是Lagrange multipliers的变形。
• O.P.: $$minmax\ f(x)\ s.t.\ g(x)=0$$
• 结论
  • 在约束曲面上任意点x，该点的梯度\(\triangledown g(x)\)正交于约束曲面。
  • 在最优点\(x^*\)，目标函数在该点的梯度\(\triangledown f(x^*)\)正交于约束曲面。
• 上面两个结论可以得出：在最优点\(x^*\)，梯度\(\triangledown g(x)\)和\(\triangledown f(x)\)的方向必相同或相反。
  • 即：存在\(\lambda \neq 0\) 使得 \(\triangledown f(x^*)=\lambda \triangledown g(x^*)\).
    • 这样可以直接与约束式联立求解。
    • 
  • or: 存在\(\lambda \neq 0\) 使得 \(\triangledown f(x^*) +\lambda \triangledown g(x^*) = 0\).
    • 这个其实就是上面\(L(x, \lambda)=f(x)+\lambda(b-g(x))\)这个方法，对L函数求偏导置零就可以得到了。
    • 所以说是一种变形而已。

KKT conditions (Karush-Kuhn-Tucker conditions)

• 不等式约束，注意是有等于的。\(g(x)\leq 0\) 而不是\(g(x)< 0\)。
• 最优点在\(g(x) < 0\)：
  • 那\(g(x)\leq 0\) 这个约束不起作用了
  • 需要直接通过\(\triangledown f(x)=0\)来获得最优解。相当于将L 函数中的\(\lambda\)置零。
• 最优点在\(g(x)= 0\)：
  • 和前面的等式约束差不多。
  • 注意此时\(\triangledown f(x^*)\)的方向必须与\(\triangledown g(x^*)\)相反，即存在常数\(\lambda>0\)使得\(\triangledown f(x^*)+\lambda \triangledown g(x^*) =0\)。
    • 为什么相反呢？
    • 梯度方向是函数值上升最快的方向。
    • 如果g(x)梯度和f(x)一样，那么g(x)能取的地方应该是绿色区域而不是红色区域了，会导致目标函数无穷大而无解。因为约束是小于等于0，而不是大于等于0。如果和f(x)一样，那就是红圈里面，往里面才大。
    • ?
• KKT：
  • 多个约束优化问题：
    • 
    • h是等式约束
    • g是不等式约束
  • 拉格朗日函数：
    • 
  • KKT conditions：
    • 
    • \(g_j(x) \leq 0\)：原本的不等式约束
    • \(\mu_j \geq 0\)：因为g的梯度方向得和f函数相反，所以权值得是非负的。（因为那个梯度的关系是从这个拉格朗日函数求偏导得来的，对梯度关系要求\(\mu_j \geq 0\)，所以对这个拉格朗日函数也要求\(\mu_j \geq 0\)。）
    • \(\mu_j g_j(x) = 0\)：
      • 因为有的最优点在\(g_j(x)<0\)，所以这些情况下\(\mu_j=0\)
      • 只有最优点在\(g_j(x)=0\)上，才会有\(\mu_j\geq 0\)，乘起来还是0。
    • \(\triangledown_xL(x,\lambda,\mu) = 0\)
    • \(h_i(x)=0\)
• KKT conditions有什么用？
  • 满足KKT条件后极小化Lagrangian 即可得到在不等式约束条件下的可行解。

Dual Problem

• 一个优化问题可以由两个角度来考察，主问题 primal problem和对偶问题dual problem。
• 主问题：
  • 
• 对于主问题的拉格朗日函数：
  • 
  • 拉格朗日的对偶函数 dual function：

    • \[\Gamma(\lambda, \mu) = inf_{x\in \mathbb{D}}\ L(x,\lambda, \mu) = inf_{x\in \mathbb{D}}(f(x)+\sum_{i=1}^m \lambda_i h_i(x) +\sum_{j=1}^n \mu_j g_j(x)) \]

• 
  • \(\mu \succeq 0\)：表示μ的分量均非负。
  • 约束 \(h_i(x)=0\)，所以第一项为0。
  • KKT conditions，第二项也是为0。
• 
  • 由于L中后面两项小于等于0，所以可行域中的L值小于f值。
  • 对偶函数给出了主问题最优值的下界。
• 对偶问题：基于对偶函数能获得的最好下界是什么？
  • \(max_{\lambda,\ \mu}\ \Gamma(\lambda, \mu)\ s.t.\ \mu \succeq 0\)
  • dual variable：对偶变量，\(\mu, \lambda\)。
  • 无论主问题的凸性如何，对偶问题始终是凸优化问题（concave）。
• 对偶问题最优值为d*。
  • 弱对偶性 weak duality： \(d^* \leq q^*\)
  • 强对偶性 strong duality： \(d^*=p^*\)
    • 此时由对偶问题能获得主问题的最有下界。
    • 如果主问题为凸优化问题，f(x) 和 g(x)均为凸函数，h(x)为仿射函数，且其可行域中至少有一点使不等式约束严格成立，则此时强对偶性成立。
    • 

Example

Dual is the "Transpose" of Primal

• 
• 
  • 标准形式的primal and dual problem (standard form).
• 如果原问题是min，可以先转换成max。这样找dual problem就简单多了。

Complementary Slackness

• 在standard form of primal dual problem，原问题的constraint是小于等于号，对偶问题是大于等于。
• 可以通过加入slack variables, excess variables将其变为等号。
• 
• Complementary Slackness Theorem
  • 
  • 可行解是最优，当且仅当Dual可行解与slack variables的乘积, Primal可行解与excess variables乘积为0。
• 如果知道了对偶问题的最优解，可以用Complementary Slackness来找原问题的最优解。
  • 

Strong Duality Theorem

什么是仿射函数

• Affine Function.
• 仿射函数，即最高次数为1的多项式函数。常数项为零的仿射函数称为线性函数。

Reference

• 《Pricing Communication Networks》，Appendix A中Lagrange Method for Constrained Optimization.
• 如何理解拉格朗日乘子法？ - 马同学的回答 - 知乎 https://www.zhihu.com/question/38586401/answer/457058079
• 《机器学习》周志华 附录
• https://www.youtube.com/watch?v=lSM_TQehx00&list=PLerojHoghhwtjYmOh8AwmMu5JJ6cGuq_u&index=3&t=246s
• complementary Slackness