东北大学最优化方法全部课件

开始

最优化方法

（最优化课件研制组）退出主讲：张京最优化方法开始最优化方法

（最优化课件研制组）退出主讲：张京最

最优化方法为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法是在第二次世界大战前后，在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。最优化方法解决问题一般步骤：（1）提出需要进行最优化的问题，开始收集有关资料和数据；（2）建立求解最优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件；（3）分析模型，选择合适的最优化方法；（4）求解方程。一般通过编制程序在电子计算机上求得最优解；（5）最优解的验证和实施。随着系统科学的发展和各个领域的需求，最优化方法不断地应用于经济、自然、军事和社会研究的各个领域。

第1章预备知识1.1经典极值问题

1.例子，

2.数学模型

第一，无约束极值问题或

解法：解方程组

第二，仅含等式约束的极值问题

或

解法：Lagrange乘子法1.2实例数据拟合问题原料切割问题运输问题营养配餐问题分配问题1.3基本概念

1.最优化问题的向量表示法设

则（1）

以向量为变量的实值函数定义向量间的序关系(定义1.1)：等于＝，小于，严格小于。由此（2）以向量为变量的实向量值函数最优化问题的一般形式

（3）

2.最优化问题的分类

试验问题：用于检验、比较最优化方法优劣的一些最优化问题。3.

术语目标函数等式约束

不等式约束容许解（点）容许集

求解问题（3）是指：在容许集中找一点目标函数在该点取极小值，即对于容许集中的任，总有

意一点最优点（极小点）

最优值

最优解严格极小点局部非严格极小点严格极小点非严格极小点全局，使得

到目前为止，大多数最优化算法求到的都是局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。

4.极大值问题与极小值问题的关系

1.4二维问题图解法

二维极值问题有时可以用图解的方式进行求解，有明显的几何解释。例求解

图解法的步骤：，显然；②取并画出相应的曲线（称之为等值线）.

③确定极值点位置，并用以往所学方法求之。

易知本题的极小值点。

再复杂点的情形见P13上的例1.7。

虽然三维及以上的问题不便于在平面上画图，图解法失效，但仍有相应的等值面的概念，且等值面具有以下性质：①有不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；②等值面不会在区域的内部中断，除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故；①令

⑶等值面稠密的地方，目标函数值变化得比较快；等值面稀疏的地方，目标函数值变化得比较慢；⑷在极值点附近，等值面（等值线）一般近似地呈现为同心椭球面族（椭圆线族）。1.5梯度和Hesse矩阵本段讨论都基于对函数以下及今后的讨论中还经常要用到以下一些向量的知识。可微的假定。

与。

记作。向量也常用希腊字母等表示。向量内积的性质：ⅰ)（对称性）；ⅱ)

（线性性）；ⅲ),当且仅当时，（正定性）；向量的内积设则称为向量的内积，其实，

向量的长单位向量

向量的夹角，

向量的正交

（正交性）

1.可微

定义1.7设.如果存在维向量对于可任意小的维非零向量，总有在点那么称函数处可微。

若令便得到（1.9）的等价形式

.（1.10）

2.梯度

定理1.1若在点处可微，则在该点关于各个变量的一阶偏导数存在，并且

定义1.8以函数的个偏导数为分量的向量称为在点处的梯度，记为。。

梯度也称为函数关于变量于是，（1.10）可写为这个公式与一元函数展开到两项的Taylor公式是相对的。

梯度的性质：当梯度连续时，第一，若，则必垂直于过点处的等值面；的一阶偏导数。

第二，梯度方向是函数具有最大变化率的方向。下面以为例来解释这个性质。上图是该函数的等值线图。今考虑一点，不妨取坐标为。设想有出发沿某个方向移动到了点，其坐标，那么目标函数值将产生如下变化量一动点从设为假定。试问：动点沿哪个方向移动会使目标函数值有最多的下降或上升？从图上看，这相当于问：在以点为圆心、以1为半径的圆周上，哪一个点具有最大的或最小的目标函数值。

为了一般地描述函数在点处沿情况及变化速度，须引入上升方向和下降方向及方向导数的概念。方向的变化函数在点处沿方向的变化反映的是函数在一条直线上的变化，空间中由一点和一方向所确定的直线方程为

上升方向和下降方向设是连续函数。

若存在，对于都有，则称方向是在点处的上升方向；若存在对于都有，则称方向是在点处的下降方向。定义1.9设在点处可微，是非方向上的单位向量。如果极限零向量存在，则称其为函数在点处沿方向的方向导数，。记作思考：与的异同。

若，则方向是在点处的上升方向；根据极限理论，易见若，则方向是在点处的下降方向。因此，方向导数的正负决定了函数值的升降。定理1.2设在点处可微，则，其中是非零向量方向上的单位向量。定理1.2又表明：只要，则方向是在点处的上升方向；只要，则方向是在点处的下降方向。

函数值升降的快慢则是由方向导数绝对值的大小决定的。绝对值越大，升或降的速度就越快；绝对值越小，升或降的速度就越慢。这是因为据此有ⅰ)等号成立当且仅当与同方向或与同方向。且当与同方向时，取到最大值

。当与同方向时，取到最小值

ⅱ)

若是锐角，则;若是钝角，则。因此，方向导数又可以称为函数在点处沿方向的变化率。使函数值下降最快的方向称为最速下降方向。最速下降方向为例1.8P19ⅱ)若是锐角，则;若是

几个常用函数的梯度公式（1）若，则，即（2）（3）；（4）.；；2.Hesse矩阵

问：函数关于变量的二阶导数又是什么？

先来看什么是向量值函数的可微。定义1.11设。若的所有分量

在点都可微，则称向量值函数在点处可微。

定义表明，在点处可微，则成立，其用向量形式可简单地表示为其中称为向量值函数在点处的导数，

而称为向量值函数在点处的Jacobi矩阵。设具有二阶连续偏导数，且则矩阵称为函数关于变量的二阶导数，简记为。也称为多元实值函数的Hesse矩阵。

例1.9P21

几个特殊的向量值函数的导数公式：（1）；（2）；（3）；（4）设，其中。则利用（4），可得多元函数展开到三项的Taylor公式（1.29）或（1.31）这个公式与一元函数展开到三项的Taylor公式是相对应的。

