《非线性约束优化》由会员分享,可在线阅读,更多相关《非线性约束优化(20页珍藏版)》请在金锄头文库上搜索。
1、第 四 章,约束最优化方法,问题 min f(x) s.t. g(x) 0 h(x)=0 约束集 S=x|g(x) 0 , h(x)=0,高等数学中所学的条件极值: 一、等式约束性问题的最优性条件: 考虑 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),一、等式约束性问题的最优性条件: (续) 若(x*,y*)是条件极值,则存在* ,使 fx(x*,y*)+ * x (x*,y*) =0 f
2、y(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, ,l,一、等式约束性问题的最优性条件: (续) 几何意义是明显的:考虑一个约束的情况: 最优性条件即:,一 等式约束下的拉格朗日乘子算法 考虑等式约束问题: 令拉格朗日函数: 则等式约束下规划问题转化成无约束问题: min L(X, ) 该问题有极值点的必要条件为:,充分条件: 如果 且行列式方程: 所有根Zj0(j=1,2,n-
3、l),则X*为局部极小点;反 之所有Zj0,为局部极大点;有正有负非极值点,例题4-1用拉格朗日乘子算法求解: 解: 令 极大点的必要条件: 对于得到的三个根。 使用充分条件检验如下:,计算: 展开z的(n-l)=(2-1)=1次多项式方程,得,一个信息处理技术中重要的例子求最优隶属度函数 )背景介绍聚类分析 )目标函数符号说明 构造拉日函数: 最优化的一阶必要条件为 代回上式进入到约束条件: 得 所以,FCM的中心迭代过程,2)不等式约束问题的Khun-Tucker条件:,考虑问题 min f(x) s.t. gi(x) 0 i=1,2, ,m 设 x*S=x|gi(x) 0 i=1,2,
4、,m , 并令 I=i| gi(x*) =0, i=1,2, ,m 称I为 x*点处的起作用集(紧约束集)。 如果x*是l.opt. ,对每一个约束函数来说,只有当它是起作用约束时,才产生影响,如:,g2(x)=0,问题: 事先并不知道约束集?,定理(任意情况的最优性必要条件):(K-T条件) 问题(fg), 设=x|gi(x) 0, , x*, I为x*点处的起作用集,设f, gi(x) ,i I在x*点可微, gi(x) ,i I在x*点连续。 向量组gi(x*), i I线性无关。 构造拉日函数: 如果x*-l.opt. 那么, u*i0, 使得 )驻点条件: )互补条件: )非负条件:
5、 )不等式约束: )等式约束: 说明: )如果是max问题等,要改变叙述。 )在一定条件下上面叙述变成充要条件。,二阶充分条件 设拉格朗日函数为 为非线性规划的严格局部极小点的充分条件: ) 为-点; ) 拉日函数的海瑟矩阵在方向正定,并且 方向满足下列等式:,例求解不等式约束问题的K-T点,并判断是否为局部极小 解: )K-条件: 考虑两种情况: )局部最小判别:看课本,3罚函数法(外点法),例题用外点法求解,解:都是不等式约束。定义外部罚函数 解法一,可行域,不可行域,解法二 迭代法,3. 内点罚函数法 与外点法对应,但只适合不等式约束问题,3. 闸函数法:(续) 因此,求解下列序贯无约束规划问题 例题 用内点法求解,解:构造罚函数: 1)微分法: 解得 让 ,得,4. 罚函数类算法与闸函数法的缺点: 1 当罚函数法(闸函数法)的 ( 0+)时, 惩罚项 + 0或0 + 形式,在计算上有困难; 2 计算一系列无约束问题,故计算量大。,