第八篇:拉格朗日对偶性

拉格朗日对偶性

  在约束最优化问题中,拉格朗日对偶性(Lagrange duality)可以将原始问题转换为对偶问题,然后通过求解对偶问题的解得到原始问题的解。

原始问题

约束最优化问题

  假设$f(x),c_i(x),hj(x)$是定义在$R^n$上的连续可微函数,则约束最优化问题的原始问题为
$$
\begin{align}
& \underbrace{min}
{x\in{R^n}}f(x) \
& s.t. \, c_i(x)\leq0,\quad{i=1,2,\cdots,k} \
& hj(x)=0,\quad{j=1,2,\cdots,l}
\end{align}
$$
  如果不考虑约束条件,约束问题就是
$$
\underbrace{min}
{x\in{R^n}}f(x)
$$
  因为已经假设$f(x),c_i(x),h_j(x)$连续可微,直接对$f(x)$求导取0,即可求出最优解,但是这里有约束条件,因此得想办法去掉约束条件,而拉格朗日函数正是干这个的。

广义拉格朗日函数

  为了解决上述原始问题,引入广义拉格朗日函数(generalized Lagrange function)
$$
L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ici(x)+\sum{j=1}^l\beta_jh_j(x)
$$
其中$x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T\in{R^n}$,$\alpha_i\geq0,\beta_j$是拉格朗日乘子。

  如果把$L(x,\alpha,\beta)$看作是关于$\alpha_i,\betaj$的函数,求其最大值,即
$$
\underbrace{max}
{\alpha,\beta}L(x,\alpha,\beta)
$$
  由于$\alpha_i,\beta_j$作为拉格朗日乘子已经可知,因此可以把$L(x,\alpha,\beta)$看作是关于$x$的函数
$$
\thetaP(x)=\underbrace{max}{\alpha,\beta}L(x,\alpha,\beta)
$$
其中下标$P$表示原始问题。

约束条件的考虑

联系管理员微信tutu19192010,注册账号

上一篇
下一篇
Copyright © 2022 Egon的技术星球 egonlin.com 版权所有 帮助IT小伙伴学到真正的技术