非线性规划的基本概念

关于非线性规划的基本概念

在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。

非线性规划是运筹学的重要分支之一。最近30多年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。

一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。第2页,共78页，星期六，2024年，5月非线性规划问题举例例一：选址问题设有个市场，第个市场位置为，它对某种货物的需要量为。现计划建立个仓库，第个仓库的存储容量为试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。设第个仓库的位置为第个仓库到第个市场的货物供应量为则第个仓库到第个市场的距离为第3页,共78页，星期六，2024年，5月目标函数为约束条件为

（1）每个仓库向各市场提供的货物量之和不能超过它的存储容量。

（2）每个市场从各仓库得到的货物量之和应等于它的需要量。（3）运输量不能为负数第4页,共78页，星期六，2024年，5月例2.木梁设计问题把圆形木材加工成矩形横截面的木梁，要求木梁高度不超过，横截面的惯性矩（高度的平方宽度）不小于，而且高度介于宽度与4倍宽度之间。问如何确定木梁尺寸可使木梁成本最小.设矩形横截面的高度为，宽度为，则圆形木材的半径而木梁长度无法改变，因此成本只与圆形木材的横截面积有关。第5页,共78页，星期六，2024年，5月目标函数为约束条件为

第6页,共78页，星期六，2024年，5月（1）数学规划模型的一般形式：其中,简记为MP(MathematicalProgramming)2非线性规划问题的数学模型第7页,共78页，星期六，2024年，5月（2）简记形式：引入向量函数符号：第8页,共78页，星期六，2024年，5月（3）数学规划问题的分类：

若为线性函数，即为线性规划(LP)；

若至少一个为非线性,

即为非线性规划(NLP)；

对于非线性规划，若没有,即X=Rn,称为

无约束非线性规划或无约束最优化问题；否则称为约束非线性规划或约束最优化问题。第9页,共78页，星期六，2024年，5月（4）可行域和可行解：称为MP问题的约束集或可行域。若x在X内，称x为MP的可行解或者可行点。第10页,共78页，星期六，2024年，5月（5）最优解和极小点对于非线性规划（MP），若，并且有如果有定义:第11页,共78页，星期六，2024年，5月如果有定义则称x*是(MP)的局部最优解或局部极小解,第12页,共78页，星期六，2024年，5月

例1：用图解法求解

minf(x)=(x1－2)2+(x2－2)2s.t.h(x)=x1+x2-6=0x1x20662233最优解

x*=(3，3)T可行解

x

=(1.5，4.5)T最优级解即为最小圆的半径：f(x)=(x1－2)2+(x2－2)2=23非线性规划问题的图解法

对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。第13页,共78页，星期六，2024年，5月x1x206622D可行域最优解

x*=(2，2)T

例2：用图解法求解

minf(x)=(x1-2)2+(x2-2)2s.t.h(x)=x1+x2-6≤03非线性规划问题的图解法最优级解即为最小圆的半径：f(x)=(x1-2)2+(x2-2)2=0第14页,共78页，星期六，2024年，5月解：①先画出等式约束曲线的图形——抛物线，例3：用图解法求解②再画出不等式约束区域，

③最后画出目标函数等值线，

所以最优解x*=(4,1),最优值minf(x)=4.第15页,共78页，星期六，2024年，5月4梯度、Hesse矩阵、Jacobi阵(1)二次函数一般形式:矩阵形式:二次型:矩阵A的正定性:正定、半正定、负定、不定。其中A＝AT。二次型的正定性:正定、半正定、负定、不定。第16页,共78页，星期六，2024年，5月（2）梯度

定义：f(x)是定义在En上的可微函数。f(x)的n个偏导数为分量的向量称为f(x)的梯度.

性质：设f(x)在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质：

性质一函数在某点的梯度不为零，则该梯度方向必与过该点的等值面垂直;

性质二梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向）。第17页,共78页，星期六，2024年，5月解：由于例：试求目标函数在点x=[0,1]T

处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。

则函数在x=[0,1]T

处的最速下降方向是这个方向上的单位向量是：第18页,共78页，星期六，2024年，5月解：由于例：试求目标函数在点x=[0,1]T

