第二章 无约束最优化
§1 一维搜索
对于无约束问题
(1)
的求解思路，根据上一章最优性条件的分析可有两条：
1°、若可微，则可考虑求稳定点
(2)
（2）是一非线性方程组，可以动用求解非线性方程组的手段处理，不过这也是相当复杂的问题，何况若不可微，此路便行不通，故通常都采用使目标函数逐次下降的搜索方法。
2°、搜索方法是从某一初始点出发，先选择一个下降方向，然后于方向上找一点，使，如此进行下去会得到点列，满足。设，若于处已无下降方向，则即为局部最小点。关于收敛速度有如下定义：
定义1：对于收敛于最优解的序列，若存在与无关的数，和，当从某个开始后，有
（3）
则称序列是阶收敛的。当，时，称为线性收敛，时称为超线性收敛，超线性收敛的另一种形式是，且。时称为二阶收敛，还有所谓二次收敛，它是指当一个算法用于具有对称正定矩阵的二次函数时，在有限步内可以获得它的极小点。一般说来，具有二次收敛的算法，往往具有超线性收敛性，因而属于比较好的算法之列。
对于预先给定的精度要求，作为计算结束的检验条件可采取以下几种办法之一：
i、
ii、
iii、
ⅳ、，其中是一个可接受的目标值一般的，从出发，沿着下降方向（称为搜索方向）找一，使得，则可表示成：
（4）
其中称为步长，若它的选取满足
（5）
则称搜索是精确的一维搜索，为最优步长；否则称为不精确的。一维搜索是最优化方法的基础，它有一个重要的性质：
定理1、设具有连续偏导数，而是从出发沿着方向做精确的一维搜索得到的，则：
（6）
证：设，则，因为最优步长，即，故必有，又因，故（6）成立。
一维搜索就是求一元函数的极小值，但用求稳定点的方法往往很困难，下面介绍一些常用方法。
1°、使用导数的方法。如Newton法、抛物线法、三次样条插值法、对分法等。
欲求，的根。
①考虑用在某初始点的二阶Taylor展开式近似代替：
由得
由此可得迭代公式：
， （7）
这种求一元函数最小值的方法叫Newton法。一般的，欲求，则有，号称切线法。它是二阶收敛的，缺点是对初值要求较高，其附近二阶导数须不变号。
关于算法的收敛性有如下结果：
定理2：设二次连续可微。考虑由映射定义的Newton算法，设使得和，设开始点充分接近，因而存在，，使得对满足的每一个，有：
（1），
（2）
则算法收敛于。
(2)之分子相当于与其在点的Taylor一阶展开之差，因此只有充分接近，才能保证足够小，使。
②用二次函数来近似替代：选择三点，满足两头大，中间小：，，过，，做二次函数，令，解得极小点，去掉或，对余下的三点（仍须满足两头大，中间小）重复以上步骤，直到满足精度为止，这种方法称为抛物线法，其收敛阶为1.618。
③用在两点及的函数值，及导数值，（与异号）做三次函数，使，，，，试图用的极小值点近似的极小值点。若，终止；否则，用替换或中导数与之同号者，继续迭代。这种方法称为三次样条插值法。一般来说比抛物线法敛速快。
④对分法：要求连续，，计算，去掉，中与之同号者。
若为伪凸函数即可采用上述方法。因为伪凸：1，若，由伪凸性是极小点。2，若，当，bk]。3，若，当，。此外,次数n必须满足为最后区间的长度.
2°、不用导数的方法，如“成功——失败”法、分数法、0.618法等。
①“成功——失败”法：假定已确定初始点和初始步长，若，则称搜索成功，下一步令，比较和（一般取），继续向前搜索，若，则称搜索失败，下一步反向搜索，比较和，（一般取），这样不断迭代，每次步长都要改变，直到为止。此法简单易行，且对无任何要求，因此最实用。
②分数法及0.618法。这些方法适用于单峰函数。分数法（亦称Fibonacci法）是用Fibonacci数：
计算头两个试验点:
，关于区间中点对称，比较，，去掉值较大的一段，然后取余下区间内保留之试验点的对称点为新试验点，如此继续下去，当进行（n－1）次试验后，余下的已试验点是区间的中点，最后一次试验安排在这点附近，从而得到最终剩余区间。这里n是计算函数值的次数，它是事先确定的，从而亦事先确定，所选试验点均在等分的分点上。可证，经n次试验后，区间缩短为，（剩余空间之比依次为，，，，它们的积便是），可由，确定试验次数n。
分数法是n次试验后所余空间最短者，故亦称优选法。
如果考虑使每次试验区间缩短率都相等（等于），则试验点显然应关于中点对称：
于是有，解之得。这就是0.618法，亦称黄金分割法。可证，即为分数法的极限。
0.618法比较简单，并且不必预先确定试验次数，也避免使用Fibonacci数，易于普及，但它收敛速度要比分数法慢些，并且由于累计误差的影响，试验次数以最多安排11次为宜。
如果函数是严格拟凸的（与单峰函数大体相当），则通过计算在这个区间内两点的值，不定区间能够被缩小。对此有以下定理：
定理3：设在区间上严格拟凸，设，，若，则对，;如果，则对，（不然，对前者则应有，由，矛盾）。
精确一维搜索计算量大，并且有时意义不是很大，反不如计算量小的不精确搜索效果好，后者只要求比下降一定数量，以及的绝对值比的小一定数量。现在通常采用Goldstein（1965）和Powell（1975）提出的两个条件来设计不精确一维搜索方法，即对给定常数，要求
1°、
2°、
常取。
设区间，先取，若满足要求10,2°，令;若不满足1°，令，另取，重新计算；若不满足2°，令，另取，重新计算。
§2 最优性条件考虑无约束问题(1):
定义2 下降方向。
对于问题（1），设是任一给定点，为非零向量。若存在，使，有，则称为在点的下降方向。
定理4 设在上可微，若存在向量，使得
（8）
则必为在点的下降方向。
证,由Taylor公式得
若(8)式成立，则易知定理结论成立。 证毕
若，取，(8)式自然成立，故知此时负梯度方向一定是下降方向。
定理5 设在点处可微，若是问题(1)的局部最优解，则必有
。
证,用反证法。若，则在点必存在下降方向，从而与是局部最优解的假设矛盾，故。 证毕定理6 （二阶必要条件）设在点处二阶可微，若是局部最优解，则，且Hesse矩阵半正定。
证,此时有
因是局部最优解，故当充分小时，，由的任意性知，半正定。 证毕定理7 （二阶充分条件）设二阶可微，若，正定，则是问题（1）的严格局部最优解。
证,由正定，故，于是对充分小的必有
又因，从而由Taylor公式知，。 证毕
在使用上述最优性条件的过程中，人们普遍感到求得驻点后，再计算Hesse矩阵并判断其是否正定有时相当麻烦，计算量也很大，更何况有时Hesse矩阵半正定或有些函数的极值恰好在梯度不存在的点处取得，则以上二阶充分条件便不能使用。
1986年Botsko给出了是问题（1）严格局部最优解的一阶充分条件：
定理8设表示以点为中心以δ为半径的开球，又已知元函数在内连续，且在/内可微，若/，都有
(9)
则是问题（1）严格局部最优解。
证,利用一阶Taylor公式,将f(在x点展开:
(10)
由于(9)成立,故有<0,/,于是由(10)约略有
/
严格地,由中值公式及(9),有
其中.
这说明是问题（1）严格局部最优解。 证毕
上述一阶充分条件克服了以往的某些不足，是对原最优性条件的很好补充，但由于的不确定性，这有时给检验(11)式是否成立带来一定的困难。下面的几个改进结果，可使其发挥更大的作用[33]。
1° 设表示以点为中心以为半径的开球，元函数在内连续，在/内可微，则是问题（1）的局部最优解的必要条件是
， (11)
其中 ，。
证,若是问题（1）的局部最优解,由(10)必有
,/
将，代入上式即得(11).
证毕据10可立得:
2° 在1°的假设条件下，若，满足/，且有
(12)
则一定不是问题（1）的局部最优解。
容易看出，若把条件，式中的符号“”换成“”，则它差不多还是为问题（1）的局部最优解的充分条件。特别是当f(x)在某邻域连续，且（条件极值情形）时，此条件充分性一定成立。不过若，则还需增加一定的条件，这就是下面的
3° 在 1°的假设条件下，若点/，有
，； （13）
及 ,(14)
则是问题（1）的严格局部最优解。
(14)有极限形式:
=>0 (15)
(15)用起来往往更便捷,
4°在1°的假设条件下，若是伪凹函数,且条件(11)成立,则x*是局部最优解。
由伪凹函数的性质及(11)知.必有
,i=1,…n, /
注意当/时有
其中
可取适当小,使 /,由于伪凹函数一定是拟凹函数，于是便有
)
从而为局部最优解。
50 在1°的假设条件下，若，满足
/，且对有（12）式成立，对有（13）式成立，则一定不是的极值点。
6° 在1°的假设条件下，若，满足
，且对有（12）式成立，对有（13）式成立，则一定不是的极值点。
例 判断四元函数的极值情况。
解 易解得唯一驻点（0，0，0，0）。
但，总有
；
，
故由4°知，点（0，0，0，0）不是极值点。所以，函数无极值。
§3 下降法
对于无约束问题(1)的求解思路，根据前述分析，通常都采用使目标函数逐次下降的搜索方法。在一维搜索的基础上，对于搜索方向选择的不同方式，就得到各种不同的方法。下面介绍几种常见的方法。
1° 最速下降法（梯度法）
取，则在精确一维搜索之下便有
（16）
它因目标函数局部下降最快而得名。对之有以下收敛结果：
定理9 设具连续一阶偏导数，给定，，假定水平集
有界，令{}是由最速下降法产生的点列，则{}的每一个聚点满足。
证,显然严格下降，故有极限，记，由的严格单调性知，对{}的任一收敛子列{}，亦有，设,若，则对适当小的，有
从而由连续性，必有充分接近的，使
但，故必有，矛盾。因此，必有。
由定理6知，。即相继两次迭代中，搜索方向是正交的，这使得最速下降法通过极小点的路线是锯齿形的，并且越靠近极小点步长越小，收敛越慢。这说明对局部来说下降最快的方向相对整体来说就不一定是下降最快的方向，可能走许多弯路。
为了克服梯度正交的现象，人们曾采用缩小（乘以0.9）的作法，也常用
（称为加速步）来代替的方向（称为平行切线法或Partan 方法）。这种搜索方向的混合使用效果较好。
2° Newton法
把求一元函数极值的Newton迭代公式(7)用于多元函数，即选择搜索方向为
（17）
称为Newton方向，便有
（18）
此即Newton法的迭代公式。
若正定，则可证Newton法产生的点列收敛到极小点。
3° 变尺度法
（Ⅰ）基本原理
最速下降法和Newton法可统一成
（19）
其中是n 阶对称矩阵，是最优步长。当时，（19）为最速下降法（16）。当时，则得Newton法（18）。前者收敛太慢，后者要计算二阶导数和求逆，工作量太大，在变量较多或因次较高时，几乎不能应用。因此，如能做到的选取既不需要计算二阶导数矩阵和求逆，又能逐步逼近，那么由（19）确定的算法可能会收敛得快，而计算也简单，变尺度法就是由这样的考虑而构造出来的。
首先，希望算法具有下降性质，即
由（19）知，只要对称正定即可。
其次，要求间的迭代具有简单的递推形式，而避免求逆：
（20）
其中称为修正矩阵。
最后要求。为此，将在点展开，得
两边求导，得
（21）
令，得
当正定时，有
因此，若令
（22）
那么，就可以很好地近似于，(22)式称为拟Newton条件
（Quasi－Newton condition）
若令 （23）
则（22）可简记为
将代入(22)/，可得
（24）
满足上式条件的有无穷多，因此由拟Newton条件（22）式确定的是一族算法。
（Ⅱ）秩1修正算法
显然，修正矩阵简单化是考虑问题的出发点之一，其简单程度可用秩的多少来恒量，故先想到秩1修正。于（24）式易见，若向量使，可得
（25）
修正（25）是秩1修正。容易验证，对之，拟Newton条件（22）式成立。由于与矩阵的逆近似，故此类修正又称为单秩逆修正。
可取及（对称）等，但效果均不佳。如果选择
（26）
其中，，是绝对值最大分量（设为第个）的绝对值，则不仅效果奇佳，而且计算更简单（这时），同时可证，由此引出的算法具超线性收敛性[31]。
如果，令，则有
（27）
称为正修正，若令
（28）
则得秩1正修正。特别地，如令，则得著名的Broyden秩1修正：
（29）
此修正对于解非线性方程组很有效。
（Ⅲ）秩2修正算法
（ⅰ）DFP算法（Davidon Fletcher 和Powell）
设想
代入(24)，得
令 ，则得
所以有 （30）
这就是DFP变尺度法的计算公式。
（ⅱ）BFGS算法
它是由Broyden Fletcher Goldfarb和Shanno等人于1970年给出的，公式如下：
（31）
(30)式与(31)式关系密切，若将(30)式中的与互换，并将换成，就得(31)式的正修正：
反之亦然。
可以证明，（30）式与（31）式都满足拟Newton方程且具有正定性的传递性，由它们产生的点列超线性收敛，特别是BFGS算法比DFP算法更具有数值稳定性和存储量少的特点，即使对精确度不高的不精确一维搜索，也能证明它是超线性收敛的，因此，得到广泛应用。
（ⅲ）强拟Newton算法[32]
由拟Newton条件（22）的推导可知，如果也很接近的话，则在（21）中，令便成立
（32）
可以想见，如果令满足
（33）
则与将有更好的接近度，而已往构造的，例如，DFP算法（30），BFGS算法（31），对于非二次函数一般不满足（33）。易证（33）等价于
（34）
当时，称（33）或（34）为强拟Newton条件。满足强拟Newton条件的一般不再有对称性和正定性，规模也随的增大而增大。关键在如何求解（34）。
注意（34）可写成
（35）
式中
均为已知的阶矩阵，为所求阶矩阵，将（35）转置得
（36）
今的每一列均是未知变量，可见（36）实际上是具相同系数矩阵的个不同的方程组，于是可得下表
（37）
这里是人工变量（作用后叙）。对于表（37），按照通常的Gauss消元，一举可求出个方程组的基本解，表（37）中竖线右边第列恰为之第列里基变量的值（其余变量均取0值），从而可得 。求的计算量为，若较小，，其实只有。
值的选取有相当的灵活性，但适当与否至关重要，它的大小取决于之间的接近程度。若保持不变，则迭代中增加一个拟Newton条件（相当个约束条件）的同时，需去掉另一个，这相当于在表(37)中增加一行，再减掉一行；不过在减掉一行之前，为消除其影响，应以原来该行所加人工变量一列中任一非零元素为主元，实行一次Gauss消元，然后将该主元所在行换成要增加的一行，再于该行选一主元实行一次Gauss消元，即可得一新的迭代矩阵。可见，即使很大，充其量，计算量只有，并且也不必象DFP等算法那样，迭代步后，须令，重新开始，对、的要求也放宽许多，如、的对称正定性等。
由于未必对称正定，故迭代程序应为
（38）
当时，（36）中的都是n阶矩阵，若初始矩阵 非奇异，则迭代具有非奇异传递性，具递推性质，算法（38）具二次收敛性和超线性收敛性。注意：此时，由于对未提出任何要求，因此，即使出现降秩现象，导致奇异对收敛性也无影响。
例2 求解问题
解,取初始点，梯度模允许误差
取 ，
经一维搜索，可得，于是得
据此表(37)，有形式：
44.73 -22.72 1
2.70 -1.49
-1.97 1 0.044
-0.11884 0.06558
从而得
于是
再经一维搜索，得
于是有形式（略去了人工变量）：
44.73 -22.72
0.642 -1.28
2.70 -1.49
0 -0.16
1 0
0 1
0.0810 0.0405
0.0406 0.1453
从而得
（接近对称）
已满足要求，它比用DFP算法迭代7步的结果还好。
§1 一维搜索
对于无约束问题
(1)
的求解思路，根据上一章最优性条件的分析可有两条：
1°、若可微，则可考虑求稳定点
(2)
（2）是一非线性方程组，可以动用求解非线性方程组的手段处理，不过这也是相当复杂的问题，何况若不可微，此路便行不通，故通常都采用使目标函数逐次下降的搜索方法。
2°、搜索方法是从某一初始点出发，先选择一个下降方向，然后于方向上找一点，使，如此进行下去会得到点列，满足。设，若于处已无下降方向，则即为局部最小点。关于收敛速度有如下定义：
定义1：对于收敛于最优解的序列，若存在与无关的数，和，当从某个开始后，有
（3）
则称序列是阶收敛的。当，时，称为线性收敛，时称为超线性收敛，超线性收敛的另一种形式是，且。时称为二阶收敛，还有所谓二次收敛，它是指当一个算法用于具有对称正定矩阵的二次函数时，在有限步内可以获得它的极小点。一般说来，具有二次收敛的算法，往往具有超线性收敛性，因而属于比较好的算法之列。
对于预先给定的精度要求，作为计算结束的检验条件可采取以下几种办法之一：
i、
ii、
iii、
ⅳ、，其中是一个可接受的目标值一般的，从出发，沿着下降方向（称为搜索方向）找一，使得，则可表示成：
（4）
其中称为步长，若它的选取满足
（5）
则称搜索是精确的一维搜索，为最优步长；否则称为不精确的。一维搜索是最优化方法的基础，它有一个重要的性质：
定理1、设具有连续偏导数，而是从出发沿着方向做精确的一维搜索得到的，则：
（6）
证：设，则，因为最优步长，即，故必有，又因，故（6）成立。
一维搜索就是求一元函数的极小值，但用求稳定点的方法往往很困难，下面介绍一些常用方法。
1°、使用导数的方法。如Newton法、抛物线法、三次样条插值法、对分法等。
欲求，的根。
①考虑用在某初始点的二阶Taylor展开式近似代替：
由得
由此可得迭代公式：
， （7）
这种求一元函数最小值的方法叫Newton法。一般的，欲求，则有，号称切线法。它是二阶收敛的，缺点是对初值要求较高，其附近二阶导数须不变号。
关于算法的收敛性有如下结果：
定理2：设二次连续可微。考虑由映射定义的Newton算法，设使得和，设开始点充分接近，因而存在，，使得对满足的每一个，有：
（1），
（2）
则算法收敛于。
(2)之分子相当于与其在点的Taylor一阶展开之差，因此只有充分接近，才能保证足够小，使。
②用二次函数来近似替代：选择三点，满足两头大，中间小：，，过，，做二次函数，令，解得极小点，去掉或，对余下的三点（仍须满足两头大，中间小）重复以上步骤，直到满足精度为止，这种方法称为抛物线法，其收敛阶为1.618。
③用在两点及的函数值，及导数值，（与异号）做三次函数，使，，，，试图用的极小值点近似的极小值点。若，终止；否则，用替换或中导数与之同号者，继续迭代。这种方法称为三次样条插值法。一般来说比抛物线法敛速快。
④对分法：要求连续，，计算，去掉，中与之同号者。
若为伪凸函数即可采用上述方法。因为伪凸：1，若，由伪凸性是极小点。2，若，当，bk]。3，若，当，。此外,次数n必须满足为最后区间的长度.
2°、不用导数的方法，如“成功——失败”法、分数法、0.618法等。
①“成功——失败”法：假定已确定初始点和初始步长，若，则称搜索成功，下一步令，比较和（一般取），继续向前搜索，若，则称搜索失败，下一步反向搜索，比较和，（一般取），这样不断迭代，每次步长都要改变，直到为止。此法简单易行，且对无任何要求，因此最实用。
②分数法及0.618法。这些方法适用于单峰函数。分数法（亦称Fibonacci法）是用Fibonacci数：
计算头两个试验点:
，关于区间中点对称，比较，，去掉值较大的一段，然后取余下区间内保留之试验点的对称点为新试验点，如此继续下去，当进行（n－1）次试验后，余下的已试验点是区间的中点，最后一次试验安排在这点附近，从而得到最终剩余区间。这里n是计算函数值的次数，它是事先确定的，从而亦事先确定，所选试验点均在等分的分点上。可证，经n次试验后，区间缩短为，（剩余空间之比依次为，，，，它们的积便是），可由，确定试验次数n。
分数法是n次试验后所余空间最短者，故亦称优选法。
如果考虑使每次试验区间缩短率都相等（等于），则试验点显然应关于中点对称：
于是有，解之得。这就是0.618法，亦称黄金分割法。可证，即为分数法的极限。
0.618法比较简单，并且不必预先确定试验次数，也避免使用Fibonacci数，易于普及，但它收敛速度要比分数法慢些，并且由于累计误差的影响，试验次数以最多安排11次为宜。
如果函数是严格拟凸的（与单峰函数大体相当），则通过计算在这个区间内两点的值，不定区间能够被缩小。对此有以下定理：
定理3：设在区间上严格拟凸，设，，若，则对，;如果，则对，（不然，对前者则应有，由，矛盾）。
精确一维搜索计算量大，并且有时意义不是很大，反不如计算量小的不精确搜索效果好，后者只要求比下降一定数量，以及的绝对值比的小一定数量。现在通常采用Goldstein（1965）和Powell（1975）提出的两个条件来设计不精确一维搜索方法，即对给定常数，要求
1°、
2°、
常取。
设区间，先取，若满足要求10,2°，令;若不满足1°，令，另取，重新计算；若不满足2°，令，另取，重新计算。
§2 最优性条件考虑无约束问题(1):
定义2 下降方向。
对于问题（1），设是任一给定点，为非零向量。若存在，使，有，则称为在点的下降方向。
定理4 设在上可微，若存在向量，使得
（8）
则必为在点的下降方向。
证,由Taylor公式得
若(8)式成立，则易知定理结论成立。 证毕
若，取，(8)式自然成立，故知此时负梯度方向一定是下降方向。
定理5 设在点处可微，若是问题(1)的局部最优解，则必有
。
证,用反证法。若，则在点必存在下降方向，从而与是局部最优解的假设矛盾，故。 证毕定理6 （二阶必要条件）设在点处二阶可微，若是局部最优解，则，且Hesse矩阵半正定。
证,此时有
因是局部最优解，故当充分小时，，由的任意性知，半正定。 证毕定理7 （二阶充分条件）设二阶可微，若，正定，则是问题（1）的严格局部最优解。
证,由正定，故，于是对充分小的必有
又因，从而由Taylor公式知，。 证毕
在使用上述最优性条件的过程中，人们普遍感到求得驻点后，再计算Hesse矩阵并判断其是否正定有时相当麻烦，计算量也很大，更何况有时Hesse矩阵半正定或有些函数的极值恰好在梯度不存在的点处取得，则以上二阶充分条件便不能使用。
1986年Botsko给出了是问题（1）严格局部最优解的一阶充分条件：
定理8设表示以点为中心以δ为半径的开球，又已知元函数在内连续，且在/内可微，若/，都有
(9)
则是问题（1）严格局部最优解。
证,利用一阶Taylor公式,将f(在x点展开:
(10)
由于(9)成立,故有<0,/,于是由(10)约略有
/
严格地,由中值公式及(9),有
其中.
这说明是问题（1）严格局部最优解。 证毕
上述一阶充分条件克服了以往的某些不足，是对原最优性条件的很好补充，但由于的不确定性，这有时给检验(11)式是否成立带来一定的困难。下面的几个改进结果，可使其发挥更大的作用[33]。
1° 设表示以点为中心以为半径的开球，元函数在内连续，在/内可微，则是问题（1）的局部最优解的必要条件是
， (11)
其中 ，。
证,若是问题（1）的局部最优解,由(10)必有
,/
将，代入上式即得(11).
证毕据10可立得:
2° 在1°的假设条件下，若，满足/，且有
(12)
则一定不是问题（1）的局部最优解。
容易看出，若把条件，式中的符号“”换成“”，则它差不多还是为问题（1）的局部最优解的充分条件。特别是当f(x)在某邻域连续，且（条件极值情形）时，此条件充分性一定成立。不过若，则还需增加一定的条件，这就是下面的
3° 在 1°的假设条件下，若点/，有
，； （13）
及 ,(14)
则是问题（1）的严格局部最优解。
(14)有极限形式:
=>0 (15)
(15)用起来往往更便捷,
4°在1°的假设条件下，若是伪凹函数,且条件(11)成立,则x*是局部最优解。
由伪凹函数的性质及(11)知.必有
,i=1,…n, /
注意当/时有
其中
可取适当小,使 /,由于伪凹函数一定是拟凹函数，于是便有
)
从而为局部最优解。
50 在1°的假设条件下，若，满足
/，且对有（12）式成立，对有（13）式成立，则一定不是的极值点。
6° 在1°的假设条件下，若，满足
，且对有（12）式成立，对有（13）式成立，则一定不是的极值点。
例 判断四元函数的极值情况。
解 易解得唯一驻点（0，0，0，0）。
但，总有
；
，
故由4°知，点（0，0，0，0）不是极值点。所以，函数无极值。
§3 下降法
对于无约束问题(1)的求解思路，根据前述分析，通常都采用使目标函数逐次下降的搜索方法。在一维搜索的基础上，对于搜索方向选择的不同方式，就得到各种不同的方法。下面介绍几种常见的方法。
1° 最速下降法（梯度法）
取，则在精确一维搜索之下便有
（16）
它因目标函数局部下降最快而得名。对之有以下收敛结果：
定理9 设具连续一阶偏导数，给定，，假定水平集
有界，令{}是由最速下降法产生的点列，则{}的每一个聚点满足。
证,显然严格下降，故有极限，记，由的严格单调性知，对{}的任一收敛子列{}，亦有，设,若，则对适当小的，有
从而由连续性，必有充分接近的，使
但，故必有，矛盾。因此，必有。
由定理6知，。即相继两次迭代中，搜索方向是正交的，这使得最速下降法通过极小点的路线是锯齿形的，并且越靠近极小点步长越小，收敛越慢。这说明对局部来说下降最快的方向相对整体来说就不一定是下降最快的方向，可能走许多弯路。
为了克服梯度正交的现象，人们曾采用缩小（乘以0.9）的作法，也常用
（称为加速步）来代替的方向（称为平行切线法或Partan 方法）。这种搜索方向的混合使用效果较好。
2° Newton法
把求一元函数极值的Newton迭代公式(7)用于多元函数，即选择搜索方向为
（17）
称为Newton方向，便有
（18）
此即Newton法的迭代公式。
若正定，则可证Newton法产生的点列收敛到极小点。
3° 变尺度法
（Ⅰ）基本原理
最速下降法和Newton法可统一成
（19）
其中是n 阶对称矩阵，是最优步长。当时，（19）为最速下降法（16）。当时，则得Newton法（18）。前者收敛太慢，后者要计算二阶导数和求逆，工作量太大，在变量较多或因次较高时，几乎不能应用。因此，如能做到的选取既不需要计算二阶导数矩阵和求逆，又能逐步逼近，那么由（19）确定的算法可能会收敛得快，而计算也简单，变尺度法就是由这样的考虑而构造出来的。
首先，希望算法具有下降性质，即
由（19）知，只要对称正定即可。
其次，要求间的迭代具有简单的递推形式，而避免求逆：
（20）
其中称为修正矩阵。
最后要求。为此，将在点展开，得
两边求导，得
（21）
令，得
当正定时，有
因此，若令
（22）
那么，就可以很好地近似于，(22)式称为拟Newton条件
（Quasi－Newton condition）
若令 （23）
则（22）可简记为
将代入(22)/，可得
（24）
满足上式条件的有无穷多，因此由拟Newton条件（22）式确定的是一族算法。
（Ⅱ）秩1修正算法
显然，修正矩阵简单化是考虑问题的出发点之一，其简单程度可用秩的多少来恒量，故先想到秩1修正。于（24）式易见，若向量使，可得
（25）
修正（25）是秩1修正。容易验证，对之，拟Newton条件（22）式成立。由于与矩阵的逆近似，故此类修正又称为单秩逆修正。
可取及（对称）等，但效果均不佳。如果选择
（26）
其中，，是绝对值最大分量（设为第个）的绝对值，则不仅效果奇佳，而且计算更简单（这时），同时可证，由此引出的算法具超线性收敛性[31]。
如果，令，则有
（27）
称为正修正，若令
（28）
则得秩1正修正。特别地，如令，则得著名的Broyden秩1修正：
（29）
此修正对于解非线性方程组很有效。
（Ⅲ）秩2修正算法
（ⅰ）DFP算法（Davidon Fletcher 和Powell）
设想
代入(24)，得
令 ，则得
所以有 （30）
这就是DFP变尺度法的计算公式。
（ⅱ）BFGS算法
它是由Broyden Fletcher Goldfarb和Shanno等人于1970年给出的，公式如下：
（31）
(30)式与(31)式关系密切，若将(30)式中的与互换，并将换成，就得(31)式的正修正：
反之亦然。
可以证明，（30）式与（31）式都满足拟Newton方程且具有正定性的传递性，由它们产生的点列超线性收敛，特别是BFGS算法比DFP算法更具有数值稳定性和存储量少的特点，即使对精确度不高的不精确一维搜索，也能证明它是超线性收敛的，因此，得到广泛应用。
（ⅲ）强拟Newton算法[32]
由拟Newton条件（22）的推导可知，如果也很接近的话，则在（21）中，令便成立
（32）
可以想见，如果令满足
（33）
则与将有更好的接近度，而已往构造的，例如，DFP算法（30），BFGS算法（31），对于非二次函数一般不满足（33）。易证（33）等价于
（34）
当时，称（33）或（34）为强拟Newton条件。满足强拟Newton条件的一般不再有对称性和正定性，规模也随的增大而增大。关键在如何求解（34）。
注意（34）可写成
（35）
式中
均为已知的阶矩阵，为所求阶矩阵，将（35）转置得
（36）
今的每一列均是未知变量，可见（36）实际上是具相同系数矩阵的个不同的方程组，于是可得下表
（37）
这里是人工变量（作用后叙）。对于表（37），按照通常的Gauss消元，一举可求出个方程组的基本解，表（37）中竖线右边第列恰为之第列里基变量的值（其余变量均取0值），从而可得 。求的计算量为，若较小，，其实只有。
值的选取有相当的灵活性，但适当与否至关重要，它的大小取决于之间的接近程度。若保持不变，则迭代中增加一个拟Newton条件（相当个约束条件）的同时，需去掉另一个，这相当于在表(37)中增加一行，再减掉一行；不过在减掉一行之前，为消除其影响，应以原来该行所加人工变量一列中任一非零元素为主元，实行一次Gauss消元，然后将该主元所在行换成要增加的一行，再于该行选一主元实行一次Gauss消元，即可得一新的迭代矩阵。可见，即使很大，充其量，计算量只有，并且也不必象DFP等算法那样，迭代步后，须令，重新开始，对、的要求也放宽许多，如、的对称正定性等。
由于未必对称正定，故迭代程序应为
（38）
当时，（36）中的都是n阶矩阵，若初始矩阵 非奇异，则迭代具有非奇异传递性，具递推性质，算法（38）具二次收敛性和超线性收敛性。注意：此时，由于对未提出任何要求，因此，即使出现降秩现象，导致奇异对收敛性也无影响。
例2 求解问题
解,取初始点，梯度模允许误差
取 ，
经一维搜索，可得，于是得
据此表(37)，有形式：
44.73 -22.72 1
2.70 -1.49
-1.97 1 0.044
-0.11884 0.06558
从而得
于是
再经一维搜索，得
于是有形式（略去了人工变量）：
44.73 -22.72
0.642 -1.28
2.70 -1.49
0 -0.16
1 0
0 1
0.0810 0.0405
0.0406 0.1453
从而得
（接近对称）
已满足要求，它比用DFP算法迭代7步的结果还好。
