[拉格朗日乘子法学习笔记]

一、定义

当求$n$元函数$f(x_1,x_2,..,x_n)$在$l$个约束条件$g_{i}(x_1,x_2,…,x_n)=0$下的极值时,

我们可以将原问题转化为下面的问题:

$F(x_1,x_2,…,x_n,\lambda_1,\lambda_2,…,\lambda_l)=f(x_1,x_2,…,x_n)+\Sigma_{i=1}^{l}g_{i}(x_1,x_2,…,x_n)$

待定系数$\lambda_i$被称作拉格朗日乘子。

在极值点处,有偏导$\frac{\partial F}{\partial x_i}=0$,$\frac{\partial F}{\partial \lambda_i}=0$。

于是我们有了$n+l$个方程,便可以解出极值点的坐标。

二、例题

现在有$n$个与原点距离为$r_i$的点,求这些点构成的凸包面积的最大值,$n\leq 8$。

解法一:随机每个点与坐标轴的角度,用爬山算法求解,多随机几次正确性较高,精度也不错。

解法二:拉格朗日乘子法,我们先枚举那些点在凸包上,再枚举他们的排列顺序,

那么现在的面积可表示为:$f(x_1,x_2,…,x_n)=\frac{1}{2}(r_{1}r_{2}sin(x_1)+…+r_{n}r_{1}sin(x_n))$

有约束条件:$g(x_1,x_2,…,x_n)=x_1+x_2+…+x_n-2\pi = 0$

因为函数$f$一定单峰,所以他的极值点就是最值点。

我们构造函数$F_{x_1,x_2,…,x_2,\lambda}=f(x_1,x_2,…,x_n)+\lambda g(x_1,x_2,…,x_n)$

有方程:

$\frac{\partial F}{\partial x_i}=\frac{1}{2}r_{i}r_{i+1}cos(x_i)+\lambda=0$

$\frac{\partial F}{\partial \lambda_i}=x_1+x_2+…+x_n-2\pi = 0$

因为$x_i\in[0,\pi]$,且$cos(x_i)$在定义域内单减,所以我们可以二分$\lambda$,

通过前$n$个方程算出$x_i$,当第二个等式满足时得到当前的最优解方案,代回原式算出最优解。

对于每一种点集和排列取$max$就是答案了。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注