强wolfe准则

极小广义方差法1. 引言极小广义方差法（Minimum Generalized Variance, MGV）是一种用于求解优化问题的数值方法。

它可以用于寻找一个函数的最小值点，或者在给定约束条件下找到使目标函数最小化的变量取值。

MGV方法在数学和工程领域都有广泛的应用，特别是在非线性优化、控制理论和机器学习等领域。

本文将介绍极小广义方差法的基本原理、算法步骤以及应用示例，并探讨其优缺点和改进方法。

2. 基本原理极小广义方差法是基于方差的概念进行优化的一种方法。

在确定目标函数最小时，我们希望找到一组变量取值，使得这组取值下目标函数的方差最小。

因此，MGV方法通过调整变量取值来寻找最小方差点。

具体而言，假设我们有一个目标函数f(x)，其中x是一个n维向量。

我们希望找到一个x，使得f(x)最小，并且满足一系列约束条件g(x)<=0。

那么可以定义一个新的函数J(x)，即广义方差函数：J(x) = f(x) + λ * Σ(g(x))²其中λ是一个非负的参数，用于平衡目标函数和约束条件。

当λ趋近于无穷大时，J(x)的最小值点就是满足约束条件的最小值点。

3. 算法步骤极小广义方差法包括以下几个基本步骤：步骤1：确定初始点选择一个合适的初始点x0作为算法的起始点。

步骤2：计算梯度和海森矩阵计算目标函数f(x)在当前点xk处的梯度gk和海森矩阵Hk。

梯度表示了目标函数在当前点的变化率，而海森矩阵则表示了梯度的变化率。

步骤3：求解线性方程组解决下面的线性方程组，找到一个搜索方向pk：Hk * pk = -gk这个方程组可以通过各种数值方法来求解，例如共轭梯度法、牛顿法等。

步骤4：确定步长确定一个合适的步长αk，使得在搜索方向上移动一段距离。

常用的方法有Armijo 准则、Wolfe-Powell准则等。

步骤5：更新变量更新变量xk+1 = xk + αk * pk，并计算新的目标函数值和梯度。

步骤6：判断停止条件根据一定的停止条件判断算法是否终止。

最优化共轭梯度法最优化共轭梯度法（Conjugate Gradient Method）是一种迭代求解线性方程组或优化问题的方法。

它的特点是对于二次正定函数，可以在有限次迭代内精确地求出最优解。

在非二次函数的优化问题中，共轭梯度法表现出了较好的收敛性和全局能力。

共轭梯度法的核心思想是通过选择适当的方向，使得每一次方向的梯度互相“共轭”，从而加快收敛速度。

当目标函数为二次函数时，共轭梯度法能够在有限次迭代中得到精确解；而对于非二次函数的优化问题，共轭梯度法通过先验条件选择合适的方向，最大程度地减小目标函数值。

共轭梯度法的基本步骤如下：1.初始化参数：设置初始点的位置和方向，对于非二次函数，通常选取梯度方向作为方向。

2. 计算步长：通过线方法（如Armijo准则、Wolfe准则等）定位到目标函数上降速度最快的点，并计算目标函数在该点的梯度。

3.更新方向：利用“共轭”梯度法，根据先验条件计算新的方向。

4.判断终止条件：判断目标函数值是否满足设定的终止条件，若满足则停止迭代，否则返回步骤2对于二次函数，最优化共轭梯度法表现出了优良的性能。

当目标函数是非二次函数时，共轭梯度法的表现会有所下降，但仍然比一般的梯度下降法更具有优势。

因此，共轭梯度法常被用于求解大规模线性方程组、信号处理、数字滤波、机器学习等领域。

最优化共轭梯度法的优点在于：收敛速度较快，全局能力较强，不需要存储海量信息。

然而，该方法也存在一些缺点。

首先，共轭梯度法对目标函数的性质有一定的要求，例如目标函数必须是光滑的，并且梯度向量必须是有效的。

其次，共轭梯度法对初始点的选择较为敏感，不同的初始点可能导致不同的解。

总结来说，最优化共轭梯度法是一种高效的优化算法，可以加快目标函数收敛速度，尤其适用于解决二次函数优化问题。

在非二次函数的优化问题中，共轭梯度法以其较好的收敛性和全局能力在实际应用中发挥着重要作用。

Frank-Wolfe 算法（也称为条件梯度法或梯度投影算法）是一种用于解决凸优化问题的迭代算法。

该算法的基本原理涉及到在每一步通过梯度信息在一个约束集合上寻找一个线性化的近似最优解。

以下是 Frank-Wolfe 算法的基本原理和一个简单的Python 实现。

基本原理：
给定一个凸优化问题：
min x∈C f(x)
其中f(x)是目标函数，C是一个约束集合。

Frank-Wolfe 算法的迭代步骤如下：
1.在当前点x k处计算目标函数的梯度∇f(x k)。

2.在约束集合C中找到一个关于梯度的线性化近似最优解s k。

这通常通过求
解线性子问题来实现。

3.根据线性化近似解更新当前点x k，即执行x k+1=x k+αk(s k−x k)。

4.重复上述步骤直到满足停止准则。

