_无约束非线性规划实验实例

格式：doc
大小：33.50 KB
文档页数：3

下载文档原格式

非线性规划无约束问题.pptx

器在单位时间内的经济效益是最好的？
4
非线性规划
目标函数或约束条件中有非线性函数的规划问题
5
非线性规划的最优解可能在其可行域中的任意一点达到
不一定是全局最优解
6
背景理论计算相对于计算要求，计算能力仍十分有限
7
8
背景为加快计算速度，必须明确各种方法的特点，
以针对不同问题选择最合适的方法
f(x2)＞f(x1)，去掉[a0,x2]，此时x*[x2,b0]
f(x)
o a0 x2 x1 x*
b0 x
x1,x2 在x*的左侧
39
f(x2)＝f(x1)： a.去掉[x1,b0]，此时x*[a0,x1] b.去掉[a0,x2]，此时x*[x2,b0]
f(x)
o a0 x2 x* x1 b x x1,x2 在x*的两侧0
2
f
(1.941,
3.854)
31.794 9.764
9.764 4
H
(
x2
)
2
f
(1.053,1.028)
11.194 2.212
2.212 4
H
(
x3
)
2
f
(0.6117,1.4929)
0.519 4.447
4.447
4
31
求得各点的H特征值和稳定点类型如下：
32
33
一维搜索法多项式近似
斐波那契（Fibonacci）法（分数法） 0.618法无需求导，根据函数值判断搜索方向适用于求解已知极值区间的单峰函数
37
一维搜索法（消去法）
f(x2)＜f(x1)，去掉[x1,b0]，此时x*[a0,x1]

最速下降法原理及例题实例

