非线性规划问题的求解方法

一、非线性规划问题的几种求解方法1. 罚函数法（外点法） 基本思想：利用目标函数和约束函数构造辅助函数： 要求构造的函数 具有这样的性质：当点 x位于可行域以外时， 取值很大，而离可行域越远则越大；当点在可行域内时，函数 因此可以将前面的有约束规划问题转换为下列无约束规划模型： 其中称为 罚项， 称为罚因子， 称为罚函数。的定义一般如下：函数 一般定义如下：算法步骤如何 将此算法模块化 :求解非线性规划模型例子罚项函数：无约束规划目标函数：global lamada%主程序 main2.m,罚函数方法x0=1 1; lamada=2;c=10; e=1e-5;k=1;while lamada*fun2p(x0)=ex0=fminsearch(fun2min,x0);lamada=c*lamada;k=k+1;enddisp(最优解 ),disp(x0)disp(k=),disp(k) 程序 1： 主程序 main2.m程序 2：计算 的函数 fun2p.mfunction r=fun2p(x)%罚项函数r=(x(1)-1)3-x(2)*x(2)2; 程序 3：辅助函数程序 fun2min.mfunction r=fun2min(x)%辅助函数global lamadar=x(1)2+x(2)2+lamada*fun2p(x);运行输出：最优解1.00012815099165 -0.00000145071779k=33 练习题： 1、用外点法求解下列模型 2、将例子程序改写为一个较为 通用的罚函数法程序 。（考虑要提供哪些参数） 2. 内点法（障碍函数法）仅适合于 不等式约束的最优化问题其中都是连续函数，将模型的定义域记为构造辅助函数为了保持迭代点含于可行域内部，我们定义障碍函数 3. 问题转化为一个无约束规划由于 很小，则函数 取值接近于f(x)， 所以原问题可以归结为如下规划问题的近似解： 练习题：请用内点法算法求解下列问题： 小结q讲解了两个 求解有约束非线性最小化规划特点：q易于实现，方法简单；q没有用到目标函数的导数q问题的转化技巧（近似为一个无约束规划）4、其它求解算法（ 1）间接法（ 2）直接法 q直接搜索法q以梯度法为基础的 间接法q无约束规划的 Matlab求解函数q数学建模案例分析（ 截断切割 ， 飞机排队）（ 1）间接法在非线性最优化问题当中，如果目标函数能以解析函数表示，可行域由不等式约束确定，则可以利用目标函数和可行域的已知性质，在理论上推导出目标函数为最优值的必要条件，这种方法就称为 间接法 （也称为解析法 ） 。一般要用到目标函数的导数。（ 2）直接法直接法 是一种数值方法这种方法的基本思想是 迭代 ，通过迭代产生一个点序列 X(k) ， 使之逐步接近最优点。 只用到 目标函数 。如黄金分割法、 Fibonacci、 随机搜索法。（ 3）迭代法一般步骤注意： 数值求解最优化问题的计算效率取决于确定搜索方向 P (k)和步长 的效率。 最速下降法（ steepest descent method）由法国数学家 Cauchy于 1847年首先提出。在每次迭代中，沿最速下降方向（ 负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为 最优梯度法 。 特点：方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢；越是接近极值点，收敛越慢；它是其它许多无约束、有约束最优化方法的基础。该法一般用于最优化开始的几步搜索。 以梯度法为基础的最优化方法求 f(x)在 En中的极小点 思想：q方向导数是反映函数值沿某一方向的变化率问题 q方向导数沿梯度方向取得最大值基础：方向导数、梯度q通过一系列一维搜索来实现。q本方法的核心问题是选择搜索方向。q搜索方向的不同则形成不同的最优化方法。最速下降法 算法： 算法说明可通过 一维无约束搜索方法 求解例子：用最速下降法解下列问题分析：1、编写一个梯度函数程序 fun1gra.m2、 求 (可以调用函数 fminsearch )函数 fungetlamada.m3、 最速下降法主程序 main1.m初始条件第一步：计算梯度程序 fun1gra.mfunction r=fun1gra(x)%最速下降法求解示例%函数 f(x)=2*x12+x22的梯度的计算%r(1)=4*x(1);r(2)=2*x(2);第二步：求 最优的目标函数function r=fungetlamada(lamada)%关于 lamada的一元函数，求最优步长global x0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1)2+(x0(2)-lamada*d(2)2; %注意 负 号表示是 负 梯度第三步：主程序 m