无约束非线性规划求解方法及其实现

无约束非线性规划求解方法及其实现

作者：杨玲 指导老师：陈素根

摘要:

非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。

关键词 最优化 共轭梯度法 非线性 无约束

1 引言

1.1 无约束非线性规划问题是最基本的非线性规划问题，在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。

1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。

2 正文

2.1主要介绍无约束非线性规划的相关概念

一个非线性规划问题的自变量x没有任何约束，或说可行域即是整个n维向量空间：nxR错误!未找到引用源。,则称

这样的非线性规划问题为无约束问题：错误!未找到引用源。或错误!未找到引用源。 。

一般我们研究的无约束非线性规划问题大都可以归结为求无约束最优化问题。

2.2 介绍无约束非线性规划的几种主要的求解方法及其实现

求解无约束非线性规划问题就是求解无约束非线性规划最优化的问题，可以表述为min,nfxxR。它的求解方法有许多种，大体上可以概括为两大类，一是直接法，二是解析法。解析法又被称为代数法，值得是通过计算fx的一阶，二阶偏导数及其函数的解析性质来实现极值的求解方法。相应的，不必计算fx的一阶、二阶偏导数及其函数的解析性质，仅用到函数值来实现近似值的求解方法叫直接法。

1. 先介绍直接法中的一维搜索方法，包括Fibonacci法和0.618法。

一维搜索方法就是在用迭代法沿某一已知方向求目标函数极小点的方法，常用的由斐波那契法和黄金分割法。

考虑一维极小值问题minatbft，若ft是,ab区间上的下单峰函数，我们将通过不断的缩短,ab的长度，来探索minatbft的近似最优解。在,ab中任意取两个关于,ab是对称的点1t和1t(不妨设,21tt并称它们为搜索点)，计算1ft与2ft并

比较它们的大小。对于单峰函数，若12ftft,则必有1*,tat，因而1,at是缩短了的单峰区间，若21ftft,则有2*,ttb，故2,tb是缩短了的单峰区间，若21ftft，则1,at和2,tb都是缩短了的单峰。因而通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，又可以获得更短的单峰区间。如此下去，在单峰区间缩短到充分小时，可以取最后的搜索点作为minatbft最优解的近似值，下面介绍斐波那契法来选取搜索点，使给定的单峰区间的长度能尽快缩短。

Fibonacci法：

若数列nF满足关系：011FF，21nnnFFF，2,3,n，则称nF为Fibonacci数列，nF称为第n个Fibonacci数，称相邻两个Fibonacci数之比1nnFF为Fibonacci分数。当用斐波那契法以n个探索点来缩短某一区间时，区间长度的第一次缩短率为1nnFF，其后各次分别为231122,,,nnnnFFFFFF，由此，若1t和2t，21tt单峰区间,ab中的第1个和第2个探索点的话，则应有比例关系11nnFtabaF，22anntFbaF，从

而11nnFtabaF，22nnFtabaF，它们关于,ab是对称的点。

如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超过精度0，这也要求最后区间的长度不超过，即nbaF。由此，按照预先给定的精度，确定使nbaF成立的最小整数n作为搜索次数，直到进行第n次探索点为止。用上述不断缩短函数fx单峰区间的方法来求minatbft的近似解是Kiefer(1953年)提出的，叫Fibonacci法。具体步骤如下：

1选取初始数据，确定单峰区间00,ab,给出搜索精度0，由nbaF确定搜索次数n；

21k，0aa，0bb，计算最初两个搜索点，按11nnFtabaF，22nnFtabaF计算1t，2t；

3while 1kn

11fft,22fft

if 12ff

2at；21tt；11nknkFtabaF；

else

1bt；12tt；12nknkFtbbaF；

end

1kk

end

4当进行至1kn时，1212ttab，此时无法比较1ft与2ft的大小来确定最终区间，为此，取211212tabtaba，其中为任意小点的数，在1t和2t这两点中，以函数值较小者为近似极小值，相应的函数值为近似极小值，并得最终区间1,at或2,tb。