多元函数的Taylor展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。

1.凸集1.6凸函数与凸规划

直观上，凸集就是空间中内部无“洞”，边界又不向内凹的一些点的集合，其基本特征是该集合中任意两点间的线段仍然属于这个集合。非凸集凸集空间中两点间的线段是由点的凸组合定义的。定义1.12设是中的个已知点。点，若存在满足的非负实数

对于使得，则称是的一个凸组合。

又若是满足的正实数，则称是的一个严格凸组合。两点的凸组合恰是连接两点的的线段。线段，而严格凸组合是不含端点

定义1.13设集合。如果中任意两点的，那么集合称为凸集。任意凸组合仍然属于规定：空集是凸集。

思考：空间中三个不同点的凸组合的集合，空间中四个不同点的凸组合的集合.常见的凸集有超平面，直线，球.

定理1.5凸集的交集是凸集。又若是满足的正实数，则称是的一个严格凸组合。两点的凸组合恰是2.凸函数定义1.16设，其中为凸集。若对于中的任意互异两点和任意一对满足的非负实数，

总有则称是定义在凸集上的凸函数。又若对于任意的正实数，总有一对满足则称是定义在凸集上的严格凸函数。2.凸函数定义1.16设，其中为凸集。若对于中的任意互若是凸集上的（严格）凸函数，则称是凸集上的（严格）凹函数。凸函数有以下重要性质。定理1.6

（1）若是定义在凸集上的凸函数，是也是上的凸函数。任意的非负实数，则（2）若是定义在凸集上的凸函数，则也是上的凸函数。

由定理1.6易见，定义在凸集上的任意有限个凸函数的任意非负组合仍然是凸函数。例1.10若是凸集上的（严格）凸函数，则称是凸集上的（严格）凹函数。凸定理1.7

设，其中为非空凸集，若是凸函数，则对于任意实数，

水平集是凸集。证若是空集，则是凸集。以下设非空。任取，则

。又设但，根据的凸性，必有即。因此，是凸集。

判断一个函数是否为凸函数，一般说来，是比较困难的。但当函数可微时，有以下几个判定定理。定理1.7设定理1.7设，其中为非空凸集，若是凸函数，则对于任意实数定理1.8设是可微函数，其中为凸集。则ⅰ)

为凸函数的充要条件是对于中的任意两点，都有ⅱ)

为严格凸函数的充要条件是对于中的任意都有两个互异点

定理1.8有明显直观的几何解释。可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面（切线）都不在曲面（曲线）的上方。右图画出了一维的情形。定理1.8设是可微函数，其中为凸集。则ⅰ)为凸函数的充定理1.9设是二次可微函数，为非空开凸集。则为上凸函数的充要条件是Hesse矩阵在上处处半正定。定理1.10设是二次可微函数，为非空凸集，若的Hesse矩阵在上处处正定，则是上的严格凸函数。这个命题的逆命题不真。例如，在上为严格凸函数，在处是半正定的。但是它的Hesse矩阵定理1.9设是二次可微函数，为非空开凸集。则为上凸函数的3.凸规划

设是定义在非空凸集上的凸函数，则形式为（1.36）的最优化问题称为凸规划问题，简称凸规划。换言之，定义在凸集上的凸函数的极小化问题是凸规划问题。若都是上的凹函数，都是上的线性函数，容易验证集合是凸集。在这种情况下，凸规划（1.36）可以表示成如下形式（1.37）3.凸规划设是定义在非空凸集上的凸函数，则形式为（1.下面的定理指出了凸规划的一些重要性质。定理1.11设是凸规划（1.36）的局部极小点。则i）是（1.36）的全局极小点；ii）当是严格凸函数时，是（1.36）的唯一极小点；iii）（1.36）的全部极小点的集合是凸集。定理1.12设是可微凸函数，是非空。

凸集，则是凸规划（1.36）的极小点的充要中任意一点，总有。条件是，对于

定理1.12表明，凸规划（1.36）在最优点处的任何容许方向（定义4.3）都不是下降方向。推论1.13设是可微凸函数，是非空凸集，。若使得，则是凸规划（1.36）的全局极小点。下面的定理指出了凸规划的一些重要性质。定理1.11设是凸4.二次函数与二次规划函数（1.38）称为元二次函数，其中是对称矩阵。若是正定的，则（1.38）称为正定二次函数。，

，

注意到，

于是由定理1.10得知：正定二次函数是严格凸函数。在最优化算法构造中，正定二次函数起着特殊的作用，本书的许多章节都要涉及它。4.二次函数与二次规划函数（1.38）称为元二次函数，其形式为（1.39）的最优化问题称为二次规划问题，简称二次规划。若是半正定的或正定的，则（1.39）称为二次凸规划。定理1.14

一个

对称矩阵为正定矩阵的充要条件是的各阶主子式皆大于零。形式为（1.39）的最优化问题称为二次规划问题，简称二次规开始

最优化方法

（最优化课件研制组）退出主讲：张京最优化方法开始最优化方法

（最优化课件研制组）退出主讲：张京1.7极小点的判定条件函数在局部极小点满足什么条件？反之，满足什么条件的点是的局部极小点？定理1.15设具有一阶连续偏导数，是的内点。若是的局部极小点，则（1.40）注意，条件式（1.40）不是充分的，仅仅是必要的。例如，在点处的梯度是但是点是这个双曲抛物面的鞍点，而不是极小点。

根据定理1.15与推论1.13，容易得到凸规划问题全局极小点的一个一阶充分且必要条件。1.7极小点的判定条件函数在局部极小点满足什么条件？反之推论1.16设是可微凸函数，是非空开凸集，。则是（1.36）的全局极小点的充要条件是.定义1.17设可微，若，则称为的驻点。驻点包括极大值点、极小值点和鞍点。定理1.17设具有二阶连续偏导数，

，且。若正定，则是的严格局部极小点。

一般来说，这个定理仅具有理论意义。因为对于复杂的目标函数，Hesse矩阵不易求得，其正定性也很难判定。推论1.16设是可微凸函数，是非空开凸集，。则定理1.18设具有二阶连续偏导数，且。

