文档介绍：无约束非线性规划求解方法及其实现作者：杨玲指导老师：陈素根摘要:
非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组, 则称 f 为 Fibonacci 数列，
n
• • • f
Fibonacci 数，称相邻两个 Fibonacci 数之比 F-1 为 Fibonacci n
分数。当用斐波那契法以n个探索点来缩短某一区间时，区间长
F
度的第一次缩短率为，其后各次分别为
(t2 v t1)单峰区间
n
F F F
芦^，芦^，，于，由此，若t 1和12 ,
n-1 n — 2 . . . 2
[a , b ]中的第1个和第2个探索点的话，则应有比例关系
t 一 a F t F F /
_J = 2 - a 二 n-2 t = a 卄一 1 \ 疗一 a
b - a F b - a F ，从而 i F
n ， n n ，
t2 = a +卓（b-a），它们关于bb］是对称的点。
n 如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超过精度5〉0 ,这也要求最后区间的长度不超过
b 一 a b 一 a
5，即仝。由此，按照预先给定的精度5，确定使
FF
nn
成立的最小整数n作为搜索次数，直到进行第n次探索点为止。
用上述不断缩短函数f（x）单峰区间的方法来求minf °）的近似
a<t<-
解是 Kiefer（1953 年）提出的，叫 Fibonacci 法。具体步骤如下：
1 Q选取初始数据，确定单峰区间-［给出搜索精度5 >°，由
——a
〒<5确定搜索次数 n
2 k =1 a = a
， 0 ，
b=b0 ，计算最初两个搜索点，按
t = a+- (-- a)
i ~F~
n
if
f1 V f2
a=t t = t
2； 2 1；
=a+
F
n _1_ k
F
n 一 k
(b 一 a )
9
t2 = a + 字(-- a)计算 11，12；
n
» while k Vn-1 f =f (t) f = f (t)
“ “ - 2
else
b—t t — t t = b + n-1-k (b - a )
1 ; 1 2 ； 2 F
n-k
end
k—k+1
end “。当进行至k—n-1时，广t2—2(a+b)，此时无法比较
f (t1 ) 与 f (t 2 ) 的大小来确定最终区间，为此，取 t = 1 (a + b)
2 2
(b-a)，其中*为任意小点的数，在11 和2
t — a+
1
(1 ) + *
12丿
这两点中，以函数值较小者为近似极小值，相应的函数值为近似
极小值，并得最终区间b "或bl 由上述分析可知，斐波那契法使用对称搜索方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数达到预定的某一缩短率。
2. 下面介绍解析法中的最速下降法、牛顿法、共轭梯度法和变
尺度法。
最速下降法：
对基本迭代格式
Xk+1 = Xk + t p
k ，我们一般考虑从点
，使目标函数下降得最快。
x k p p 出发沿哪一个方向
Xk
由微积分的相关知识我们可以知道，点的负梯度方向
p =-f (Xk ) x
是从点
k
出发使 f 下降最快的方向。为此
负梯度方向 -V f ( X k )
fx
为在点
处的最速下降
xk
出发沿
Xk+1 = Xk +t pk
方向，按基本迭代式 k 每一轮从点
-V f(Xk)
最速下降方向作一维搜索，来建立求解无约束极值问题的方法称之为最速下降法。该方法的特点是每轮的搜索方向都是目标函数在当前点下降最快的方向。同时，
Vf(Xk )= 0或口Vf(xk)&作为停止条件。其具体的步
X0
骤为：(a).选取初始数据。选取初始点，给定终止误差,
令 k:=0.
(b).求梯度向量。计算f()，若口 f( )口，
Xk
停止迭代，输出。否则进行(c)。 (c).构造负梯度方
pk — —'Vf(Xk ) t
f(Xk +t pk ) — minf (Xk +tpk)
Xk+1 — Xk+ t
t >0
向。取。 (d). 进行一维搜索。求 k ，使得
k：k +1
进行(b).
例题：用最速下降法求解无约束非线性规划问题，
诚叮(x)= X2 + 25X2，其中X = (X!，X2)T，要求选取初始点