表 1-1 迭代次数k
Xk (0.00,3.00)T (2.70,1.51)T (2.52,1.20)T (2.43,1.25)T (2.37,1.16)T (2.33,1.18)T (2.30,1.14)T (2.28,1.15)T
f (X k ) 52.00
0.34 0.09
∇f ( X k ) (−44, 24)T (0.73,1.28)T (0.80, −0.48)T (0.18, 0.28)T (0.30, −0.20)T (0.08, 0.12)T (0.15, −0.08)T (0.0算目标函数的梯度和 Hesse 阵
设d
(k )
= [ d1 , d 2 ] ， ∇f ( X ( k ) ) = [ g1 , g 2 ] 得到精确一维搜索步长 αk = g1d1 + g 2 d 2 3d + d 2 2 − 2d1d 2
2 1
取X
(1)
= (0, 0)T ，则 ∇f ( X (1) ) = [ −2, 0] ，所以 d (1) = −∇f ( X (1) ) = [ 2, 0 ] ，
求单变量极小化问题：
min f ( x 0 + tp 0 ) = min f (44t , 3 − 24t )
t ≥0 t ≥0
= min(44t − 2)4 + (92t − 6)2
t ≥0
的最优解 t 0 ，由 0.618 法可得 t 0 = 0.06 ，于是
X 1 = x 0 + t 0 p 0 = (2.70,1.51)T ∇f ( X 1 ) = (0.73,1.28)T ∇f ( X 1 ) = 1.47 > ε
10 −2 ，停止计算，所以 X (9) = [ 0.988, 0.988] 作为问题的最优解。

用最速下降法求解无约束非线性规划问题

运筹学实习报告姓名： xxxxxxxxxx 学号： xxxxxxxxxxx 专业班级： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日题目：用最速下降法求解无约束非线性规划问题摘要：无约束最优化问题的求解方法分为解析法和直接法两大类。

解析法需要计算函数的梯度，其中最速下降法就属于解析法中的一种。

对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。

本文通过理论的计算方法，进一步分析，最后用c++编程实现求出允许误差内的最优解。

此编程可用于计算符合下列形式的函数求最优解过程：f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中：a[i] (i=0,1,2,3,4,5) 为函数的系数。

本文以“ 李占利主编，中国矿业大学出版社出版”的《最优化理论与方法》第五章 “无约束最优化方法，5.1 最速下降法 ”例5—1为实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。

然后应用c++语言编程，得到在精度范围内的精确最优解。

C++编程计算的最优解为 : T x x ]0329218.0,00823045.0[)3(*-==。

即转化为分数结果为：⎥⎦⎤⎢⎣⎡-==412432)3(*x x 。

满足精度要求的模为：1010736154.0||||)3(=<=εp 。

关键词：无约束非线性规划解析法最速下降法梯度模最优解一、算法思想无约束最优化方法中的最速下降法首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。

6-3无约束非线性规划问题的求解

2. 搜索步长: k 取最优步长 , 即满足 f ( x k k d k ) min f ( x k d k ) 。
梯度法算法步骤：
1. 给定初始点 x 1 R n , 允许误差 0 , 令k 1 。 2. 计算搜索方向 d k f ( x k ) ;
3. 若 || d k || , 则停止计算， x k 为所求极值点；否则，求最优步长 k
无约束非线性规划问题的求解方法分为解析法和直接法两类。
解析法
需要计算函数的梯度，本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法
直接法仅通过比较目标函数值的大小来移动迭代点。本章
主要介绍步长加速法等直接方法。
一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。
得最佳步长k
(f ( X k ))T f ( X k ) ( f ( X ( k ) ))T P ( k ) k T (f ( X k )) Af ( X k ) f ( X k )T H ( X k )f ( X k )
H( Xk ) A
若函数f(x)不是二次函数，可用上式得到k的近似值.
2 2 1 min f ( X ) 2 x x 例6-8 用最速下降法求解： ,2 初始点 X 0 1 1
1 精度 10 。

解因为函数f(x)为二次函数，故可用上述公式计算最佳步长k
4 x f ( X ) 1 2 x2
4 0 H(X ) 0 2
使得 f ( x k k d k ) min f ( x k d k )。

第五小组_非线性规划-无约束极值问题

6 12 6 /17 ( , ) 17 17 12 /17 f ( X (1) )T f ( X (1) ) 1 0 = = = -12 f ( X (0) )T f ( X (0) ) 289 (-12, 6) 6 P (1) = -f ( X (1) ) + 0 P (0) f ( X (1) )T P (1) 17 l1 = = (1) T (1) ( P ) AP 10 X (2) = X (1) + l1 P (1) 1 = 1 6 /17 1 12 90 210 = - + = , 12 /17 289 -6 289 289
但P(i) ≠0 ,A为正定，即
a1 p(i )T AP(i ) = 0
p(i )T AP(i ) = 0 故必有ai= 0,i =1,2,L从而P（1）， P（2），… P（n）线性独立
非线性规划：无约束极值问题
梯度法共轭梯度法变尺度法正定二次函数极小问题
二、基本定理
1 T • 无约束极值的一个特殊情形是： min f ( x) = X AX + BT X + c 2
梯度法共轭梯度法变尺度法
计算步骤：
（计算H ( k )，P k） = - H ( k )f ( X ( k ) ) （在P 0）方向进行一维搜索，确定最佳步长l0
min f ( X ( k ) + lk P ( k ) ) = f ( X ( k ) + lk P ( k ) )
l
则X ( k +1) = X ( k ) + lk P ( k ) 满足精度要求，则停止迭代；否则则重复上述步骤

非线性-无约束规划

6）实用收敛性：）
定义最优解集如下 S* = { x | x 具有某种性质 } 例：S*={x| x---g.opt} S*={x| x---l.opt} S*={x|∇f(x)=0} S*={x| f’(x)≤β} (β为给定实数,称为阈值）当下列情况之一成立时当下列情况之一成立时，称算法收敛具有该性质点之一成立时， 1°∃x(k) ∈S*; ° 2°∀k，{X(k)}任意极限点∈S* ° 任意极限点∈ 任意极限点
* ak 为最优步长。最优步长。则称
根据单变量的驻点条件: 根据单变量的驻点条件 d f(xk+akPk)/dak=0 （当ak=ak* 时）以及复合函数的求导法则可得：以及复合函数的求导法则可得：
∇f ( x
k +1 T
) P =0
k
2）缩小区间的非精确一维搜索
（1）单峰的概念）若对任意λ 若对任意 1 ,λ2, α≤ 1º 若α2 ≤
停
11. 最优步长的一维搜索 1) 精确一维搜索（假定求目标函数极小值）假定求目标函数极小值） * ak 是在给定 k和方向是目标函数，设f(X)是目标函数，如果是在给定X 是目标函数矢量P 通过f(x)=f(xk+akPk) 的极小化而产生矢量 k下，通过
ak* = arg ak min f ( x k + ak P k )
∂ u ∂u ∂u ∂u = cos α + cos β + cos γ ∂ l ∂x ∂y ∂r
2. 海瑟矩阵
海瑟矩阵是对称形式：
∂2 f ( X ) ∂x12 ∂2 f ( X ) 2 H ( X ) = ∇ f ( X ) = ∂x2 ∂x1 ...... ∂2 f ( X ) ∂xn ∂x1

第三章无约束非线性规划

的值越大，函数f ( x )在xk 处下降量越大。由Cauchy Schwartz 不等式：
T |gk d k | ||d k ||||gk || T 可知，当且仅当d k gk时，gk d k 最小， gk d k 最大，从而 T
gk 是最速下降方向。以-gk 为下降方向的方法叫最速下降法。
#
最优性条件
迭代算法的步骤第一步：给定最优解的一个初始估计，选择初始点x (0)，置k 0；第二步：如果x ( k )满足最优解估计的终止条件，停止迭代；第三步：确定下降方向d ( k ) , 使得目标函数f ( x )从x ( k )出发，沿 d ( k )方向，在射线x ( k ) d ( k ) ( 0)上选取步长k，使得 f(x ( k ) k d ( k ) )<f ( x ( k ) ) 则令x ( k 1) x ( k ) k d ( k ) . 第四步：得到最优解的一个更好的估计x ( k 1) x ( k ) k d ( k )，置 k k 1后转步2.
#
• • • • • • • • • • • • • • • • • • • • • • • •
function [x,minf] = minNewton(f,x0,eps) format long; if nargin == 2 eps = 1.0e-6; end df = diff(f); d2f = diff(df); k = 0; tol = 1; while tol>eps dfx = subs(df,findsym(df),x0); if diff(d2f) == 0 d2fx = double(d2f); else d2fx = subs(d2f,findsym(d2f),x0); end x1 = x0 - dfx/d2fx; k = k + 1; tol = abs(dfx); x0 = x1; end x = x1; minf = subs(f,findsym(f),x); format short;

无约束非线性规划

常用的确定搜索方向的方法。最速下降法共轭梯度法牛顿法拟牛顿法（变尺度法）
一、最速下降法
问题：在x (k)处，沿什么方向d (k)，函数f(x)下降最快？
结论：负梯度方向是函数的最速下降方向。
最速下降法就是以x (k)处的负梯度方向作为搜索方向，即令
d (k) f (x(k) )
求解问题
研究生《高级运筹学》课件
无约束非线性规划
2015年5月
本章内容
第一节：最优性条件第二节：一维搜索第三节：最速下降法和共轭梯度法第四节：牛顿法和拟牛顿法
第一节: 最优性条件
本章仅讨论如下无约束非线性规划问题：
min f (x)
xRn
假定f(x)具有二阶连续偏导数。
一、无约束极小化问题的最优性条件
计算函数值， f1＝f（a1）， f2＝f（b1）有下列三种情况：
f(b1) f(a1)
f(a1) f(b1)
f(a1)
f(b1)
a a1
b1
b
a a1
b1 b
a a1
b1 b
综合为两种情况：
①若f(a1)<f(b1), 则取 [a,b1]为缩短后的搜索区间。
②若f(a1)f(b1), 则取 [a1,b]为缩短后的搜索区间。
(k)
(k)
k
当方向d (k)给定，求最佳步长k, 就是求一元函数
() f (x(k) d (k) )
的极小点问题。这一过程称为一维搜索。
二、一维搜索的方法：
1. 精确线搜索，即解方程： d() 0 d
2. 试探法；按照某种方式找试探点，通过一系列试探点的比较确定极小点。 3. 函数逼近法：用较简单的曲线近似代替原来的曲线，用近似曲线的极小点来估计原曲线的极小点。

运筹学实验报告之非线性规划

数学与软件科学学院实验报告学期：2012至2013 第1学期 2012年11月23日课程名称: 运筹学专业:数学与应用数学 2011级1班实验编号：2 实验项目：非线性规划指导教师：黄娟姓名：杨志刚学号：2011060151 实验成绩：＿＿＿＿＿一、实验目的及要求了解Matlab 优化工具箱中约束优化函数和无约束优化函数，掌握函数调用格式和参数的具体含义，熟悉M 函数的编写，能利用Matlab 求解非线性规划问题。

二、实验内容编写相应的M 函数和M 文件，调用Matlab 优化工具箱中相应的优化函数，并能正确读取结果。

三、实验步骤(该部分不够填写.请填写附页)调用函数fmincon （）求解约束非线性规划的步骤<1> 把约束非线性规划问题化为要求的格式初始点为x0=（0，1）’<2> 编写目标函数的M 函数(MP_fun.m), 并保存。

function y=MP_fun(x)y=x(1)*x(1)-x(2);<3> 编写约束函数的M 函数(MP_con.m), 并保存。

function [c, ceq]=MP_con(x)c=[x(1)*x(1)+x(2)*x(2)-4];ceq=[ ];<4> 编写M 文件(MP.m)，并保存。

x0=[0;1]; xm=[-inf;1/2]; xM=[0;inf];aeq=[]; beq=[];[x,f_opt,flag]=fmincon(…MP_fun', x0, [], [], aeq, beq, xm, xM, …MP_con')<5> 运行M 文件. 在》后输入MP ，按“Enter”键。

调用函数fminunc （）求解无约束非线性规划的步骤<1> 把无约束非线性规划问题化为要求的格式min f(x1,x2)=x1^2+8*x1+x2^2-4*x2初始点x0=(7,8)‟.<2> 编写目标函数的M 函数(UMP_fun.m), 并保存。

实验五--非线性规划

当矩阵ＨJk ＩT Jk 为病态矩阵时，用G − N 算法可能得不到正确的解，甚至到ＨJk ＩT Jk 不可逆时， L − M 算法中有两个主要的步骤：一是解方程｛Q Ｋ µI ｝！x ］ −∇S Ｈx(k) Ｉ（其中µ 为阻尼系数）ＱＮ给定初始点x(0) ，选取参数β ∈ ＨＰ, ＱＩ，µν > Ｑ精度ε > Ｐ，置k ］Ｐ；ＲＮ计算f Ｈx(k) Ｉ, S Ｈx(k) Ｉ；ＳＮ计算∇f Ｈx(k) Ｉ；ＴＮ计算∇S Ｈx(k) Ｉ］Ｈ∇f Ｈx(k) ＩＩT f Ｈx(k) Ｉ；ＵＮ令Q ］Ｈ∇f Ｈx(k) ＩＩT ∇f Ｈx(k) Ｉ解方程｛Q Ｋ µI ｝！x ］ −∇S Ｈx(k) Ｉ；ＶＮ令x(k+1) ］ x(k) Ｋ！x，计算终止条件是否满足，不满足转Ｗ；ＷＮ若S Ｈx(k+1) Ｉ < S Ｈx(k) ＩＫ β Ｈ∇S Ｈx(k) ＩＩT ！x，令µ ］ µ/ν ，转Ｘ，否则令µ ］ µ ∗ ν ，转Ｕ；ＸＮ令k ］ k ＫＱＬ转ＲＮＱ function ｛ x Ｌ minf ｝］ minLMＨ f Ｌ x0 Ｌ beta Ｌ u Ｌ v Ｌ var Ｌ eps ＩＲ format long ［ＳＴＵ end Ｖ S ］ transpose Ｈ f Ｉ ∗ f ［Ｗ k ］ length Ｈ f Ｉ［Ｘ n ］ length Ｈ x0 Ｉ［Ｙ x0 ］ transpose Ｈ x0 Ｉ［ＱＰ A ］ jacobian Ｈ f Ｌ var Ｉ［ＱＱ tol ］Ｑ［Ｔ i f nargin ］］Ｖ eps ］ＱＮＰ e − Ｖ［
xk+1 ］ xk − ＨJk ＩT Jk
−1

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

无约束非线性规划求解
例1125 2
min ()sin(6)x f x e x -=⋅
function minf1125()
x0=1;
[x,y]=fminsearch(@fun,x0)
function y=fun(x)
y=exp(-x*x)*sin(6*x);
在命令窗口输入：
Minf1125回车
>> minf1125
x =
0.7448
y =
-0.5573
例1126 4422121212m in 143824120y x x x x x x =+---+
function minf1126()
x0=[7,7];
[x,y]=fminsearch(@fun,x0)
function y=fun(x)
y=x(1)^4+x(2)^4-14*x(1)^2-38*x(2)^2-24*x(1)+120*x(2);
在命令窗口输入：
Minf1126回车
>> minf1126
x =
3.0000 3.0000
x =
3.0000 3.0000
y =
-18.000
例1127：用最速下降法解下列问题
22
12m in ()2f x x x =+ 初始条件 (1)[1,1],0.0001T
x ε== 分析：
1、编写一个梯度函数程序fun1gra.m
2、求(可以调用函数fminsearch )函数fungetlamada.m
3、最速下降法主程序main1.m
第一步：计算梯度程序 fun1gra.m
function r=fun1gra(x)
%最速下降法求解示例
%函数f(x)=2*x1^2+x2^2的梯度的计算
%
r(1)=4*x(1);
r(2)=2*x(2);
第二步：求()k λ最优的目标函数
function r=fungetlamada(lamada)
%关于lamada 的一元函数，求最优步长
global x0
d=fun1gra(x0);
r=2*(x0(1)-lamada*d(1))^2+(x0(2)-lamada*d(2))^2;
%注意负号表示是负梯度
第三步：主程序main1.m
%最速下降方法实现一个非线性最优化问题
% min f(x)=2*x1^2+x2^2
global x0
x0=[ 1 1 ];
yefi=0.0001;
k=1;
d=-fun1gra(x0);
lamada=1;
while sqrt(sum(d.^2))>=yefi
lamada=fminsearch('fungetlamada',lamada);%求最优步长lamada
x0=x0-lamada*fun1gra(x0);%计算x0
d=fun1gra(x0);%计算梯度
k=k+1;%迭代次数
end
disp('x='),disp(x0),disp('k='),disp(k),disp('funobj='),disp(2*x0(1)^2+x0(2)^2) 实验任务：分别用优化工具箱和最速下降法求解4.2（2）、4.3并比较。