外点法求约束最优化问题

数学规划课程设计题目外点法求约束最优化问题姓名学号成绩-1-摘要罚函数是应用最广泛的一种求解式的数值解法，基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。（这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给予很大的目标函数值，迫使这一系列无约束问题的极小值或者无限地向可行解（域）逼近，或者一直保持在可行集（域）内移动，直到收敛于原来约束问题的极小值点。）本文.......外点法可用于求解不等式约束优化问题，又可用于求解等式约束优化问题，主要特点是惩罚函数定义在可行域的外部，从而在求解系列无约束优化问题的过程中，从可行域外部逐渐逼近原约束优化问题最优解。关键词：罚函数法、约束最优化问题、外点法-2-一、预备知识（基本理论）看下是否还有定理、定义等等，可以加一些外点惩罚函数法的一般形式考虑不等式约束优化设计时：对),2,1(,0)(..),(minmuXgtsRxXfun构造一般形式的外点惩罚函数为：21})(,0{min)(),(muukkXgrXfrXP其中：（1）当满足所有约束条件时惩罚项为0，即0)(,0min21muukXgr（2）当X违反某一约束条件，即0)(Xgu时0)()(,0min221XgrXgrukmuuk表明X在可行域外，惩罚项起作用，且若X离开约束边界越远，惩罚力度越大。这样用惩罚的方法迫使迭代点回到可行域。（3）惩罚因子kr是一递增的正数数列，即krrrr210且kkrlim一般1kr考虑等式约束的优化问题：),,2,1(0)(...),(minpvXhtsRXXfvn构造外点罚函数：pvvkkXhrXfrXP12)()(),(同样，若X满足所有等式约束则惩罚项为0；若不能满足，则0)(2pqvvkXhr且随着惩罚因子的增大而增大；-3-综合等式约束和不等式约束情况，可以得到一般约束优化问题的外点罚函数公式为：mupvvukkXhXgrXfrXp1212)())(,0min()(),(实际计算中，因为惩罚因子kr不可能达到无穷大，故所得的最优点也不可能收敛到原问题的最优点，而是落在它的外面，显然，这就不能严格满足约束条件。为了克服外点惩罚函数法的这一缺点，对那些必须严格满足的约束（如强度、刚度等性能约束）引入约束裕度u，即将这些约束边界向可行域内紧缩，移动一个微量，得到),,2,1(0)()(muXgXguuu这样用重新定义的约束函数来构造惩罚函数，得到最优设计方案。外点惩罚函数法的迭代步骤：1.给定初始点0X，初始惩罚因子1r，维数n迭代精度和递增系数1C；2.构造外点惩罚函数),(kkrXP；3.选用无约束优化方法来求解惩罚函数极小点，即，),(min),(kkkrXPrXP4.检验是否满足迭代终止条件1kkXX或)()(1kkXfXf若满足转6，若不满足转5；5.令1krrCk，转2；6.输出最优解，迭代终止。二、解问题1问题重述用外点法求解约束最优化问题1..)2min(212221xxtsxx2问题求解解：构造罚函数221211,0min),(xxMxxMX用解析法求解1,0min222111xxMxx-4-1,0min242122xxMxx021xx即，0)1(240)1(22212211xxMxxxMxMMxMMx3232221),min(KMX的解为KKKKMMMMY32,322当KM时，)31,32(*x，32)2min(2221xx即解为:32)2min(2221xx程序解法：利用MATLAB编写程序如下：m=zeros(1,50);a=zeros(1,50);b=zeros(1,50);f0=zeros(1,50);%ab为最优点坐标，f0为最优点函数值，f1f2最优点梯度。symsx1x2e;%e为罚因子。m(1)=1;c=10;a(1)=0;b(1)=0;%c为递增系数。赋初值。f=x1^2+2*x2^2+e*(1-x1-x2)^2;f0(1)=1;fx1=diff(f,'x1');fx2=diff(f,'x2');fx1x1=diff(fx1,'x1');fx1x2=diff(fx1,'x2');fx2x1=diff(fx2,'x1');fx2x2=diff(fx2,'x2');%求偏导、海森元素。fork=1:100%外点法e迭代循环.-5-x1=a(k);x2=b(k);e=m(k);forn=1:100%梯度法求最优值。f1=subs(fx1);%求解梯度值和海森矩阵f2=subs(fx2);f11=subs(fx1x1);f12=subs(fx1x2);f21=subs(fx2x1);f22=subs(fx2x2);if(double(sqrt(f1^2+f2^2))=0.001)%最优值收敛条件a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f));break;elseX=[x1x2]'-inv([f11f12;f21f22])*[f1f2]';x1=X(1,1);x2=X(2,1);endendif(double(sqrt((a(k+1)-a(k))^2+(b(k+1)-b(k))^2))=0.001)&&(double(abs((f0(k+1)-f0(k))/f0(k)))=0.001)%罚因子迭代收敛条件a(k+1)%输出最优点坐标，罚因子迭代次数，最优值b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend-6-得结果：ans=0.6666ans=0.3333k=5ans=0.6666即min()的最优结果为0.6666写一些总结性内容三、参考文献[1]范玉妹，徐尔，赵金玲，胡毅庆.数学规划及其应用[M].北京：冶金工业出版社，2009[2]姜启源，谢金星，叶俊.数学建模[M].北京：高等教育出版社，2003[3][沙特]M.H.Alsuwaiyel.算法设计技巧与分析[M].北京：电子工业出版社，2009[4]刘卫国.MATLAB程序设计及其应用[M].北京：高等教育出版社，2006[6]唐加福,汪定伟,许宝栋,李露.基于评价函数的遗传算法求解非线性规划问题[J].控制与决策学报，2000(5)