拉格朗日函数最优化问题

目的：将有约束条件的函数最优化问题通过拉格朗日函数转化为无条件的函数最优化问题。

条件极值最优化问题：

对于无条件的函数最优化问题，常用的有3种方式：

• 梯度下降：求解一阶导数，其实就是使用泰勒一阶展开逼近最优解
• L-BFGS：求解二阶导数，其实是使用泰勒二阶展开逼近
• IIS

对于有条件约束的函数最优化问题，该怎么求呢？

数学上给出了两种求解的方式，下面以求解二元函数的条件极值为例：

例：求解二元函数 f(x,y) 在 \varphi(x,y)=0 条件下的极值的方法与步骤：

方法一 化条件极值为无条件极值

第一步：从条件 \varphi(x,y)=0 中，求出y的显函数^[1]形式 y=\varphi(x) .

第二步：将 y=\varphi(x) 带入二元函数 f(x,y) 中，化为一元函数 f[x,\varphi(x)] 的无条件极值.

第三步：求出一元函数 f[x,\varphi(x)] 的无条件极值极为所求.

方法二 拉格朗日乘数法

第一步：构造拉格朗日函数 L(x,y,\lambda)=f(x,y)+\lambda\varphi(x,y)

第二步：由一阶偏导数组成方程组

L'x = 0

L'y = 0 解之即可

L'\lambda = 0

所以，拉格朗日乘数法是求条件极值的一种方法，具体过程就是将带条件的函数极值问题转化为无条件的极值问题

例：求函数 Z=x^{2}+y^{2} 在条件 2x+3y=1 下的极值

解： L(x,y,\lambda)=x^{2}+y^2+\lambda(2x+3y-1)

L'x = 2x+2y=0 ①

L'y =2x+3y= 0 ② 解得 x=\frac{2}{13} ，y=\frac{3}{13}

L'\lambda=2x+3y-1= 0 ③

拉格朗日对偶问题

原始问题

带约束条件的最优化问题泛化表示方法

\min_{x\in R^{n}}{f(x)}

c_{i}\leq0，i=1,2,...,k

h_{j}(x)=0，j=1,2,...,l

可以将约束条件表示为K个不等式约束条件和L个等式约束条件，我们命名其为原始问题（意思就是所有函数最优化问题都可以转化为求最小值问题，所有约束条件都可以转化为上面两个条件的形式，这是因为求最大值和求最小值可以相互转化，比如：求得一个极大值A，那么转化为极小值就是负A, X>0可以转化为-X<0）

拉格朗日函数

定义某原始最优化问题的拉格朗日函数为：

L(x,\alpha,\beta)=f(x)+\sum_{i=1}^{k}{\alpha_{i}c_{i}(x)}+\sum_{j=1}^{l}{\beta_{j}h_{j}(x)}

其中ci是第i个不等式约束函数(需要整理^[2])，bj是第j个等式约束函数，αi,βj叫做拉格朗日乘子

拉格朗日函数的特性

学习特性的目的是为了求解拉格朗日函数，找到最优化问题的解

极小极大问题：

令 \theta_{p}(x)=\max_{\alpha_{i}\beta_{j}\alpha_{i}\geq0}L(x,\alpha,\beta) 此处有一个约束条件：αi≥0

则 \{_{\theta_{p}(x)=maxf(x)，x满足原始约束条件}^{+\infty，其他}

所以，当满足约束条件时，对 \theta_{p}(x) 进行极小化，就相当于对原始问题的先进行最大化，然后再进行最小化

p^{*}=\min_{x}\theta_{p}(x)=\min_{x}\max_{\alpha_{i}\beta_{j}\alpha_{i}\geq0}L(x,\alpha,\beta)=\min_{x}\max_{\alpha_{i}\beta_{j}\alpha_{i}\geq0}f(x)

证明

• 先看满足约束条件的情况

若满足约束条件ci≤0，得到 αici≤0，即 L(x,\alpha,\beta) 函数中间部分 \sum_{i=1}^{k}{\alpha_{i}c_{i}(x)} ≤0

再由约束条件hj=0，可知 L(x,\alpha,\beta) 最后一部分 \sum_{j=1}^{l}{\beta_{j}h_{j}(x)} =0

此时 L(x,\alpha,\beta) 最大，就是该函数中间一部分和最后一部分为0的时刻，即f(x)最大，所以 \theta_{p}(x)=maxL(x,\alpha,\beta)=maxf(x)

• 不满足约束条件的情况

不满足原始问题的条件ci≤0时，拉格朗日函数中间部分的值为正无穷(正正得正)

不满足条件hj=0时，βj可正可负，hj可正可负，拉格朗日函数最后一部分最大时也是正无穷

极大极小问题：

定义 \theta_{D}(\alpha,\beta)=\min_{x}L(x,\alpha,\beta)

此时极大化 \theta_{D} \max_{\alpha_{i}\beta_{j}\alpha_{i}\geq0}\theta_{D}(\alpha,\beta)=\max_{\alpha_{i}\beta_{j}\alpha_{i}\geq0}\min_{x}L(x,\alpha,\beta)

称为拉格朗日函数的极大极小问题，也称为原始问题的对偶问题

设 d^{*}=\max_{\alpha_{i}\beta_{j}\alpha_{i}\geq0}\theta_{D}(\alpha,\beta) 对偶最优化问题的最优解

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

当f(x)和 c_{i} 函数为凸函数， h_{j}(x) 为仿射函数时，有

p^{*}=d^{*}=L(x^{*},\alpha^{*},\beta^{*})

构造一阶导数方程组^[3]，并结合约束条件（包含原始问题的约束条件和拉格朗日函数的约束条件）来求解，这一步也称KKT条件

L'x^{*} = 0

L'\alpha^{*} = 0

L'\beta^{*} = 0

\alpha_{i}^{*}\geq0，i=1,2,...,k 拉格朗日函数约束条件

c_{i}\leq0，i=1,2,...,k

h_{j}(x)=0，j=1,2,...,l

\alpha_{i}^{*}c_{i}(x^{*})=0， i=1,2,...,k 根据上面的约束条件和拉格朗日函数特性推倒的条件

参考

1. ^形如z=f(x,y)的是显函数，除此以外的都是隐函数
2. ^整理成A≤B的形式
3. ^参考上面求二元函数条件极值