处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。新点是：函数值：第19页,共78页，星期六，2024年，5月几个常用的梯度公式：第20页,共78页，星期六，2024年，5月（3）Hesse矩阵多元函数f(x)关于x的二阶导数，称为f(x)的Hesse矩阵.当f(x)的所有二阶偏导数连续时,即Hesse矩阵是对称的.时，第21页,共78页，星期六，2024年，5月几个常用Hessian公式：第22页,共78页，星期六，2024年，5月（4）Jacobi矩阵向量变量值函数：向量值函数g(x)在点x0处的Jacobi矩阵向量变量值函数的导数：第23页,共78页，星期六，2024年，5月(1)凸函数：定义5凸函数和凸规划第24页,共78页，星期六，2024年，5月例：正定二次函数其中A是正定矩阵，f(x)是凸函数。参见P104例。第25页,共78页，星期六，2024年，5月性质1:（2）凸函数的性质性质2:是凸集。证明:略.第26页,共78页，星期六，2024年，5月定理1：（一阶条件）n=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。

（3）凸函数的判定第27页,共78页，星期六，2024年，5月定理2：（二阶条件）第28页,共78页，星期六，2024年，5月（4）凸规划的定义及其性质：凸规划定义：第29页,共78页，星期六，2024年，5月凸规划性质：凸规划的任一局部最优解都是它的整体最优解。

凸规划是以后重点讨论的一类非线性规划凸函数线性函数第30页,共78页，星期六，2024年，5月（1）微分学方法的局限性：

实际的问题中，函数可能是不连续或者不可微的。

需要解复杂的方程组，而方程组到目前仍没有有效的算法。

实际的问题可能含有不等式约束，微分学方法不易处理。6非线性规划方法概述第31页,共78页，星期六，2024年，5月（2）数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列{xk}{xk}的最后一点为最优解{xk}有限{xk}无限{xk}收敛于最优解第32页,共78页，星期六，2024年，5月迭代格式xkxk+1pk称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。产生tk和pk的不同方法，形成了不同的算法。第33页,共78页，星期六，2024年，5月定义：特殊搜索方向——下降方向第34页,共78页，星期六，2024年，5月定义：特殊搜索方向——可行下降方向解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到下降，同时还是可行方向。这样的方向称为可行下降方向。第35页,共78页，星期六，2024年，5月定义：算法收敛、下降迭代算法集合S上的迭代算法：（1）初始点；（2）按照某种搜索方向pk产生下一个迭代点（i）如果点列收敛于最优解，则称此算法收敛。（ii）如果，则称此算法为下降迭代算法。...第36页,共78页，星期六，2024年，5月（3）下降迭代算法步骤（1）给出初始点，令；（2）按照某种规则确定下降搜索方向；（3）按照某种规则确定搜索步长，使得；（4）令，；（5）判断是否满足停止条件。是则停止，否则转第2步。搜索步长确定方法：称为最优步长，且有对

