§1 变分法简介
作为数学的一个分支，变分法的诞生，是现实世界许多现象不断探索的结果，人们可以追寻到这样一个轨迹：
约翰·伯努利（Johann Bernoulli ，1667－1748）1696年向全欧洲数学家挑战，提出一个难题：“设在垂直平面内有任意两点，一个质点受地心引力的作用，自较高点下滑至较低点，不计摩擦，问沿着什么曲线下滑，时间最短？”
这就是著名的“最速降线”问题（The Brachistochrone Problem ）。它的难处在于和普通的极大极小值求法不同，它是要求出一个未知函数（曲线），来满足所给的条件。这问题的新颖和别出心裁引起了很大兴趣，罗比塔（Guillaume Francois Antonie de l'Hospital 1661-1704）、雅可比·伯努利（Jacob Bernoulli 1654-1705）、莱布尼茨（Gottfried Wilhelm Leibniz,1646-1716）和牛顿（Isaac Newton1642—1727）都得到了解答。约翰的解法比较漂亮，而雅可布的解法虽然麻烦与费劲，却更为一般化。后来欧拉（Euler Lonhard ，1707～1783）和拉格朗日(Lagrange, Joseph Louis ，1736-1813)发明了这一类问题的普遍解法，从而确立了数学的一个新分支——变分学。
有趣的是，在1690年约翰·伯努利的哥哥雅可比·伯努利曾提出著名的悬链线问题 (The Hanging Chain Problem)向数学界征求答案，即，固定项链的两端，在重力场中让它自然垂下，问项链的曲线方程是什么。在大自然中，除了悬垂的项链外，我們还可以观察到吊桥上方的悬垂钢索，挂着水珠的蜘蛛网，以及两根电线杆之间所架设的电线，这些都是悬链线（catenary ）。
伽利略（Galileo, 1564～1643）比贝努利更早注意到悬链线，他猜测悬链线是抛物线，从外表看的确象，但实际上不是。惠更斯（Huygens, 1629～1695）在1646年（当时17岁），经由物理的论证，得知伽利略的猜测不对，但那时，他也求不出答案。到1691年，也就是雅可比·伯努利提出悬链线问题的第二年，莱布尼兹、惠更斯（以62岁）与约翰·伯努利各自得到了正确答案，所用方法是诞生不久的微积分，具体说是把问题转化为求解一个二阶常微分方程
解此方程并适当选取参数，得
)(21ax ax
e e a
y -+= （1）
即为悬链线。
悬链线问题本身和变分法并没有关系，然而这和最速降线问题一样都是贝努利兄弟间的相互争强好胜、不断争吵的导火索，虽然雅可比·贝努利在解决悬链线问题时略占下风，但他随后所证明的“悬挂于两个固定点之间的同一条项链，在所有可能的形状中，以悬链线的重心最低，具有最小势能”，算是扳回了一局，俩兄弟扯平了！之所以提到悬链线问题，有两方面考虑，其一，这是有关数学史上著名的贝努利家族内的一个趣闻，而这是一个在变分法乃至整个数学物理领域有着巨大贡献的家族，其二，有关悬链线的得几个结论，可以用变
???????='=+=0)0()0()(102
2
2y y y dx dy a dx
y d
分法来证明！
现实中很多现象可以表达为泛函极小问题，我们称之为变分问题。求解方法通常有两种：古典变分法和最优控制论。我们这儿要介绍的基本属于古典变分法的范畴。 1.1 变分法的基本概念 1.1.1 泛函的概念
设S 为一函数集合，若对于每一个函数S t x ∈)(有一个实数J 与之对应，则称J 是定义在S 上的泛函，记作))((t x J 。S 称为J 的容许函数集。
例如，在],[10x x 上光滑曲线y(x)的长度可定义为
?
'+=1
21x x dx y J （2）
考虑几个具体曲线，取1,010==x x ，
若x x y =)(，则
?=+==1
211)())((dx x J x y J
若y(x)为悬链线，则
??-----=
+=-+=+10101
22
24)(1)2(e e dx e e dx e e e e J x
x x x x x 对应],[101x x C 中不同的函数y(x)，有不同曲线长度值J ，即J 依赖于y(x)，是定义在
函数集合],[101x x C 上的一个泛函，此时我们可以写成
))((x y J J =
我们称如下形式的泛函为最简泛函
?=f
t t dt t x
t x t F t x J 0
))(),(,())(( （3） 被积函数F 包含自变量t ，未知函数x (t)及导数x
(t)。上述曲线长度泛函即为一最简泛函。 1.1.2 泛函极值问题
考虑上述曲线长度泛函，我们可以提出下面问题：
在所有连接定点),(),(1100y x B y x A 和的平面曲线中，试求长度最小的曲线。
即，求{}
1100101
)(,)(],,[)()()(y x y y x y x x C x y x y x y ==∈∈，使
?
'+=1
21))((x x dx y x y J
取最小值。此即为泛函极值问题的一个例子。以极小值为例，一般的泛函极值问题可表述为，
称泛函))((t x J 在S t x ∈)(0取得极小值，如果对于任意一个与)(0t x 接近的S t x ∈)(，都有))(())((0t x J t x J ≥。所谓接近，可以用距离ε<))(),((0t x t x d 来度量，而距离可以定义为
|})()(||,)()({|max ))(),((0000t x t x
t x t x t x t x d f
t t t --=≤≤
泛函的极大值可以类似地定义。其中)(0t x 称为泛函的极值函数或极值曲线。
1.1.3 泛函的变分
如同函数的微分是增量的线性主部一样，泛函的变分是泛函增量的线性主部。作为泛函的自变量，函数)(t x 在)(0t x 的增量记为
)()()(0t x t x t x -=δ
也称函数的变分。由它引起的泛函的增量记作
))(())()((00t x J t x t x J J -+=?δ
如果J ?可以表为
))(),(())(),((00t x t x r t x t x L J δδ+=?
其中L 为x δ的线性项，而r 是x δ的高阶项，则称L 为泛函在)(0t x 的变分，记作
))((0t x J δ。用变动的)(t x 代替)(0t x ，就有))((t x J δ。
泛函变分的一个重要形式是它可以表为对参数α的导数：
))()(())((=+??
=
ααδα
δt x t x J t x J （4）
这是因为当变分存在时，增量
)),(()),(())(())((x t x r x t x L t x J x t x J J αδαδαδ+=-+=? 根据L 和r 的性质有
)),(()),((x t x L x t x L δααδ=
0)
),((lim
)
),((lim
00
==→→x x
x t x r x t x r δαδαδα
αδαα
所以
α
αδαδααα)
()(lim
)(00x J x x J x x J -+=+??→= )(),()
,(),(lim
x J x x L x x r x x L δδα
αδαδα==+=→
1.2 泛函极值的相关结论
1.2.1 泛函极值的变分表示
利用变分的表达式（4），可以得到有关泛函极值的重要结论。
泛函极值的变分表示：若))((t x J 在)(0t x 达到极值（极大或极小），则
0))((0=t x J δ （5）
证明：对任意给定的x δ，)(0x x J αδ+是变量α的函数，该函数在0=α处达到极值。根据函数极值的必要条件知
0)(00=+??
=ααδα
x x J 再由（4）式，便可得到（5）式。
变分法的基本引理：],[)(21x x C x ∈?，],[)(211x x C x ∈?η，0)()(21==x x ηη，有
?
≡2
1
0)()(x x dx x x η?，
则],[ ,0)( 21x x x x ∈≡?。
证明略。
1.2.2 泛函极值的必要条件
考虑最简泛函（3），其中F 具有二阶连续偏导数，容许函数类S 取为满足端点条件为固定端点（6）的二阶可微函数。
00)(x t x =，f f x t x =)( （6）
泛函极值的必要条件：设泛函（3）在x(t)∈S 取得极值，则x(t)满足欧拉方程
0=-
x x F dt
d F （7） 欧拉方程推导：首先计算（3）式的变分：
0))()((=+??
=ααδαδt x t x J J ?=++??
=f t t dt t x t x t x t x t F 00
))()(),()(,(ααδαδα
?
+=
f
t t x x dt x x
x t F x x x t F 0
]),,(),,([ δδ 对上式右端第二项做分布积分，并利用0)()(0==f t x t x δδ，有
??
-=f
f
t t x t t x xdt x
x t F dt
d
dt x x
x t F 0
),,(),,(δδ ， 所以
?-
=f
t t x x xdt F dt
d F J 0
][δδ 利用泛函极值的变分表示，得
0][0
=-
?
f
t t x x x d t F dt
d F δ 因为x δ的任意性，及0)()(0==f t x t x δδ，由基本引理，即得（7）。 （7）式也可写成
0=---x F x F F F x x x x x t x
（8） 通常这是关于x(t)的二阶微分方程，通解中的任意常数由端点条件（6）确定。 1.2.3 几种特殊形式最简泛函的欧拉方程
(i) F 不依赖于x
，即),(x t F F =
这时0≡x F ，欧拉方程为0),(=x t F x ，这个方程以隐函数形式给出)(t x ，但它一般不满足边界条件，因此，变分问题无解。
(ii) F 不依赖x ，即),(x
t F F = 欧拉方程为
0),(=x
t F dt
d
x 将上式积分一次，便得首次积分1),(c x
t F x = ，由此可求出),(1c t x ?= ，积分后得到可能的极值曲线族
()dt c t x ?=1,?
(iii) F 只依赖于x
，即)(x F F = 这时0,0,0===x x x t x F F F ，欧拉方程为
0=x x F x
由此可设0=x 或0=x x F ，如果0=x ，则得到含有两个参数的直线族21c t c x +=。另外
若0=x x F 有一个或几个实根时，则除了上面的直线族外，又得到含有一个参数c 的直线族
c kt x +=，它包含于上面含有两个参数的直线族 21c t c x += 中，于是，在)(x
F F =情况下，极值曲线必然是直线族。
（iv ）F 只依赖于x 和x
，即),(x x F F = 这时有0=x t F ，故欧拉方程为
0=--x x x x x F x F x F
此方程具有首次积分为
1c F x F x =-
事实上，注意到F 不依赖于t ，于是有
0)()(=-=--+=-x x
x x x x x F dt
d
F x F dt d x F x x F x F F x F dt d 。 1. 3 几个经典的例子
1.3.1 最速降线问题
最速降线问题 设A 和B 是铅直平面上不在同一铅直线上的两点，在所有连结A 和B 的平面曲线中，求一曲线，使质点仅受重力作用，初速度为零时，沿此曲线从A 滑行至B 的时间最短。
解 将A 点取为坐标原点，B 点取为B(x 1,y 1)，如图1。根据能量守恒定律，质点在曲
线)(x y 上任一点处的速度
dt
ds
满足（s 为弧长）
mgy dt ds m =??
?
??2
21
将dx x y ds )('12
+=代入上式得 dx gy
y dt 2'12
+= 图1最速降线问题
于是质点滑行时间应表为)(x y 的泛函
dx gy
y x y J x ?
+=2
2
2'1))(( 端点条件为
11)(,0)0(y x y y ==
最速降线满足欧拉方程，因为
y
y y y F 2
'1)',(+=
不含自变量x ，所以方程（8）可写作
0''''''=--y F y F F y y yy y
等价于
0)'('=-y F y F dx
d
作一次积分得
12
)'1(c y y =+ 令 ,2
'θ
ctg
y =则方程化为
)cos 1(2
2sin '112121θθ-==+=
c c y c y 又因
θθθθθ
θd c ctg d c y dy dx )cos 1(22
2cos 2sin '11-===
积分之，得
2)sin (2
c c
x +-=
θθ
由边界条件0)0(=y ，可知02=c ，故得
??????
?-=-=).cos 1(2
)sin (2
11θθθc y c x 这是摆线（园滚线）的参数方程，其中常数1c 可利用另一边界条件11(y x y =）来确定。 1.3.2 最小旋转面问题
最小旋转面问题 对于xy 平面上过定点),(11y x A 和),(22y x B 的每一条光滑曲线
)(x y ，绕x 轴旋转得一旋转体。旋转体的侧面积是曲线)(x y 的泛函))((x y J ，易得
dx x y x y x y J x x )('1)(2))((2
1
2?+=π
容许函数集可表示为
{}
2211211)()(][)()(y x , y y x ,y ,x x C x |y x y S ==∈=
解 因 "1y y F +=不包含x ，故有首次积分
12
2''
1'''1'c y y y
y y y F y F y =+-+=-
化简得 2
1'1y c y +=
令sht y ='，代入上式， cht c t sh c y 1211=+= 由于 dt c sht
shtdt c y dy dx 11'===
积分之，得 21c t c x += 消去t ，就得到1
2
1c c x ch
c y -= 。 这是悬链线方程，适当选择条件（令该悬链线过（0，1/a ）点，且该点处的切线是水平的）就可得到（1）。本例说明，对于平面上过两个定点的所有光滑曲线，其中绕x 轴旋转所得旋转体的侧面积最小的是悬链线！ 1.3.3 悬链线势能最小
1691年，雅可比·伯努利证明：悬挂于两个固定点之间的同一条项链，在所有可能的形状中，以悬链线的重心最低，具有最小势能。下面我们用变分法证明之。
考虑通过A 、B 两点的各种等长曲线。令曲线y ＝f(x)的长度为L ，重心坐标为),(y x ，
则
?
?+==b
a
b a
dx dx
dy ds L 2
)(
1 由重心公式有
L
dx dx
dy x x b
a
?
+=
2
)(
1 ， L
dx dx
dy y y b
a
?
+=
2
)(
1
由于只需探讨曲线重心的高低，所以只对纵坐标的公式进行分析，注意到问题的表述，说明L 是常数，不难看出重心的纵坐标是y(x)的最简泛函，记作
?'+=b
a
dx y x y x y J 2)(1)())((
此时对应的欧拉方程（8）可化为
01)(2=-'-''y y y
令dx
dy p =
解得 0),1(2
2>+=k p k y ，进而得 )]([1c x k ch k
y +=
。
此即为悬链线，它使重心最低，势能最小！大自然中的许多结构是符合最小势能的，人们称之为最小势能原理。 1.4 泛函极值问题的补充
1.4.1 泛函极值的几个简单推广
（ⅰ）含多个函数的泛函 使泛函
?=2
1
)',,',,())(),((x x dx z z y y x F x z x y J
取极值且满足固定边界条件
.)(,)(,)(,)(22112211z x z z x z y x y y x y ====
的极值曲线)(),(x z z x y y ==必满足欧拉方程组
???
???
?=-=-00''z z y y F dx d F F dx
d F （ii ）含高阶导数的泛函
使泛函 ?
=
2
1
)",',,())((x x dx y y y x F x y J
取极值且满足固定边界条件
11)(y x y =,221122')(',')('y x y y x y y x y ===，）（
的极值曲线)(x y y =必满足微分方程
0"22
'=+-y y y F dx
d F dx d F （iii ） 含多元函数的泛函
设D y x c y x z ∈∈),(,),(2，使泛函 ??=
D
y x
dxdy z z
z y x F y x z J ),,,,()),((
取极值且在区域D 的边界线l 上取已知值的极值函数),(y x z z =必满足方程
0=??
-??-
y x z z z F y
F x F 上式称为奥式方程。
1.4.2端点变动的情况（横截条件）
设容许曲线)(t x 在0t 固定，在另一端点f t t =时不固定，是沿着给定的曲线)(t x ψ=上变动。于是端点条件表示为
?
?
?==)()()(0
0t t x x t x ψ
这里t 是变动的，不妨用参数形式表示为 f f dt t t α+=
寻找端点变动情况的泛函极值必要条件，可仿照前面端点固定情况进行推导，即有 0
),,(00
=+++??=
=?
αααδαδα
δdt x x
x x t F J f
f dt t t
f t t t t x t t x x dt F x F xdt F dt
d
F f f f
==++-
=
?
δδ 0
)( （9） 再对（9）式做如下分析：
（i ）对每一个固定的f t ，)(t x 都满足欧拉方程，即（9）式右端的第一项积分为零； （ii ）为考察（9）式的第二、第三项，建立f dt 与f
t t x =δ之间的关系，因为
)()()(f f f f f f dt t dt t x dt t x αψααδα+=+++ 对α求导并令0=α得
f f t t f f dt t x dt t x
f
)()(ψδ =+= 即
f f f t t dt t x t x f
)]()([ -==ψ
δ （10） 把（10）代入（9）并利用f dt 的任意性，得
0])([=-+=f t t x F x F ψ （11）
（11）式就是确定欧拉方程通解中另一常数的定解条件，称为横截条件。
横截条件有两种常见的特殊情况：
（i ）当)(t x ψ=是垂直横轴的直线时，f t 固定，)(f t x 自由，并称)(f t x 为自由端点。此时（9）式中0=f dt 及f
t t x =δ的任意性，便得自由端点的横截条件
0==f
t t x F
（12）
（ii ）当)(t x ψ=是平行横轴的直线时，f t 自由，)(f t x 固定，并称)(f t x 为平动端点。
此时0=ψ ，（11）式的横截条件变为
0=-=f
t t x F x F
* （13）
注意，横截条件与欧拉方程联立才能构成泛函极值的必要条件。
1.4.3 有约束条件的泛函极值
在最优控制系统中，常常要涉及到有约束条件泛函的极值问题，其典型形式是对动态系统
))(),(,()(t u t x t f t x
= * （14） 寻求最优性能指标（目标函数）
?
+
=f
t t f f dt t u t x t F t x t t u J 0
))(),(,())(,())((? * （15）
其中)(t u 是控制策略，)(t x 是轨线，0t 固定，f t 及)(f t x 自由，n R t x ∈)(，m R t u ∈)(（不受限，充满m
R 空间），F f ,,?连续可微。
下面推导取得目标函数极值的最优控制策略)(*
t u 和最优轨线)(*
t x 的必要条件。 采用拉格朗日乘子法，化条件极值为无条件极值，即考虑
?-++=f
t t T f f dt x
u x t f t u x t F t x t u x J 0
)]),,()((),,([))(,(),,(1 λ?λ （16） 的无条件极值，首先定义（14）式和（15）式的哈密顿（Hamilton ）函数为
),,()(),,(),,,(u x t f t u x t F u x t H T
λλ+= （19）（17） 将其代入（16）式，得到泛函
?-+=f
t t T f f dt x
u x t H t x t u x J 0
]),,,([))(,(),,(1 λλ?λ （20）(18)
下面先对其求变分
))()(,({1f f f f t x t x dt t J αδα?α
δ++??
=
0})]()(),,,([0
=+++-++++?
αααδαδλλαδλλαδαδdt x x
u u x x t H T dt t t f f []f f f f t t T T f t t T f t T f t x T
f x
dt u x t H dt dt t x ==-++=)()(),,,()()()()( λλ??δ dt x x
H H u H x T T T u T x T t t f
])()()()([0
δλδλδλδδλ--+++? )()]([]),,,([)(f f f t x T f t t t T f t x t u x t F dt ?δ?++==
??+--+++=f
f f t t T t t f T
t t T
T
u T
x T
dt x x t dt x
H H u H x 0
)()(])()()()[(λδδλδλδλδδλ
注意到)(f t t t x x
f
δδ≠=，f f f t t dt t x
t x x
f
)()( -==δδ，因而 f
f
f
t t x T f t t t T f t x u x t H dt J ==-++=)()]([]),,,([)(1λ?δλ?δ
?
+-+++
f
t t u T T x T dt H u x H H x 0
])()()()()[(δδλλδλ
再令01=J δ，由δλδδδ,,),(,u x t x dt f f 的任意性，便得
（i ）*
*
,λx 必满足正则方程：
① 状态方程 ),,(u x t f H x
==λ ② 协态方程 x
H -=λ 。 （ii ）哈密顿函数),,,(*
*λu x t H 作为u 的函数，也必满足 0=u H 并由此方程求得*
u 。
（iii ）求*
**,,u x λ时，必利用边界条件 ① 00)(x t x =， （用于确定*
x ） ②
)()(f
t x f t ?λ=， （用于确定*λ）
③ f
f t t t u x t H =-=),,,(λ?， （确定f t ）
1.4.4 最大（小）值原理
如果受控系统
),,(u x t f x
= ，00)(x t x =
其控制策略)(t u 的全体构成有界集U ，求U t u ∈)(，使性能指标 ?
+=f
t t f f dt u x t F t x t t u J 0
),,())(,())((?
达到最大（小）值。
最大（小）值原理：如果),,(u x t f ，))(,(f f t x t ?和),,(u x t F 都是连续可微的，那么最优控制策略)(*t u 和相应的最优轨线)(*t x 由下列的必要条件决定：
（i ）最优轨线)(*t x ，协态向量)(*t λ由下列的必要条件决定：
),,(u x t f dt dx
=，U t u ∈)(， x
H dt d ??-=λ （ii ）哈密顿函数
),,()(),,(),,,(*****u x t f t u x t F u x t H T λλ+= 作为)(t u 的函数，最优策略)(*t u 必须使
),,,(max ),,,(*
*
*
*
*
λλu x t H u x t H U
u ∈=
或使
),,,(min ),,,(*
*
*
*
*
λλu x t H u x t H U
u ∈=(最小值原理)
（iii ）满足相应的边界条件
① 若两端点固定，则正则方程的边界条件为 0)0(x x =，f f x t x =)(。
② 若始端固定，终端f t 也固定，而)(f t x 自由，则正则方程的边界条件为 0)0(x x =，))(,()()(f f t x f t x t t f ?λ=。
③ 若始端固定，终端)(,f f t x t 都自由，则正则方程的边界条件为 0)0(x x =，))(,()()(f f t x f t x t t f ?λ=， 0))(,())(),(),(,(=+f f t f f f f t x t t t u t x t H f ?λ。
最速下降法求解线性代数方程组 要求：对于给定的系数矩阵、右端项和初值，可以求解线性代数方程组 一、最速下降法数学理论 在基本迭代公式k k k k P t X X +=+1中，每次迭代搜索方向k P 取为目标函数)(X f 的负梯度方向，即)(k k X f P -?=，而每次迭代的步长k t 取为最优步长，由此确定的算法称为最速下降法。 为了求解问题)(min X f ，假定我们已经迭代了k 次，获得了第k 个迭代点k X 。现在从k X 出发，可选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方向)进行搜索应该是有利的，至少在k X 邻近的范围内是这样。因此，去搜索方向为 )(k k X f P -?=. 为了使目标函数在搜索方向上获得最多的下降，沿k P 进行一维搜索，由此得到第1+k 个跌带点，即 )(1k k k k X f t X X ?-=+， 其中步长因子k t 按下式确定 ))((m in ))((k k k k k k X f t X f X f t X f ?-=?-， ))(,(1k k k X f X ls X -?=+. （1） 显然，令 ,2,1,0=k 就可以得到一个点列 ,,,210X X X ,其中0X 是初始点，由计算者任意选定。当)(X f 满足一定的条件时，由式（1）所产生的点列}{k X 必收敛于)(X f 的极小点。
二、最速下降法的基本思想和迭代步骤 已知目标函数)(X f 及其梯度)(X g ，终止限21,εε和3ε. （1）选定初始点0X ，计算)(),(0000X g g X f f ==；置0=k . （2）作直线搜索：),(1k k k g X ls X -=+；计算)(),(1111++++==k k k k X g g X f f . 用终止准则检验是否满足：若满足，则打印最优解))(,(11++k k X f X ，结束；否则，置1+=k k ，转（2） （3）最速下降法算法流程图如图所示.
《MATLAB 程序设计实践》课程考核 实践一、编程实现以下科学计算法，并举一例应用之。（参考书籍《精通MATLAB 科学计算》，王正林等著，电子工业出版社，2009年） “最速下降法无约束最优化” 最速下降法： 解： 算法说明：最速下降法是一种沿着N 维目标函数的负梯度方向搜索最小值的方法。 原理：由高等数学知识知道任一点的负梯度方向是函数值在该点下降最快的方向，那么利用负梯度作为极值搜索方向，达到搜寻区间最速下降的目的。而极值点导数性质，知道该点的梯度=0，故而其终止条件也就是梯度逼近于0，也就是当搜寻区间非常逼近极值点时，即：当▽f(a ）→0推出f(a ）→极值）（x f ，f(a ）即为所求。该方法是一种局部极值搜寻方法。 函数的负梯度表示如下： -g(x ）=-▽f(x)=-?????1 )(x x f 2)(x x f ?? … T N x x f ?????)( 搜索步长可调整，通常记为αk （第k 次迭代中的步长）。该算法利用一维的线性搜索方法，如二次逼近法，沿着负梯度方向不断搜索函数的较小值，从而找到最优解。 方法特点（1）初始值可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径胃绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。（3）全局收敛，线性收敛，易产生扭摆现象而造成早停。 算法步骤：最速下降法的基本求解流程如下： 第一步 迭代次数初始化为k=0，求出初始点0x 的函数值f 0=f （0x ）。 第二步 迭代次数加1，即k=k+1，用一维线性搜索方法确定沿负梯度方向-1-k g 的步长1k -α，其中1k -α=ArgMinaf （111k /----k k g g x α）。 第三步 沿着负梯度方向寻找下一个接近最小值的点，其中步长为1k -α，得到下一点的坐标为：1111/-----=k k k k k g g x x α。
最速下降法Matlab实现 实验目的： 1.掌握迭代法求解无约束最优化问题的基本思想 2.通过实验掌握最速下降法的Matlab算法的基本步骤 实验内容： 1.迭代法求解无约束最优化问题的基本思想 给定一个初始点x(0), 按照某一迭代规则产生一个迭代序列{x(k)}. 使得若该序列是有限的, 则最后一个点就是原问题的极小点; 否则, 若序列{x(k)} 是无穷点列时, 它有极限点且这个极限点即为原问题的极小点. 设x(k) 为第k 次迭代点, d(k) 为第k 次搜索方向, a(k)为第k 次步长因子, 则第k 次迭代完成后可得到新一轮(第k + 1 次) 的迭代点 x(k+1) = x(k) + a(k) d(k). 2.无约束优化问题迭代算法的一般框架 步0 给定初始化参数及初始迭代点x(0). 置k := 0. 步1 若x(k) 满足某种终止准则, 停止迭代, 以x(k) 作为近似极小点. 步2 通过求解x(k) 处的某个子问题确定下降方向d(k). 步3 通过某种搜索方式确定步长因子a(k), 使得f(x(k) + a(k) d(k)) < f(x(k)). 步4 令x(k+1) := x(k) + a(k) d(k), k := k + 1, 转步1. 3. 最速下降法的基本步骤 步0 选取初始点x(0) ∈R^n, 容许误差0 ≤e ?1. 令k := 1. 步1 计算g(k) = ?f(x(k)). 若‖g(k)‖≤e, 停算, 输出x(k)作为近似最优解. 步2 取方向d(k)= ?g(k). 步3 由线搜索技术确定步长因子a(k),即 min f(a(k))=f(x(k)+a(k)d(k)). 步4 令x(k+1) := x(k) + a(k)d(k)), k := k + 1, 转步1.
最速下降法 %% 最速下降法图示 % 设置步长为0.1，f_change为改变前后的y值变化，仅设置了一个退出条件。syms x;f=x^2; step=0.1;x=2;k=0; %设置步长,初始值,迭代记录数 f_change=x^2; %初始化差值 f_current=x^2; %计算当前函数值 ezplot(@(x,f)f-x.^2) %画出函数图像 axis([-2,2,-0.2,3]) %固定坐标轴 hold on while f_change>0.000000001 %设置条件，两次计算的值之差小于某个数，跳出循环 x=x-step*2*x; %-2*x为梯度反方向，step为步长，！最速下降法！ f_change = f_current - x^2; %计算两次函数值之差 f_current = x^2 ; %重新计算当前的函数值 plot(x,f_current,'ro','markersize',7) %标记当前的位置 drawnow;pause(0.2); k=k+1; end hold off fprintf('在迭代%d次后找到函数最小值为%e，对应的x值为%e\n',k,x^2,x)
wolfe准则 unction [alpha, newxk, fk, newfk] = wolfe(xk, dk) rho = 0.25; sigma = 0.75; alpha = 1; a = 0; b = Inf; while (1) if ~(fun(xk+alpha*dk)<=fun(xk)+rho*alpha*gfun(xk)'*dk) b = alpha; alpha = (alpha+a)/2; continue; end if ~(gfun(xk+alpha*dk)'*dk>= sigma*gfun(xk)'*dk) a = alpha; alpha = min([2*alpha, (b+alpha)/2]); continue; end break; end newxk = xk+alpha*dk; fk = fun(xk); newfk = fun(newxk);
实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期: 20１０年5月１0日~２010年5月１５日 三、实验目的 掌握最速下降法,牛顿法和共轭梯度法的算法思想，并能上机编程实现相应的算法。 二、实验要求 用ＭA ＴLA Ｂ实现最速下降法，牛顿法和共轭梯度法求解实例。 四、实验原理 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f 在迭代点k x 处的T ａylor 展开式作为模型函数,并利用这个二次模型函数的极 小点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向k d 仅仅是负梯度方向k g -与上一次接 待的搜索方向1-k d 的组合。 五.运行及结果如下： 最速下降法: 题目：f=（x-2）^２+(y-４）^2 Ｍ文件： fu ｎcti ｏn [R,n]=stee ｌ（x0,y0，e ｐs) syms ｘ； syms y ; f=(x-2)^2+(ｙ-４）^2; ｖ=[x,y]; ｊ＝ｊac ｏbi ａｎ(f ，v); T=[s ｕbs(j(１),ｘ,x0）,subs （j （2),ｙ，y0)]; temp=s ｑrt((Ｔ(1)）^2＋(T （2))＾2); x １＝x0;y １=y ０; ｎ=0; sym ｓ k ｋ; w ｈi ｌe (temp>eps ） ｄ=－Ｔ； ｆ1=x １+kk*d(1);f2=ｙ1+k ｋ*ｄ（２); fT=[su ｂs(j （1),ｘ,ｆ１),ｓｕb ｓ(j(2),ｙ,ｆ2)]; fu ｎ=sqrt((fT(1））^2+(ｆT(2)）^２）;
第五题： 解：选择类型为： 2/13()x t y t x e x =+ 其中123,,x x x 是待求参数。根据最小二乘原理，参数123,,x x x 是下面优化问题的解。 []2 8 1231 m in (,,)()i i i f x x x y t y == -? 用最速下降法求解这一无约束的最优化问题。 zuiyouhua.m function sh=zuiyouhua(x0) % x0为初始猜测值 syms x y z a al; %====================================== t=[0.2,1,2,3,5,7,11,16]; r1=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60]; minf=0; for i=1:8 r(i)=x*exp(y/t(i))+z-r1(i); %构造最小二乘最优化的目标函数 minf=r(i)^2+minf; end %====================================== f1=diff(minf,x); f2=diff(minf,y); f3=diff(minf,z); %求目标函数的梯度 F=[f1,f2,f3]; %====================================== Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); k=0; %====================================== %最速下降法核心迭代程序 while 1 x1=x0+a*Fx; P=subs(minf,{x,y,z},x1); xx1=xianxing(P); %调用线性搜索函数 al=huangjing(P,xx1); %调用黄金分割法函数； x0=x0+al*Fx; Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); if norm(Fx1)<5e-4 sh=x0; return; end end %====================================== function xx=xianxing(Pa) %一维搜索法线性搜索函数 aa=findsym(Pa); a1=1; h=0.5; k=0; t1=2; while 1 a2=a1+h; Pa1=subs(Pa,aa,a1); Pa2=subs(Pa,aa,a2); if Pa2< Pa1 h=t1*h; a0=a1; a1=a2; k=k+1; if k>1000 disp('迭代步数太多，可能不收敛！'); end else if k==0 h=-h; a0=a2; else c1=min(a0,a2); d1=max(a0,a2); xx=[c1,d1]; return; end end end %====================================== function al1=huangjing(Pb,xx2)
梯度法（又名,最速下降法） (该法总可以收敛，但是，在接近真解时收敛的速度会放慢。) 梯度法又称为最速下降法，用于求解实系数非线性方程组 12(,,,)0, 1,2,,i n f x x x i n == （7－15） 的一组根。梯度法首先是定义一个目标函数 2 12121 (,,,)(,,,) n n i n i x x x f x x x =Φ= ∑ （7－16） 使目标函数2 1 n i i f =Φ= ∑ 达到最小的12,,,n x x x 是我们寻找的一组解，这是非 线性最小二乘法问题。 如果第(0,1,2,)k k = 步求得一组解1 2 ,,,n k k k x x x ，使得 12(,,,)n k k k x x x ε Φ< （7－17） 则认为1 2 ,,,n k k k x x x 是原方程组满足一定精度的()ε要求的一组解。 梯度法的计算过程是： （1）先给定一组不全为零的初值1 2 000,,,n x x x ，第k 步的一组根为1 2 ,,,n k k k x x x ； （2）计算目标函数1 2 (,,,)n k k k x x x Φ 的值；(单独子程序:fn =TargetFunction) （3）若1 2 (,,,)n k k k x x x εΦ< ，则认为1 2 ,,,n k k k x x x 是满足一定精度()ε的一组 解，否则，作如下修正计算 1 α +=?Φ=-?i k i i k k k i i x x x x x （7－18） 其中
121212********* 1111222 (,,,) (,,,)(,,,)(,,,)(,,,)(,,,)(,,,)*,1,2,,α ==?Φ= ??? ??Φ ? ? ???Φ+-Φ?Φ=??Φ+-Φ?Φ= ?Φ+-Φ?Φ = ?==∑ n k j j n n n n n n k k k k n j j x x k k k k k k k k k k k k k k k k k k n n n k i i x x x x x h x x x x x x h x x h x x x x x h x x x h x x x x h h H x i n ??? ???? ??? ? ?????? （7－19） H 为控制收敛的常数，通常选为（10－5～10－6），收敛精度ε 选为（10－6～10 －8 ）。 （4）重复修正1 k i x +，直到 12111 (,,,)n k k k ε +++ΦΦΦ< ，计算终止。
牛顿法 迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-?? Matlab 代码： function [x1,k] =newton(x1,eps) hs=inline('(x-1)^4+y^2'); 写入函数 ezcontour(hs,[-10 10 -10 10]); 建立坐标系 hold on; 显示图像 syms x y 定义变量 f=(x-1)^4+y^2; 定义函数 grad1=jacobian(f,[x,y]); 求f 的一阶梯度 grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度 k=0; 迭代初始值 while 1 循环 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式 if norm(x1-x2) end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y ) 随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发 展。可以让它们与广义预测控制相结合，建立高精度、多模态的预测模型。 使广义预测控制在异常情况下可以稳定运行，推进广义预测控制的进一步 发展。 2.2.1最速下降法 最速下降法是无约束最优化中是比较有效的方法，它是以d}=一可(x})作为下 降方向的算法。其迭代格式为 xx+i=xx一。*Of (xk) 上式中，一般通过精确线搜索准则求得步长因子。*，当然也不排除可以利用非精确 线搜索准则来求得步长因子。*。不管最速下降法采取何种线搜索准则，它均具有全 局收敛性，但是这也不能直接就认为最速下降算法就是一个良好的优化算法。在实际 试验中，有很多优化问题利用最速下降法并不是下降的特快，反而下将的十分缓慢。 这是因为出现了锯齿现象:就是在计算过程中，最速下降法开始几步还是挺快的，但 是当目标函数f (x)的等高线接近于一个球的时候，就出现了类似锯齿现象，前进十 分缓慢，降低了算法的效能。 2.2.12.2.2 牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+}=xA十d} (2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 最优化问题((1-1)的最优解x的时候，并且}Z.f (x.)正定的时候，那么牛顿法就会有 很快的收敛速度，而由此算法产生的点列也具有了超线性收敛速度，同时还在一定条 件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较 远的时候，这时的}Z.}(x})就不一定是正定的了，也就存在了一个问题，那就是此时 的牛顿方向就不一定是下降方向，有可能是上升方向，此时由此算法产生的点列可能 也就不收敛于无约束最优化问题((1-1)的最优解了。综上所述，让步长“R =1即“*恒 取常数是不合适的。经过研究学者们发现了一个方法可以改善这个情况，那就是利用 已有的线搜索方法来确定步长因子，也就是步长因子是可变的。其迭代格式为 x1. }, = x:一a}.OZ f (x}.)一，Of (x,. ) C 2-6 ) 2.2.2牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+i=xA+d}(2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 1. 算法原理 最速下降法的搜索法向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。 已知目标函数在()k X 点的梯度为： ()() () ()()() () ()12 ... T k k k k n f X f X f X f X x x x ?? ???? ??=?????? ? 当求目标函数的最小点时，由于函数沿负梯度方向下降最快，故在()k X 点的探索方向应取该点的负梯度方向，即 ()() ()()() k k k f X S f X ?=- ? 显然，()k S 为单位向量。这样第1k +次迭代计算所得的新点为 () () ()()(1)()()()()() k k k k k k k k f X X X S X f X αα+?=+=- ? 负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最速下降的过程，它们依赖于 () () () k k f X α?的大小。 步长()k α有两种取法： 一种方法是任意给定一个初始步长，使满足条件： ()()()()()()k k k k f X S f X α+< 另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步长α，即对目标函数极小，以得到最优步长： ()()()()()0 min ()()k k k k k f X S f X S ααα>+=+ 以此最优步长作为由() k X 点出发沿该点的负梯度方向探索的步长() k α 。 这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来进行判断： ()()()()()1()(1) 2()() (1) 3k k k k k k f X f X f X f X X X εεε--??≤? ?-?≤?? ?-≤?? 2. 算法步骤 用最速下降法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下： （1） 取初始点 (0)x ，精度0ε>，令0k = （2） 计算搜索方向() ()()k k v f x =-?，其中()()k f x ?表示函数()f x 在点()k x 处的梯 度； （3） 若()k v ε≤，则停止计算；否则，从()k x 出发，沿()k v 进行一维搜索，即求k λ， 使得() ()()()0 ()min ()k k k k k f x v f x v λλλ≥+=+。此处的一维搜索可以用黄金分割 法等算法，当然也可以用MATLAB 的min f bnd 函数； （4） 令(1) ()(),1k k k k x x v k k λ+=+=+，转步骤（2）。 3. 算法的MATLAB 实现 在MATLAB 中编程实现的最速下降法函数为：min FD 功能：用最速下降法求解多维函数的极值。 调用格式：[,min ]min (,0,var,)x f FD f x eps = 其中，f ：为目标函数； 0x ：初始点； var ：自变量向量； eps ：精度； x ：目标函数取最小值时的自变量值； min f ：目标函数的最小值。 最速下降法的MATLAB 程序代码如下： 《最优化方法》 课程设计 题目：共轭梯度法算法分析与实现 院系：数学与计算科学学院 专业：数学与应用数学 姓名：梁婷艳 学号：0800730103 指导教师：李丰兵 日期：2015 年12 月30 日 在各种优化算法中，共轭梯度法是非常重要的一种。本文主要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度, 而且算法结构简单, 容易编程实现。 在本次实验中,我们首先分析共轭方向法、对该算法进行分析，运用基于共轭方向的一种算法—共轭梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共轭梯度法和牛顿法的不同之处以及共轭梯度法的优缺点。 共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。 关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化 In a variety of optimization algorithms, conjugate gradient method is a very important one.In this paper, the conjugate gradient method is between the steepest descent method and Newton method for unconstrained optimization between a method, it has superlinear convergence rate, and the algorithm is simple and easy programming. In this experiment, we first analyze the conjugate direction method, the algorithm analysis, the use of a conjugate direction-based algorithm - conjugate gradient method for unconstrained optimization problems. Unconstrained optimization method is to select the core issue of the search direction.Conjugate gradient method is the basic idea of the conjugate descent method with the most combined points in the gradient using the known structure of a set of conjugate directions, and search along the direction of this group, find the minimum point of objective function. According to the basic nature of the conjugate direction, this method has the quadratic termination. Combined with the preparation of this algorithm matlab program for solving unconstrained optimization problems, combined with Newton’s theory of knowledge, writing matlab program to solve the same problem of unconstrained optimization, comparison analysis, the conjugate gradient method and Newton method different Office and the advantages and disadvantages of the conjugate gradient method. Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, is not only the conjugate gradient method to solve large linear systems one of the most useful, but also large-scale solution nonlinear optimization algorithm is one of the most effective. Conjugate gradient method is a typical conjugate direction method, each of its search direction is conjugate to each other, and the search direction d is just the negative gradient direction with the last iteration of the search direction of the portfolio, therefore, storage less computational complexity. Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization 课程论文 论文题目：最速下降法原理及其算法实现课程名称：现代信号处理新方法 学院：自动化学院 专业班级：控制科学与工程1班学号： 92 姓名：严春景 任课教师：谢胜利 2014年6月20日 最速下降法原理及其算法实现 内容摘要 摘要：基于最速下降法在解决无约束非线性规划问题中的重要性，对其原理与算法予以讨论。论文主要是参阅大量数学分析和运筹学书籍以及一些学术资料，结合自己在平时学习中掌握的知识，并在指导老师的建议下，针对最速下降法的基本思路和原理进行研究。 关键词：运筹学最速下降法无约束梯度法最优解 The steepest descent method, principle and its algorithm Abstract Based on the steepest descent method in solving unconstrained nonlinear programming problem, the importance of the principle and the algorithm is discussed. Paper mainly refer to a mathematical analysis and operations research books and some academic material, usually in the study of knowledge and mastery in teacher's suggestion, the steepest descent method according to the basic ideas and principles were studied. Key words：operational research steepest descent method Unconstrained gradient method optimal solution 我们将要讨论的无约束优化问题的格式为： min ()f x ()n x R ∈ (一)无约束优化问题的最优性条件 无约束优化问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。 定理1 设f :n R R →在点*n x R ∈处一阶可导。若存在n p R ∈，使 *()0T f x p ?< 则向量p 是f 在点*x 处的下降方向。 定理2 （一阶必要条件） 设:n f R R →在点n x R *∈处一阶可导。若x *是f 的局部极小点，则 ()0f x *?= 由数学分析中我们已经知道，使()0f x ?=的点x 为函数f 的驻点或平稳点。函数f 的一个驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数f 的鞍点。以上定理告诉我们，x *是无约束问题的的局部最优解的必要条件是：x *是其目标函数f 的驻点。 现给出无约束问题局部最优解的充分条件。 定理3 （二阶必要条件） 设:n f R R →在点n x R *∈处二阶可导。若*x 是f 的局部极小点，则必有()0f x *?=且2()f x *?半正定。 定理4 （二阶充分条件） 设:n f R R →在点n x R *∈处二阶可导。若 ()0f x *?=，并且2()f x *?正定 则x *是f 的严格局部极小点。 无约束优化问题有很多种算法，比如最速下降法，牛顿法，拟牛顿法，共轭梯度法，我们只针对两种方法进行讨论，分析，比较，还有MATLAB 算法的实现，在接下来的篇幅中，我们将讨论最速下降法和共轭梯度法。 (二)最速下降法 最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 第四章 无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这 种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的， 无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过 对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度 法、共轭梯度法等。 二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯 形法等。 无约束优化问题的一般形式可描述为： 求n 维设计变量 []12T n n X x x x R =∈L 使目标函数 ()min f X ? 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解： 1、解析法 可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方 程 0)(min *=X f 的解。也就是求Ｘ＊使其满足 解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值 点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性 的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题 的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用 数值迭代的方法直接求解无约束极值问题。 2、数值方法 数值迭代法的基本思想是从一个初始点) 0(X 出发，按照一个可行的搜索方向)0(d ρ搜索，确定最佳的步长0α使函数值沿)0(d ρ方向下降最大，得到)1(X 点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为 ),2,1,0()()()1(Λρ=+=+k d X X K K K K α （4.2） 在上式中， ()K d r 是第是 k+1 次搜索或迭代方向，称为搜索方向（迭代方向）。 由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点)(k X 、搜索方向)(k d ρ和迭代步长K α，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向)(k d ρ上确定最优步长K α的方法，本章我们将讨论如何确定搜索方向)(k d ρ。 最常用的数值方法是搜索方法，其基本思想如下图所示： 0)(0)(0)(*2*1*=??=??=??n x X f x X f x X f M %最速下降梯度法matlab程序 % Steepest Descent Method % By Kshitij Deshpande clc clear all warning off prompt = {\'Coeficients if X1=\',\'Coefficients of X2=\',\'Coefficeint of X1X2=\',\'Initial Point=\'}; def = {\'[2 1 0]\',\'[1 -1 0]\',\'2\',\'[0 0]\'}; a=inputdlg(prompt,\'Data\',1,def); a=char(a); [m,n]=size(a); x1 = eval(a(1,1:n));x2=eval(a(2,1:n));x1x2=eval(a(3,1:n));X1=eval(a(4,1:n)); delf1(1) = polyval(polyder(x1),X1(1)); delf1(1) = (delf1(1))+(x1x2*X1(2)); delf1(2) = polyval(polyder(x2),X1(1)); delf1(2) = (delf1(2))+(x1x2*X1(1)); s=-delf1; %%%%%%%%%% %report srep(1,1:2)=s; %%%%%%%%%% x1new(1)=s(1)^2;x1new(2)=2*X1(1)*s(1);x1new(3) = X1(1)^2; x1new=x1new*x1(1); x1new_(2)=x1(2)*s(1);x1new_(3)=x1(2)*X1(1); x1new = x1new+x1new_; x2new(1)=s(2)^2;x2new(2)=2*X1(2)*s(2);x2new(3) = X1(2)^2; x2new=x2new*x2(1); x2new_(2)=x2(2)*s(2);x2new_(3)=x2(2)*X1(2); x2new = x2new+x2new_; x1x2new(1)=s(1)*s(2);x1x2new(2)=X1(1)*s(2)+X1(2)*s(1);x1x2new(3)=X1(1)*X1(2); x1x2new=x1x2*x1x2new; df = polyder(x1new+x2new+x1x2new); lambda(1) = roots(df); X1=X1+lambda(1)*s; Xrep(1,1:2)=X1; delf1(1) = polyval(polyder(x1),X1(1)); delf1(1) = (delf1(1))+(x1x2*X1(2)); delf1(2) = polyval(polyder(x2),X1(2)); delf1(2) = (delf1(2))+(x1x2*X1(1)); if all(X1)== 0 fprintf(\'%d %d is the optimum point\',X1(1),X1(2)); end 课程设计报告 课程名称面向对象程序设计 课题名称 专业信息科学与计算 班级信息科学060 学号 姓名 指导教师刘洞波刘长松谭小兰 2009年 6 月14 日 一、设计内容与设计要求 1.课程设计目的： 面向对象程序设计课程设计是集中实践性环节之一，是学习完《面向对象程序设计》课程后进行的一次全面的综合练习。要求学生达到熟练掌握C++语言的基本知识和技能；基本掌握面向对象程序设计的思想和方法；能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题，从而提高动手编程解决实际问题的能力。 2.课题题目 1）公司库存管理系统 2）高校学籍管理系统 3）高校工资管理系统 4）高校人事管理系统 5）公司人员管理系统 6）通讯录程序设计 7）学生成绩管理系统 8) 图书管理系统 9）文本编辑器的设计与实现 10）学生考勤管理系统 3．设计要求： ⑴设计课题题目：每位同学根据自己学号除以10所得的余数加一选择相 应题号的课题。换题者不记成绩。 ⑵根据自己对应的课题完成以下主要工作：①完成系统需求分析：包括 系统设计目的与意义；系统功能需求（系统流程图）；输入输出的要求。②完成系统总体设计：包括系统功能分析；系统功能模块划分与设计（系统功能模块图）。③完成系统详细设计：包括数据库需求分析；数据库概念结构设计（E －R图）；数据库逻辑结构设计；类层次图；界面设计与各功能模块实现。④系统调试：调试出现的主要问题，编译语法错误及修改，重点是运行逻辑问题修改和调整。⑤使用说明书及编程体会：说明如何使用你编写的程序，详细列出每一步的操作步骤。⑥关键源程序（带注释） ⑶按规定格式完成课程设计报告，将其打印稿(A4纸)上交给老师存档。 ⑷不得抄袭他人程序、课程设计报告，每个人应体现自己的个性设计。 二、进度安排 第16 周E411 星期一8：00——12：00 E411 星期二8：00——12：00 E411 星期三8：00——12：00 E411 星期五8：00——12：00 第17 周 E413 星期二14:30——18:30 E412 星期三8：00——12：00 三、参考书籍 1.《C＋＋程序设计课程设计》刘振安编著 TP312C563 2.《C++ Builder和Delphi课程设计与系统开发案例》伍俊良清华大学出版社2004 2002最速下降法
最速下降法
最优化方法课程设计参考模版
最速下降法原理及其算法实现
最速下降法
无约束优化方法(最速下降法_牛顿法)
最速下降法Matlab程序
(完整版)最优化毕业课程设计—最速下降法
相关主题
文本预览