若存在的邻域，使得

对于，都半正定，则必是的局部极小点。

利用上节和本节的定理不难说明下面的两个论断。i）对于正定二次函数，是它的唯一极小点。

ii）若多元函数在极小点处的Hesse矩阵是正定的,则在这个极小点附近其等值面近似地呈现为同心椭球面族。推证如下：i）首先求出二次函数的驻点。令因为是正定矩阵，所以解出唯一驻点为（1.41）定理1.18设具有二阶连续偏导数，且。若存在的邻域，使因此根据推论1.13可以断定，是唯一的极小点。ii）设是多元函数的极小点，

并设是充分的一个等值面，

靠近极小点即充分小。

把在点处按Taylor公式展开，得到上式右端第二项因为是极小点而消失，再略去第四项，那么二次曲面（1.42）就是等值面的近似曲面。按假设，是正定的，因此，为中心的椭球面（1.42）是以方程。这正是我们所要说明的。因此根据推论1.13可以断定，是唯一的极小点。ii）设是1.下降迭代算法1.8算法及有关概念在集合上的迭代算法是指：开始，选定一个初始点

，置。然后按某种规则，把第

次迭代点映射为新的一点

，记为，并置这称为完成了第次迭代。

这个过程无限地进行下去，。因此，规则称为算法。

就会产生一个点列若点列收敛于，则称算法在上是收敛的；

否则，称算法在上是发散的。特别地

，当

问题（1.6）的容许集时，若除满足计算终止准则的迭代点是最优化外，对于每个，都有，则称为下降迭代

许多最优化方法都采用将多维问题转化为一维问题的处理方式。下面以无约束问题为例，说明采用这种方式时的下降算法的基本迭代格式。1.下降迭代算法1.8算法及有关概念在集合上的迭代算法是设第次迭代点已求得。若它不满足终止准则，。对于可微目标函数，即那么在该点必存在下降方向是满足的。按某种规则选取一个，例如

，再沿这个方向适当地前进一步，即在直线

上确定一个新点，使得设第次迭代点已求得。若它不满足终止准则，。对于可微目标函数，这就完成了第迭代。上式中的称为搜索方向，称为步长因子。

不过，计算机只能进行有限次迭代。因此，一般说来，数值计算不能求到精确解，而只能得到近似解。当迭代点满足事先给定的精度要求时，就终止计算，并把这个迭代点当作问题的最优解。在上数述迭代过程中，有两个规则需要确定：一个是的选取规则；一个是步长因子的选取规则。下降方向不同的规则对应着不同的最优化方法。综上所述，无约束问题下降算法的基本迭代格式如下：⑴选定初始点，置。⑵按某种规则确定下降方向。⑶按某种规则确定，使得

这就完成了第迭代。上式中的称为搜索方向，称为步长因子。⑷置。⑸判定是否满足终止准则。若满足，

则打印和；否则，置转⑵。

算法流程图见P34图1-18。2.直线搜索及其性质在搜索方向已经确定的前提下，选取步长因子的方法有多种。例如，取步长因子为某个常数。但在实际计算中，最常用的方法是直线搜索（又称一维搜索），即选取，使得（1.43）

按这种方法确定的步长因子称为最优步长因子。这种选取方法是很自然的。既然下降方向已经确定，就应该沿这个方向找到使目标函数取极小值的点。⑷置。⑸判定是否满足终止准则。若满足，则打印和；否则，置转东北大学最优化方法全部ppt课件东北大学最优化方法全部ppt课件2.直线搜索及其性质在搜索方向已经确定的前提下，选取步长因子的方法有多种。例如，取步长因子为某个常数。但在实际计算中，最常用的方法是直线搜索（又称一维搜索），即选取，使得（1.43）

按这种方法确定的步长因子称为最优步长因子。这种选取方法是很自然的。既然下降方向已经确定，就应该沿这个方向找到使目标函数取极小值的点。2.直线搜索及其性质在搜索方向已经确定的前提下，选取步长因同时这又是容易办到的，因为是以为变量的一元函数。

求一元函数极小点的迭代法称为直线搜索或一维搜索。许多最优化方法都采用将多维问题转化为一维问题的处理技术。因此可以说，一维搜索是最优化方法的一个重要支柱。这种方法的优点是，它使目标函数值在搜索方向上下降得最多；缺点是，计算量较大。在第3章的3.1节中将全面介绍直线搜索。为简便起见，今后用记号（1.44）表示从点出发沿方向对目标函数作直线。在目标函数确定的条件下，

搜索得到极小点（1.44）等价于（1.45）同时这又是容易办到的，因为是以为变量的一元函数。直线搜索的一个重要性质。定理1.19设目标函数具有一阶连续偏导数。若，则证使用反证法。假设，则或（1.47）（1.48）（1.47）表明是点处的下降方向，（1.48）表明是点处的下降方向，

这都与相矛盾。。

故必有（1.46）的几何意义是明显的。直线搜索的一个重要性质。定理1.19设目标函数具有一阶若是从点出发沿方向对目标函数搜索得到的极小点，则（1.46）指出，梯度搜索方向向量正交。

作直线必与又因为与目标函数过点的等值面（等直线）正交，所以搜索方向向量与这个等值面（等直线）在点处相切。若是从点出发沿方向对目标函数搜索得到的极小点，则（1.46）3.计算终止准则设某个算法产生的点列收敛于（1.6）的最优解。

现在的问题是：在计算机上计算时，计算到哪一个迭代点才有把握地说它就是所求问题的（近似）最解？显然，当小于预先给定的误差限时就可以就是所求的最优解。

认为但事实上是未知的，因而无法计算。不过，由极限理论知道，当

与都很小时，

也必然很小。于是，在数值计算中，可以用（1.51）作为计算终止的一个判定条件，其中是预先给定的计算终止的界限，今后称为终止限。但是，用（1.51）作为终止准则是不可靠的，因为很小并不能保证很小。3.计算终止准则设某个算法产生的点列收敛于（1.6）的最优下面图1中画出了一条一元目标函数的曲线及其有关的点。从图中可以看到，相邻两个迭代点和已经很靠近了，但它们距极小点却都很远，而且这两点的目标函数值和还由极限理论知道，当相差很大。很小时，也必然很小。因此，如果加上（1.52）下面图1中画出了一条一元目标函数的曲线及其有关的点。从图中可

