本文共 1511 字，大约阅读时间需要 5 分钟。

• 约東最优化中,常用拉格朗日对偶性将原始问题转为对偶问题
• 通过解对偶问题得到原始问题的解
• 该方法应用在许多统计学习方法
  • 最大熵模型与支持向量机

1.原始问题

• 称此为原始最优化问题或原始问题

• 首先,引进generalized Lagrange function

• ${\alpha }_i\ge 0$
• 考虑$x$的函数

• P表示原始问题

• 设给定某个$x$
• 如果$x$违反原始问题的约束
• 即存在某个$i$使$c_i(x)>0$或存在某个$j$使$h_j(w)\ne 0$,
• 就有

• 如果$x$满足约束
• 可知,
  ${\theta }_P(x)=f(x)$

• 如果考虑

• 它与(C.1)~(C.3)等价,
  • 即它们有相同的解
• $\underset{x}{\min }\underset{\alpha ,\beta ,{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )$称为广义拉格朗日函数的极小极大问题.
• 这样就把原始问题表示为
  • 广义拉格朗日函数的极小极大问题
• 定义原始问题的最优值

$$p^{\ast }=\underset{x}{\min }{\theta }_P(x)\text{\hspace{1em}(C.9)}$$

• 称原始问题的值

2.对偶问题

• 再考虑极大化${\theta }_D$,即

• 称广义拉格朗日函数的极大极小问题

• 将广义拉格朗日函数的极大极小问题表示为约束最优化问题

• 称原始问题的对偶问题.
• 定义对偶问题的最优值

• 称对偶问题的值

3.原始问题和对偶问题的关系

• 定理C.1
• 若原始问题和对偶问题都有最优值,
• 则

• 证
• (C.12)和式(C.5),对任意的$\alpha$,$\beta$和$x$,
• 有

这儿一点我没写啊

• 推论C.1
• 设$x^{\ast }$和${\alpha }^{\ast },{\beta }^{\ast }$是原始问题(C.1)~(C.3)
  • 和对偶问题(C.12)~(C.13)的可行解,
  • 且$d^{\ast }=p^{\ast }$
  • 则他们分别是原始问题和对偶问题的最优解

• 某些条件下,原始和对偶问题最优值相等,这时可用解对偶问题替代解原始问题
• 以定理形式叙述有关结论不予证明

• 定理C.2
• 考虑(C.1)-(C.3)和(C.12)-(C.13)
• 设$f(x)$和$c_i(x)$是凸,
  • $h_j(x)$是仿射函数
• 且约束$c_i(x)$严格可行,
  • 即存在$x$,对所有$i$有$c_i(x)<0$
• 则存在$x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }$,
  • 使$x^{\ast }$是原始问题的解,
  • ${\alpha }^{\ast },{\beta }^{\ast }$是对偶问题的解
• 且

• 定理C.3
• 设谁和谁是凸,谁是仿射函数,且不等式约束谁是严格可行
• 则分别是原始问题和对偶问题的解的充要条件是满足
• KKT条件

• (C.24)称为KKT的对偶互补条件.
• 由此条件可知:啥啊

转载地址：https://cyj666.blog.csdn.net/article/details/105035971 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！