最优化方法约束非线性最优化方法

1、第 四 章约束最优化方法问题 min f(x) s.t. g(x) 0 h(x)=0 约束集 S=x|g(x) 0 , h(x)=0 (fgh)1 高等数学中所学的条件极值：一、等式约束性问题的最优性条件： 考虑 min f(x) s.t. h(x)=0 问题: 在(x,y)=0的条件下, 求z=f(x,y)极值. min f(x,y)。 s.t. (x,y)=0 引入Lagrange乘子： Lagrange函数 L(x, y;)= f(x,y)+ (x,y)2一、等式约束性问题的最优性条件： (续) 若(x*,y*)是条件极值，则存在* ，使 fx(x*,y*)+ * x (x*,y*) =

2、0 fy(x*,y*)+ * y(x*,y*) =0 (x*,y*)=0 推广到多元情况，可得到对于(fh)的情况： min f(x) s.t. hj(x)=0 j=1,2, ,l 若x*是(fh)的l.opt. ,则存在* Rl使 以及 hj(x)=0， j=1,2, ,l3一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况： 最优性条件即：-f( ) h( )h(x)f(x*)h(x*)这里 x* -l.opt. f(x*)与h(x*) 共线，而非l.opt.f( )与h( )不共线。4一 等式约束下的拉格朗日乘子算法考虑等式约束问题:令拉格朗日函数: 则等式约

3、束下规划问题转化成无约束问题: min L(X, )该问题有极值点的必要条件为:5充分条件: 如果 且行列式方程:所有根Zj0(j=1,2,n-l)，则X*为局部极小点；反之所有Zj0，为局部极大点；有正有负非极值点6例题4-1用拉格朗日乘子算法求解: 解: 令 极大点的必要条件:对于得到的三个根。使用充分条件检验如下：7计算:展开z的(n-l)=(2-1)=1次多项式方程，得8一个信息处理技术中重要的例子求最优隶属度函数）背景介绍聚类分析）目标函数符号说明构造拉日函数：最优化的一阶必要条件为 代回上式进入到约束条件：得所以9FCM的中心迭代过程102)不等式约束问题的Khun-Tucker条

4、件： 考虑问题 min f(x) s.t. gi(x) 0 i=1,2, ,m 设 x*S=x|gi(x) 0 i=1,2, ,m , 并令 I=i| gi(x*) =0， i=1,2, ,m 称I为 x*点处的起作用集（紧约束集）。 如果x*是l.opt. ,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：g2(x)=0 x*g1(x)=0g1(x*)=0, g1为起作用约束，约束集已知时回归到含等式优化问题问题:事先并不知道约束集？11 定理（任意情况的最优性必要条件）：（K-T条件） 问题(fg), 设=x|gi(x) 0，,x*,I为x*点处的起作用集，设f, gi(x)

5、 ,i I在x*点可微， gi(x) ,i I在x*点连续。 向量组gi(x*), i I线性无关。构造拉日函数： 如果x*-l.opt. 那么， u*i0, 使得）驻点条件：）互补条件：）非负条件：）不等式约束：）等式约束：说明：）如果是max问题等，要改变叙述。）在一定条件下上面叙述变成充要条件。12二阶充分条件设拉格朗日函数为为非线性规划的严格局部极小点的充分条件：）为-点；）拉日函数的海瑟矩阵在方向正定，并且 方向满足下列等式：13例求解不等式约束问题的K-T点，并判断是否为局部极小解：）K-条件：考虑两种情况：）局部最小判别：看课本143罚函数法（外点法）15例题用外点法求解解：都是不等式约束。定义外部罚函数解法一可行域不可行域16解法二迭代法173.内点罚函数法与外点法对应，但只适合不等式约束问题183.闸函数法：（续）因此，求解下列序贯无约束规划问题例题用内点法求解解：构造罚函数： 1）微分法：解得 让，得194.罚