这个条件，那么可靠性就会加强。上图2指出了只采用（1.52）也是不可靠的。虽然与

相差很小，可是相应的两个迭代点和却相距很远，它们距极也很远。

小点需要注意的是，实际应用中，由于和

所取的量纲有时太大，这时如果仍然以（1.51）和（1.52）作为终止准则就太严格了。结果要么是用更多的计算才能使得（1.51）和（1.52）得到满足，而这是不划算的；要么是永远不能满足。解决这个问题的办法是，先对和

作无量纲处理，然后再结合（1.51）和（1.52），给出（1.53）和（1.54）作为终止准则。这个条件，那么可靠性就会加强。上图2指出了只

此外，有一类无约束最优化方法在求解过程中利用了梯度。由于

为极小点的必要条件是。因此，当满足（1.55）时，一般可以认为就是所要求的最优解。由于条件不是充分的，所以单独以（1.55）作为终止准则也是不可靠的。

最后的结论是：对于使用导数的最优化方法，可按书上图所示的判别过程作为终止准则；对于不使用导数的最优化方法，则只需把图中涉及的部分去掉。今后统称为Himmelblau计算终止准则，简称H终止准则。此外，有一类无约束最优化方法在求解过程中利用东北大学最优化方法全部ppt课件例1：已知求解：，例1：已知求解：，例2：用图解法求解解：①画出目标函数的等值线；②画出等式约束例2：用图解法求解解：①画出目标函数的等值线；②画出等式约束的图形，它是一条抛物线；③画出不等式约束所代表的区域。的图形，它是一条抛物线；③画出不等式约束所代表的区域。容许集为抛物线的一段，最优解为目标函数的等值线与容许集的切点，即最优点满足方程⑴公切线平行轴，切点为⑵代入得容许集为抛物线的一段，最优解为目标函数的等值线与容许集的切点解得或得切点不在容许集上，最优点为最优值点交点解得或得切点不在容许集上，最优点为最优值点交点例3：用图解法求解①画出目标函数的等值线；②画出等式约束解：例3：用图解法求解①画出目标函数的等值线；②画出等式约束解：的图形，它是一条抛物线；

③画出不等式约束所代表的区域。的图形，它是一条抛物线；

③画出不等式约束所代表的区域。容许集为抛物线的一段，最优解为抛物线的端点，即方程的解最优值目标函数的等值线与容许集的切点，即最优点满足方程容许集为抛物线的一段，最优解为抛物线的端点，即方程的解最优值切点点不在容许集上.最优解切点点不在容许集上.最优解例4：设目标函数为从点出发，沿的方向作直线搜索，试求搜索到的极小点并验证解：例4：设目标函数为从点出发，沿的方向作直线搜索，试求搜索到的东北大学最优化方法全部ppt课件例5：判别最优化问题是否为凸规划解：正定并用图解法求出最优点。例5：判别最优化问题是否为凸规划解：正定并用图解法求出最优点

从图上可判别出容许集为淡绿色区域，此区域为凸集，故此最优化问题为凸规划。用解析方法也可证明容许集为凸集。从图上可判别出容许集为淡绿色区域，此区域为凸都为半平面，它们的交集为凸集，以下判别为凸函数。各阶主子式非负，为凸函数。为凸集。即容许集为凸集。都为半平面，它们的交集为凸集，以下判别为凸函数。各阶主子式非用一阶导数判别的凸性。用一阶导数判别的凸性。为凸函数。即容许集为凸集。为凸集.为凸函数。即容许集为凸集。为凸集.

由图解法可求得局部极小点，它一定是此最优化问题的全局最优点。最优点满足条件解得为全局最优点。由图解法可求得局部极小点，它一定是此最优化开始

最优化方法

（最优化课件研制组）退出主讲：张京最优化方法开始最优化方法

（最优化课件研制组）退出主讲：张京最

在最优化中，目标函数和约束函数皆为线性函数的优化问题称为线性规划（LP），它是相对简单的最优化问题。本章是有关线性规划的理论与求解方法的内容。

第二章线性规划在最优化中，目标函数和约束函数皆为线性函数的2.1线性规划的各种形式1.标准形式和典范形式如下形式的线性规划称为线性规划的标准形式。其中各称为价格系数，各采用向量－矩阵表示法，标准形式可以简写为。

（2.1）称为右端项。（2.2）2.1线性规划的各种形式1.标准形式和典范形式如下在进行理论分析时，有时需要把表示成这样，（2.2）中的又可写成若中有个列向量可以合并成为单位矩阵，且

例如，如下线性规划，此时（2.2）则称为线性规划的典范形式。就呈现为典范形式，因为和可合并成单位矩阵。在进行理论分析时，有时需要把表示成这样，（2.2）中的又可写不失一般性，假定单位矩阵位于前列，即典范形式呈现为（2.3）其中。用向量－矩阵表示法，那么（2.3）可简写成（2.4）不失一般性，假定单位矩阵位于前列，即典范形式呈现为（2.3）2.一般形式线性规划（2.5）3.一般形式与标准形式的关系（1）松弛变量2.一般形式线性规划（2.5）3.一般形式与标准形式考虑“”约束中的第个不等式（2.6）引入非负变量，迫使使不等式约束（2.6）变为等式约束（2.7）的非负变量称为松弛变量。（2）剩余变量考虑“”约束中的第个不等式（2.7）（2.8）引入非负变量，迫使考虑“”约束中的第个不等式（2.6）引入非负变量，迫使使不引入非负变量，迫使使不等式约束（2.8）变为等约束（2.9）的非负变量（2.9）称为剩余变量。在引入个松弛变量、个剩余变量后，线性规划（2.5）可化成标准形式：（2.10）引入非负变量，迫使使不等式约束（2.8）变为等约束（2.9）它含有个变量、个等式约束。

注意，新引入变量的价格系数全部设为零。因此，在（2.10）的目标函数中没有出现新变量。

下面说明线性规划（2.5）与其标准形式（2.10）是等价的。

