下载文档原格式
第七讲无约束优化一阶方法1.最速下降法的由来最速下降法考虑无约束问题其中，函数具有一阶连续偏导数.),(min x f ,n R x 人们在处理这类问题是，总希望从某一点出发，选择一个目标函数值下降最快的方法，以利于尽快达到极小点. 基于此愿望，1847年法国数学家Cauchy 提出了最速下降法. 后来，Curry 等人作了进一步的研究，得到现在众所周知的一种最基本的方法.最速下降法利用负梯度为方向作为搜索方向.设在附近连续可微，为搜索方向向量，，由泰勒展开式得那么目标函数在处沿着方向下降的变化率如下所示：)(k k x f d -∇=)(x f k x k d )(k k x f g ∇=,0),()()(>++=+ααααo d g x f d x f k Tk k k k )(x f k x k d其中为与夹角. 要使得变化率最小，只有当值为时才能达到，也就是取得负梯度方向.ααα)()(lim 0k k k x f d x f -+→αααα)(lim 0o d g k Tk +=→θcos k T k k T k d gd g ==θk g k d k d 1-)(x f ∇)(x f ∇-cos事实上，最速下降方向也可以这样来考虑。
因为目标函数在处沿方向的变化率为，故最速下降的单位方向是如下非线性规划问题的解.根据Schwartz 不等式，有去掉绝对值符号，可以得到.由上式知，当时等号成立. 因此负梯度方向为最速下降方向.d g T k )(x f k x d d dmin d g T k ..t s 1≤d kk T k g d g d g ≤≤k T kg d g -≥k k g g d -=3.最速下降法计算步骤1.给定初始点，容许误差，令2. 计算搜索方向;3. 若，则停止计算，输出作为近似最优解；否则从出发，沿进行一维线搜索，确定步长因子，使得4. 令，令，转步骤2.n R x ∈00>ε1:=k )(k k x f d -∇=ε≤k d k x k x k d k αk k k k d x x α+=+11:+=k k 0()min ()k k k k k k k f x d f x d ααα≥+=+4.最速下降法的锯齿现象由步骤3，为求出从出发沿方向的极小点，令由此得出.即方向与正交.这表明迭代产生的序列所循路径是“之”字形的。
pytorch 使用共轭梯度法在PyTorch中，可以使用torch.optim包中的ConjugateGradient 优化器来使用共轭梯度法。
共轭梯度法是一种有效的无约束优化算法，特别适用于解决大规模线性方程组或二次优化问题。
以下是一个使用共轭梯度法解决最小二乘问题的示例：```pythonimport torchfrom torch.optim import ConjugateGradient# 定义最小二乘问题的系数矩阵和目标向量A = torch.tensor([[2, 1], [1, 2]], dtype=torch.float)b = torch.tensor([[7], [8]], dtype=torch.float)# 定义模型参数x = torch.tensor([[0], [0]], requires_grad=True)# 创建共轭梯度法优化器optimizer = ConjugateGradient([x])# 迭代优化for i in range(100):optimizer.zero_grad()loss = torch.sum(torch.square(torch.matmul(A, x) - b))loss.backward()optimizer.step()# 打印最终优化的结果print(x)```在示例中，首先定义了一个最小二乘问题的系数矩阵A和目标向量b，然后定义了模型参数x。
使用ConjugateGradient优化器来对模型参数进行优化。
在每次迭代中，首先将梯度清零，然后计算损失函数，然后通过调用backward()进行反向传播并计算梯度，最后通过调用step()更新模型参数。
最后打印出优化的结果。
注意，共轭梯度法要求损失函数是二次函数，因此在实际应用中需要根据具体情况进行相应的模型和损失函数的定义。
天津大学《最优化方法》复习题(含答案)天津大学《最优化方法》复习题（含答案）第一章 概述(包括凸规划)一、 判断与填空题1 )].([arg )(arg m in m axx f x f nnRx Rx -=∈∈ √2 {}{}.:)(min :)(max nnR D x x f R D x x f ⊆∈-=⊆∈ ⨯3 设.:R R D f n →⊆ 若nR x∈*，对于一切nR x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(minx f Dx ∈的全局最优解. ⨯4 设.:R RD f n→⊆ 若Dx∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(minx f Dx ∈的严格局部最优解. ⨯5 给定一个最优化问题，那么它的最优值是一个定值. √6 非空集合nR D ⊆为凸集当且仅当D 中任意两点连线段上任一点属于D . √7 非空集合nR D ⊆为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √8 任意两个凸集的并集为凸集. ⨯ 9 函数RR D f n→⊆:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √10 设RRD f n→⊆:为凸集D 上的可微凸函数，Dx ∈*.则对D x ∈∀，有).()()()(***-∇≤-x x x f x f x f T⨯ 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n是凸集。
√12 设{}kx 为由求解)(minx f Dx ∈的算法A 产生的迭代序列，假设算法A 为下降算法，则对{},2,1,0∈∀k ，恒有)()(1kk x f x f ≤+ .13 算法迭代时的终止准则（写出三种）：_____________________________________。
14 凸规划的全体极小点组成的集合是凸集。
√15 函数RR D f n→⊆:在点kx 沿着迭代方向}0{\n kR d∈进行精确一维线搜索的步长kα，则其搜索公式为 .16 函数RRD f n →⊆:在点kx 沿着迭代方向}0{\n kR d∈进行精确一维线搜索的步长kα，则=+∇k T k k k d d x f )(α 0 .17 设}0{\n kR d∈为点nkR D x⊆∈处关于区域D 的一个下降方向，则对于0>∀α，),0(αα∈∃使得.D d x k k∈+α⨯二、 简述题1 写出Wolfe-Powell 非精确一维线性搜索的公式。
最速下降法1.最速下降方向函数f(x)在点x处沿方向d的变化率可用方向导数来表示。
对于可微函数，方向导数等于梯度与方向的内积，即：Df(x;d) = ▽f(x)T d,因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：min ▽f(x)T ds.t. ||d|| ≤ 1当 d = -▽f(x) / ||▽f(x)||时等号成立。
因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。
2.最速下降算法最速下降法的迭代公式是x(k+1) = x(k) + λk d(k) ,其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即d = -▽f(x(k)).λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).计算步骤如下：(1)给定初点x(1) ∈ R n，允许误差ε> 0，置k = 1。
(2)计算搜索方向d = -▽f(x(k))。
(3)若||d(k)|| ≤ε，则停止计算；否则，从x(k)出发，沿d(k)进行一维搜索，求λk，使f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).(4)令x(k+1) = x(k) + λk d(k)，置k = k + 1，转步骤(2)。
共轭梯度法1.共轭方向无约束问题最优化方法的核心问题是选择搜索方向。
以正定二次函数为例，来观察两个方向关于矩阵Ａ共轭的几何意义。
设有二次函数：f(x) = 1/2 (x - x*)T A(x - x*) ,其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面1/2 (x - x*)T A(x - x*) = c是以x*为中心的椭球面，由于▽f(x*) = A(x - x*) = 0，A正定，因此x*是f(x)的极小点。
第41卷第3期玉林师范学院学报（自然科学）Vol.41,No.3 2020年6月Journal of Yulin Normal University(Natural Science)Jun.,2020靳文慧,吴庆军.无约束优化一个修正的HS三项共轭梯度法[J].玉林师范学院学报（自然科学），2020，41（3）:48-53.无约束优化一个修正的HS三项共轭梯度法靳文慧,吴庆军（玉林师范学院数学与统计学院，广西玉林537000）摘要：针对无约束优化问题，本文提出了一个修正的HS三项共轭梯度法。
基于拟牛顿方程新型割线条件，提出了具有充分下降性质的改进HS三项共轭梯度参数公式。
在弱Wolfe-Powell线搜索技术下，获得了算法的全局收敛性。
数值实验结果表明该算法是有效的。
关键词：无约束最优化；三项共轭梯度法；割线条件；充分下降搜索方向；全局收敛性中图分类号：O224文献标志码：A文章编号：1004-4671(2020):03-0048-06A Modified HS Three-term Conjugate Gradient Methodfor Unconstrained OptimizationJin Wenhui,Wu Qingjun(School of Mathematics and Statistics,Yulin Normal University,Yulin,Guangxi537000)Abstract:In this paper,a modified Hestenes-Stiefel three-term conjugate gradient method is proposed for unconstrained op⁃timization.Based on the new secant condition of quasi-Newton equation,we propose a modified Hestenes-Stiefel three-term formula,which has the sufficiently descent property without any conditions.The global convergence under weak Wolfe⁃Powell line search technique is established for general functions.Numerical experiments show that the proposed algorithm is very effective.Key words:unconstrained optimization;three-term conjugate gradient method;secant condition;sufficiently descent search direction;global convergence1IntroductionIn this paper,we consider the following unconstrained optimization problem:min x→ℜn f(x),(1) where f(x):ℜn→ℜis a continuously differentiable function that the gradient will be denoted by g.The nonlinear conjugate gradient(CG)method is one of the most effective line search methods for(1)due to its simplicity and its very low memory requirement.The iterative processes of the CG method is defined byxk+1=x k+αk d k,k=0,1,2,⋯,(2) where x k is the current iterate,αk is called the step length which is determined by some line search and d k is the searchdirection defined bydk=ìíî-g k+βk d k-1,if k≥1-g k,if k=0,(3)收稿日期：2020-01-05基金项目：广西自然科学基金项目(2018GXNSFAA281099)，广西教育厅科研项目(KY2015YB244)，玉林师范学院科研项目(2019YJKY16)。
无约束最优化中两种改进共轭梯度法的收敛性证明周安娃;范浩;黄青群【摘要】对于无约束优化中已提出的两种改进共轭梯度算法:改进的DY算法(MDY)和新的混合HS-DY算法(NH),证明了其在Wolfe线搜索下的全局收敛性.证明中的关键技巧是利用DY算法公式的一个等价公式,也正是由于该策略的运用,使得证明更为简化,进而得到了上述两种改进的共轭梯度法的全局收敛性.%Considering two modified conjugare gradient methods which had been presented: the modified DY method and the new hybrid HS-DY method for unconvex function, we explore the global convergence of these two methods with the Wolfe line search. It is very important to use a equivalence formula of DY method for the proof, which makes it simplify and shows that these modified methods are both globally convergent.【期刊名称】《桂林电子科技大学学报》【年(卷),期】2011(031)001【总页数】4页(P37-40)【关键词】共轭梯度法;下降方向;全局收敛性【作者】周安娃;范浩;黄青群【作者单位】桂林电子科技大学,数学与计算科学学院,广西,桂林,541004;桂林电子科技大学,数学与计算科学学院,广西,桂林,541004;桂林电子科技大学,数学与计算科学学院,广西,桂林,541004【正文语种】中文【中图分类】O224其中:gk是f在点xk处的梯度,βk是一参数。
