第一章非线性规划理论（1）第一节非线性优化规划模型及其解的概念, 第二节凸函数与凸规划, 第三节下降迭代算法第四节一维搜索方法第一节非线性优化规划模型及其解的概念线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中含有自变量的非线性函数，则这样的规划问题就是非线性规划。
有些实际问题可以表示成线性规划，但有些实际问题则需要用非线性规划模型来表达。
例1 求，使得（1）该数学模型中目标函数是一个二次函数，因此它是一个非线性规划。
又如：求，使得（2）是一个非线性规划。
1.1 非线性规划问题的数学模型非线性规划数学模型的一般形式为（3）其中是维欧氏空间中的向量（点），是目标函数，为约束条件，、都是元实函数。
说明：（1）由于我们有，当需使目标函数极大化时，只需使其负值极小化即可，因而仅考虑极小化的情况不失一般性。
（2）若某约束条件是“”不等式，仅需要在约束两端乘以“－1”，即可将这个约束变为“”。
又由于约束等价于因而我们可以将非线性规划模型写成下面的形式：（4）或（5）模型中的称为非线性规划的可行域，而中的元素称为可行解。
1.2 二维问题的图解法当只有两个决策变量时，求解非线性规划也可以像线性规划那样用图解法。
例2解：先画出可行域X2ABCDO x1可行域等值线最优解画出抛物线，即图中的曲线，再画出直线，即图中的直线，得可行域。
画出等值线，图中有一条等值线与抛物线交于B点，当动点从A点出发延抛物线移动时，动点从A移向B时，目标函数值下降，动点从B移向C 时，目标函数值上升，所以在可行域范围内B点的函数值最小，所以B 点是一个极小点。
当动点由C点向D点移动时，目标函数再次下降，在D（4，1）点目标函数值最小，所以D点是最优解。
本例中，B点称为局部极小点，而D点称为全局极小点，即最小点。
1.3 非线性规划的基本概念1.3.1关局部极小和全局极小的定义设为定义在维欧氏空间的某一个区域上的元实函数，对于，如果存在某一个使得所有与距离小于的都有，则称为在上的局部极小点，而为局部极小值。
如果当时，有，则称为在上的严格局部极小点，而为严格局部极小值。
设为定义在维欧氏空间的某一个区域上的元实函数，如果存在，对于所有，都有，则称为在上的全局极小点，而为全局极小值。
如果当时，有，则称为在上的严格全局极小点，而为严格全局极小值。
若将上述的不等式反向，即可得到相应极大点和极大值的定义。
1.3.2 多元函数极值点存在的条件我们知道对于二阶可微的一元函数极值点存在的条件为必要条件：充分条件：对于极小点：且对于极大点：且对于无约束多元函数，其极值点存在的必要条件和充分条件与一元函数类似。
1、极值点存在的必要条件下面的定理1给出了元实函数在点取得极值的必要条件。
定理1 设是维欧氏空间的上的某一个开集，在上有连续的一阶偏导数，且在取得局部极值，则必有（6）或写成（7）此处（8）为在点处的梯度。
满足条件的称为的驻点或稳定点。
注：由数学分析知识可知，函数的梯度有两个重要性质：（1）函数在某点的梯度与函数过该点的等值面（或等值线）正交；（2）梯度向量的方向是函数值增加最快的方向，而负梯度向量的方向是函数值减少最快的方向。
2、二次型二次型是的二次齐次函数（9）式中，即矩阵（10）为对称矩阵。
一个二次型唯一对应一个对称矩阵，反之一个对称矩阵也唯一确定一个二次型。
若对于任意，实二次型，则称二次型是正定的，也称对称矩阵为正定的；若对于任意，实二次型，则称二次型是负定的，也称对称矩阵为负定的；若对于任意，实二次型，则称二次型是半正定的，也称对称矩阵为半正定的；若对于任意，实二次型，则称二次型是半负定的，也称对称矩阵为半负定的。
由线性代数知道，实二次型是正定（对称矩阵为正定）的充要条件是对称矩阵左上角各阶主子式都大于零，即（11）实二次型是负定（对称矩阵为负定）的充要条件是对称矩阵左上角各阶主子式负正相间，即（12）（13）3、极值点存在的充分条件下面的定理2给出了元实函数在点取得极小值的充分条件。
定理2 设是维欧氏空间的上的某一个开集，在上具有连续的二阶偏导数，若，且正定，则为的严格局部极小点。
其中（14）为在点处的海赛（Hesse）矩阵。
第二节凸函数与凸规划2.1 凸函数与凹函数1、定义设是定义在维欧氏空间的上的某一个凸集上的函数，若，，恒有（15）则称为定义在的凸函数。
若，，恒有（16）则称为定义在的严格凸函数。
若将式子（15）和（16）中不等号反向，即可得出凹函数和严格凹函数的概念。
容易看出，若是凸函数（严格凸函数），则为凹函数（严格凹函数），凸函数和凹函数的几何意义如图所示。
OO凸函数凹函数2、性质性质1 设是定义在上的凸函数，，则也是凸函数。
性质2 设在凸集上的函数，是任意实数，则水平集是凸集。
3、凸函数的判别要判定一个函数是否为凸函数，可以直接使用凸函数的定义，也可以采用下面的判别法。
（1）一阶条件设是维欧氏空间的上的某一个开凸集，在上可微，则为上的凸函数的充要条件是：恒有（17）而为上的严格凸函数的充要条件是：，恒有（18）若将式子（17）和（18）中不等号反向，即可得出凹函数和严格凹函数的充要条件。
（2）二阶条件设是维欧氏空间的上的某一个开凸集，在上二阶可微，则为上的凸函数（凹函数）的充要条件是：，其海赛矩阵是半正定（半负定）的。
而，的海赛矩阵是正定（负定）的，则为上的严格凸函数（严格凹函数）。
4、凸函数的极值函数的局部极值并不一定是最小值，它只反映了函数的局部性质，而最优化的目的往往是求出函数在整个区域中的最小值（或最大值）。
为此，必须求出所有的极小值加以比较（有时还需考虑其边界值），以便从中选出最小值。
然而，对于定义在凸集上的凸函数而言，则用不着进行这种麻烦的工作，它的极小值就等于其最小值，而且它的极小点形成一个凸集。
由一阶条件可得：设是维欧氏空间的上的某一个开凸集，是上的可微凸函数，如果使得对于所有的都有，（19）则就是在上的最小点（全局极小点）。
2.2 凸规划现在考虑非线性规划（4）：（4）或（5）若其中的为凸函数，全是凹函数（即全是凸函数），则称这种规划为凸规划。
凸规划具有下面很好的性质：（1）凸规划的可行域为凸集；（2）凸规划的最优解集是凸集；（3）凸规划的任何局部最优解也是全局最优解；（4）若目标函数为严格凸函数，且最优解存在，则最优解是唯一的。
由于线性函数既可视为凸函数，又可视为凹函数，故线性规划是凸规划。
例3 试分析非线性规划解：函数和的海赛矩阵的行列式为知为严格凸函数，为凹函数，由于其他约束是线性函数，所以这个非线性规划是一个凸规划，C点是它的唯一最优点：。
CO第三节下降迭代算法由前面的讨论可知，对于可微函数，为了求其最优解，可以令其梯度等于零，求出驻点，然后再用充分条件判别，以求得最优解。
从表面上看，似乎问题已经解决，但是对于一般的元函数来说，由条件得到的常常是一个非线性方程组，求解它相当困难。
此外，许多实际问题往往很难求出或根本求不出目标函数对各个自变量的偏导数，从而使一阶必要条件难以应用。
为了解决非线性规划的计算问题本节介绍迭代法。
迭代法的基本思想为：我们并不一下子就能找出函数的最优点，而是从最优点的某一个初始估计出发，按照一定的规则（即所谓算法），先找出一个比更好的点（对于极小化问题来说，比更小；对于极大化问题来说，比更大），再找出比更好的点，…….如此下去，就产生了一个解的序列。
若该点列有一个极限点，即（20）就称该点列收敛于。
对于极小化问题，我们要求选取的某一种算法所产生的解的序列其对应的目标函数值应是逐步减小的，即要求具有这种性质的算法称为下降迭代法。
下降迭代法的一般迭代格式为：（1）选取某一个初始点，令（表示将0赋值于变量）；（2）确定搜索方向：若已得出某一个迭代点，且不是极小点，从出发确定一个搜索方向，沿这个方向应能找到使的目标函数下降的点（对约束问题，有时还要求这样的点是可行的点）。
（3）确定步长。
沿方向前进一个步长，得新的点。
即在由出发的射线上，通过选定步长（因子），得下一个迭代点使得（4）检验新得到点是否为要求的极小点或近似的极小点，如果满足要求，迭代停止，否则，令，返回（2）部继续迭代。
注：在以上步骤中选定搜索方向对算法起着关键的性的作用，各种算法的区分主要在于搜索方向的方法不同。
在许多算法中，步长的选取是由使目标函数值沿搜索方向下降最多（极小问题）为依据的，即沿射线求的极小，即选取使（21）由于这一工作是求以为变量的一元函数的极小点，故称这一过程为（最优）的一维搜索，由此确定的步长称为最佳步长。
这种搜索有一个重要性质，就是在搜索方向上所得最优点处的梯度和该搜索方向正交，即有下面的定理。
定理3 设目标函数具有连续的一阶偏导数，按下述规则产生则有（22）如图所示。
由于真正的极值点事先并不知道，故在实际只能根据相继两次迭代得到的计算结果来判断是否已达到要求，从而需要有下面的终止迭代计算准图1则，常用的准则有：（1）根据相继两次迭代结果的绝对误差：（2）根据相继两次迭代结果的相对误差：（3）根据函数梯度的模足够小：其中为足够小的正数。
第四节一维搜索方法当用到上述迭代法求函数极小点时常常要用到一维搜索，即沿某个一直方向求目标函数的极小点。
一维搜索的方法很多，试探法（斐波那契法（Fibonacci分数法、0.618法），插值法等。
1、斐波那契法（Fibonacci）设是区间上的下单峰函数，在此区间内有唯一的极小点，在的左侧函数是严格下降的，而在的右侧函数是严格上升的，若在此区间内任取O a0 t* t1s1b0O a0 t1s1t* b0图2 图3两个点，计算函数值，，则可能出现一下两种情况：（1）（图2），此时极小点必在区间内；称为保留区间，此时称为保留点。
（2）（图3），此时极小点必在区间内。
此时为保留区间，而为保留点。
即将区间原来缩小为仍包括极小点的区间或。
若再继续下去，为了利用已计算的函数值或，将前一次的保留点作为一个试算点，只需在或内选取一个新的试算点即可。
例如假如在区间内，取试算点（保留点），再选一个作为另一个试算点，一般可以取，即，在区间上与对称，如图4所示)，只需计算出，即可与比较。
如此继续下去，最终可以得到满足一定误差要求的的近似解。
我们称这种方法为序惯试验法。
0 a1 t2 s2b1试问如何选取试算点，通过计算次函数值能将长度的区间缩成长度为一个单位的区间呢？假设是斐波那契（Fibonacci）数列，即，（23）利用上述公式可以计算出各个的值如下表1012345678910111213…1123581321345589144233377…若经过次函数值计算，将长度为的区间缩成长度为一个单位的区间，则缩短后的区间长度1与原来区间的长度之比称为缩短率。