用外点法求解非线性约束最优化问题

1、题目：用外点法求解非线性约束最优化问题学 院 信息管理学院 学生姓名 余 楠 学 号 专 业 数量经济学 届 别 2013 指导教师 易 伟 明 职 称 教 授 二O一三年十二月用外点法求解非线性约束最优化问题摘要约束最优化问题是一类重要的数学规划问题。本文主要研究了用外点罚函数法对约束非线性规划问题进行求解。对于一个约束非线性规划用罚函数求解的基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。本文最后利用c语言编程得到满足允许误差内的最优解。本文主要对一个约束非线性规划问题的实例，首先利用上述迭代的方法，计算出各迭代点的无约束极值问题的最优解。然后应用

2、c语言编程，得到精确地最优解，需迭代四次次才使得0.001，得到的最优解为=()。关键词：外点罚函数法 非线性规划 约束最优化 迭代最优解1、 背景描述线性规划的目标函数和约束条件都是决策变量的线性函数，但如果目标函数或约束条件中含有决策变量的非线性函数，就称为非线性规划。非线性规划与线性规划一样，也是运筹学的一个极为重要的分支，它在经济、管理、计划、统计以及军事、系统控制等方面得到越来越广泛的应用。 非线性规划模型的建立与线性规划模型的建立类似，但是非线性规划问题的求解却是至今为止的一个研究难题。虽然开发了很多求解非线性规划的算法，但是目前还没有适用于求解所有非线性规划问题的一般算法，每个方

3、法都有自己特定的适用范围。罚函数法是应用最广泛的一种求解非线性规划问题的数值解法，它的基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给予很大的目标函数值，迫使这一系列无约束问题的极小值点无限的向可行集（域）逼近，或者一直保持在可行集（域）内移动，直到收敛于原来约束问题的极小值点。外点法的经济学解释如下：若把目标函数看成“价格”，约束条件看成某种“规定”，采购人员在规定的范围内采购时价格最便宜，但若违反了规定，就要按规定加收罚款。采购人员付出的总代价应是价格和罚款的综合。采购人员的目标是使总代价最

4、小，当罚款规定的很苛刻时，违反规定支付的罚款很高。这就迫使采购人员在规定的范围内采购。数学上表现为罚因子足够大时，无约束极值问题的最优解应满足约束条件，而成为约束问题的最优解。二、基础知识2.1 约束非线性优化问题的最优条件该问题是一个约束非线性优化问题，利用外点罚函数法求解该问题，约束非线性优化问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此有以下几个定理。设具有不等式约束的极值问题：min s.t.(X)0 (*)定理1(Kuhn-Tucker条件)在(*)中假设：是局部最小值；f(X),i=1,2,m在点连续可微；(),i线性无关，则存在一组参数使得广义Lagrange

5、函数满足：对以上定理做几点说明：(1)本应是：或,即是紧约束函数在处的梯度的非负线性组合，但若规定：当时则等式可写成：(2)等价于(3)如果对所有线性无关，则称为约束的一个正则点，即如果在处起作用的约束函数的梯度是线性无关的，则是一个正则点。如果不是正则点，则K-T条件可能不成立。定理2 设是问题(*)的可行解，,是凸函数，且在可微，又有满足K-T条件，则是全局最优解。根据以上两个定理可见，对凸规划来说，K-T条件也是借的充分必要条件。然而从具体例子可以看出利用极值的必要条件和充分条件去求非线性规划问题的最优解不都是很容易的，下面介绍应用广泛的外点罚函数法的基本算法。2.2外点罚函数法的基本思

6、想它的基本思路是通过目标函数加上惩罚项，这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给与很大的目标函数值，迫使这一系列无约束问题的极小值点或者无限的向可行集逼近，或者一直保持在可行集内移动，直到收敛于原来约束问题的极小值点。先考虑不含等式约束的非线性规划问题： (1)构造一个函数： 现把，则当时，当时，即有： (2)再构造函数： 求解无约束极值问题：(3)若(3)有极小值，则由(2)可看出，这时应有，即点，因而不仅是问题(3)的最优解，同时也是原问题(1)的最优解。从而把约束极值问题(1)的求解变为无约束极值问题(3)的求解。但是，用上述方法构造的函数在处不连续，更没有导数。为了求

7、解方便，将该函数修改为：修改后的函数在处的导数等于0，而且，对任意的t都连续。当时仍有，当时有：，而可改为：或等价地：问题(3)就变为： (4)如果原规划问题(1)有最优解，则式(4)的最优解为原问题(1)的最优解或近似最优解。若,则是原问题的最优解，这是因为对任意的有：即当时有：。即使,它也会相当接近于式(1)的约束条件的边界。这是因为：若为式(4)的最优解，则在M相当大的情况下，只可能使相当小，即相当靠近约束域R的边界。函数称为罚函数，其中第二项称为惩罚项，M称为罚因子。实际计算时，总是先给定一个初始点和初始罚因子，求解无约束极值问题(4)：，若其最优解，则它已是(1)的最优解；否则，以为

