专题六--非线性规划介绍及其matlab求解方法.ppt

非线性规划
y
引言
如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题。
与线性规划一样,非线性规划也是运筹学的一个重要分支,于 20 世纪 50 年代开始逐步形成,到20 世纪 70 年代开始处于兴旺发展时期。随着计算机技术的日益发展,很多领域越来越重视这门学科,应用非线性规划方法进行设计、管理等,非线性规划理论自身也得到了进一步的发展。
与线性规划问题不同,非线性规划问题可以有约束条件,也可以没有约束条件。但无论如何,非线性规划总可以用如下的一般形式来描述:
min f(X)
. gi(X)  0,i = 1, …, m ()
hj(X) = 0,j = 1, …, l
其中 X = (x1, x2, …, xn)Rn,f,g,h是定义在 Rn 上的实值函数。
非线性规划问题的求解
尽管非线性规划也有相当丰富的求解方法,但远不如线性规划那样具有高效、通用的解法。一般来说,求解非线性规划问题要比求解线性规划问题困难的多,目前还没有适合于各种问题的一般算法,各个算法都有一定的局限性。
众所周知:如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到),且求出的是全局最优解。
但是非线性规划却没有这样好的性质,其最优解(如果最优解存在)可能在可行域的任意一点达到,而一般非线性规划算法给出的也只能是局部最优解,不能保证是全局最优解。
非线性规划模型中的约束条件通常是不等式形式,古典的 Lagrange 乘数法是不适用的。这也是非线性规划区别于古典极值问题的地方,同时也是求非线性规划最优解时产生困难的原因。因此,对于非线性规划问题,一般都是采用迭代的方法求解。
迭代方法的基本思想
从一个选定的初始点 x0Rn 出发,按照某一特定的迭代规则产生一个点列{xk},使得当{xk} 是有穷点列时,其最后一个点是非线性规划的最优解;当{xk} 是无穷点列时,它有极限点,并且其极限点是非线性规划的最优解。
迭代法一般步骤
注意:数值求解最优化问题的计算效率取决于确定搜索方向P (k)和步长的效率。
使用迭代方法求解非线性规划的关键在于,如何构造每一轮的搜索方向和确定适当的步长。
根据上述迭代思想,可以设计出许多相应的具体算法。例如,求解无约束非线性规划问题有:最速下降法、共轭梯度法、牛顿法、拟牛顿法等等;求解约束非线性规划问题有:可行方向法、惩罚函数法、复形法等等。
最简单的优化模型
———函数的极值
一元函数的极值