首先，它们的容许点是一一对应的，且对应的容许点的函数值相等。因为若

是（2.5）的一个容许点，那么按公式（2.7）和（2.9）引入非负的松弛变量和剩余变量后，显然将是（2.10）的容许点。反之亦然。故（2.5）的容许点与（2.10）的容许点一一对应。又（2.5）与（2.10）的目标函数相同，且都只是的函数，所以（2.5）与（2.10）所对应的容许点的函数值相等。它含有个变量、个等式约束。注意，新引入变量的其次，若是（2.10）的最优点，它所对应的最优值为，那么，由前面的证明可知，其前个分量组成的向量也一定（2.5）的最优点。反之亦然。

因此，线性规划（2.5）与其标准形式（2.10）是等价的。该结论表明，可以只讨论标准线性规划。例2.1将线性规划

化为标准形式，并用图解法求解原问题，给出标准形式的解。其次，若是（2.10）的最优点，它所对应的最优值为，那么，由解对第1个约束引入松弛变量，对第2个约束引入。于是，该线性规划的标准形式为剩余变量图解法求解原线性规划如下：解对第1个约束引入松弛变量，对第2个约束引入。于是，该线最优解在直线与的交汇处，即。相应的标准形式的最优解为。（3）自由变量

以上讨论都考虑变量的取值是非负的（当变量的取值非正，那么它的负变量的取值即是非负的）。实际中，如果某些变量没有这种约束，也就是说，某些变量可以任意取值，那么这些变量称为自由变量。自由变量可以通过以下两种方法把它消除。例如，假若是自由变量。第一种方法：引入两个非负变量和，令（2.11）将其代入到线性规划的目标函数和约束函数中，自由变量

就消除了。注意，求出新线性规划的最优点后，再利用（2.11）便可以定出。最优解在直线与的交汇处，即。相应的标准形式的最优解为。（3）第二种方法：取一个包含的等式约束，例如由此解出（2.12）

将此式代入到线性规划的目标函数和其他约束函数中，自由变量也消除了。求出新线性规划的最优点后，。利用（2.12）再定出

第一种方法将增加变量的数目，导致问题的维数增大。第二种方法正好相反。2.2基本定理考虑标准线性规划（2.2），即第二种方法：取一个包含的等式约束，例如由此解出（2.12）记容许集。不妨假定

，。1.极点与基本容许解定义2.2有限个半空间的交称为凸多面体。半空间是凸集，故凸多面体是凸集。边界为直线或平面是多面体的几何特征。多面体凸多面体定义2.3有界的的凸多面体称为凸多胞形。凸多面体

凸多胞形记容许集。不妨假定，。1.极点与基本容许解定义2.定理2.1

线性规划（2.2）的容许集是凸多面体。(2)凸集的极点与凸集相关的另一个重要概念是凸集的极点。定义2.5若凸集中的某个点不能表示为这个集合中另外两个不同点的严格凸组合，即则称为凸集的极点。定理2.1线性规划（2.2）的容许集是凸多面体。(2)凸(3)基本容许解当（2.2）的容许解又是“的基本解”时，就称其为（2.2）的基本容许解。方程组满足“基本”条件的的解称为的基本解。的基本解是如何定义的呢？将表示成向量形式(3)基本容许解当（2.2）的容许解又是“的基本解”时，就称因为，故中必含有阶的可逆矩阵

，称为基。基的每个列向量称为基向量，的其余列向量称为非基向量。与基向量对应的变量称为基变量，与非基向量对应的变量称为非基变量。若基是单位矩阵，则称为标准基。非基变量取值皆为0的解称为基本解。满足的基本解称为线性规划（2.2）关于基的基本容许解。因为，故中必含有阶的可逆矩阵，称为基。基的每个列向量称为基不失一般性，设则令

。若，得基本解么该基本解是关于基的基本容许解。

，那例2.3P48

定义2.10基变量取值皆不为0的基本解称为非退化的，否则称为退化的；若（2.2）的所有基本容许解都是非退化的，则线性规划（2.2）称为非退化的，否则称为退化的。例2.4P49不失一般性，设则令。若，得基本解么该基本解是关于基(3)基本容许解与极点的关系引理2.2设

，，。则是基本容许解

的正分量所对应的的列向量线性无关。定理2.3

设,则是（2.2）的基本容许解是的极点。从几何角度讲，例2.3中的约束条件

表示空间一条直线在第一象限中的直线段部分。如图所示：(3)基本容许解与极点的关系引理2.2设，，。则是基红线部分为容许集。有两个极点和它们恰恰是两个基本容许解。例2.4如图所示：有两个极点和推论2.4容许集的极点个数有限。红线部分为容许集。有两个极点和它们恰恰是两个基本容许解2.线性规划基本定理引理2.5设.不妨设

且线性相关。那么一定存在最多有个正分量的容许解。定理2.7

线性规划（2.2）若有容许解，则必有基本容许解。

定理2.8

线性规划（2.2）若有最优解，则必有最优基本容许解。从几何上看，解线性规划存在以下几种可能情形：唯一解无穷多解解无界无解2.线性规划基本定理引理2.5设.不妨设且线性相2.3

单纯形法由前述知，（2.2）的容许集

是凸多面体，

中的极点个数有限。（2.2）若有容许解，则必有基本容许解；若有最优解，则必有最优基本容许解。据此，对于线性规划，我们只关心基本容许解即可。因此，一个显而易见的求解方法是求出全部基本容许解（极点），比较目标函数值就能确定最优解。可是，当数值较大时，这种法的计算量相当大，逆矩阵也不易求。Dantzig给出的单纯形法基本上解决了这个问题。单纯形法的基本思想是：首先找到（求出）一个极点（基本容许解），并依据最优性准则判断其最优性，如非最优，则沿凸多面体条棱找到（迭代到）

的一使目标值降低（不找比的）的下一个极点（基本容许解）的目标值高数是有限的，所以在一定的条件下，总可以找到（迭代到），……。因为极点个最优极点（最优基本容许解）或者说明解无界。2.3单纯形法由前述知，（2.2）的容许集是凸多面体，如图所示。Dantzig单纯形法的思想涉及以下三个具体问题：有最优点解无界一、初始基本容许解的产生；二、最优性准则；三、基本容许解的改进。如图所示。Dantzig单纯形法的思想涉及以下三个具体问题1.最优性准则考虑标准线性规划（2.21）设为容许基。

