无约束规划方法 迭代法的基本步骤 下降算法类 拟牛顿算法 共轭方向算法类 1/68 无约束优化是指在没有任何约束条件限制下，寻找目标函数的最优解的问题。这个 问题可以形式化地表示为： minimize f(x) s.t.x\in R^n 其中，Sf:R^n\to RS是一个实数值函数，SxS是一个$n$维向量。在这个问题中， $x$可以取任何实数值，没有任何限制。 无约束优化在实际应用中有很多重要的现实意义。例如，在工程设计中，需要寻找 一些参数的最优值，以实现最佳的性能和成本效益。这些参数可以表示为一个向量 SxS,目标函数Sf(x)$表示系统的性能和成本。无约束优化可以帮助工程师和设计师 寻找最优的参数值，从而实现最佳的性能和成本效益。 另一个重要的应用是机器学习和深度学习中的模型训练问题。在这些问题中，需要 寻找一组参数，使得模型的预测误差最小化。这些参数可以表示为一个向量SxS, 目标函数Sf(x)$表示模型的预测误差。无约束优化可以帮助机器学习算法找到最优 的参数，从而提高模型的预测准确性和性能。 除了以上两个例子，无约束优化还在经济学、物理学、金融学、计算机科学等领域 中得到广泛应用。 1
无约束优化是指在没有任何约束条件限制下，寻找目标函数的最优解的问题。这个 问题可以形式化地表示为： minimize f(x) s.t. x \in R^n 其中，$f: R^n \to R$是一个实数值函数，$x$是一个$n$维向量。在这个问题中， $x$可以取任何实数值，没有任何限制。 无约束优化在实际应用中有很多重要的现实意义。例如，在工程设计中，需要寻找 一些参数的最优值，以实现最佳的性能和成本效益。这些参数可以表示为一个向量 $x$，目标函数$f(x)$表示系统的性能和成本。无约束优化可以帮助工程师和设计师 寻找最优的参数值，从而实现最佳的性能和成本效益。 另一个重要的应用是机器学习和深度学习中的模型训练问题。在这些问题中，需要 寻找一组参数，使得模型的预测误差最小化。这些参数可以表示为一个向量$x$， 目标函数$f(x)$表示模型的预测误差。无约束优化可以帮助机器学习算法找到最优 的参数，从而提高模型的预测准确性和性能。 除了以上两个例子，无约束优化还在经济学、物理学、金融学、计算机科学等领域 中得到广泛应用。 1
一、选代法的基本结构给定初始估计x，第k次迭代的基本结构为：p,（1）确定一个搜索方向（2）确定步长αk使得维搜索问题f(x*+αp)<f(x*)(3）置xk+l=x+αkp采用不同方法构造P和不同方法寻找αk就对应不同算法。2/68无约束优化问题的解往往需要求解一个高维非线性问题，而且在大多数情况下，解析解是无法求得的。因此，通常需要使用数值优化算法来求解无约束优化问题。而迭代法是一种重要的数值优化算法，因此大多数无约束优化算法都是基于送代法的迭代法的基本思想是从一个初始解开始，逐步改进解的质量，直到达到某个终止条件。在无约束优化问题中，通常是从一个初始点开始，通过迭代计算得到目标函数的最小值点。每一次送代都会得到一个新的解，这个新的解接近目标函数的最小值点。如果终止条件满足，送代过程就会停止，此时得到的解就是目标函数的最小值点或近似最小值点。选代法的优点是适用范围广，可以用来求解各种类型的优化问题，包括无约束优化问题、约束优化问题、非线性优化问题等。此外，送代法还可以灵活地调整迭代过程中的参数和算法，以便更好地适应不同的问题和数据。因此，大多数无约束优化算法都是迭代法。这些算法包括最速下降法、共轭梯度法牛顿法、拟牛顿法等。虽然这些算法在迭代次数和收敛速度等方面有所不同，但它们都基于迭代法的基本思想，通过送代逐步优化目标函数，最终得到最优解。2
无约束优化问题的解往往需要求解一个高维非线性问题，而且在大多数情况下，解 析解是无法求得的。因此，通常需要使用数值优化算法来求解无约束优化问题。而 迭代法是一种重要的数值优化算法，因此大多数无约束优化算法都是基于迭代法的 。 迭代法的基本思想是从一个初始解开始，逐步改进解的质量，直到达到某个终止条 件。在无约束优化问题中，通常是从一个初始点开始，通过迭代计算得到目标函数 的最小值点。每一次迭代都会得到一个新的解，这个新的解接近目标函数的最小值 点。如果终止条件满足，迭代过程就会停止，此时得到的解就是目标函数的最小值 点或近似最小值点。 迭代法的优点是适用范围广，可以用来求解各种类型的优化问题，包括无约束优化 问题、约束优化问题、非线性优化问题等。此外，迭代法还可以灵活地调整迭代过 程中的参数和算法，以便更好地适应不同的问题和数据。 因此，大多数无约束优化算法都是迭代法。这些算法包括最速下降法、共轭梯度法 、牛顿法、拟牛顿法等。虽然这些算法在迭代次数和收敛速度等方面有所不同，但 它们都基于迭代法的基本思想，通过迭代逐步优化目标函数，最终得到最优解。 2
二、最速下降法（梯度法）函数值增加最快的方向送代公式：Vf(x*)xk+1 = xk +αkp如何选择下降方向？下降方向1、最速下降法（梯度法）-Vf(xk)函数值下降最快的方向搜索方向dk=-Vf(xh)(2）搜索步长：αk取最优步长，即满足f(xk+αkph)=min f(x+αph)。3/68最速下降法是一种经典的优化算法，它是代表性的迭代算法之一，也是其他许多优化算法的基础和起点。然而，由于其收敛速度较慢，实际应用中通常需要与其他更快的算法组合使用，以提高优化效率。在现代机器学习和深度学习领域，最速下降法已经被许多更加高级的算法所取代比如共轭梯度法、拟牛顿法、Adam等。这些算法综合考虑了梯度信息、历史信息等因素，使得优化过程更加高效和稳定。但是，最速下降法作为最简单、最基础的优化算法之一，仍然有其重要的地位和研究价值。3
最速下降法是一种经典的优化算法，它是代表性的迭代算法之一，也是其他许多优 化算法的基础和起点。然而，由于其收敛速度较慢，实际应用中通常需要与其他更 快的算法组合使用，以提高优化效率。 在现代机器学习和深度学习领域，最速下降法已经被许多更加高级的算法所取代， 比如共轭梯度法、拟牛顿法、Adam等。这些算法综合考虑了梯度信息、历史信息 等因素，使得优化过程更加高效和稳定。但是，最速下降法作为最简单、最基础的 优化算法之一，仍然有其重要的地位和研究价值。 3
2、最速下降法算法步骤D给定初始点xER",允许误差ε>0，令k=1。(②)计算搜索方向p=-Vf(x)；(3)若p≤8,则停止计算，x为所求极值点；否则，求最优步长α，使得f(x* +αxp")=min f(x* +α p*)。(4)令xk+1=xk+αkpk,令k:=k+1,转2。4/68该方法的思想是在每一步中，选择当前点的下降方向为函数在该点的梯度负方向并以一定的步长沿该方向送代至函数局部极小值点。具体而言，对于一个实数值函数sf(x)s，如果sf(x)s的梯度S)nablaf(x)s存在且非零，那么最速下降法的迭代公式为：Sx_[k+1)=x_k-lalpha_k /nablaf(x_k)s其中，Slalpha_ks是选代步长，可以通过线性搜索、二分搜索等方法求解
该方法的思想是在每一步中，选择当前点的下降方向为函数在该点的梯度负方向， 并以一定的步长沿该方向迭代至函数局部极小值点。 具体而言，对于一个实数值函数$f(x)$，如果$f(x)$的梯度$\nabla f(x)$存在且非零， 那么最速下降法的迭代公式为： $x_{k+1}=x_k-\alpha_k \nabla f(x_k)$ 其中，$\alpha_k$是迭代步长，可以通过线性搜索、二分搜索等方法求解。 4
例1用最速下降法求解：minf(x)=x+3x初始x=(2,1)，求迭代一次后的迭代点x2解: : Vf(x)=(2x1,6x2)T:: p’ =-Vf(x")=(-4,-6).: x+αp=(2-4α,1-6α)令 p(α)=f(x +αp)=(2-4α)+3(1-6α)求解minp(α)13令 (α)=-8(2-4α)-36(1-6α)=0 =α =6236-8x=x +αpl31'315/68下面给出一个简单的例子，说明如何使用最速下降法求解一个二次函数的极小值点当然，在实际应用中，我们通常需要考虑更加复杂的优化问题，如多维函数、非凸函数等。5
下面给出一个简单的例子，说明如何使用最速下降法求解一个二次函数的极小值点 。 当然，在实际应用中，我们通常需要考虑更加复杂的优化问题，如多维函数、非凸 函数等。 5
3、最速下降法的总体收敛性定理定理1设eCl，在最速下降法中采用精确一维搜索或不精确一维搜索，则产生的迭代点列（x）的每一个聚点是驻点。定理2设fEC，且Vf(x）≤M.对任何给定的的初始值x和?>0,采用精确一维搜索最速下降法或者有限终止，或limf(x）=-00,或limVf(x）=0遗憾的是最速下降法的整体收敛性并不能保证它是一个有效的方法。6/68最速下降法的整体收敛性并不能保证它是一个有效的优化方法，原因有以下几点：收敛速度较慢。最速下降法是一种基本的迭代算法，每次只考虑梯度信息，没有考虑历史信息，因此其收敛速度较慢。在实际应用中，通常需要使用更加高效的算法，如共轭梯度法、拟牛顿法等。可能会陷入局部极小值点。最速下降法只考虑当前点的梯度信息，容易受到局部极小值点的影响而陷入其中，无法跳出。为了避免这种情况，通常需要使用一些启发式方法，如随机化初始化、多次运行等。对于某些函数可能会表现不佳。最速下降法对于某些函数可能会表现不佳，如梯度病态问题、高阶导数信息不充分等情况。此时需要考虑其他更加高级的算法，如牛顿法、拟牛顿法等。6
最速下降法的整体收敛性并不能保证它是一个有效的优化方法，原因有以下几点： 收敛速度较慢。最速下降法是一种基本的迭代算法，每次只考虑梯度信息，没有考 虑历史信息，因此其收敛速度较慢。在实际应用中，通常需要使用更加高效的算法 ，如共轭梯度法、拟牛顿法等。 可能会陷入局部极小值点。最速下降法只考虑当前点的梯度信息，容易受到局部极 小值点的影响而陷入其中，无法跳出。为了避免这种情况，通常需要使用一些启发 式方法，如随机化初始化、多次运行等。 对于某些函数可能会表现不佳。最速下降法对于某些函数可能会表现不佳，如梯度 病态问题、高阶导数信息不充分等情况。此时需要考虑其他更加高级的算法，如牛 顿法、拟牛顿法等。 6
4、最速下降法的性质性质．设f(x)有一阶连续偏导数，若步长αk满足f(x* + αxp*)=min f(x* +αp*)则有 Vf(x+αp)pk=0 。证明:令 p(α)=f(x*+αp*),则 p'(α)=Vf(xk +αp)pk: f(xk +αkph)=min f(xk +αph).: p'(α)=Vf(xk+αkph)pk=0.注:因为梯度法的搜索方向pk+1=-Vf(x+αkp),所以(pk+1) ph =0= pk+1 Iph。7/68这个性质也被称为“正交性质”，它是由最速下降法的选代方式决定的
这个性质也被称为“正交性质”，它是由最速下降法的迭代方式决定的。 7
最速下降法的锯齿现象数值实验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当目标函数的等值线接近于一个扁长的椭球时，最速下降法开始几步下降较快，后来就出现锯齿现象，下降十分缓慢。8/68正交性质表明，最速下降法在选代的过程中可能会出现“之”字形走动的现象，即在目标函数等高线图中，算法的迭代轨迹呈现出连续的“之”字形走动。8
正交性质表明，最速下降法在迭代的过程中可能会出现“之”字形走动的现象，即 在目标函数等高线图中，算法的迭代轨迹呈现出连续的“之”字形走动。 8
三、Newton法min f(x)问题：s.t.xeR"选代公式：xk+1=x+αpk要求f(x* +α,p)<f(x*)1.Newton法的基本思想：利用f(x）在xk处的二阶Tavlor展开式的极小值点作为xk+19/68韦达在十七世纪初提出了一个多项式方程求根的算法，每一次计算精度数位增加一位。用现在的话说叫线性收敛或一阶收敛。韦达的算法解释起来很费功夫，有兴趣的读者可以参考引文[1] 。据考证，牛顿于1664年左右读到韦达的技巧，约1669年写入《分析论》（Deanalysi）。但这部书直至1711年才由威尔士数学家琼斯（WilliamJones，1675-1749）为他编辑出版。牛顿在书中改进了韦达的思路，提出一个近似求解多项式方程的新方法。以三次方程x3－2x-5=0为例。他首先注意到在2与3之间有个解（读者可以用介值定理验证），于是他把这个解写成x=2+p，代入原方程化简后得到p的三次方程p3+6P2+10p-1=0。当然，解这个新方程看起来跟老方程一样困难。但p的方程可以用上微积分的思路求解：因为p很小，它的平方和立方就更小，于是三次函数p3+6p2+10p-1可以用线性部分10p-1近似。解10p-1=0得到p=0.1。也就是×的近似从2到2.1，精确数位翻倍。然后，牛顿依法炮制，即令p=0.1+q，代入0=p3+6p2+10p-1：0=(0.1+q)3+6(0.1+q)2+10(0.1+q)-1=q3+6.3q2+11.23q+0.061=11.23q+0.061得到q~-0.0054，也就是x=2.1+q=2.0956。再令q=-0.0054+r，同法得r~0.00004852。这样经过三步以后，牛顿找到原方程的一个8位精确的近似解：9
韦达在十七世纪初提出了一个多项式方程求根的算法，每一次计算精度数位增加一 位。用现在的话说叫线性收敛或一阶收敛。韦达的算法解释起来很费功夫，有兴趣 的读者可以参考引文[1] 。 据考证，牛顿于1664年左右读到韦达的技巧，约1669年写入《分析论》（De analysi）。但这部书直至1711年才由威尔士数学家琼斯（William Jones，1675-1749 ）为他编辑出版。牛顿在书中改进了韦达的思路，提出一个近似求解多项式方程的 新方法。以三次方程x3 – 2x – 5 = 0为例。他首先注意到在2与3之间有个解（读者可 以用介值定理验证），于是他把这个解写成x = 2 + p， 代入原方程化简后得到p的 三次方程p3 + 6 P2 + 10p – 1 = 0。当然，解这个新方程看起来跟老方程一样困难。 但p的方程可以用上微积分的思路求解：因为p很小，它的平方和立方就更小，于是 三次函数p3 + 6 p2 + 10p – 1 可以用线性部分 10p – 1近似。解10p-1=0 得到 p ≈ 0.1。 也就是 x 的近似从 2 到 2.1， 精确数位翻倍。 然后，牛顿依法炮制，即令p = 0.1 + q，代入0 = p3 + 6 p2 + 10p – 1： 0= (0.1+q)3+6(0.1+q)2+10(0.1+q)-1=q3+6.3q2+11.23q+0.061≈11.23q+0.061 得到q ≈ -0.0054，也就是x=2.1+q≈2.0956 。再令q = -0.0054 + r，同法得r ≈- 0.00004852。这样经过三步以后，牛顿找到原方程的一个8位精确的近似解： 9
x=2+p+q+r=2+0.1-0.0054-0.00004852=2.09455147每算一步精确数位加倍！在其1687年首版的辉煌巨著《自然哲学的数学原理》中，牛顿求解了用于天文学的x-esinx=M这个超越方程。他将其中的正弦函数用级数展开，得到一个近似的多项式方程。然后他就可以用上述数值逼近多项式方程解的法子得到原方程的近似解正如他在二十年前所做的那样，他没有明确地用到函数的导数概念来推导这个数值方法，也没有明确提出送代概念和公式。这就是后人所知牛顿参与创立“牛顿法”的过程。牛顿的贡献是用微积分思路，在韦达方法的基础上把巴比伦方法从平方根方程x2-A=0推广到一般的多项式求根
x = 2 + p + q + r ≈ 2 + 0.1 – 0.0054 - 0.00004852 = 2.09455147 每算一步精确数位加倍！ 在其1687年首版的辉煌巨著《自然哲学的数学原理》中，牛顿求解了用于天文学的 x – e sin x = M这个超越方程。他将其中的正弦函数用级数展开，得到一个近似的多 项式方程。然后他就可以用上述数值逼近多项式方程解的法子得到原方程的近似解 。正如他在二十年前所做的那样，他没有明确地用到函数的导数概念来推导这个数 值方法，也没有明确提出迭代概念和公式。 这就是后人所知牛顿参与创立“牛顿法”的过程。牛顿的贡献是用微积分思路，在 韦达方法的基础上把巴比伦方法从平方根方程 x2-A=0 推广到一般的多项式求根。 9