第七章 无约束最优化的解析法本章主要内容：最速下降法及其收敛性与收敛速度 Newton 切线法及其收敛性与收敛速度 阻尼Newton 法 共轭梯度法及其收敛性 变度量法、最小二乘法教学目的及要求：掌握最速下降法并理解其收敛性与收敛速度，掌握Newton 切线法并理解其收敛性与收敛速度，了解阻尼Newton 法；掌握共轭梯度法并理解其收敛性；了解变度量法、最小二乘法。
教学重点：最速下降法．教学难点：变度量法．教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合．教学时间：6学时．教学内容：§7.1 最速下降法考虑无约束最优化问题m i n ()f x ， （7.1.1）其中:n f R R →具有一阶连续偏导数．算法7-1（最速下降法）Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>，令0k =． Step2 检查是否满足终止准则．计算()k f x ∇，若()k f x ε∇<，迭代终止，k x 为问题（7.1.1）的近似最优解；否则，转Step3．Step3 进行一维搜索．取()k k d f x =-∇，求k λ和1k x +，使得()min ()k k k k k f x d f x d λλλ≥+=+， 1k k k k x x d λ+=+．令:1k k =+，返回Step2．特别地，考虑1m i n ()2T T f x x Qx b x c =++， （7.1.2） 其中,n n n x R Q R ⨯∈∈为正定矩阵，,n b R c R ∈∈．设第k 次迭代点为k x ，从点k x 出发沿()k f x -∇作一维搜索，得1()k k k k x x f x λ+=-∇，其中k λ为最优步长．根据定理 6.1.1，有1()()0T k k f x f x +∇∇=．而(),n f x Q x b x R∇=+∀∈， 所以1()()()k k k k f x f x Q f x λ+∇=∇-∇，从而(()())()0T k k k k f x Q f x f x λ∇-∇∇=，而Q 正定，即()()0T k k f x Q f x ∇∇>，故由上式解出()()()()T k k k T k k f x f x f x Q f x λ∇∇=∇∇， （7.1.3） 于是1()()()()()T k k k k k T k k f x f x x x f x f x Q f x +∇∇=-∇∇∇， （7.1.4） 这是最速下降法用于问题（7.1.2）的迭代公式．例1 用最速下降法求解问题2212min ()4f x x x =+， （7.1.5）其中12(,)T x x x =．取初始点(0)(1,1)T x =，允许误差0.1ε=．解 问题（7.1.5）中的f 是正定二次函数，且800,,0020Q b c ⎛⎫⎛⎫=== ⎪ ⎪⎝⎭⎝⎭．f 在点12(,)T x x x =处的梯度12()(8,2)T f x x x ∇=．第一次迭代：令搜索方向(0)(0)()(8,2)T d f x =-∇=--，(0)d ε==>，从点(0)x 出发沿(0)d 作一维搜索，由（7.1.3）式和（7.1.4）式有0680.130769520λ==， (1)(1,1)0.130769(8,2)(0.046152,0.738462)T T T x =+--=-．第二次迭代：令(1)(1)()(0.369216, 1.476924)T d f x =-∇=-，(1) 1.522375d ε==>，从点(1)x 出发沿(1)d 作一维搜索，按（7.1.4）式得(2)(0.101537,0.147682)T x =．第三次迭代：令(2)(2)()(0.812296,0.295364)T d f x =-∇=--，(2)0.864329d ε==>，按（7.1.4）式求得(3)(0.009747,0.107217)T x =-．第四次迭代：令(3)(3)()(0.077976,0.214434)T d f x =-∇=-，(3)0.228171d ε==>，按（7.1.4）式求得(4)(0.019126,0.027816)T x =．第五次迭代：令(4)(4)()(0.153008,0.055632)T d f x =-∇=--，(4)0.162807d ε==>，按（7.1.4）式求得(5)(0.001835,0.020195)T x =-．此时，(5)()f x ε∇=<，已满足精度要求，故得问题（7.1.5）的近似最优解(5)(0.001835,0.020195)T x =-．实际上问题（7.1.5）的最优解为(0,0)T x =．定理7.1.1 设:n f R R →具有一阶连续偏导数，0n x R ∈，记0()f x α=，假定水平集(,)S f α有界，令{}k x 是由最速下降法求解问题（7.1.1）产生的点列，则（1）当{}k x 是有穷点列时，其最后一个点是f 的平稳点；（2）当{}k x 是无穷点列时，它必有极限点，并且任一极限点都是f 的平稳点．定理7.1.2 设:n f R R →具有二阶连续偏导数，由最速下降法解问题（7.1.1）产生的点列{}k x 收敛于x ．若存在0ε>和0M m >>，使得当x x ε-<时，有222(),T n m y y f x y M y y R ≤∇≤∀∈， （7.1.7） 则{}k x 线性收敛于x ．§7.2 Newton 法21()()()()()()()()2T T k k k k k k f x x f x f x x x x x f x x x ϕ≈=+∇-+-∇-． 令 ()0x ϕ∇=，即2()()()0k k k f x f x x x ∇+∇-=，解之得211[()]()k k k k x x f x f x -+=-∇∇．算法7-2（Newton 法）Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>，令0k =． Step2 检查是否满足终止准则．计算()k f x ∇，若()k f x ε∇<，迭代终止，k x 为问题（7.1.1）的近似最优解；否则，转Step3．Step3 构造Newton 方向．计算21[()]k f x -∇，取21[()]()k k k d f x f x -=-∇∇． Step4 求下一个迭代点．令1k k k x x d +=+，:1k k =+，返回Step2．例2 用Newton 法求解问题（7.1.5），仍取初始点(0)(1,1)T x =，允许误差0.1ε=．解 (0)()(8,2)T f x ∇=，2(0)80()02f x ⎛⎫∇= ⎪⎝⎭，故2(0)11/80[()]01/2f x -⎛⎫∇= ⎪⎝⎭，(0)2(0)1(0)1[()]()1d f x f x -⎛⎫=-∇∇=- ⎪⎝⎭，(1)(0)(0)(1,1)(1,1)(0,0)T T T x x d =+=-=．由于 (1)()00.1f x ∇=<，迭代结束，得(1)x 为问题（7.1.5）的最优解．定理7.2.1 设:n f R R →具有三阶连续偏导数，,()0n x R f x ∈∇=，若存在0ε>和0m >，使得当x x ε-≤时，有22(),T n m y y f x y y R ≤∇∀∈， （7.2.2） 则当初始点0x 充分接近x 时，由Newton 法解问题（7.1.1）产生的点列{}k x 收敛于x ，并有二阶收敛速度．算法7-3（阻尼Newton 法）Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>，令0k =． Step2 检查是否满足终止准则．计算()k f x ∇，若()k f x ε∇<，迭代终止，k x 为问题（7.1.1）的近似最优解；否则，转Step3．Step3 构造Newton 方向．计算21[()]k f x -∇，取21[()]()k k k d f x f x -=-∇∇． Step4 进行一维搜索．求k λ和1k x +，使得()min ()k k k k k f x d f x d λλλ≥+=+， 1k k k k x x d λ+=+．令:1k k =+，返回Step2．例3 用阻尼Newton 法求解下面问题：222121min ()(1)2()f x x x x =-+-，（7.2.6） 其中12(,)T x x x =．取初始点(0)(0,0)T x =，允许误差0.1ε=．解 第一次迭代：212112212(1)8()()4()x x x x f x x x ⎛⎫----∇= ⎪-⎝⎭， 22212111168()28()84x x x x f x x ⎛⎫--+-∇= ⎪-⎝⎭， 故 (0)(0)()(2,0),()2T f x f x ε∇=-∇=>，2(0)2(0)1201/20(),[()]0401/4f x f x -⎛⎫⎛⎫∇=∇= ⎪ ⎪⎝⎭⎝⎭．于是，Newton 方向 (0)2(0)1(0)[()]()(1,0)T d f x f x -=-∇∇=，从(0)x 出发沿(0)d 作一维搜索，即求(0)(0)2400min ()min(1)2f x d λλλλλ≥≥+=-+的最优解，得到012λ=．令 (1)(0)(0)0(1/2,0)T x x d λ=+=．(1)(1)()(0,1),()1T f x f x ε∇=-∇=>．第二次迭代：2(1)2(1)184111(),[()]48124f x f x --⎛⎫⎛⎫∇=∇= ⎪ ⎪-⎝⎭⎝⎭， (1)2(1)1(1)[()]()(1/4,1/2)T d f x f x -=-∇∇=．从(1)x 出发沿(1)d 作一维搜索，即求(1)(1)24001min ()min [8(2)(2)]128f x d λλλλλ≥≥+=-+- 的最优解，得到12λ=．令(2)(1)(1)1(1,1)T x x d λ=+=．(1)(1)()(0,1),()1T f x f x ε∇=-∇=>．此时，(2)(2)()(0,0),()0T f x f x ε∇=∇=<，得问题（7.2.6）的最优解为(2)(1,1)T x =，这是惟一的最优解．定理7.2.2 设:n f R R →具有二阶连续偏导数，0n x R ∈，记0()f x α=，假定水平集(,)S f α有界，并且对一切2,()n x R f x ∈∇正定．若{}k x 是由阻尼Newton法求解问题（7.1.1）产生的点列，则（1）当{}k x 是有穷点列时，其最后一个点是f 的唯一极小点；（2）当{}k x 是无穷点列时，它必收敛于f 的唯一极小点．§7.3 共轭梯度法最速下降法和Newton 法是最基本的无约束最优化方法，它们的特性各异：前者计算量较小而收敛速度慢；后者虽然收敛速度快，但需要计算目标函数的Hesse 矩阵及其逆矩阵，故计算量大．本节介绍一类无需计算二阶导数并且收敛速度快的方法．定义 设n n Q R ⨯∈为正定矩阵．若n R 中的向量组011,,,m d d d - 满足0,,0,1,,1,T i j d Qd i j m i j =∀=-≠ ，则称011,,,m d d d - 是Q 共轭的．定理7.3.1 设n n Q R ⨯∈是正定矩阵，n R 中非零向量组011,,,m d d d - 是Q 共轭的，则这m 个向量线性无关．定理7.3.2 设n p R ∈，011,,,n d d d - 是n R 中线性无关的向量组，若p 与每个i d 都正交，则0p =．考虑正定二次函数的无约束最优化问题1min ()2T T f x x Qx b x c =++， （7.3.3） 其中n n Q R ⨯∈为正定矩阵，,n b R c R ∈∈．定理7.3.3 设n n Q R ⨯∈为正定矩阵，011,,,n d d d - 是n R 中一组Q 共轭的非零向量．对于问题（7.3.3），若从任意点0n x R ∈出发依次沿011,,,n d d d - 进行一维搜索，则至多经过n 次迭代可得问题（7.3.3）的最优解．算法7-4（共轭方向法）给定一个正定矩阵n n Q R ⨯∈．Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>． Step2 选取初始搜索方向．计算0()f x ∇，求出0d ，使00()0T f x d ∇<，令0k =． Step3 检查是否满足终止准则．若()k f x ε∇<，迭代终止；否则，转Step4． Step4 进行一维搜索．求k λ和1k x +，使得()min ()k k k k k f x d f x d λλλ≥+=+， 1k k k k x x d λ+=+．Step5 选取搜索方向．求1k d +使10,0,1,,T k j d Qd j k +== ，令:1k k =+，返回Step3．如果用共轭方向法求解正定二次函数的无约束最优化问题1min ()2T T f x x Qx b x c =++， （7.3.3） 其中n n Q R ⨯∈为正定矩阵，,n b R c R ∈∈（此时算法中的正定矩阵应与二次函数的正定矩阵一致），那么容易推出迭代公式为1()T k k k k k T k kf x d x x d d Qd +∇=-． （7.3.10） 对于求解问题（7.1.1），我们还有如下一些方法．Fletcher-Reeves （FR ）公式：212()()k k k f x f x α+∇=∇；Dixon-Myers （DM ）公式：11()()()T k k k T k k f x f x d f x α++∇∇=-∇； Polak-Ribiere-Polyak （PRP ）公式：11()[()()]()()T k k k k T k k f x f x f x f x f x α++∇∇-∇=∇∇． 算法7-5（FR 共轭梯度法）Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>． Step2 检查是否满足终止准则．计算0()f x ∇，若0()f x ε∇<，迭代终止，0x为（7.1.1）的近似最优解；否则，转Step3．Step3 构造初始搜索方向．计算00(),0d f x k =-∇=．Step4 进行一维搜索．求k λ和1k x +，使得()min ()k k k k k f x d f x d λλλ≥+=+， 1k k k k x x d λ+=+．Step5 检查是否满足终止准则．计算1()k f x +∇，若1()k f x ε+∇<，迭代终止，1k x +为（7.1.1）的近似最优解；否则，转Step6．Step6 检查迭代次数．若1k n +=，令0:n x x =，返回Step3；否则，转Step7．Step7 构造共轭方向．用FR 公式取11()k k k k d f x d α++=-∇+，212()()k k k f x f x α+∇=∇，令:1k k =+，返回Step4． 注意，如果算法7-4的Step7中k α的形式改为DM 公式或PRP 公式，则分别得到DM 共轭梯度法和PRP 共轭梯度法．定理7.3.5 设:n f R R →具有一阶连续偏导数，0n x R ∈，记0()f x α=，并假设水平集(,)S f α有界．若{}k x 是由共轭梯度法（包括任何一种仅仅与算法7-5中k α的形式不同的共轭梯度法）解问题（7.1.1）所产生的点列，则（1）当{}k x 是有穷点列时，其最后一个点是f 的平稳点；（2）当{}k x 是无穷点列时，它必有极限点，并且任一极限点都是f 的平稳点．可以证明：共轭梯度法产生的点列{}k x 是n 步二阶收敛的，即2lim sup k n k k x x q x x +→∞-≤<∞-．例4 用FR 共轭梯度法求解问题（7.2.6）222121min ()(1)2()f x x x x =-+-，仍取初始点(0)(0,0)T x =，允许误差0.1ε=．222121min ()(1)2()f x x x x =-+-解 因为212112212(1)8()()4()x x x x f x x x ⎛⎫----∇= ⎪-⎝⎭， 所以(0)(0)()(2,0),()2T f x f x ε∇=-∇=>．令(0)(0)()(2,0)T d f x =-∇=，从(0)x 出发，沿(0)d 进行一维搜索，得(1)(0)(0)001/4,(1/2,0)T x x d λλ==+=．从而(1)(1)()(0,1),()1T f x f x ε∇=-∇=>．由FR 公式有2(1)02(0)()14()f x f x α∇==∇， 因此，新的搜索方向为 (1)(1)(0)0()(1/2,1)T d f x d α=-∇+=．从(1)x 出发，沿(1)d 进行一维搜索，得(2)(1)(1)111,(1,1)T x x d λλ==+=．此时(2)(2)()(0,0),()0T f x f x ε∇=∇=<．得问题（7.2.6）的最优解为(2)(1,1)T x =．§7.4 变度量法前面介绍的最速下降法和阻尼Newton 法，它们的迭代公式可以统一为1,(),k k k k k k k x x d d G f x λ+=+⎧⎨=-∇⎩ （7.4.1）其中,n n k k G R λ⨯∈是从点k x 出发沿k d 进行一维搜索的最优步长．当k n G I =（n 阶单位矩阵）时，（7.4.1）式即为最速下降法的迭代公式；当21[()]k k G f x -=∇时，（7.4.1）式就是阻尼Newton 法的迭代公式．因此，如果能够使k G 的选取既不需要计算Hesse 矩阵及其逆矩阵，又能很好地近似于21[()]k f x -∇，则由（7.4.1）式确定的迭代算法将会保持Newton 法收敛速度快的优点，同时又具有计算简单的特性．设问题（7.1.1）中目标函数f 具有二阶连续偏导数，且2()k f x ∇正定．为使由（7.4.1）中第2式确定的搜索方向是f 在点k x 处的下降方向，根据定理1.2.3，应当要求()0T k k f x d ∇<，或即()()0T k k k f x G f x ∇∇>，所以我们应要求（7.4.1）式中的k G 是正定矩阵．设在第1k +次迭代后得到1k x +，将f 在点1k x +处作Taylor 展开，取二阶近似，得21111111()()()()()()()2TT k k k k k k f x f x f x x x x x f x x x ++++++≈+∇-+-∇-， 对上式两边求梯度，有2111()()()()k k k f x f x f x x x +++∇≈∇+∇-，令k x x =，得到2111()()()()k k k k k f x f x f x x x +++∇-∇≈∇-，即21111[()][()()]k k k k k f x f x f x x x -+++∇∇-∇≈-．易知，当f 为正定二次函数时，上式成为等式，即 21111[()][()()]k k k k k f x f x f x x x -+++∇∇-∇=-． （7.4.2）因为具有正定Hesse 矩阵的函数在极小点附近可用二次函数很好地近似，所以如果我们迫使1k G +满足类似于（7.4.2）式的关系式，即令111[()()]k k k k k G f x f x x x +++∇-∇=-， （7.4.3）则1k G +就可以很好地近似于211[()]k f x -+∇．因此称（7.4.3）式为拟Newton 条件．为方便起见，记1k k k x x x +∆=-，1()()k k k g f x f x +∆=∇-∇，1k k k G G G +∆=-，并称k G ∆为校正矩阵，则拟Newton 条件可以写成k k k k k G g x G g ∆∆=∆-∆． （7.4.4）综上所述，我们得到如下的一类算法．算法7-6（拟Newton 法）Step1 选取初始数据．选取初始点0n x R ∈和初始矩阵0G ，要求0G 为正定矩阵（可取0n G I =），给定允许误差0ε>，令0k =．Step2 检查是否满足终止准则．计算()k f x ∇，若()k f x ε∇<，迭代终止，k x 为问题（7.1.1）的近似最优解；否则，转Step3．Step3 构造搜索方向．令()k k k d G f x =-∇．Step4 进行一维搜索．求k λ和1k x +，使得()min ()k k k k k f x d f x d λλλ≥+=+， 1k k k k x x d λ+=+．Step5 产生校正矩阵．求出满足（7.4.4）的校正矩阵k G ∆，令1,:1k k k G G G k k +=+∆=+，返回Step2．算法7-7（DFP 法）Step1 选取初始数据．选取初始点0x 和初始矩阵0n G I =，给定允许误差0ε>．Step2 检查是否满足终止准则．计算0()f x ∇，若0()f x ε∇<，迭代终止，0x 为（7.1.1）的近似最优解；否则，转Step3．Step3 构造初始DFP 方向．取00()d f x =-∇，令0k =．Step4 进行一维搜索．求出k λ和1k x +，使得01()min (),.k k k k k k k k k f x d f x d x x d λλλλ≥++=+⎧⎪⎨=+⎪⎩ Step5 检查是否满足终止准则．计算1()k f x +∇，若1()k f x ε+∇<，迭代终止，1k x +为（7.1.1）的近似最优解；否则，转Step6．Step6 检查迭代次数．若1k n +=，令0:n x x =，返回Step3；否则，转Step7．Step7 构造DFP 方向．用DFP 公式1T T k k k k k k k k T T k k k k kx x G g g G G G x g g G g +∆∆∆∆=+-∆∆∆∆，算出1k G +，取111()k k k d G f x +++=-∇，令:1k k =+，返回Step4．定理7.4.4 设:n f R R →具有一阶连续偏导数，0n x R ∈，记0()f x α=，并假设水平集(,)S f α有界．若{}k x 是由DFP 法求解问题（7.1.1）产生的点列，则（1）当{}k x 是有穷点列时，其最后一个点是f 的平稳点；（2）当{}k x 是无穷点列时，它必有极限点，并且其任一极限点都是f 的平稳点．可以证明DFP 法具有超线性收敛性．算法7-8（BFGS 法）Step1 选取初始数据．选取初始点0x 和初始矩阵0n G I =，给定允许误差0ε>．Step2 检查是否满足终止准则．计算0()f x ∇，若0()f x ε∇<，迭代终止，0x 为（7.1.1）的近似最优解；否则，转Step3．Step3 构造初始BFGS 方向．取00()d f x =-∇，令0k =．Step4 进行一维搜索．求出k λ和1k x +，使得01()min (),.k k k k k k k k k f x d f x d x x d λλλλ≥++=+⎧⎪⎨=+⎪⎩ Step5 检查是否满足终止准则．计算1()k f x +∇，若1()k f x ε+∇<，迭代终止，1k x +为（7.1.1）的近似最优解；否则，转Step6．Step6 检查迭代次数．若1k n +=，令0:n x x =，返回Step3；否则，转Step7． Step7 构造BFGS 方向．用BFGS 公式111()T T T T k k k k k k k k k k k k k T T T k k k k k kx x g G g G G x g G G g x x g x g x g +⎛⎫∆∆∆∆=++-∆∆+∆∆ ⎪∆∆∆∆∆∆⎝⎭， 算出1k G +，取111()k k k d G f x +++=-∇，令:1k k =+，返回Step4．可以证明BFGS 法具有超线性收敛性．§7.5 最小二乘法在实际应用中，我们经常遇到目标函数为若干个函数的平方和的最优化问题： 21min ()()mi i s x f x ==∑， （7.5.1）其中n x R ∈，一般假设m n ≥，这类问题称为最小二乘问题．当每个()i f x 都是线性函数时，问题（7.5.1）称为线性最小二乘问题，否则，称为非线性最小二乘问题．由于最小二乘问题相对于一般无约束最优化问题而言具有特殊形式，因此除能运用本章前面介绍的一般求解方法外，还应有更为简便有效的方法．一、线性最小二乘法当()i f x 为线性函数时，即1(),1,2,,ni ij j i j f x a x b i m ==-=∑ ，问题（7.5.1）就成为线性最小二乘问题．如令11111,n m mn m a a b A b a a b ⎛⎫⎛⎫ ⎪ ⎪== ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭，12()((),(),,())T m f x f x f x f x = ，则 2()()()()()T T s x f x f x Ax b Ax b Ax b ==--=-， 从而问题（7.5.1）可表示为2min ()s x Ax b =-． （7.5.2） 因为()()()2T T T T T s x Ax b Ax b x A Ax b Ax b b =--=-+，所以()s x 为二次函数，且2()22,()2T T T s x A Ax A b s x A A ∇=-∇=．显然，对一切n y R ∈，均有20T T y A Ay Ay =≥，即知，T A A 是半正定矩阵，从而由定理2.3.7知，()s x 是n R 上的凸函数．定理7.5.1 n x R ∈是问题（7.5.2）的最优解的充要条件是x 满足方程组T T A Ax A b =． （7.5.3） 容易知道，矩阵T A A 正定的充要条件是对于一切非零向量n y R ∈，有20T T y A Ay Ay =>．记1212(,,,),(,,,)T n n y y y y A p p p == ，则上式等价于10nj j j Ay p y ==≠∑． （7.5.4）而（7.5.4）式成立的充要条件是向量组12,,,n p p p 线性无关，这又等价于rank A n =．从而T A A 为正定矩阵的充要条件是rank A n =，换句话说，()s x 为正定二次函数的充要条件是rank A n =．定理7.5.2 若rank A n =，则1()T T x A A A b -= （7.5.5）为问题（7.5.2）的唯一最优解．显然，方程组Ax b =有解的充分必要条件是问题（7.5.2）的最优值min ()0s x =．例5 求解线性最小二乘问题 2min Ax b -， （7.5.6）其中31223,3141A b ⎛⎫⎛⎫ ⎪ ⎪=-=- ⎪ ⎪ ⎪ ⎪--⎝⎭⎝⎭．解 因为11472671,()726714350T T A A A A --⎛⎫⎛⎫== ⎪ ⎪-⎝⎭⎝⎭，所以，由公式（7.5.5），求得问题（7.5.6）的最优解22673213/14137141343/103501x ⎛⎫-⎛⎫⎛⎫⎛⎫ ⎪=-= ⎪⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭ ⎪-⎝⎭． 由于问题（7.5.6）的最优值为()()11.454285710T Ax b Ax b --=≠．因此，方程组12121232,233,41x x x x x x +=⎧⎪-=-⎨⎪-+=-⎩无解．二、Gauss-Newton 法现在讨论非线性最小二乘问题2m i n ()()s x f x =， （7.5.7） 其中12,()((),(),,()),()n T m i x R f x f x f x f x f x ∈= 不全是线性函数，且假定()i f x 具有一阶连续偏导数，1,2,,i m = ．算法7-9（阻尼Gauss-Newton 法）Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>，令0k =． Step2 检查是否满足终止准则．计算()k f x 及Jacobi 矩阵()k f x ∇，若()()T k k f x f x ε∇<，迭代终止，k x 为问题（7.5.7）的近似极小点；否则，转Step3．Step3 构造Gauss-Newton 方向．计算1[()()]T k k f x f x -∇∇，取1[()()]()()T T k k k k k d f x f x f x f x -=-∇∇∇．Step4 进行一维搜索．求k λ和1k x +，使得()min ()k k k k k s x d s x d λλλ≥+=+， 1k k k k x x d λ+=+．令:1k k =+，返回Step2．同阻尼Newton 法一样，阻尼Gauss-Newton 法具有全局收敛性．三、Levenberg-Marquardt 法算法7-10（LM 法）Step1 选取初始数据．选取初始点0x ，给定初始参数00α>，放大因子1β>及允许误差0ε>，令0k =．Step2 求目标函数值．计算()k f x 及()k s x ． Step3 求Jacobi 矩阵．计算()k f x ∇． Step4 检查是否满足终止准则．若()()T k k f x f x ε∇<，迭代终止，k x 为问题（7.5.7）的近似最优解；否则，转Step5．Step5 构造LM 方向．计算1[()()]T k k k n f x f x I α-∇∇+，令1[()()]()()T T k k k k n k k d f x f x I f x f x α-=-∇∇+∇．Step6 检查目标函数是否下降．计算()k k f x d +和()k k s x d +， 若()()k k k s x d s x +<，转Step8；否则，转Step7．Step7 放大参数．令:k k αβα=，返回Step5．Step8 缩小参数．令11,/,:1k k k k k x x d k k ααβ++=+==+，返回Step2． 初始参数0α和放大因子β应取适当数值，例如，根据经验可取00.01,10αβ==．可以证明，LM 法具有全局收敛性．。