由上述分析可知，斐波那契法使用对称搜索方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数达到预定的某一缩短率。

2. 下面介绍解析法中的最速下降法、牛顿法、共轭梯度法和变尺度法。

（1)最速下降法：

对基本迭代格式1kkkkxxtp，我们一般考虑从点kx出发沿哪一个方向kp，使目标函数下f降得最快。由微积分的相关知识我们可以知道，点kx的负梯度方向

()kkpfx是从点kx出发使f下降最快的方向。为此，负梯度方向()kfx为f在点kx处的最速下降方向，按基本迭代式1kkkkxxtp每一轮从点kx出发沿最速下降方向()kfx作一维搜索，来建立求解无约束极值问题的方法称之为最速下降法。该方法的特点是每轮的搜索方向都是目标函数在当前点下降最快的方向。同时，()0kfx或()kfx作为停止条件。其具体的步骤为：(a).选取初始数据。选取初始点0x，给定终止误差，令k:=0. (b).求梯度向量。计算()kfx，若()kfx，停止迭代，输出kx。否则进行(c)。 (c). 构造负梯度方向。取()kkpfx。 (d). 进行一维搜索。求kt，使得0()min()kkkkktfxtpfxtp，令1kkkkxxtp，

=1kk：进行(b).

例题：用最速下降法求解无约束非线性规划问题，2212min25fxxx，其中12,Txxx，要求选取初始点02,2Tx，终止误差610。

解：1）122,50Tfxxx,编写M文件deta f.m如下：

function.[f,df]=deta f(x);

f=x(1)^2+25*x(2)^2;

df(1)=2*x(1);

df(2)=50*x(2)^2;

2)编写M文件zuisu.m

clc

x=[2,2];

[f0,g]=deta f(x);

while norm(g)>0.000001

p=-g/norm(g);

t=1.0;f=deta f(x+t*p);

end

x=x+t*p

[f0,g]=deta f(x)

end

(2). 牛顿法：

牛顿法是求无约束最优解的一种古典解析算法，其基本思想是在寻找收敛速度最快的无约束最优化方法中，在每次迭代时，用适当的二次函数去近似目标函数f，并用迭代点指向近似二次函数极小点的方向来构造搜索方向，然后精确地求近似二次函数的极小点，以这个极小点作为f的极小点的近似值。

牛顿法的迭代步骤：

1）给定初始点和收敛精度；

2）计算kfx，kHx，1kHx

3）求11kkkkkxxKHxfx；

4）检查收敛精度，若1kkxx，则1*kxx，停止；否则1kk，返回2）继续。

牛顿法的优点是每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值变大的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有严格要求。但是牛顿法也有缺点，它对目标函数要求严格，函数必须具有连续的一、二阶导数；海赛矩阵必须正定且非奇异。还有牛顿法的计算复杂，存储量大。

(3). 共轭梯度法：

共轭梯度法最早是由计算数学家Hestenes和几何学家Stiefel

在20世纪50年代初为求解线性方程组,nAxbxR而各自独立提出的。在A为对称正定阵时，方程组,nAxbxR等价于最优化问题1min2nTTxRxAxbx，由此，Hestenes和Stief的方法也可以看做是求二次函数极小值得共轭梯度法。在1964年Fetcher和Reeves将这种方法推广到了非线性优化，得到了求一般函数极小值的共轭梯度法。对于无约束最优化问题minnxRfx，其中:nfRR连续可微有下界，共轭梯度法是解决这类问题中的最有效的数值方法之一。特别是在大规模问题上，共轭梯度法因为算法简便、所需存储量小、收敛速度快等特性而在许多工程科学领域采用。

对于无约束优化问题，给出一个初始值0x，算法迭代产生点列12,,xx。假设某一kx是无约束优化问题的解，或者该点列收敛于最优解。在第1k次迭代中，当前迭代点为kx，产生下一个迭代点1kkkkxxad，其中nkdR是搜索方向，