并不妨设,,。将（2.21）改写为（2.22）1.最优性准则考虑标准线性规划（2.21）设为容许基。并令，得关于的基本容许解

目标函数值设

为任一容许解，则由（2.22）解出代入目标函数中得令，于是（2.26）故

. 因为，因此，只要，必有由此得到判断基本容许解是最优解的一个充分条件。令，得关于的基本容许解目标函数值设为任一容许解，则由（定义2.11在标准线性规划（2.21）中，设是一个基，则称为变量关于基的判别数。判别数的向量形式为易知。

定理2.9（线性规划最优性准则）在标准线性规划（2.21）中，设

是容许基。若所有变量关于基的判别数皆非正，则关于基的基本容许解是最优解。

定义2.12在标准线性规划（2.21）中，若关于基基本容许解是最优解，则称是最优基。定义2.11在标准线性规划（2.21）中，设是一个基，例2.5考虑标准线性规划试分别求关于基和

的基本解。若是容许解，则判别其最优性。解关于的基变量取值

故关于的基本解

是基本容许解。计算例2.5考虑标准线性规划试分别求关于基和的基本解。若最优性准则未满足，因此不能断定是否是最优解。因此关于的基变量取值

故关于的基本解

也是基本容许解。计算最优性准则满足，因此断定是最优解。最优性准则未满足，因此不能断定是否是最优解。因此关于的基变量2.基本容许解的改进（1）Gauss-Jordan方程组假定是（2.21）的一个基。由得等价方程组记则（2.28）可写成

（2.28）（2.29）2.基本容许解的改进（1）Gauss-Jordan方程组假（2.29）称为关于基的Gauss-Jordan方程组（G-J方程组）。典范线性规划的主约束即是一个G-J方程组。G-J方程组的性质：

ⅰ）一个基决定唯一的G-J方程组；ⅱ）若是容许基，则由其G-J方程组可得出关于的基本容许解

ⅲ）在G-J方程组中,基变量的系数向量构成单位矩阵。

性质ⅰ）说明求新的基本容许解的过程实质上就是不同基的G-J方程组间的转化过程。这个转化过程很容易实现。设是新基，是用非基向量替换中的得到的矩阵。

这时G-J方程组间的转化过程就是要将非基变量的系数向量变为单位向量（性质ⅲ）.要实现这个过程，则必须有元素（2.29）称为关于基的Gauss-Jordan方程组（G-，称为主元。转化过程显示如下：

关于基的Gauss-Jordan方程组

关于基的Gauss-Jordan方程组为保证解的改进，替换须满足以下两个条件：，称为主元。转化过程显示如下：关于基的Gauss-Jord第一，容许性条件。即保证的G-J方程组的右端项非负的条件。第二，下降性条件。即保证的基本容许解的目标函的基本容许解的目标函数值的条件。数值小于i）容许性条件由，即主元还必须为正。结论是：为保证的G-J方程组的右端项非负，

（2.36）主元必须是满足的正数。如果主元不存在，则线性规划解无界（定理2.12）。第一，容许性条件。即保证的G-J方程组的右端项非负的条件。第例2.6

考虑例2.5中的线性规划

关于的G-J方程组试把和分别引入基，求新的基本容许解。ⅱ）下降性条件新解。

中只有其余分量皆为0。于是，由（2.26）式得（2.37）由于，所以只要，则特别当时，只要，必有例2.6考虑例2.5中的线性规划关于的G-J方程组试把结论是：引入判别数为正的变量，将保证的基本的基本容许解的目标函数值。容许解的目标函数值不大于引理2.10定理2.11（单纯形法基本定理）在标准线性规划（2.21）中，假设：ⅰ）是容许基，关于的基本容许解；是非退化的，即ⅱ）非基变量的判别数；ⅲ），是用公式（2.36）确定的一个行标；ⅳ）用替换中的，而其余基向量不变，构成。矩阵那么，是容许基，且关于的基本容许解的结论是：引入判别数为正的变量，将保证的基本的基本容许解的目标目标函数值小于关于的基本容许解的目标函数值。

定理2.12

在标准线性规划（2.21）中，假设：ⅰ）是容许基；ⅱ）非基本变量的判别数；ⅲ）。那么线性规划（2.21）存在可以使目标函数值任意减小的容许解。（2）单纯形表

以上过程都可以清晰地在一张表——单纯形表上进行，称之为表上作业法。假设已知（容许）基，那么关于的信息全部反映在以下两个式子（线性规划的两个关键数学式）中，目标函数值小于关于的基本容许解的目标函数值。定理2.12称之为关于基的增广G-J方程组。

