第五节无约束非线性规划常用解法。
第六节约束非线性规划的最优性条件。
第七节约束非线性规划的常用解法。
第五节无约束非线性规划常用解法。
无约束极值问题可以表述为。
在求解上述问题时常用迭代法，迭代法大体上可以分为两类：一类称为解析法，它会用到函数的一阶或二阶导数；另一类称为直接法，它主要在迭代过程中使用函数值而不是使用导数。一般说来，直接法的收敛速度较慢，只适于变量较少的情况，但是具有步骤简单，特别是适用于目标函数解析表达式十分复杂或导数难以计算的情况。
下面介绍两种基本的解析法。
1、梯度法（最速下降法）
梯度法是一种古老的方法，但由于它的迭代过程简单，使用方便，而且又是理解其它非线性最优化方法的基础，因此非常重要。
假设目标函数具有一阶连续的偏导数，它存在极小点。以表示极小点的第次近似，为了求其第次近似，在点沿方向作射线。
将在处作泰勒展开得，其中。
是函数在点的梯度，可以假设（否则已是驻点），对于充分小的，是的高阶无穷小，此时，只要。
即可保证。因此只要取下一个迭代点，就可以使目标函数值得到改善（降低）。
下面我们设法寻找使（31）左端取最小的。因为。
其中是向量和的夹角。当时，此时，且其值最小，这个方向是负梯度方向，它是函数值减小最快的方向，梯度法就是采用负梯度方向为搜索方向。
为了得到下一个近似极小点，在选定了搜索方向之后，还要确定步长。
选取步长的一种方法是通过试算，即先取一个验证下式是否满足：
若满足，就可以取这个进行迭代，若不满足，就减小使上式成立。由于采用了负梯度方向为搜索方向，满足（33）的总是存在的。
另一种方法是：
这可以通过在负梯度方向的一维搜索来确定使最小的，这样得到的步长称为最佳步长，有时也称采用最佳步长时的梯度法为最速下降法。
下面是梯度法求函数的极小点的步骤：
1）给定初始点和允许的误差，令；
2）计算和，若，停止迭代，得近似极小点和近似极小值；否则，转入下一步；
3）作一维搜索：
并计算，然后令，转回第（2）步。
现设具有二阶连续偏导数，将在作泰勒展开：
关于求导数，并令其等于零，即可得到近似最佳步长的计算公式：
有时将搜索方向的规格化为1，即取。
此时式（35）就变为。
例2 用梯度法求函数的极小点，取允许误差。
解：取初始点，, 其海赛矩阵为，＝0.1124
故为近似极小点，此时。该问题的精确解是。
需要说明的是，最速下降法通常只是在考虑的某点的附近才具有快速下降的的性质，当接近于最优点时，收敛速度并不理想。
2、牛顿法。
首先考虑正定二次型。
此处是一个正定矩阵，，为常数。
假定该函数的极小点是，则必有。
从而。另外，对于任意点，函数在该点的梯度，消去得到，解出。
这说明，对于正定二次函数，从任意近似点出发，沿方向搜索，以1为步长，迭代一步即可达到极小点。这种方法即为牛顿法。
现在考虑一般的元实函数，假设它有二阶连续的偏导数，为其极小点的某一个近似点，在这个点附近取的二阶泰勒多项式逼近：
其中。由（39）求导数，注意到这个近似函数的极小点应满足一阶必要条件，即。
设的逆矩阵存在，可得。
由于式子（39）是一个近似式，所以从（40）解得的是一个近似极小点。为了求得的极小点，可以为搜索方向（牛顿方向），按下述公式进行迭代：
这就是所谓的阻尼牛顿法（广义牛顿法），可用于求解非正定二次函数的极小点。
牛顿法的优点是收敛速度快，缺点是有时无法进行下去需要采取改进措施。当维数较高时，计算的工作量很大。为了克服梯度法收敛速度慢及牛顿法有时失效和维数较高时计算工作量大的缺点，不少学者提出了更加使用的其它算法，如共轭梯度法、变尺法等。
第六节约束非线性规划的最优性条件。
约束极值问题可以表述为。
在大多数情况下，实际问题都受到某些条件的限制，这些限制条件常常给寻优工作带来很大的困难。下面首先说明解的最优性条件，然后研究几种基本的解法。
1、可行下降方向。
1）起作用约束。
假设是问题（5）的一个可行解，即它满足所有约束条件。对于某一个约束条件来说，满足有两种情况：一是，这时不在由这个约束条件形成的可行域的边界上，我们称这一约束为点的不起作用的约束（或无效约束）；另一种情况是，这时处于由这个约束条件形成的可行域的边界上，我们称这一约束为点的起作用的约束（或有效约束）。
显然，等式约束条件对所有的可行点都起约束作用。
2）可行方向。
设是任一个可行点，对某一方向（它也是一个向量）来说，若存在实数，使得对于任意的均有下式成立：
就称方向为点的可行方向。
设。即是点所有起作用约束下标的集合。
显然，若为点的可行方向，则存在实数，使得对于任意的均有下式成立：
从而。另一方面，由泰勒公式。
对点的起作用的约束，当足够小时，只要。
就有。此外，，对点的不起作用的约束，，由的连续性，当足够小时，也有。
从而，只要方向满足式子（41），即可保证为的可行方向。
（3）下降方向。
设，对某一方向来说，若存在实数，使得对于任意的均有下式成立：
则称方向为点的一个下降方向。
由泰勒公式。
当足够小时，只要。
就有，这说明只要方向满足（42）时，即可保证是点的一个下降方向。
4）可行下降方向。
若既是点的一个可行方向又是下降方向，则称为可行下降方向。设不是极小点，为了求其极小点，继续搜索时应当沿该点的可行下降方向进行。显然，对于某一点来说，若该点不存在可行下降方向，它就可能是局部极小点；若存在可行下降方向，它当然就不是极小点。
下面的定理从另一个角度说明了这一问题。
定理4 设是问题（5）的一个局部极小点，在处可微，而且。
在处可微，
在处连续，
则在点不存在可行下降方向，从而不存在同时满足。
其中。2、库恩－塔克（kuhn-tucker）条件。
库恩－塔克（kuhn-tucker）条件是非线性规划领域中最重要的理论成果之一，具有很重要的理论价值。
定理5 设是非线性规划（5）的局部极小点，，（在点处有一阶连续的偏导数，而且处的所有起作用约束梯度线性无关，则存在数。
44）称为库恩－塔克（kuhn-tucker）条件，满足该条件的点称为库恩－塔克点或k-t点。
构造lagrange函数。
分别对求偏导数并令其为零即可得（44）中的第一式。
库恩－塔克（kuhn-tucker）条件是确定某点为最优点的必要条件，只要是最优点，且此处其作用的约束的梯度是线性无关的，就必然满足这个条件。但是一般说来它不是充分条件，因而满足这个条件的点不一定是最优点。可是对于凸规划，这个条件是一个充分必要条件。
例1 用库恩－塔克条件解非线性规划。
解：先将其变为问题如下形式。
构造lagrange函数，分别对求导数有（，，
解该方程组，需分别考虑一下几种情况：
（1）：无解；
对应于（2）、（3）和（4）我们的到了三个库恩－塔克点，其中和。
是极大点，而为最大点，最大值为，为极小点。
3 二次规划。
若某一个非线性规划的目标函数为自变量的二次函数，约束条件都是线性函数，则称为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解。
二次规划的数学模型可以表述为。
式（46）右端的第二项为二次型。如果该二次型正定（或半正定），则目标函数为严格凸函数（或凸函数），此外，二次规划的可行域为凸集，因而上述规划属于凸规划。我们知道，凸规划的局部极小值即为其全局极值，此时库恩－塔克条件就成为极值点存在的充分必要条件。
将库恩－塔克条件中的第一个条件应用于二次规划，并用代替，就得到。
在式（47）中引入松弛变量，该式即变为（假定）
再将库恩－塔克条件中的第二个条件应用于二次规划，并考虑到式（49）可得到。
联立（48）和（49），如果得到的解也满足式（50）和（51），则这样的解就是原二次规划的解。再引入人工变量构造规划。
若解得最优解为，则就是原二次规划问题的最优解。
例2 求解二次规划。
解：将上述二次规划改写为。
可知目标函数为严格凸函数。此外。
引入人工变量在前面取负号得到。
或。此外还应满足：
用线性规划的单纯形法求解得到该线性规划的解如下：
由此得到原二次规划的问题的最优解：
第七节约束非线性规划的常用解法。
制约函数法是通过构造某种制约函数，并将它加到非线性规划的目标函数上，从而将原来的约束极值问题，转化为无约束极值问题来求解。由于这里介绍的方法需要求解一系列无约束规划问题，故称为序列无约束极小化技术，简记为sumt (sequential unconstrained minimization technique)。下面介绍两种方法：
罚函数法（或外点法）、障碍函数法（内点法）。
第一章非线性规划理论 1
第一节非线性优化规划模型及其解的概念，第二节凸函数与凸规划，第三节下降迭代算法。第四节一维搜索方法。第一节非线性优化规划模型及其解的概念。线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中含有自变量的非线性函数，则这样的规划问题就是非线性规划。有些实际问题可以表示成线性规划...
第6章非线性规划
前面几章，我们论述了线性规划及其扩展问题，这些问题的约束条件和目标函数都是关于决策变量的一次函数。虽然大量的实际问题可以简化为线性规划及其扩展问题来求解，但是还有相当多的问题很难用线性函数加以描述。如果目标函数或约束条件中包含有非线性函数，就称这样的规划问题为非线性规划问题。由于人们对实际问题解的精...
MATLAB非线性规划问题
实例1 表面积为36平方米的最大长方体体积。建立数学模型 设x y z分别为长方体的三个棱长，f为长方体体积。max f x y 36 2 x y 2 x y 实例2 投资决策问题。某公司准备用5000万元用于a b两个项目的投资，设x1 x2分别表示配给项目a b的投资。预计项目a b的年收益分别...