8、新的起始点，加大罚因子，取，重新求解(4)。如此循环，或者存在某个，使得的最优解，即是式(1)的最优解；或者存在的一个无穷大序列：，随着M值的增大，罚函数中的惩罚项所起的作用增大，的最优解与约束域R的距离越来越近。当趋于无穷大时，最优点序列就从R的外部趋于R的边界点。即趋于原问题(1)最优解。2.3约束非线性优化问题的外点罚函数法迭代步骤 外点法的迭代步骤：第1步 选取初始点，取(可取)，给定 0，令k=1；第2步 求无约束极值问题的最优解：，其中；第3步 若对某一个有，则取，其中10，置k=k+1,转(2)；否则，迭代终止，取。由以上计算步骤可知，外点罚函数法迭代终止时，求得的是目标函数驻点

9、的一个近似点。 三、题目举例 用外点罚函数法求解约束非线性规划问题：，s.t.+设初始取为=(1,1),迭代到满足允许误差=0.001为止的解。四、问题求解3.1对原无约束非线性规划迭代 构造罚函数所以对于不满足约束条件的点，有：令：，得： 得的解为： 即 ， (*)首先进行第一次迭代给定初始点，同时取代入公式(*)得，进行第二次迭代取C=10，得代入公式(*)得，进行第三次迭代代入公式(*)得，进行第四次迭代代入公式（*）得，至此满足了精度要求，迭代终止，所得原问题的最优近似解为： 3.2对原约束非线性规划进行c语言编程求解就这样无限的迭代下去，直到为止，为此，我们可以用c语言编程得到，其算

10、法设计如下图所示：给定k：=1计算求停否是C语言源程序代码：#include stdio.hvoid fun(double a,double b,double w) double re2;re0=re1=0.0;if(a0=0.0&a1=0.0)|(a0=0.0&b0=0.0)|(b0=0.0&b1=0.0)|(a1=0.0&b1=0.0)printf(无解); return;if(a0!=0.0) if(a0*b1-a1*b0=0.0)printf(无解);re1=(a0*b2-b0*a2)/(a0*b1-a1*b0); re0=(a2-re1*a1)/a0; else re1=a2/a1;

11、 re0=(a2-a1*re1)/b0; if(1-re0-re1w);printf(x1=%f ,re0);printf(x2=%fn,re1);void main() double a13,b13,w; int m,c=1;printf(请输入初始罚因子:m=); scanf(%f,&m); printf(请输入所要到的精度:w=); scanf(%f,&c); a10=2*m;a11=4+2*m;a12=2*m; b10=2+2*m; b11=2*m; b12=2*m; fun(a1,b1,w);所得结果截屏如图所示：五、结论与展望从求解的过程中可以看出，随着罚因子的增大，在求解无约束最

12、优化问题的过程中，将迫使向可行域接近。因此，很自然的会想到：初始罚因子是否取得大一些好呢？因为这样一开始就比较接近可行域。但是理论和实践都证明了这样做是不合适的。当罚因子很大时，在惩罚函数的极小点附近，其等高线会变得十分狭长，这就意味着其最小点位于一个十分狭长的深谷之中。为了使搜索不至于太困难，不能选的过大，采取渐近的方式则情况就会得到改善。初始罚因子一般可取，这在多数情况下较为恰当。外点法不只适用于含有不等式约束条件的非线性规划，对于含有等式约束的问题也适用。外点法的另一个优点是初始点容易选择，它可以在整个n维空间中选取。外点法的缺陷是：惩罚项的二阶偏导数在R的边界上不存在，因而在选择无约束

13、最优化方法时要受到限制；另外，外点法的中间结果不是可行解，不能作为近似最优解，只有迭代到最后才能得到切合实际的可行解。在使用罚函数法的过程中，当点接近最优点时，即罚因子很大时，罚函数的性质变坏，这就是其Hesse矩阵陷入严重的病态，使搜索相当困难，严重时甚至过早停机。这就是罚函数法所固有的困难。要克服这一困难，改进方法是：可考虑把罚函数和Lagrange函数结合起来，构造一个新的增广Lagrange函数，通过求解该函数的无约束极值来获得原问题的最优解。六、参考文献1 范玉妹，徐尔等编著. 数学规划及其应用M. 冶金工业出版社,20092 黄红选等编著. 运筹学：数学规划M. 清华大学出版社,20063 李虹等编著. C语言程序设计M. 南京大学出版社,20104 包振宇，孙干等编著. C语言程序设计M. 清华大学出版社有限公司,20095 刘满凤，陶长琪，柳键等编著. 运筹学教程M. 清华大学出版社,20106 运筹学教材编写组. 运筹学第三版M. 清华大学出版社，20057