下载文档原格式
目标函数极值求解的几种方法题目：()()2221122min -+-x x，取初始点()()Tx 3,11=，分别用最速下降法，牛顿法，共轭梯度法编程实现。
一维搜索法：迭代下降算法大都具有一个共同点，这就是得到点()k x 后需要按某种规则确定一个方向()k d ，再从()k x 出发，沿方向()k d 在直线（或射线）上求目标函数的极小点，从而得到()k x 的后继点()1+k x ，重复以上做法，直至求得问题的解，这里所谓求目标函数在直线上的极小点，称为一维搜索。
一维搜索的方法很多，归纳起来大体可以分为两类，一类是试探法：采用这类方法，需要按某种方式找试探点，通过一系列的试探点来确定极小点。
另一类是函数逼近法或插值法：这类方法是用某种较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来估计目标函数的极小点。
本文采用的是第一类试探法中的黄金分割法。
原理书上有详细叙述，在这里介绍一下实现过程：⑴ 置初始区间[11,b a ]及精度要求L>0,计算试探点1λ和1μ，计算函数值()1λf 和()1μf ，计算公式是：()1111382.0a b a -+=λ，()1111618.0a b a -+=μ。
令k=1。
⑵ 若L a b k k <-则停止计算。
否则，当()K f λ>()k f μ时,转步骤⑶;当()K f λ≤()k f μ时,转步骤⑷ 。
⑶ 置k k a λ=+1,k k b b =+1,k k μλ=+1,()1111618.0++++-+=k k k k a b a μ,计算函数值()1+k f μ,转⑸。
⑷ 置k k a a =+1,k k b μ=+1,k k μμ=+1,()1111382.0++++-+=k k k k a b a λ,计算函数值()1+k f λ,转⑸。
⑸ 置k=k+1返回步骤 ⑵。
1. 最速下降法实现原理描述：在求目标函数极小值问题时,总希望从一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点,正是基于这样一种愿望提出的最速下降法,并且经过一系列理论推导研究可知,负梯度方向为最速下降方向。
最优化方法实验报告Numerical Linear Algebra And ItsApplications学生所在学院：理学院学生所在班级：计算数学10-1学生姓名：甘纯指导教师：单锐教务处2013年5月实验三实验名称：无约束最优化方法的MATLAB实现实验时间: 2013年05月10日星期三实验成绩：一、实验目的：通过本次实验的学习，进一步熟悉掌握使用MATLAB软件，并能利用该软件进行无约束最优化方法的计算。
二、实验背景：（一）最速下降法1、算法原理最速下降法的搜索方向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。
2、算法步骤用最速下降法求无约束问题n R()min的算法步骤如下：xxf，a ）给定初始点)0(x ，精度0>ε，并令k=0；b ）计算搜索方向)()()(k k x f v -∇=，其中)()(k x f ∇表示函数)(x f 在点)(k x 处的梯度；c ）若ε≤)(k v ，则停止计算；否则，从)(k x 出发，沿)(k v 进行一维搜索，即求k λ，使得)(min )()()(0)()(k k k k v x f v x f λλλ+=+≥； d ）令1,)()()1(+=+=+k k v x x k k k k λ，转b ）。
（二）牛顿法1、算法原理牛顿法是基于多元函数的泰勒展开而来的，它将)()]([-)(1)(2k k x f x f ∇∇-作为搜索方向，因此它的迭代公式可直接写出来：)()]([)(1)(2)()(k k k k x f x f x x ∇∇-=-2、算法步骤用牛顿法求无约束问题n R x x f ∈),(min 的算法步骤如下：a ）给定初始点)0(x ,精度0>ε，并令k=0；b ）若ε≤∇)()(k x f ，停止，极小点为)(k x ，否则转c ）；c ）计算)()]([,)]([)(1)(2)(1)(2k k k k x f x f p x f ∇∇-=∇--令；d ）令1,)()()1(+=+=+k k p x x k k k ，转b ）。
利用共轭梯度算法求解n元正定二次函数的极小点我利用共轭梯度算法来解决n元正定二次函数的极小点问题，并通过一个简单的函数模型来测试基于该算法的程序的正确性。
通过分析该算法后，我采用matlab7.0中的设计语言来编写程序。
matlab是集数学计算、图形处理和程序设计与以设计与一体的著名数学软件，在许多科学领域成为计算机辅助设计和分析、算法研究和应用开发的基本工具和首选平台。
一．算法条件及特点：适宜条件：无约束n元正定二次函数f(x)=1txax+bt+c2n式中ａ为n⨯n对称正定阵；ｘ，ｂ∈e；c为常数。
算法特点：未知p(i)(i=0,...,n-1)关于ａ共轭，以出任给x(0)启程，依次以p(0),p(1),...,p(n-1)为搜索方向的下述算法：minf(x(k)+λp(k))＝f(x(k)+λkp(k))λ（k+1）（k）（k）x，k=0,1,...,n-1=x+λkp二．算法步骤：（1）选择初始值近似x（0）(0)p=-∇f(x)(0)，得出容许误差ε>0，k=0。
并用x（1）=x（0）+λ0p（0）∇f(x(0))tp(0)(1)和λ0=-算出x。
(0)t(0)(p)ap(k)（3）通常地，假设已得出结论x（4）||f(x(k+1)和p（k），则可计算第k+1次近似x(k+1)：（k+1）（k）（k）=x+λkpλk：minf(x(k)+λp(k)))||2≤ε，停止计算，x(k+1)即为要求的近似解。
p（k+1）=-∇f(x(k)（k）)+βkp∇f(x(k+1))t∇f(x(k+1))βk=∇f(x(k))t∇f(x(k))k=k+1计算出βk和p（k+1），并转向第三步。
三．详尽算法中变量表明：gradf：函数的梯度。
e：终止条件ε四．模型解：已知一个二维正定二次函数f(x)=3212x1+x2-x1x2-2x1221312-x1x2-2x1化为f(x)=xtax+bt+c形式，得∙将f(x)=x12+x2222a=⎛3-1⎛⎛-2⎛⎛⎛,b=⎛⎛⎛-11⎛⎛0⎛∙初始条件x(0)⎛-2⎛=4⎛⎛，ε=0。
最优化问题的算法迭代格式最优化问题的算法迭代格式最优化问题是指在一定的条件下，寻找使某个目标函数取得极值（最大值或最小值）的变量取值。
解决最优化问题的方法有很多种，其中较为常见的是迭代法。
本文将介绍几种常用的最优化问题迭代算法及其格式。
一、梯度下降法梯度下降法是一种基于负梯度方向进行搜索的迭代算法，它通过不断地沿着目标函数的负梯度方向进行搜索，逐步接近极值点。
该方法具有收敛速度快、易于实现等优点，在许多应用领域中被广泛使用。
1. 算法描述对于目标函数 $f(x)$，初始点 $x_0$ 和学习率 $\alpha$，梯度下降算法可以描述为以下步骤：- 计算当前点 $x_k$ 的梯度 $\nabla f(x_k)$；- 更新当前点 $x_k$ 为 $x_{k+1}=x_k-\alpha\nabla f(x_k)$；- 如果满足停止条件，则输出结果；否则返回第 1 步。
2. 算法特点- 沿着负梯度方向进行搜索，能够快速收敛；- 学习率的选择对算法效果有重要影响；- 可能会陷入局部极小值。
二、共轭梯度法共轭梯度法是一种基于线性方程组求解的迭代算法，它通过不断地搜索与当前搜索方向共轭的新搜索方向，并在该方向上进行一维搜索，逐步接近极值点。
该方法具有收敛速度快、内存占用少等优点，在大规模问题中被广泛使用。
1. 算法描述对于目标函数 $f(x)$，初始点 $x_0$ 和初始搜索方向 $d_0$，共轭梯度算法可以描述为以下步骤：- 计算当前点 $x_k$ 的梯度 $\nabla f(x_k)$；- 如果满足停止条件，则输出结果；否则进行下一步；- 计算当前搜索方向 $d_k$；- 在当前搜索方向上进行一维搜索，得到最优步长 $\alpha_k$；- 更新当前点为 $x_{k+1}=x_k+\alpha_k d_k$；- 计算新的搜索方向 $d_{k+1}$；- 返回第 2 步。
2. 算法特点- 搜索方向与前面所有搜索方向都正交，能够快速收敛；- 需要存储和计算大量中间变量，内存占用较大；- 可以用于非线性问题的求解。
第一、填空题1.组成优化设计数学模型的三要素是设计变量、目标函数、约束条件。
2.函数在点处的梯度为，海赛矩阵为3.目标函数是一项设计所追求的指标的数学反映，因此对它最基本的要求是能用来评价设计的优劣，，同时必须是设计变量的可计算函数。
4.建立优化设计数学模型的基本原则是确切反映工程实际问题，的基础上力求简洁。
5.约束条件的尺度变换常称规格化，这是为改善数学模型性态常用的一种方法。
6.随机方向法所用的步长一般按加速步长法来确定，此法是指依次迭代的步长按一定的比例递增的方法。
7.最速下降法以负梯度方向作为搜索方向，因此最速下降法又称为梯度法，其收敛速度较慢。
8.二元函数在某点处取得极值的充分条件是必要条件是该点处的海赛矩阵正定9.拉格朗日乘子法的基本思想是通过增加变量将等式约束优化问题变成无约束优化问题，这种方法又被称为升维法。
10改变复合形形状的搜索方法主要有反射，扩张，收缩，压缩11坐标轮换法的基本思想是把多变量的优化问题转化为单变量的优化问题12．在选择约束条件时应特别注意避免出现相互矛盾的约束，，另外应当尽量减少不必要的约束。
13．目标函数是n维变量的函数，它的函数图像只能在n+1, 空间中描述出来，为了在n维空间中反映目标函数的变化情况，常采用目标函数等值面的方法。
14.数学规划法的迭代公式是，其核心是建立搜索方向，和计算最佳步长15协调曲线法是用来解决设计目标互相矛盾的多目标优化设计问题的。
16.机械优化设计的一般过程中，建立优化设计数学模型是首要和关键的一步，它是取得正确结果的前提。
二、名词解释1．凸规划对于约束优化问题若、都为凸函数，则称此问题为凸规划。
2．可行搜索方向是指当设计点沿该方向作微量移动时，目标函数值下降，且不会越出可行域。
3．设计空间：n个设计变量为坐标所组成的实空间，它是所有设计方案的组合4．.可靠度产品在规定的条件，规定的时间内完成规定功能的概率.5．收敛性是指某种迭代程序产生的序列收敛于6.非劣解：是指若有m个目标，当要求m-1个目标函数值不变坏时，找不到一个X，使得另一个目标函数值比，则将此为非劣解。
共轭梯度法的基本思路共轭梯度法是一种优化算法，用于求解解析式的极小值。
这种算法成功的理论和实践应用广泛，是一种效率高的算法。
它的基本思路是利用迭代的方式，不断的寻找最小值，直到收敛。
共轭梯度法不同于其他优化算法的地方在于，它利用了向量之间的共轭关系，以一种不同于其他优化算法的方式计算最小化结果。
它的初始值是一个任意的向量值。
这个向量随着迭代的进行，会不断地被更新。
每一步迭代都会朝着更小的函数值的方向移动，这个方向就是梯度的反方向。
在共轭梯度法中，每一个迭代步骤都与前一个迭代步骤保持共轭。
这意味着在这个方向上的优化将只改变尚未被改变的维度，而沿着已经优化的方向不会再次搜索。
这种方式可以减少搜索空间和时间复杂度，从而使得算法更加高效。
此外，在共轭方向上，梯度的大小也逐渐减小，这也是共轭梯度法收敛速度更快的原因。
共轭梯度法最适用于大规模计算机系统上的大规模处理任务。
它通常用于解决线性方程组，如图像处理、信号处理、网络规划等。
它可以很好的解决非对称和非正定的问题。
需要指出的是，共轭梯度法很难用来寻找全局最小值，因为它只搜索梯度反方向上的最小值。
如果初值选的不好，可能会过早陷入局部最小值。
因此，对于一些特定的问题，如非线性规划等，可能需要考虑使用其他的优化算法。
总之，共轭梯度法是一种非常有用的工具，可以帮助我们快速地解决许多优化问题。
但是，它的成功与否也与问题本身和初值的选择有很大的关系，因此在实际应用中，我们需要根据具体情况进行合理的选择和调整。
共轭梯度法对于任意形式的目标函数()f X ，在极值点*X 附近展开成泰勒级数，且取前三项，有()()()****2**1()...2TT f X f Xf X X X X X f X X X ⎡⎤⎡⎤⎡⎤⎡⎤≈+∇-+-∇-⎣⎦⎣⎦⎣⎦⎣⎦因在极值点*X 处()*0f X ∇=，而()2**()f X H X ∇=为()f X 在*X 的二阶偏导数矩阵，即Hessian 矩阵，故()****1().().2T f X f X X X H X X X ⎡⎤⎡⎤≈+--⎣⎦⎣⎦ 对于二次函数来说，若令()()()2*2*2*221122,,f X f X f X a b c x x x x ∂∂∂===∂∂∂∂则()**1(),a b H X f X d b c ⎡⎤==⎢⎥⎣⎦而—常数 则，得到()()()()()()()()()()()()()()11221212121122*1**112*2**12**112**1222****11122-1()+--2---1=+--2--1-2---2x x a b f X d x x x x b c x x a x x b x x d x x x x b x x c x x d a x x b x x x x c x x ⎡⎤⎡⎤⎢⎥⎡⎤≈⎢⎥⎣⎦⎢⎥⎣⎦⎣⎦⎡⎤+⎢⎥⎡⎤⎣⎦⎢⎥+⎣⎦⎡⎤=+++⎢⎥⎣⎦由上式可知，当12*1**2x x X X x x ⎡⎤⎡⎤===⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦时，得到目标函数的极小值()*1()f X f X d ==，当22(),,...f X d d =时，则有等值线族。
令2()f X d =，代入上式，则有()()()()112222****2111221()-2---2f X d d a x x b x x x x c x x ⎡⎤=≈+++⎢⎥⎣⎦所以目标函数()f X 在*X 点附近的等值线方程为()()()()112222****1122-2---0a x x b x x x x c x x d +++=式中，122()d d d =-=常数。
使用共轭梯度法求极小值需要满足一定的条件，最基本的是共轭梯度法只适用于求解二次凸函数的极小值问题。
下面是一个使用共轭梯度法求二次函数极小值的例子：
设二次函数f(x)=1/2x'Ax-b'x，其中A为对称矩阵，b为列向量。
1. 首先，我们需要计算函数的一阶偏导数，即梯度。
在这个例子中，f(x)的一阶偏导数为▽f(x)=Ax-b。
2. 接下来，我们使用共轭梯度法来寻找函数的极小值。
共轭梯度法的基本思想是沿着一个与当前搜索方向共轭的方向进行搜索。
在这个例子中，我们首先选择一个初始点x0，并计算在该点的梯度▽f(x0)。
3. 然后，我们计算一个新的搜索方向d0，该方向与▽f(x0)共轭。
在这个例子中，我们可以选择d0=▽f(x0)。
4. 接下来，我们沿着d0方向进行搜索，直到找到一个使函数值下降的点x1。
具体来说，我们可以使用线搜索来确定搜索步长。
在这个例子中，我们可以使用精确线搜索来确定步长。
5. 然后，我们计算在新的点x1处的梯度▽f(x1)，并根据共轭梯度法的思想计算一个新的搜索方向d1。
在这个例子中，我们可以选择d1=▽f(x1)。
6. 我们重复上述步骤，直到找到一个使函数值达到极小值的点x*。
这个例子中的二次函数f(x)=1/2x'Ax-b'x可以看作是求解Ax=b问题的等价形式。
因此，这个例子也可以看作是求解Ax=b问题的一种方法。
需要注意的是，对于一般函数需要使用非线性共轭梯度法例如FR、PR+、HS、DY等。
在数学和计算机科学领域，无约束优化问题一直是一个热门的研究课题。
而fr共轭梯度法作为一种求解无约束优化问题的重要方法，在实际应用中展现出了强大的优化能力。
本文将就fr共轭梯度法求解无约束优化问题进行全面评估和探讨。
1. 无约束优化问题的定义无约束优化问题是指在没有约束条件的情况下，寻找一个函数的最小值或最大值的问题。
数学上通常用以下形式表示：\[ min\ f(x) \]\[ s.t.\ x \in R^n \]其中，\( f(x) \)为目标函数，\( x \)为自变量。
无约束优化问题在实际应用中广泛存在，比如在机器学习、信号处理、金融等领域都有着重要的应用价值。
2. fr共轭梯度法的基本原理fr共轭梯度法是一种常用的无约束优化方法，它主要用于求解二次型函数的极小值点。
其基本原理是通过迭代的方式，利用fr共轭方向进行搜索，从而逐步逼近最优解。
具体来说，fr共轭梯度法的迭代公式为：\[ x_{k+1} = x_k + \alpha_k d_k \]其中，\( x_k \)为第k次迭代的解，\( d_k \)为fr共轭方向，\( \alpha_k \)为搜索步长。
3. fr共轭梯度法的优势和局限性fr共轭梯度法相对于其他优化算法具有一定的优势，比如收敛速度较快、内存占用小等。
但是，它也存在一些局限性，比如对非二次型函数的性能表现不佳、依赖初始点选取等。
在实际应用中需要结合具体问题特点来选择合适的优化算法。
4. fr共轭梯度法在深度学习中的应用在深度学习领域，优化算法对于模型训练的收敛速度和性能表现有着重要影响。
fr共轭梯度法作为一种优化算法，被广泛应用于深度学习模型的训练过程中。
它可以有效地加速模型的收敛速度，提高训练效率。
5. 个人观点和理解从我个人的角度来看，fr共轭梯度法作为一种经典的优化算法，在实际应用中展现出了较高的效率和性能。
它在求解无约束优化问题时具有明显的优势，特别适用于二次型函数的优化。
应用共轭梯度法求解方程组121242
x x x x +=⎧⎨-=⎩的根。
初始值(0)(0,0)T x = 分析：将方程组Ax b =转化为优化问题中的极值问题然后应用共轭梯度法进行求解。
令()R x Ax b =-，只需求得x ，使得()R x 取得最小值。
则有： min ()R x ⇔2min ()R x min T R R ⇔
()()
()()
()()()()2T T T T T T T T T T T T T T T T T T T T T T T T T T R R Ax b Ax b X A b Ax b X A AX X A b b Ax b b
X A AX X A b b Ax b b
X A A X b AX b Ax b b
X A A X b AX b b
=--=--=--+=--+=--+=-+这是一个数 与1()2
T T f x x Gx b x c =++比较 则有：2,()22T T T G A A g x A A A b ==- 回到题目问题中，则对应有124124012,,04444x G g b x --⎛⎫⎛⎫⎛⎫=== ⎪ ⎪ ⎪--⎝⎭⎝⎭⎝⎭
也就是应用共轭梯度法求点使221212()2212420f x x x x x =+--+取得最小值。
程序清单：
#include <stdio.h>
#include <math.h>
double a,b,s[2]; /*全局变量*/
double E=1e-6;
double F(double x1,double x2)
{
double y;
y=2*x1*x1+2*x2*x2-12*x1-4*x2+20;
return (y);
}
void qujian(double x1,double x2) /*用前进后退法求a 的探索区间*/ {
double a0=0,h=1,a1,a2,f1,f2,X1,X2,X3,X4;
a1=a0;a2=a0+h;
X1=x1+a1*s[0];
X2=x2+a1*s[1];
f1=F(X1,X2);
X3=x1+a2*s[0];
X4=x2+a2*s[1];
f2=F(X3,X4);
if (f1>f2)
{
while(1)
{
h=h*2;
a2=a2+h;
f1=f2;
X3=x1+a2*s[0];
X4=x2+a2*s[1];
f2=F(X3,X4);
if (f1>f2) {a1=a2-h;}
else{a=a1;b=a2;break;}
}
}
else
{
h=-h/4;
while(1)
{
a1=a1+h;
f2=f1;
X1=x1+a1*s[0];
X2=x2+a1*s[1];
f1=F(X1,X2);
if(f1<f2) {a2=a1-h;h=2*h;}
else{a=a1;b=a2;break;}
}
}
}
double MIN(double x1,double x2) /*二次插值法求a的最小值*/ {
double x01,x02,x03,x0,xmin;
double f1,f2,f3,f;
double X1,X2,X3,X4,X5,X6,X7,X8;
double h=(b-a)/2;
double k1,k2;
x01=a;x02=a+h;x03=b;
X1=x1+x01*s[0];
X2=x2+x01*s[1];
X3=x1+x02*s[0];
X4=x2+x02*s[1];
X5=x1+x03*s[0];
X6=x2+x03*s[1];
f1=F(X1,X2);
f2=F(X3,X4);
f3=F(X5,X6);
while (1)
{
k1=(f3-f1)/(x03-x01);
k2=((f2-f1)/(x02-x01)-k1)/(x02-x03);
x0=(x01+x03-k1/k2)/2;
X7=x1+x0*s[0];
X8=x2+x0*s[1];
f=F(X7,X8);
if(fabs(x0-x02)<=E)
{
xmin=x0;break;
}
else if(x02<x0)
{
if(f2<f)
{x03=x0;f3=f;}
else
{x01=x02;f1=f2;x02=x0;f2=f;}
}
else
{
if(f2<f)
{x01=x0;f1=f;}
else
{x03=x02;f3=f2;x02=x0;f2=f;}
}
}
return(xmin);
}
void main()
{
double g[3],m1,m2,b;
int n=2,k=0;
double x1=0,x2=0; /*起始点*/
g[1]=4*x1-12;
g[2]=4*x2-4;
m1=g[1]*g[1]+g[2]*g[2];
s[0]=-g[1];
s[1]=-g[2];
while(1)
{
qujian(x1,x2);
a=MIN(x1,x2); /*求a的探索区间*/
x1=x1+a*s[0];
x2=x2+a*s[1];
g[1]=4*x1-12;
m2=g[1]*g[1]+g[2]*g[2];
if(sqrt(g[1]*g[1]+g[2]*g[2])<=E)
break;
if(k+1==n)
{g[1]=4*x1-12;g[2]=4*x2-4;s[0]=-g[1];s[1]=-g[2];}
else
{b=m2/m1;s[0]=-g[1]+b*s[0];s[1]=-g[2]+b*s[1];k=k+1;}
printf("最优解：\n X1=%f\n X2=%f\n",x1,x2);
}
}
运行结果：
最优解：
X1=3.000000
X2=1.000000。
