无约束最优化问题的基本研究毕业论文.docx
《无约束最优化问题的基本研究毕业论文.docx》由会员分享，可在线阅读，更多相关《无约束最优化问题的基本研究毕业论文.docx（50页珍藏版）》请在冰点文库上搜索。
无约束最优化问题的基本研究毕业论文
关于无约束最优化问题求解的基本研究
摘要
无约束最优化计算方法是数值计算领域中十分活跃的研究课题之一，快速的求解无约束最优化问题，除了自身的重要性以外，还体现在它也构成一些约束最优化问题的子问题.因此，对于无约束最优化问题，如何快速有效的求解一直是优化工作者十分关心的事.论文研究求解无约束最优化问题的几种主要的导数法，并且讨论了这些方法的优缺点以及每种方法的适用范围.同事论文分别对每
种方法给出了具体实例，并对例子进行了matlab软件实现
关键词：
无约束最优化；导数法；极值；精确度
Abstract
Unconstrainedoptimizationnumericalcalculationmethodisveryactiveinthefieldofresearch,oneofthemostrapidlysolvingunconstrainedoptimizationproblems,inadditiontoitsimportanee,isalsoreflectedinsomeoftheconstraintsthatitalsoconstitutesasub-problemofoptimizationproblems.Therefore,forunconstrainedoptimizationproblems,howfastandeffectivesolutionhasbeenoptimizedworkersveryconcernedabout.Thesisforsolvingunconstrainedoptimizationproblemsseveralmajorderivativemethod,anddiscussestheadvantagesanddisadvantagesofthesemethodsaswellasthescopeofapplicationofeachmethod.Colleaguespapersforeachmethodwerespecificexamplesaregiven,andexamplesofthematlabsoftware
Keyword:
UnconstrainedoptimizationDerivativemethodExtremumAccuracy
摘要1
ABSTRACT2
第一章绪论4
1.1研究背景与意义4
1.2问题阐述及简介4
第二章无约束问题的极值条件6
2.1.无约束极值问题6
2.2必要条件6
2.3二阶充分条件8
2.4充要条件8
第三章求解无约束最优化的几种主要方法10
3.1最速下降法10
3.2牛顿法15
3.3修正牛顿法19
3.4共轭梯度法23
3.5变尺度法26
结束语37
参考文献38
致谢39
第一章绪论
1.1研究背景与意义
追求最优化目标是人类共同的理想，最优化就是从众多可能方案中选出最佳方案，以达到最优目标.最优化理论和算法是在第二次世界大战后迅速发展起来的一门新兴的应用数学分支，它是一门应用性很强的年轻学科•虽然最优化可以
追朔到很古老的极值问题，但是直到1947年Dantzig提出一般线性规划问题的单纯形法之后，它才成为一门独立的学科•近三、四十年来随着现代科技的发展和电子计算机的广泛应用，进一步推动了最优化的迅猛发展及其理论和算法的研究.现在最优化理论已广泛应用与生产、管理、军事国防、政府决策、交通运输、经济规划等方面•
无约束最优化计算方法不仅本身有着不少实际应用，而且与约束最优化计算方法有着紧密的联系：
一方面有些处理无约束最优化问题的方法能直接推广应用于约束最优化问题；另一方面，还可以把一些约束最优化问题转化为无约束最优化问题来处理.因此从这个意义上讲，无约束最优化计算方法也是处理约束最优化问题的基本方法.
研究求解无约束最优化问题的有关理论和算法，在近几十年来迅速发展并且
日趋成熟•随着计算机的发展和普遍应用，作为一种有效的最优化方法无约束最优化方法在工程设计、管理优化、系统分析等方面的应用日益开拓，愈来愈受到应用部门的重视，所以研究无约束最优化问题的计算方法是意义重大的
1.2问题阐述及简介
无约束法指寻求n元实函数f（X）在整个n维向量空间in上的最优值点的方法.这类方法的意义在于：
虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解•
无约束最优化方法大多是逐次一维搜索的迭代算法•这类迭代算法可分
为两类.一类不涉及导数，只用到函数值，称为直接法•另一类需要用目标函数的导函数，称为解析法•这些迭代算法的基本思想是：
在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点.然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止.根据搜索方向的取法不同，可以有各种算法.属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等.属于解析型的算法有：
梯度法：
又称最速下降法.这是早期的解析法，收敛速度较慢.牛顿法：
收敛速度快，但不稳定，计算也较困难.共轭梯度法：
收敛较快，效果较好.变尺度法：
这
是一类效率较高的方法•其中达维登-弗莱彻-鲍威尔变尺度法，简称DFP法，是最常用的方法.本文主要研究无约束最优化问题中主要的几种解析法的算法理论，并对各个方法进行了举例分析和matlab软件实现.
第二章无约束问题的极值条件
2.1.无约束极值问题
考虑非线性规划问题
minfXXRn（2.1）
其中fX是定义在Rn上的实函数，这个问题是求fX在n维欧式空间的极小点，称为无约束极值问题，这是一个古典的极值问题•
2.2必要条件
为研究函数fX的极值条件，先介绍一个定理
定理2.1设函数fX在点X可微，如果存在方向d，使'fXd：
：
：
0，则
存在、0，使得对每个…0「，有fXdfX.
证明函数fXd在X的一阶Taylor展开式为
T
fXd=fX+■IfXd+：
d
=f（X（XJd创"（2.2）
-丸J
c|/d
其中当」0时，.■0.
由于IfXd：
：
：
0，当I'|充分小时，在（1.3.2）式中
Vf（XTd+
-：
IN
因此存在J“・0，使得'三iO,J时，有
-T
九可（X）d+
从而由（2.2）式得出
fNdfX.
利用上述定理可以证明局部极小点的一阶必要条件.
定理2.2设函数fX在点X可微，若X时局部最小点，贝U梯度\fX=0
证明用反证法，设VfX=0,令方向d=-\fX，则有
一T一T—一
Vf（X）d=-^f（X）Vf（X尸-Vf（X
根据定理2.1，必存在心＞0，使得当.•三［0,；：
〕时，成立
fXd:
:
:
fX
这与X是局部极小点矛盾
下面，利用函数fX的Hesse矩阵，给出局部极小点的二阶必要条件
定理2.3设函数fX在点X处二次可微，若X是局部极小点，则梯度
ifX=0,并且Hesse矩阵'2fX半正定
证明定理1.3.2已经证明'fX=0,现在只需证明Hesse矩阵'2fX半正定.
设d是任意一个n维向量，由于fX在X处二次可微，且ifX=0，则有
f（X+九d）=f（X）+〕九2dP2f（X）d+o（扎d|$）
2，
经移项整理，得到
f（X+kd）-f（X）1T2°（IIM）
2dfXd2（2.3）
扎2扎
由于x是局部极小点，当內充分小时，必有
fXd-fX
因此由（2.3）式推得
即12fX是半正定的.
2.3二阶充分条件
下面给出局部极小点的二阶充分条件
定理2.4设函数fX在点X处可微，若梯度'、fX=0,且Hesse矩阵
\2fX正定，则X是局部极小点.
证明由于IfX1=0,fX在X的二阶Taylor展开式为
（2.4）
——1—T2———I—2
f（X）=f（X^-（X-X）v2f（XXX_X）+o（|X—X）
设l2fX的最小特征值为'min0，由于'2fX正定，必有
（X-X）V2f（XXX—X）上Amin|X—X『
从而由（1.3.4）式得出
-
「o（||x-X
2X-X
|—2
f（XEf（X）+
2
X-X
-11
一
fX-fX，即X是fX的局部极小点
2.4充要条件
前面的几个定理分别给出无约束极值的必要条件和充分条件，这些条件都不是充分必要条件，而且利用这些条件只能研究局部极小点.下面在函数凸性的假设下，给出全局极小点的充分必要条件
定理2.5设fX是定义在:
n上的可微凸函数，X：
n，则X为全局极小点的
充分必要条件是梯度X=0
证明必要性是显然的，若X是全局极小点，自然是局部极小点，根据定理
1.3.2，必有ifX=0.
T
现在证明充分性，设Ifxi=o,则对任意的x:
n，有fxx吠总0，
由于fX是可微的凸函数，则有
TfX_fXifXXX=fX,
即X是全局极小点
在上述定理中，如果fX是严格凸函数，则全局极小值是唯一的
上面介绍的几个极值条件，是针对极小化问题给出的，对于极大化问题，可以给出类似的定理
例2.1利用极值条件解下列问题
min
def2
fX=x1-1x1x2-2x1
先求驻点•由于
渐=4x13-2x^2，吋=2x2-X〔X?
令fx=0,即
2x2=0，
解此方程组，得到驻点
—Tt
X=xi,x21,0.
再利用极值条件判断X是否为极小点，由于目标函数的Hesse矩阵
严2-201]02
由此可知
第三章求解无约束最优化的几种主要方法
3.1最速下降法
最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础•作为一种基本的算法，他在最优化方法中占有重要地位•
3.1.1最速下降法的算法原理
最速下降法从目标函数的
最速下降法的搜索法向是目标函数的负梯度方向,负梯度方向一直前进，直到到达目标函数的最低点
已知目标函数在X（k）点的梯度为：
当求目标函数的最小点时，由于函数沿负梯度方向下降最快，故在
方向应取该点的负梯度方向，即
屮一W（X⑹）
||可（X（k）J
显然，S（k）为单位向量.这样第k1次迭代计算所得的新点为
负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最
3.1.2步长〉k的两种取法：
一种方法是任意给定一个初始步长，使满足条件：
f（X（k）七泸）s（k））：
：
：
f（X（k））
另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步
长〉，即对目标函数极小，以得到最优步长：
minf（X（k）■〉S（k））=f（X（k^:
-（k）S（k））
:
-o
以此最优步长作为由X（k）点出发沿该点的负梯度方向探索的步长:
（k）.
这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来
进行判断：
Wf（x（k）X
f（X（k））—f（X
“|f（x（kJ"
iv（k）V（k」）||£卞
[|X-X||x
3.1.3最速下降法算法步骤
用最速下降法求无约束多维极值问题minf（X）,X•：
n的算法步骤如下：
（1）取初始点XC，精度呂＞°，令k=0
（2）计算搜索方向V（k）=」、f（x（k）），其中\f（X（k））表示函数f（X）在点X（k）处的梯度；
（3）若V（k）乞；，则停止计算；否则，从X（k）出发，沿V（k）进行一维搜索，即求'k，使得f（X（k）•'kV（k））=minf（X⑹…V（k））.此处的一维搜索可
■-0
以用黄金分割法等算法
（4）
令X（k1）二X（k）•'kV（k）,k=k1，转步骤
（2）.
¥
=J42+162=16.492
为'fX（0）二[416]T.
:
x2
梯度的模为ifX（0）
X01
梯度的负方向为S（0）-[416]T=-[0.2430.970]T
16.492
fX（0）:
S（0）=（2-0.243:
）24（2-0.970:
）2
dfX（0）*S（0）
2（2-0.243：
）（-0.243）8（2-0.970）（-0.970）d:
=7.645：
-16.492
人dfX（0）•：
・s（0）亠「*
令0,求出〉=2.157，算得
do
X⑴二[1.476-0.0923]T,'fX⑴二[2.952-0.738]丁
梯度的模为（X⑴|=J（2.952$+（-0.738$=3.043
fX⑴：
S⑴=（1.476-0.970：
）24（-0.09230.243：
）2
dfX⑴•⑴*
2.354—3.043=0，得至V:
=1.293
d:
X⑵-[0.2220.222]T/fX⑵产[0.4441.776]T
|Vf（X⑵j|=1.831＞卸=10，
未达到收敛要求，所以还应继续探索，下一步探索方向为
1
S⑵[0.4441.776]T二-[0.2420.970]T
1.831
X—XfS（2=0.222一°.242讣「宀^.222+0.970。
」Lx23）j
fX⑵S⑵严（0.222-0.242：
）24（0.2220.970：
）2
dfX⑴S
（1）
7.644：
-1.830=0
d:
得到：
:
=0.239
x⑶二[0.164-0.0098]T,lfx⑶二[0.328-0.0784]丁
円（x⑶|=0.337=10*
继续探索，当探索到点x⑺二[0.0016-0.000096f时,
\fx（7）0.00「32-于达到预定的收敛要求，因而可认为/二x⑺为最优
点，而fx\=（0.0016）24（-0.000096）2=2.59610~：
0为极小值.
3.1.4最速下降法的matlab实现
首先建立M文件：
function[x,val,k]=grad（fun,gfun,x0）
%功能：
用最速下降法求解无约束问题：
minf（x）
%输入：
x0是初始点，fun，gfun分别是目标函数和梯度
%输出：
x,val分别是近似最优点和最优值，k是迭代次数.
maxk=5000;%最大迭代次数
rho=0.5;sigma=0.4;
k=0;eps=1e-7;
while（kg=feval（gfun,x0）;%计算梯度
d=-g;%计算搜索方向
if（norm（d）m=0;mk=0;
while（m<20）%Armijo搜索
if（feval（fun,x0+rhoAm*d）end
m=m+1;
end
x0=x0+rhoAmk*d;
k=k+1;
end
x=x0;
val=feval（fun,x0）;
然后建立fun，gfun的n文件
functionf=fun（x）
f=x
（1）A2+4*x
（2）A2;
functiong=gfun（x）
g=[2*x
（1）,8*x
（2）]';
求解结果为
x=
0
0val=
0
3.1.5最速下降法的锯齿现象
最速下降法对初始点的选择要求不高，每一轮迭代工作量较少，它可以很快的从初始点达到极小点附近.但在接近极小点时，最速下降法却会出现锯齿现象，收敛速度很慢，因为对一般二元函数，在极小点附近可用极小点的二阶泰勒多项式来近似，而后者为凸函数时，他的等值线是一族共心椭圆，特别是当椭圆比较扁平时，最速下降法的收敛速度越慢.
至于最速下降法出现锯齿现象的原因，可以作如下粗略解释：
由fX在
Xk的泰勒展式：
「■二fXk-■IfXk=fxk■pk
Pk=-'fXk
为了出从Xk出发沿方向Pk的极小点，令
0（九卢f（X（k）+稣PP&）=0,
则有
Xk1XXk=0.
即方向Pjq=-VfXk1与方向Pk=」'fXk正交.这表明迭代产生的点列
xk［所循路径是“之”字行的.当Xk接近极小点X*时，每次迭代移动的步长很小，这样就呈现出锯齿现象，影响了收敛速度.因此常常将梯度法与其他方法
结合起来使用.
3.1.6最速下降法的说明
最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点.但它有一个严重缺点就是收敛速度慢.沿负梯度方向函数下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快.特别对等值线（面）有狭长深谷形状的函数，收敛速度更慢.其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，
如此继续下去就产生所谓的锯齿现象.即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.
3.2牛顿法
3.2.1牛顿法算法思想与原理
如前面所提到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并
不快，且愈接近极值点下降的愈慢.因此，应寻找使目标函数下降更快的方法.牛顿法就是一
种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小
值点来近似原目标函数的极小值点并逐渐逼近改点
一维目标函数f（X）在x（k）点逼近用的二次曲线（即泰勒二次多项式）为
（X⑹）=f（X（k）rf（X（k））（x-x（k））冷f（X（k））（X-X（k））2
此二次函数的极小点可由（X（k））=0求得.
对于n维问题，n为目标函数f（X）在X（k）点逼近用的二次曲线为：
（X（k）^f（X（k））：
：
£f（x（k））.[X-X（k）]^[X-X（k）]TA2f（X（k））.[X-x（k）]
令式中的Hessian\2f（x（k））=H（X（k）），则上式可改写为：
（X⑹）二f（X（）ff（X（k））.[X-X（k）]!
[X-X（k）]T.H（X（k））.[X-X（k）]
:
f（X）
当'X）=0时可求得二次曲线;:
（X）的极值点，且当且仅当改点处的Hessian矩阵为正定时有极小值点•
由上式得：
P〔（X）='、、f（X（k））-H（X（k））[XX（k）]
令l（X）=0，则If（X（k））-H（X（k））[X-X（k）]=0
若H（X（k））为可逆矩阵，将上式等号两边左乘H（X（k））'，则得
H（X（k））丨（X（k））-In[X—X（k）]=0
整理后得
x=X（k）_「H（X（k））]」Nf（X（k））
当目标函数f（X）是二次函数时，牛顿法变得极为简单、有效，这时H（X（k））是一个常
数矩阵，式
（X（k））=f（X（k）p；f-f（X（k））.[X-X（k）]2XX（k）]T.H（X（k））.[XX（k）]变成精确
:
f（X）
表达式，而利用式X二X（k）-||H（X（k））、f（X（k））作一次迭代计算所得的X就是最优点
X*•在一般情况下f（X）不一定是二次函数，则不能一步就能求出极小值，即极小值点不在
-||H（X（k））lf（X（k））方向上，但由于在X（k）点附近函数:
（X）与f（X）是近似的，所以
这个方向可以作为近似方向，可以用式X=X（k）-||H（X（k））'lf（X（k））求出点X作为一
个逼近点X（k1）.这时式X二X（k）-||H（X（k））f（X（k））可改成牛顿法的一般迭代公式：
X（k1）=X（k）-H（X（k））ff（X（k））
式中-1|H（X（k））、f（X（k））称为牛顿方向，通过这种迭代，逐次向极小值点X*逼近•
牛顿法是基于多元函数的泰勒展开而来的，它将-H（X（k））'lf（X⑹）作为探索
方向，因此它的迭代公式可直接写出来：
1
X（k1）=X（k）一屮（X（k））\f（X（k））
3.2.2牛顿法算法步骤
（1）给定初始点x（0），及精度；.0,令k=0;
（2）若fX（k））「:
；；，停止，极小点为X（k），否则转步骤（3）;
（3）计算『.2f（X（k））J，令S（k）二-H（X（k））'lf（X（k））；
（4）令X（k1）=X（k）S（k），k二k1，转步骤
（2）.
例3.2试用牛顿法求目标函数f（X）=x2*x；-x<|X2-10为-4x2•60的极小点.
解：
取X（k）-〔00T，贝U
ex!
■CX[ex?
_；2
-11
◎2f
e2f
2一
'&2欣1
r2■CX?
X=X（k）
2
H（X（k））八2f（X（k））=
;2
1
X（k°=X（k）—||H（X（k））'f（X（k））
_0121-10_8
|t_031（12-4||6
x":
即为最小点求
3.2.3牛顿法的matlab实现
首先建立M文件newton.m
function[x,fval,iterations]=newton（fun,xO,tol）
%这是一个用Newton法求解无约束优化问题的matlab程序
%第一个参数fun是一个包含函数，梯度,hessiar矩阵的M文件
%比如：
%function[f,grad,hessian]=fun_grad_hess（x）
%f=x
（1）A3+（x
（2）-
升级会员 