Python 实现：
以下是一个简单的 Python 实现，假设目标函数是二次函数：
这是一个简单的二次函数的例子。

在实际应用中，你需要替换quadratic_objective、quadratic_gradient、和quadratic_linear_oracle为实际问题中的目标函数、梯度函数和线性预测函数。

此外，可以根据实际情况选择合适的步长规则。

第九章一维搜索第九章一维搜索本章开始研究非线性规划的具体算法。

本章首先讨论一维搜索问题，又称为线搜索问题，这是以后各章中介绍的各种计算过程中的重要组成部分。

§1 一维搜索概念考虑非线性规划问题：min ().. f s t S∈x x (NP)的一维搜索问题，其中约束集nS X R ??，目标函数:f X R →。

1.1 一维搜索问题来源根据第八章中求解(NP)的基本下降算法的步骤知，已知迭代点k x 和满足条件()0k T k f ?<="" bdsfid="75" p="" s="">的搜索方向ks 后，要求步长k λ>0，使kkS λ+∈x s ，并且()()k k k k f f λ+<="" bdsfid="81" p="" s="" x="">这就是一维搜索问题，又称为线搜索问题。

这时若对所有0λ>，有kkS λ+∈x s ，则称为无限制一维搜索问题(如nS R =时)，否则称为有限制一维搜索问题。

记()()kkf ?λλ=+x s ，则一维搜索问题(1.1.2)等价于确定步长{0|}k kk S λλλ∈≥+∈x s ，使()(0)k ?λ?< (1.1.3)条件(1.1.1)等价于(0)0?'<。

我们称1()()(0)()kk k k D f f ??λ+=-=-x x 为下降量。

1.2 一维搜索分类一维搜索方法可以分成以下三类：1．简单一维搜索，即取k λ=1。

这种方法计算简便，但不一定满足下降条件(1.1.3)。

2．最优一维搜索，即取arg min ()()k k k k k Sf λλ?λλ+∈==+x s x s ，这时称k λ为最优步长。

阻尼⽜顿法（Python实现）阻尼⽜顿法（Python实现）使⽤⽜顿⽅向，分别使⽤Armijo准则和Wolfe准则来求步长求解⽅程f(x1,x2)=(x21−2)4+(x1−2x2)2的极⼩值import numpy as npimport tensorflow as tfdef fun(x): # 函数f(x)# return 100 * (x[0] ** 2 - x[1]) ** 2 + (x[0] - 1) ** 2 测试⽤return (x[0] - 2) ** 4 + (x[0] - 2 * x[1]) ** 2def hessian(x): # ⿊塞阵return np.array([[12 * (x[0] - 2) ** 2 + 2, -4],[-4, 8]], dtype=np.float32)def gfun(x): # 梯度gradx = tf.Variable(x)with tf.GradientTape() as tape:# tape.watch(x)z = fun(x)return tape.gradient(z, x).numpy()# return np.array([4 * (x[0] - 2) ** 3 + 2 * (x[0] - 2*x[1]), -4 * (x[0] - 2*x[1])])def dampnm_armijo(fun, gfun, hessian, x0): # 使⽤Armijo准则来求步长因⼦的阻尼⽜顿法maxk = 100rho = .55sigma = .4k = 0epsilon = 1e-5while k < maxk:gk = gfun(x0)Gk = hessian(x0)dk = -np.linalg.inv(Gk) @ gkif np.linalg.norm(gk) < epsilon:breakm = 0mk = 0while m < 20:if fun(x0 + rho ** m * dk) < fun(x0) + sigma * rho ** m * gk.T @ dk:mk = mbreakm += 1x0 = x0 + rho ** mk * dkk += 1x = x0val = fun(x)return x, val, kdef dampnm_wolfe(fun, gfun, hessian, x0): # 使⽤Wolfe准则来求步长因⼦的阻尼⽜顿法maxk = 1000k = 0epsilon = 1e-5while k < maxk:gk = gfun(x0)Gk = hessian(x0)dk = -np.linalg.inv(Gk) @ gkif np.linalg.norm(gk) < epsilon:break# m = 0rho = 0.4sigma = 0.5a = 0b = np.infalpha = 1# j = 0while True:if not ((fun(x0) - fun(x0 + alpha * dk)) >= (-rho * alpha * gfun(x0).T @ dk)):# j+=1b = alphaalpha = (a + alpha) / 2continueif not (gfun(x0 + alpha * dk).T @ dk >= sigma * gfun(x0).T @ dk): a = alphaalpha = np.min([2 * alpha, (alpha + b) / 2])continuebreakx0 = x0 + alpha * dkk += 1x = x0val = fun(x)return x, val, kif __name__ == '__main__':x0 = np.array([[0.], [3.]])x, val, k = dampnm_armijo(fun, gfun, hessian, x0) # Armijo准则print('近似最优点：{}\n最优值：{}\n迭代次数：{}'.format(x, val.item(), k)) x, val, k = dampnm_wolfe(fun, gfun, hessian, x0) # wolfe准则print('近似最优点：{}\n最优值：{}\n迭代次数：{}'.format(x, val.item(), k))运⾏结果：Processing math: 100%。