增广G-J方程组其实可由线性规划（2.21）的原始数据经初等行变换得到。原有(2.45）式左乘即得（2.43）式，（2.43）式再左乘加到（2.46）式上便得（2.44）式。

隐去增广G-J方程组中的变量和的系数向量，将其余数据列成表（2.51）称之为关于基的增广G-J方程组。增广G-J方称为关于基的单纯形表。若是最优基，则称为最优表。单纯形表是增广G-J方程组的简单表示。表称为线性规划的准备表。类似前面的推导，由准备表容易导出单纯形表称为关于基的单纯形表。若是最优基，则称为最优表。单纯形表是增

至此，含有标准基的线性规划问题的求解彻底解决。归纳见（3）。例2.7求解例2.5中的线性规划。P64-55（3）典范线性规划的解法考虑典范线性规划是标准容许基。

典范线性规划含有标准容许基，它的准备表既是单纯形表，因此单纯形法可以直接启动。算法2.1（单纯形法）P65单纯形法本质上是求解典范线性规划的算法。至此，含有标准基的线性规划问题的求解彻底解决。

定理2.13在使用单纯形法（算法2.1）求解典范线性规划时，若各次迭代出的基本容许解皆是非退化的，则算法在有限步终止。

推论2.14典范线性规划或者存在最优基本容许解，或者解无界。对于如下形式的线性规划其中。先引入非负变量将其化为典范形式然后就可以启动单纯形法。定理2.13在使用单纯形法（算法2.1）求例2.8求解线性规划P66例2.8求解线性规划P663.初始基本容许解的产生对于标准线性规划（2.54）引入个人工变量

，求解辅助线性规划——一个典范线性规划（2.55）其中。

显然（2.55）不可能无解。3.初始基本容许解的产生对于标准线性规划（2.54）引入个设（2.55）的最优值为，显然。设最优表对应的G-J方程组为（2.56）注意：与等价。（2.54）与（2.55）的关系：若，则（2.54）无解；

若，则由（2.56）可得到（2.54）的一个初始基本容许解。

以下讨论在下进行。分两种情形：

（1）在最优表中人工变量已全部退出基变量（表现为中不存在基向量）。

这时，与等价的中有了标准基，

表明（2.54）有了初始基本容许解，这时可以开始求解（2.54）（见下面的4.（1））。即设（2.55）的最优值为，显然。设最优表对应的G-J方程组为（2）在最优表中至少还有一个人工变量是基变量（表中有基向量）。

现为假设第个人工变量仍是基变量，那么它的取值为

。因为，所以。考虑（2.56）的第个方程（2.58）以下分两种情形：ⅰ）若，则（2.58）实质上成为的第个方程是多余方程，

。这表明从而的第个方程也多余。

划去第个方程，人工变量将彻底消失。ⅱ）若至少有一个不为0，不妨设

以为主元在最优表上进行换基运算，人工变量（2）在最优表中至少还有一个人工变量是基变量（表中有基向量）就会从基变量中消失。

重复以上步骤，直到人工变量全部从基变量中消失，最终的G-J方程组为这时与等价的中也有了标准基，从而

（2.54）也有了初始基本容许解，于是可以开始求解（2.54）（见下面的4.（2））。4.标准线性规划的解法

按3.求出（2.54）的初始基本容许解之后，接下来求解（2.54），与3.中的（1）、（2）对应，分别为（1）求解线性规划就会从基变量中消失。重复以上步骤，直到人工变量（2）求解线性规划总结：一般来说，解线性规划主要分为两大步：

第一步，化标准形（有时不需要）；

第二步，启动两阶段单纯形法（当标准形是典范线性规划时，直接进入第二阶段）。例求解线性规划（2）求解线性规划总结：一般来说，解线性规划主要分为两大步：例2.9求解线性规划例2.10求解线性规划例2.9求解线性规划例2.10求解线性规划2.4退化的处理

在非退化假定下，单纯形法（算法2.1）具有有限终止性（定理2.13）。取消非退化假定，情况会是怎么样？第一，算法2.1可能发生无限循环，求不到最优解；第二，适当修改选主元的规则，则可以保证单纯形法仍具有有限步终止性。1.选主元规则

单纯形法的核心是换基运算，而换基运算的首要步骤是选主元。选取主元列标的规则称为进基规则；选取主行标的规则称为退基规则。进基规则和退基规则合称选主元规则。选主元规则有多种多样，常用的进基规则有以下两种：ⅰ）最大正判别数进基规则2.4退化的处理在非退化假定下，单纯形法（算ⅱ）正判别数最小下标进基规则

选取正判别数中最小的下标作为主元的列标。算法2.2和算法2.3就采用这种进基规则。

常用的退基规则是最小行标退基规则。在使用公式（2.36）确定主元行标，若最小比值在多行上取得，则从中选取最小的行标作为主元的行标。

选取最大判别数的下标作为主元的列标。若同时有多个等值的最大正判别数，则选取其中最小的下标为主元的列标；

最大正判别数进基规则与最小行标退基规则合称Dantzig规则。算法2.1采用的就是这种规则。计算实践表明，在各种选主元规则中，Dantzig规则效果较好，在求解同一线性规划问题时，迭代次数相对较少。它的缺点是，在求解退化问题时，算法可能产生无限循环，求不到最优解。ⅱ）正判别数最小下标进基规则选取正判别数中最小2.避免循环的规则这里介绍一种最简单的避免循环的规则—Bland规则。Bland规则设在单纯形法的迭代过程中，当前容许基是关于的基容许解不是最优解，则主元列标和行标分别由如下两个规则确定：ⅰ）Bland进基规则采用正判别数最小下标进基规则，即主元列标是由此确定进基。ⅱ）Bland退基规则假定。设2.避免循环的规则这里介绍一种最简单的避免循环的规则—Bl又设则主元行标由式确定，由此确定退基。换句话说，在所有可能的退基向量中，选取下标最小的向量退基。

Bland证明：使用带有Bland规则的单纯形法求解典范线性规划，不会发生基的循环。又设则主元行标由式确定，由此确定退基。换句话说，在所有可能2.5修正单纯形法修正单纯形法是计算机实现的单纯形法。注意到，包含全部信息的单纯形表中的数据完全由基（实际是）及原始数据决定。可以就有一切。说有举例说明修正单纯形法的概貌。2.5修正单纯形法修正单纯形法是计算机实现的单纯形法。注意例如求解例如求解解建立单纯形表如下解建立单纯形表如下东北大学最优化方法全部ppt课件东北大学最优化方法全部ppt课件开始

最优化方法

（最优化课件研制组）退出主讲：张京最优化方法开始最优化方法

（最优化课件研制组）退出主讲：张京最

第三章无约束最优化方法

从本章起，以后两章将讨论非线性规划问题。本章首先讨论无约束最优化问题，其一般形式为（3.1）其中

求解无约束问题的最优化方法可以分为两大类：一类是根据目标函数的梯度（即一阶导数），有时还要根据Hesse矩阵（即二阶导数）提供的信息构造出来的方法——导数方法。本章介绍其中的最速下降法、Newton法、共轭梯度法和拟Newton法。另一类是不使用导数，仅仅利用目标函数值的信息构造出来的方法——直接方法。本章将介绍其中的步长加速法、方法加速法和单纯形替换法。两类方法各有利弊。前者收敛速度快，但需要计算梯度，甚至需要计算Hesse矩阵；后者不涉及导数，适应性强，但收敛速度慢。一般的经验是，在可以求得目标函数导数的情况下，尽可能使用导数方法。第三章无约束最优化方法从本章起，以后两3.1直线搜索

直线搜索（一维搜索）是指求解如下一元函数极小化问题（3.3）的迭代方法，其中。在微积分中，解决问题（3.3）的范围一般限于方程（3.4）可以直接解出的情况。而这里介绍的直线搜索对严格的要求。当然，对于可以求出导数的情况，相应的求解方法一般也会简单些。不作直线搜索，理论上，分为精确的和不精确的。

精确的直线搜索方法主要分为两类：一类为区间收缩法，另一类为函数逼近法。本节将相应地介绍两种常用的精确的直线搜索方法：适用于一般函数的黄金分割法和适用于一般连续函数的抛物线插值法。最后还将介绍实用的不精确一维搜索技术。3.1直线搜索直线搜索（一维搜索）是指求解如

精确的直线搜索算法的实现通常是在所谓的搜索区间上进行的1.搜索区间的确定在以下讨论中，总假定一元函数是单谷函数。定义3.1设，是

在L上的全局极小点。如果对于L上任意的两点，当时，

；当时，

，那么称是区间L上的单谷函数。下图给出了单谷函数的基本图形。精确的直线搜索算法的实现通常是在所谓的搜索区定义3.2设,是在L上的全局极小点。如果能够找到，使得

那么闭区间就称为极小点的一个搜索区间，记为

。搜索区间有时也记作，其中显然，单谷函数的定义域区间是搜索区间。单谷函数的性质。定理3.1

设是单谷函数极小点的一个搜索区间。在内任取两点

，若，则

是极小点的一个搜索区间；若

，则是极小点的一个搜索区间。直线搜索算法的第一步一般得先确定的一个

（初始）搜索区间。根据定理3.1，可以给出确定搜索区间的如下算法。定义3.2设,是在L上的全局极小点。如果能够找到，使算法3.1（确定搜索区间）已知：目标函数。选定初始点和步长。②计算，，。③若，则置，，，，，。，转⑤；否则转④。④置⑤计算，。若，则转⑥；否则转④。⑥置，（即为搜索区间），计算结束。上述过程开始时，必须选定初试点和步长。对于任意给定的，一般来说，无固定选取模式。算法3.1（确定搜索区间）已知：目标函数。选定初始点和步长。但对于在下降算法模式中所引入的而言，可选取等于0（理论上）或接近0（实际计算中）。而对于，如果选得过小，那么需要迭代许多次才能找到一个搜索区间；如果选得太大，虽然很少几步就可能把极小点包括进来，但是这又会给下一步搜索极小点的过程增加负担。下面是确定的一种比较合理而有效的方法。但对于在下降算法模式中所引入的而言，可选取等于0（理论上）或第一次迭代（，即从到的迭代）时，

的初始步长可取为1，或根据问题中出现的数据的数量级估计选定。而以后各次迭代的初始步长可按公式（3.5）计算，（3.5）其中。这是因为从到的距离一般比从到的距离小或接近，所以把按（3.5）算出的作为下一次迭代的初始步长是合适的。在实际计算中，当较小时，相应的可取得小些，而随着的增大，相应的可取得接近1。第一次迭代（，即从到的迭代）时，的初始步长可取为1，或根据东北大学最优化方法全部ppt课件2.直线搜索的方法（1）黄金分割法

黄金分割法属于区间收缩法。它适用于任何单谷函数求极小值问题。对函数除“单谷”外，不作其它要求，甚至可以不连续。因此这种方法的适用面相当广。

黄金分割法的思想是：在每次迭代中，合理地设置两个插入点的位置，以使得在计算函数值次数同样多的条件下，将区间缩小得最快。设区间的长为1。在距点分别为和的地方插入和。为了确定和，提出以下条件：

第一，希望和在中的位置是对称的。按这一条件，有2.直线搜索的方法（1）黄金分割法黄金分割即.（3.6）这样无论删去哪一段，总保留长为的区间。第二，删掉一段，例如删掉，在保留下来的区间，使得里再插入一个点在中的位置与在中的位置具有相同的比例，从而保证每次迭代都能缩小区间。按这一条件，有以同一比率即或.（3.7）把（3.7）代入（3.6）中，得到关于的一元二次方程其合理的根是（3.8）即代回（3.6），得

在古代，人们认为按比率0.618分割线段是最协调的，胜似黄金，故称黄金分割。因此，上述按比率0.618缩小搜索区间的迭代方法称为黄金分割法或0.618法。算法3.2（黄金分割法）P145代回（3.6），得在古代，人们认为按比率0.6东北大学最优化方法全部ppt课件（2）抛物线插值法

抛物线插值法属于函数逼近法。它适用于连续的单谷函数求极小值问题。抛物线插值法的思想是：设在搜索区间上连续。记

和。

如果（3.9）与（3.10）（两等号不同时成立）同时成立，那么可以过和

三点作抛物线插值，设抛物线方程为（3.11）其实是在区间上对所作的一个曲线拟合。（2）抛物线插值法抛物线插值法属于函数逼近法。记的极小点为，则根据

提供的信息，我们可以将搜索区间缩小，然后在缩小了的区间上再作抛物线插值。如此下去，最终可以求到在

中的极小点。

令(3.12）解出（3.13）记的极小点为，则根据提供的信息，我们可以将搜索区间缩小，根据插值条件和，列出关于

和的线性方程组由此解出，，并代入（3.13）中，得（3.14）根据插值条件和，列出关于和的线性方程组由此解出，，并代入（这个公式的使用条件仅仅是和

三点不共线。可以证明（习题3.5），在（3.9）和（3.10）（两等号不同时成立）同时成立的条件下，由（3.14）所确定的是的极小点，并且。以下讨论算法的终止准则和缩小搜索区间的方法。按（3.14）计算出。由极限理论知道，如果

与都很小，那么也必然很小，当然也应该很小。

计算经验指出，可以采用（3.15）

作为终止准则。这个公式的使用条件仅仅是和三点不共线。当终止准则满足时，取和中函数值较小的点提供的缩小。这个过程如下：作为极小点；当终止准则未满足时，则需要利用信息将原来的搜索区间①比较和的大小，有两种情况：若，则转②；否则，转③。②若，则置，转④；