k的梯度第37页,共78页，星期六，2024年，5月（4）终止条件②④①③第38页,共78页，星期六，2024年，5月（5）常用的收敛性判别准则:（１）点收敛准则:(可取Rn中任一种模)。e£--)1()(kkxx·（２）目标函数值准则：（绝对差）。e£--)()()1()(kkffxx（３）目标函数值准则：（相对差）。e£--)()()()()1()(kkkfffxxx取其中之一,也可同时取(1)与(2);(1)与(3);或(1),(2)和(3)等。第39页,共78页，星期六，2024年，5月（6）算法的收敛速度则称的收敛阶为。设算法所得的点列为，如果1.线性收敛（当k充分大时）：2.超线性收敛：3.二阶收敛：（*）式中

=2时成立。（*）第40页,共78页，星期六，2024年，5月

单变量(一维)最优化一维最优化问题进退法黄金分割法抛物线搜索法三次插值法第41页,共78页，星期六，2024年，5月下降迭代算法中最优步长的确定..一维最优化问题：解析的方法（极值点的必要条件）一、一维最优化问题第42页,共78页，星期六，2024年，5月1.单峰函数定义：设是区间上的一元函数，是在上的极小点，且对任意的有（a）当时，（b）当.....则称是单峰函数。..第43页,共78页，星期六，2024年，5月性质：通过计算区间[a,b]内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理

设是区间上的一元函数，是在上的极小点。任取点则有（1）如果，则（2）如果则.....第44页,共78页，星期六，2024年，5月2搜索法求解：或基本过程：

给出[a,b],使得x*在[a,b]中。[a,b]称为搜索区间。

迭代缩短[a,b]的长度。

当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。第45页,共78页，星期六，2024年，5月二．进退法思想从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。进退法的计算步骤如何确定包含极小点的一个区间？第46页,共78页，星期六，2024年，5月例：第47页,共78页，星期六，2024年，5月假定：已经确定了单峰区间[a,b]x1x2ababx12新搜索区间为[a,x2]新搜索区间为[x1,b]三.黄金分割法（0.618法）第48页,共78页，星期六，2024年，5月区间缩小比例的确定：区间缩短比例为(x2-a)/(b-a)缩短比例为(b-x1)/(b-a)缩短比例满足：

每次插入搜索点使得两个区间[a,x2]和[x1,b]相等；

每次迭代都以相等的比例缩小区间。0.618法x1x2ababx1x2第49页,共78页，星期六，2024年，5月黄金分割法的计算公式的推导：第50页,共78页，星期六，2024年，5月第51页,共78页，星期六，2024年，5月通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。同理可得。第52页,共78页，星期六，2024年，5月3.0.618法的算法步骤：第53页,共78页，星期六，2024年，5月确定[a,b],计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a)是否是停止，输出x1否以[a,x2]为新的搜索区间是停止，输出x2否以[x1,b]为新的搜索区间3.0.618法的算法框图：第54页,共78页，星期六，2024年，5月黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的其它的试探点算法：Fibonacci算法。第55页,共78页，星期六，2024年，5月例：解：t1t230t1、第一轮：t1=1.146,t2=1.854t2－0>0.5第56页,共78页，星期六，2024年，5月2、第二轮：t2=1.146,t1=0.708t2－0=1.146>0.53、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.1460tt2t1第57页,共78页，星期六，2024年，5月4、第四轮：t2=0.876=(1.146-0.438),t1=0.708b-t1=1.146-0.708<0.5输出：t*=t2=0.876为最优解，最优值为-0.079801.146tt1t2第58页,共78页，星期六，2024年，5月四．Fibonacci法

此法类似于0.618法，也是用于单峰函数。其计算过程也与0.618类似，第1次迭代计算两个试探点，以后每次迭代只需新加一点，另一试探点取自上次的迭代点。此法与0.618法的主要差别为：区间长度的缩短比率不是常数，而是由Fibonacci数确定；给出精度后，迭代次数可预先确定；适合于参数只能取整数值的情况。

定义称满足条件（i）F0=F1=1；（ii）的数列{Fn}为Fibonacci数列。第59页,共78页，星期六，2024年，5月由定义推知Fibonacci数列的前10项为1,1,2,3,5,8,13,21,34,55,89。通过求解递推关系可求得该数列的通项为úúûùêêëéøöççèæ--øöççèæ+=++1125125151nnnF（2.3）由（2.3）式可求得。利用Fibonacci数的这一特点，用法中的0.618，再梢加改进，便是Fibonacci法。618.01»-nnFF618.01代替nnFF-在Fibonacci法中，第n次迭代的搜索区间的长度（记为）是上一次区间长度的倍第60页,共78页，星期六，2024年，5月所以要使在第n次迭代时搜索区间的长度不超过ε，只需£01LFnε

（2.4）

即可。因

是已知值，所以给出精度ε后利用（2.4）式可求得迭代次数。Fibonacc法在迭代中计算试探点的公式为即有第61页,共78页，星期六，2024年，5月Fibonacci法(1)对初始区间和精度ε>0，求目标函数值的计算次数n，使置辨别常数δ>0。计算试探点计算函数值和。置k=1。（2）若，则转（3）；若，则转（4）。第62页,共78页，星期六，2024年，5月（3）

（5）置k﹕=k+1，转（2）。（4）

（6）

第63页,共78页，星期六，2024年，5月思想在极小点附近，用二次三项式四.抛物线（二次）插值即“两头大中间小”第64页,共78页，星期六，2024年，5月如何计算函数令x=33221123322221111111121fxfxfxxfxfxf-第65页,共78页，星期六，2024年，5月抛物线插值算法步骤：解出第66页,共78页，星期六，2024年，5月思路：五.三次插值法第67页,共78页，星期六，2024年，5月设令则有第68页,共78页，星期六，2024年，5月求解满足的极小点令而解方程（3），有两种情况：由（2）可知第69页,共78页，星期六，2024年，5月第70页,共78页，星期六，2024年，5月极小点的计算公式：令第71页,共78页，星期六，2024年，5月算法步骤：第72页,共78页，星期六，2024年，5月第73页,共78