7无约束最优化的解析法

无约束最优化问题的求解算法和应用随着科技的发展和应用领域的扩大，无约束最优化问题已经越来越成为一种关注的研究领域。

在现实生活中，无约束最优化问题的求解可以应用在多个方面，比如金融、医学、机械工程等等。

然而，在实际应用中，我们往往需要利用已经发展的优秀算法进行求解。

本文将会介绍无约束最优化问题的求解算法及其应用。

一、无约束最优化问题的概念无约束最优化问题指的是在一定的条件下，通过调整某些变量来最大或最小化指定的目标函数。

这些变量的调整需遵守一定的限制条件，并且通过各种数值分析方法，比如数值解析和计算机数值算法等技术来求解这样的问题。

无约束最优化问题的数学形式一般为：$$ \min_{x \in \mathbb{R}^n} f(x) $$其中，$x \in \mathbb{R}^n$ 是 $n$ 维空间中的一个向量，$f(x)$ 则是目标函数，该函数需要满足一定的条件，比如连续、可微、凸等等。

当函数连续、可微的情况下，就能有效地应用求导法来求解这个问题。

二、基于梯度下降的算法在求解无约束最优化问题时，最常用的算法就是基于梯度下降的算法。

该算法通过沿着负梯度的方向一步步得逼近全局极小值。

算法的主要流程如下：1、初始化变量$x$，比如$x=0$;2、计算目标函数$ f(x)$ 的梯度 $\nabla f(x)$;3、计算下降方向 $p$，$p=-\nabla f(x)$;4、选择步长 $\alpha$，更新$x$ $x_{k+1} = x_{k} + \alpha p$;5、重复执行步骤2-4 进行更新，直到满足一定的终止条件为止。

这种方法的收敛性非常好，同时也比较容易实现。

在实际应用中，通常会将其与其他迭代方法组合使用，比如牛顿、拟牛顿等方法来提升其求解精度。

三、基于共轭梯度的算法基于梯度下降的算法虽然求解精度较好，但是当求解目标函数具有高度弱凸性质时，算法的收敛速度会相对较慢。

为了克服这类问题，研究人员往往会采用共轭梯度法。

第七章 无约束最优化的解析法本章主要内容：最速下降法及其收敛性与收敛速度 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 法具有全局收敛性．。

无约束优化问题的求解方法无约束优化问题是指在不考虑任何限制条件下，通过调整自变量来寻找函数的最大值或最小值的问题。

在数学和工程领域中，无约束优化问题是一个重要的研究方向，其解决方法也非常丰富和多样。

下面将介绍几种常用的无约束优化问题求解方法。

一、梯度下降法梯度下降法是一种基于一阶导数信息的优化算法。

其基本思想是通过不断迭代地朝着函数的负梯度方向进行搜索，从而找到函数的极小值点。

具体来说，梯度下降法的迭代公式如下：x_(x+1)=x_x−x∇x(x_x)，其中x_x代表第x次迭代的自变量的取值，x称为学习率，∇x(x_x)是函数x(x_x)在点x_x处的梯度。

梯度下降法是求解无约束优化问题的常用方法，具有易于实现和收敛性等优点。

但是，梯度下降法有时可能会陷入局部最优解，因此需要进行多次尝试或采用改进的算法。

二、共轭梯度法共轭梯度法是一种基于二阶导数信息的优化算法。

其基本原理是通过逆Hessian矩阵的乘法来更新自变量的取值，从而加速搜索速度。

具体来说，共轭梯度法的迭代公式如下：x_(x+1)=x_x−x_x,x∇x(x_x)，x_x,x=x∇x(x_x)+x_x,x−1共轭梯度法具有高效、迭代次数少、不需要存储Hessian矩阵等优点。

然而，共轭梯度法也存在一些问题，如对于某些特定的函数可能会陷入收敛困难、对于非二次函数可能收敛速度较慢等。

三、拟牛顿法拟牛顿法是一种综合利用一阶和二阶导数信息的优化算法。

其基本思想是通过利用函数在当前点处的一阶导数和二阶导数近似值来构造一个局部的二次模型，从而求解优化问题。

拟牛顿法的迭代公式如下：x_(x+1)=x_x−(x_x)^−1∇x(x_x)，x_x是拟牛顿法的Hessian矩阵近似值。

拟牛顿法具有利用了二阶导数信息、不需要进行二阶导数计算、有较好的全局收敛性等优点。

但是，拟牛顿法也存在一些问题，如需要存储和更新Hessian矩阵近似值、对于非光滑函数可能无法收敛等。