非线性约束优化

非线性约束优化第一页，共二十页，2022年，8月28日

高等数学中所学的条件极值：一、等式约束性问题的最优性条件：考虑minf(x)

s.t.h(x)=0

问题:在ф(x,y)=0的条件下,求z=f(x,y)极值.minf(x,y)。s.t.ф(x,y)=0

引入Lagrange乘子：λ

Lagrange函数L(x,y;λ)=f(x,y)+λф(x,y)第二页，共二十页，2022年，8月28日一、等式约束性问题的最优性条件：(续)

若(x*,y*)是条件极值，则存在λ*

，使

fx(x*,y*)+λ*фx(x*,y*)=0

fy(x*,y*)+λ*фy(x*,y*)=0

Ф(x*,y*)=0

推广到多元情况，可得到对于(fh)的情况：

minf(x)

s.t.hj(x)=0j=1,2,…,l

若x*是(fh)的l.opt.,则存在*∈Rl使以及hj(x)=0，j=1,2,…,l第三页，共二十页，2022年，8月28日一、等式约束性问题的最优性条件：(续)

几何意义是明显的：考虑一个约束的情况：

最优性条件即：-▽f(ㄡ

)ㄡ

▽h(ㄡ)h(x)－▽f(x*)▽h(x*)这里x*---l.opt.▽f(x*)与▽h(x*)共线，而ㄡ非l.opt.▽f(ㄡ)与▽h(ㄡ)不共线。第四页，共二十页，2022年，8月28日一等式约束下的拉格朗日乘子算法考虑等式约束问题:令拉格朗日函数:

则等式约束下规划问题转化成无约束问题:minL(X,)该问题有极值点的必要条件为:第五页，共二十页，2022年，8月28日充分条件:

如果且行列式方程:所有根Zj>0(j=1,2,…,n-l)，则X*为局部极小点；反之所有Zj<0，为局部极大点；有正有负非极值点第六页，共二十页，2022年，8月28日例题4-1用拉格朗日乘子算法求解:

解:

令极大点的必要条件:对于得到的三个根。使用充分条件检验如下：第七页，共二十页，2022年，8月28日计算:展开z的(n-l)=(2-1)=1次多项式方程，得第八页，共二十页，2022年，8月28日一个信息处理技术中重要的例子－求最优隶属度函数１）背景介绍－聚类分析２）目标函数－符号说明构造拉日函数：最优化的一阶必要条件为

代回上式进入到约束条件：得所以第九页，共二十页，2022年，8月28日FCM的中心迭代过程第十页，共二十页，2022年，8月28日2)不等式约束问题的Khun-Tucker条件：

考虑问题

minf(x)

s.t.

gi(x)

0i=1,2,…,m

设x*∈S={x|gi(x)

0i=1,2,…,m},并令

I={i|gi(x*)=0，i=1,2,…,m}

称I为x*点处的起作用集（紧约束集）。如果x*是l.opt.,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：g2(x)=0x*g1(x)=0g1(x*)=0,g1为起作用约束，约束集已知时回归到含等式优化问题问题:事先并不知道约束集＝？第十一页，共二十页，2022年，8月28日

定理（任意情况的最优性必要条件）：（K-T条件）问题(fg),设Ｄ={x|gi(x)

0，},

x*∈Ｄ,

I为x*点处的起作用集，设f,gi(x),i∈I在x*点可微，gi(x),iI在x*点连续。向量组{▽gi(x*),i∈I}线性无关。构造拉日函数：如果x*----l.opt.那么，u*i≥0,使得１）驻点条件：２）互补条件：３）非负条件：４）不等式约束：５）等式约束：

说明：１）如果是max问题等，要改变叙述。２）在一定条件下上面叙述变成充要条件。第十二页，共二十页，2022年，8月28日２．二阶充分条件设拉格朗日函数为为非线性规划的严格局部极小点的充分条件：１）为Ｋ－Ｔ点；２）拉日函数的海瑟矩阵在Ｙ方向正定，并且Ｙ方向满足下列等式：第十三页，共二十页，2022年，8月28日例４２求解不等式约束问题的K-T点，并判断是否为局部极小解：

１）ｋ－Ｔ条件：考虑两种情况：２）局部最小判别：自行看课本第十四页，共二十页，2022年，8月28日3．罚函数法（外点法）第十五页，共二十页，2022年，8月28日例题４－３用外点法求解解：都是不等式约束。定义外部罚函数１．解法一可行域不可行域第十六页，共二十页，2022年，8月28日解法二迭代法第十七页，共二十页，2022年，8月28日

3.内点罚函数法与外点法对应，但只适合不等式约束问题第十八页，共二十页，2022年，8月28日3.闸函数法：（续）因此，求解下列序贯无约束规划问题例题用内点法求解解：构造罚函数：1）微分法：解得让，得第十九页，共二十页，2022年，8