单纯形法
1. 算法原理
单纯形法的基本思想是：
设(0)(1)(),,...,n x x x 是n R 中的1n +个点，构成一个当前的单纯形，max min ,x x 定义如下：
{}(0)(1)()max ()max (),(),...,()n f x f x f x f x =
{}(0)(1)()min ()min (),(),...,()n f x f x f x f x = 记x 为这个单纯形除去max x 外的所有顶点的形心，
()max 01n i i x x x n =??=- ???
∑ 取max x 关于x 的反射点(1)n x +，(1)max ()n x x x x +=+-构成新的单纯形，反复上述过程，直到达到停止条件。
2. 函数min f search
1） 函数语法
min (,0)x f search fun x =
min (,0,)
[,]min (...)
[,,]min (...)
[,,,]min (...)
x f search fun x options x fval f search x fval exitflag f search x fval exitflag output f search ====
函数输入： fun ：目标函数
0x ：迭代初始点
options ：函数参数设置
函数输出：
x ：最优点
fval ：最优点对应的函数值
exitflag ：函数停止信息
1：函数收敛正常停止
0：迭代次数，目标函数计算次数达到最大数
-1：算法被输出函数停止
output ：函数运算信息
2）函数使用
BanaFun m
（1）目标函数程序.
function f BanaFun x
=不含导数解析式
()()
f x x x
=-+-
100*((2)(1)^2)^2(1(1))^2
-函数不需要导数信息。
Nelder Mead Simplex
SimplexUnc m
（2）算法参数设置：.
('arg','','','','',250,'','') =
options optimset L eScale off gradobj off MaxFunEvals display iter
SimplexUnc m
（3）函数调用运算：.
=
('arg','','','','',250,'','') options optimset L eScale off gradobj on MaxFunEvals display iter
x=-
[ 1.9,2]
x fval exitflag output f search BanaFun x options
=
[,,,]min(@,,)
3）计算结果
Iteration Func-count min f(x) Procedure
0 1 267.62
1 3 236.4
2 initial simplex
2 5 67.2672 expand
3 7 12.2776 expand
4 8 12.2776 reflect
5 10 12.277
6 contract inside
6 12 6.76772 contract inside
7 13 6.76772 reflect
8 15 6.76772 contract inside
9 17 6.76772 contract outside
10 19 6.62983 contract inside
11 21 6.55249 contract inside
12 23 6.46084 contract inside
13 24 6.46084 reflect
14 26 6.46084 contract inside
15 28 6.45544 contract outside
16 30 6.42801 expand
17 32 6.40994 expand
18 34 6.32449 expand
19 36 6.28548 expand
20 38 6.00458 expand
21 39 6.00458 reflect
22 41 5.43287 expand
24 44 4.63434 expand
25 45 4.63434 reflect
26 47 4.63434 contract inside
27 49 4.63434 contract outside
28 51 4.31027 expand
29 53 4.31027 contract inside
30 55 4.00991 expand
31 56 4.00991 reflect
32 58 3.55664 expand
33 59 3.55664 reflect
34 61 3.23438 reflect
35 63 3.23438 contract inside
36 65 2.9515 expand
37 67 2.82878 reflect
38 69 2.56426 reflect
39 71 2.54453 contract outside
40 73 2.43615 reflect
41 75 2.34358 reflect
42 77 2.28129 reflect
43 79 2.21473 reflect
44 81 2.08627 reflect
45 82 2.08627 reflect
46 84 1.86677 reflect
47 86 1.86677 contract inside
48 88 1.80424 reflect
49 90 1.58432 expand
50 91 1.58432 reflect
51 93 1.27128 expand
52 94 1.27128 reflect
53 96 1.05673 reflect
54 98 1.05673 contract inside
55 100 0.816708 expand
56 102 0.816708 contract inside
57 104 0.816708 contract inside
58 106 0.760575 reflect
59 108 0.601009 expand
60 110 0.601009 contract inside
61 112 0.516477 reflect
62 114 0.516477 contract inside
63 115 0.516477 reflect
64 117 0.416316 expand
65 119 0.416316 contract inside
66 120 0.416316 reflect
68 124 0.345716 contract inside
69 126 0.285909 expand
70 128 0.281068 reflect
71 130 0.22878 reflect
72 132 0.22878 contract inside
73 134 0.203104 expand
74 136 0.148 expand
75 138 0.0999997 expand
76 140 0.0999997 contract inside
77 141 0.0999997 reflect
78 143 0.0217142 expand
79 145 0.0217142 contract inside
80 147 0.0217142 contract inside
81 148 0.0217142 reflect
82 150 0.0217142 contract inside
83 152 0.0217142 contract inside
84 154 0.0191193 reflect
85 156 0.00610404 expand
86 158 0.00610404 contract outside
87 160 0.00261955 reflect
88 161 0.00261955 reflect
89 163 0.000256151 reflect
90 165 0.000256151 contract inside
91 166 0.000256151 reflect
92 168 0.000256151 contract inside
93 170 0.00020711 contract inside
94 172 0.00010357 contract inside
95 174 2.09236e-005 contract inside
96 176 2.09236e-005 contract inside
97 178 1.80497e-006 reflect
98 180 1.80497e-006 contract inside
99 182 1.80497e-006 contract inside 100 184 1.80497e-006 contract inside 101 185 1.80497e-006 reflect
102 187 3.74217e-007 contract inside 103 189 3.74217e-007 contract inside 104 191 3.26526e-007 contract inside 105 193 8.07652e-008 contract inside 106 195 1.66554e-008 contract inside 107 197 1.66554e-008 contract inside 108 199 1.66554e-008 contract inside 109 201 5.57089e-009 contract outside 110 203 1.86825e-009 contract inside
111 205 1.86825e-009 contract outside
112 207 5.53435e-010 contract inside
113 208 5.53435e-010 reflect
114 210 4.06855e-010 contract inside
Optimization terminated:
the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-004 and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-004
x =
1.0000 1.0000
fval =
4.0686e-010
exitflag =
1
output =
iterations: 114
funcCount: 210
algorithm: 'Nelder-Mead simplex direct search'
message: [1x196 char]
拉格朗日乘子法 约束优化问题的标准形式为： min (),..()0,1,2,...,()0,1,2,...,n i j f x x R s t g x i m h x j l ∈≤=== ,,:n i j f g h R R →其中 约束优化算法的基本思想是：通过引入效用函数的方法将约束优化问题转换为无约束问题，再利用优化迭代过程不断地更新效用函数，以使得算法收敛。 1. 罚函数法 罚函数法（内点法）的主思想是：在可行域的边界上筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数陡然增大，以示惩罚，阻止迭代点穿越边界，这样就可以将最优解“挡”在可行域之内了。 它只适用于不等式约束： min (),..0,1,2,...,n i f x x R s t g i m ∈≤= 它的可行域为： {|()0,1,2,...,}n i D x R g x i m =∈≤= 对上述约束问题，其其可行域的内点可行集0D ≠?的情况下，引入效用函数： min (,)()()B x r f x rB x =+%、 其中11()()m i i B x g x ==-∑%或1 ()|ln(())|m i i B x g x ==-∑% 算法的具体步骤如下： 给定控制误差0ε>，惩罚因子的缩小系数01c <<。 步骤1：令1k =，选定初始点(0)0x D ∈，给定10r >（一般取10）。 步骤2：以()k x 为初始点，求解无约束 min (,)()()k B x r f x r B x =+% 其中11()()m i i B x g x ==-∑%或1 ()|ln(())|m i i B x g x ==-∑%，得最优解()()k k x x r = 步骤3：若()()k k r B x ε<%，则()k x 为其近似最优解，停；否则，令,1k k r cr k k ==+， 转步骤2.
无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数f(x)=(x1-5)2+(x2-6)2 的最优解。 一、简述鲍威尔法的基本原理 从任选的初始点x⑴o出发，先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索，得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴ 再沿此方向作一维搜索，得该方向上的一维极小点x⑴. 从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向，称为新生方向。 接着，以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴ 弃去第一环方向组中的第一个方向e1，将第一环新生方向S1补在最后，构成第二环的基本搜索方向组e2,e3,S1，依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接 Xo⑵与x3⑵,又得第二环的新生方向 S2=x3⑵-xo⑵ 沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点 二、鲍威尔法的程序 #include "stdafx.h" /* 文件包含*/ #include
#include
行域 φ 内，选择一个初始点 X 然后确定一个可行 得一个目标函数有所改善的可行的新点 X 即完成了 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： s .t . min f (x ) g u (x ) ≤ 0 h v (x ) = 0 x ∈ R n u = 1, 2,..., m v = 1, 2,..., p < n 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于 这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由 m 个不等式约束条件 gu(x )≤0 所确定的可 0 搜索方向 S ，且以适当的步长沿 S 方向进行搜索，取 1 一次迭代。以新点为起始点重复上述搜索过程，每次 均按如下的基本迭代格式进行计算： X k+1=X k +α k S k (k=0,1,2,..) 逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算 不论何时终止，都可以获得比初始点好的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局 部最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集
φ(X,μ1,μ2)=F(X)+∑μ 1 G??g j X)??+∑μ2H??h k(X)?? a)可行域是凸集；b)可行域是非凸 集 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数 结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优 化问题。 m l j=1k=1 新目标函数 然后对新目标函数进行无约束极小化计算。 加权因子 间接法是结构优化设计中广泛使用的有效方法，其特点： 1）由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和数值计算的稳定性大有提高； 2）可以有效处理具有等式约束的约束优化问题； 3）目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精度，甚至导致计算失败。
项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、Newton 法（修正Newton 法）的程序。 [实验学时] 2学时 [实验准备] 1．掌握最速下降法的思想及迭代步骤。 2．掌握Newton 法的思想及迭代步骤； 3．掌握修正Newton 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题：【选作一个】 1．用最速下降法求 22120min ()25[22]0.01T f X x x X ε=+==，，，． 2．用Newton 法求 22121212min ()60104f X x x x x x x =--++-， 初始点 0[00]0.01T X ε==，，． 最速下降法 Matlab 程序： clc;clear; syms x1 x2; X=[x1,x2]; fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17; fxd1=[diff(fx,x1) diff(fx,x2)]; x=[2 3]; g=0; e=0.0005; a=1; fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); step=0; while g>e step=step+1; dk=-fan; %点x(k)处的搜索步长
ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+ak*dk; x=xu; %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); %计算目标函数点x(k+1)处一阶导数值 fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序 #include
第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由m 个不等式约束条件g u (x )≤0所确定的可行域φ内，选择一个初始点0 X 然后确定一个可行搜索方向S ，且以适当的步长沿S 方向进行搜索，取得一个目标函数有所改善的可行的新点1 X 即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算： k+1k k k =+S (k=0,1,2,..)X X α逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好 的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部 最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集 1,2,...,1,2,...,u m v p n == 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。 然后对新目标函数进行无约束极小化计算。 间接法是结构优化设计中广泛使用的有效方法，其特点： 1） 由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和 数值计算的稳定性大有提高； 2） 可以有效处理具有等式约束的约束优化问题； 3） 目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精 度，甚至导致计算失败。 a) 可行域是凸集；b)可行域是非凸集 () ()()()121211 ,,m l j k j k X F X G g X H h X φμμμμ==??=++? ?????∑∑ 新目标函数 加权因子 分数: ___________任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间： 一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差， 拉格朗日乘子法 约束优化问题的标准形式为: min (),..()0,1,2,...,()0,1,2,...,n i j f x x R s t g x i m h x j l ∈≤=== ,,:n i j f g h R R →其中 约束优化算法的基本思想就是:通过引入效用函数的方法将约束优化问题转换为无约束问题,再利用优化迭代过程不断地更新效用函数,以使得算法收敛。 1. 罚函数法 罚函数法(内点法)的主思想就是:在可行域的边界上筑起一道很高的“围墙”,当迭代点靠近边界时,目标函数陡然增大,以示惩罚,阻止迭代点穿越边界,这样就可以将最优解“挡”在可行域之内了。 它只适用于不等式约束: min (),..0,1,2,...,n i f x x R s t g i m ∈≤= 它的可行域为: {|()0,1,2,...,}n i D x R g x i m =∈≤= 对上述约束问题,其其可行域的内点可行集0D ≠?的情况下,引入效用函数: min (,)()()B x r f x rB x =+%、 其中11()()m i i B x g x ==-∑%或1 ()|ln(())|m i i B x g x ==-∑% 算法的具体步骤如下: 给定控制误差0ε>,惩罚因子的缩小系数01c <<。 步骤1:令1k =,选定初始点(0)0x D ∈,给定10r >(一般取10)。 步骤2:以()k x 为初始点,求解无约束 min (,)()()k B x r f x r B x =+% 其中11()()m i i B x g x ==-∑%或1 ()|ln(())|m i i B x g x ==-∑%,得最优解()()k k x x r = 步骤3:若()()k k r B x ε<%,则()k x 为其近似最优解,停;否则,令,1k k r cr k k ==+,转步骤2、 2. 拉格朗日乘子法 多维无约束优化算法 多维无约束优化问题的一般数学表达式为： 求n 维设计变量 使目标函数 多维无约束优化算法就是求解这类问题的方法，它是优化技术中最重要最基础的内容之一。因为它不仅可以直接用来求解无约束优化问题，而且实际工程设计问题中的大量约束优化问题，有时也是通过对约束条件的适当处理，转化为无约束优化问题来求解的。所以，无约束优化方法在工程优化设计中有着十分重要的作用。 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 各种优化方法之间的主要差异是在于构造的搜索方向，因此，搜索方向的构成问题乃是无约束优化方法的关键。 下面介绍几种经典的无约束优化方法。 1、梯度法 基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。 搜索方向s 取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。 为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有 12[]T n x x x = x ()min f →x ()k f -?x k αmin ()n f R ∈x x 1(0,1,2,)k k k k s k α+=+= x x 1(0,1,2,) k k k k s k α+=+= x x 1()(0,1,2,) k k k k a f k +=-?= x x x 1()[()]min [()]min ()k k k k k k k a a f f a f f a f ?α+=-?=-?=x x x x x 单纯形法 1. 算法原理 单纯形法的基本思想是： 设(0)(1)(),,...,n x x x 是n R 中的1n +个点，构成一个当前的单纯形，max min ,x x 定义如下： {}(0)(1)()max ()max (),(),...,()n f x f x f x f x = {}(0)(1)()min ()min (),(),...,()n f x f x f x f x = 记x 为这个单纯形除去max x 外的所有顶点的形心， ()max 01n i i x x x n =??=- ??? ∑ 取max x 关于x 的反射点(1)n x +，(1)max ()n x x x x +=+-构成新的单纯形，反复上述过程，直到达到停止条件。 2. 函数min f search 1） 函数语法 min (,0)x f search fun x = min (,0,) [,]min (...) [,,]min (...) [,,,]min (...) x f search fun x options x fval f search x fval exitflag f search x fval exitflag output f search ==== 函数输入： fun ：目标函数 0x ：迭代初始点 options ：函数参数设置 函数输出： x ：最优点 fval ：最优点对应的函数值 exitflag ：函数停止信息 1：函数收敛正常停止 0：迭代次数，目标函数计算次数达到最大数 -1：算法被输出函数停止 output ：函数运算信息 2）函数使用 BanaFun m （1）目标函数程序. function f BanaFun x =不含导数解析式 ()() f x x x =-+- 100*((2)(1)^2)^2(1(1))^2 -函数不需要导数信息。 Nelder Mead Simplex SimplexUnc m （2）算法参数设置：. ('arg','','','','',250,'','') = options optimset L eScale off gradobj off MaxFunEvals display iter SimplexUnc m （3）函数调用运算：. = ('arg','','','','',250,'','') options optimset L eScale off gradobj on MaxFunEvals display iter x=- [ 1.9,2] x fval exitflag output f search BanaFun x options = [,,,]min(@,,) 3）计算结果 Iteration Func-count min f(x) Procedure 0 1 267.62 1 3 236.4 2 initial simplex 2 5 67.2672 expand 3 7 12.2776 expand 4 8 12.2776 reflect 5 10 12.277 6 contract inside 6 12 6.76772 contract inside 7 13 6.76772 reflect 8 15 6.76772 contract inside 9 17 6.76772 contract outside 10 19 6.62983 contract inside 11 21 6.55249 contract inside 12 23 6.46084 contract inside 13 24 6.46084 reflect 14 26 6.46084 contract inside 15 28 6.45544 contract outside 16 30 6.42801 expand 17 32 6.40994 expand 18 34 6.32449 expand 19 36 6.28548 expand 20 38 6.00458 expand 21 39 6.00458 reflect 22 41 5.43287 expand 第四章无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题 （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。 无约束优化问题的一般形式可描述为： 求n 维设计变量 []12T n n X x x x R =∈L 使目标函数 ()min f X ? 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解： 1、解析法 可以利用无约束优化问题的极值条 件求得。即将求目标函数的极值问题变成求方程 0)(min *=X f 的解。也就是 求Ｘ＊ 使其满足 解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，0)(0)(0)(*2*1*=??=??=??n x X f x X f x X f M 例4-1 MA TLAB实现，用M函数文件形式求解： syms s t; f=s^2+3*t^2-2*t*s+4*t+3*s; [x,minf]=minZBLH(f,[-2 6],[0.2 0.2],1.5,[t s],0.0001,0.0001) 坐标轮换minZBLH函数文件如下： function [x,minf] = minconPS2(f,x0,delta,u,var,eps1,eps2) %目标函数：f; %初始点：x0; %收缩系数：u; %自变量向量：var; %步长精度：eps1; %自变量精度：eps2； if nargin == 7 eps2 = 1.0e-6; end n = length(var); y = x0; bmainCon = 1; while bmainCon yf = subs(f,var,y); yk_1 = y; for i=1:n tmpy = zeros(size(y)); tmpy(i) = delta(i); tmpf = subs(f, var,y+tmpy); if tmpf < yf bcon = 1; while bcon tmpy(i) = 2*tmpy(i); tmpf_i = subs(f, var,y+tmpy); if tmpf_i 第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想： 所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长 3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤ 111/2 21K K K K n i i i X X X X ε++=??-=-≤???? ∑（） 2） 11()()()() () K K K K K f X f X f X f X or f X ε ε ++-≤-≤ 3）(1)()K f X ε+?≤ 第三节 常用的一维搜索方法 本节主要解决的是如何确定最优步长的问题。 从初始点(0)X 出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下： (1)(0)00(2)(1)11(1)() K K k k X X S X X S X X S ααα+=+=+= + 现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即 (1)()min ()min ()min ()K K K k k f X f X S f αα+=+= 由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定 区间[,]a b 应满足 ()(*)()f a f f b α>< 第四章 无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这 种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的， 无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过 对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? （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 无约束最优化直接方法和间接方法的异同 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最 目录 1.多维有约束优化............................................. 错误!未定义书签。 题目.................................................... 错误!未定义书签。 已知条件................................................ 错误!未定义书签。 建立优化模型............................................ 错误!未定义书签。 问题分析及设计变量的确定............................. 错误!未定义书签。 目标函数的确定....................................... 错误!未定义书签。 约束条件的建立...................................... 错误!未定义书签。 优化方法的选择.......................................... 错误!未定义书签。 数学模型的求解.......................................... 错误!未定义书签。 确定数学优化模型.................................... 错误!未定义书签。 运用Matlab优化工具箱对数学模型求解.................. 错误!未定义书签。 1. 最优解以及结果分析................................ 错误!未定义书签。 2.多维无约束优化............................................. 错误!未定义书签。 题目.................................................... 错误!未定义书签。 确定优化设计模型........................................ 错误!未定义书签。 运用Matlab优化工具箱对数学模型求解...................... 错误!未定义书签。 编写目标函数........................................ 错误!未定义书签。 绘制该函数的平面和空间等值线........................ 错误!未定义书签。 利用matlab工具箱fminunc函数对该模型进行求解........ 错误!未定义书签。 求解结果............................................. 错误!未定义书签。 约束优化算法的关键技术研究及应用 约束优化问题广泛存在于科学研究和工程应用领域中,目前对其研究已成为智能信息处理领域的研究热点。现有约束优化算法在处理约束单目标优化问题时存在易陷入局部最优、收敛精度不高以及参数设计困难等问题,特别对于非线性、强约束和多峰值的约束多目标优化问题存在所求Pareto解集分布不均匀以及收敛性欠佳的缺陷,从而限制了约束优化算法在实际中的应用。 因此,研究更为有效的约束优化算法具有重要的理论意义和现实意义。本文针对约束优化算法在处理约束单目标优化问题和约束多目标优化问题时的不足,对约束优化算法中的约束处理技术、进化策略、多样性维持策略以及精英选择策略等各项关键技术展开深入研究。 在理论研究上提出了一系列改进措施,使改进算法在求解各类约束优化问题上的性能得到全面提升。在实际应用上将改进算法用于优化实际工程问题,以改善现有方法的优化效果。 论文的主要研究内容包括以下六个方面。第一,针对基于双种群存储技术的约束单目标优化算法存在收敛精度较低的问题,提出一种基于混合策略的双种群约束单目标优化算法。 首先,提出约束支配和最优约束支配来更新不可行解集,保留目标函数值和约束违反度均优的不可行解,以提高算法的探索能力和搜索效率。其次,采用混合策略进化种群,在进化前期利用Deb准则产生可行解,并通过保留非劣不可行解来提高多样性,在进化后期让最优和次优个体指导进化,以加快种群收敛。 最后,采用佳点集来生成初始种群,改善初始种群多样性。仿真实验结果验证了改进算法的有效性。 第二,针对ε约束多样性维持能力不足以及参数设置困难的问题,提出一种基于自适应ε的约束单目标优化算法。首先,对个体比较准则进行改进,让约束违反度和目标函数值均较优的不可行解参与进化,加大对可行域边界的探索力度,从而提高种群多样性,避免陷入局部最优。 其次,提出自适应ε调整策略,根据可行解在种群中所占的比例对ε进行自适应调整,平衡目标函数和约束违反度的关系,从而更加合理地进行个体比较。仿真实验结果验证了改进算法的有效性。 第三,针对现有约束多目标优化算法所求Pareto解集分布性较差的问题,提出一种基于双种群的约束多目标优化算法。首先,对Harmonic距离进行改进,去除Pareto等级较差个体和较远个体的影响,从而更加准确地反映种群的分布性,并且有效减少计算量。 其次,提出的不可行解集更新方式通过紧密联系与可行解集的关系,能够保留优秀的不可行解,有利于提高种群多样性和算法搜索效率。最后,对变异策略进行改进,充分利用最优可行解和优秀不可行解的有效信息来引导种群进化,较好地兼顾探索能力和开发能力。 仿真实验结果验证了改进算法的有效性。第四,针对目前约束多目标优化算法所求Pareto解集收敛性不佳的问题,提出一种基于自适应ε截断策略的约束多目标优化算法。 首先,提出自适应ε截断选择策略,优先保留Pareto最优可行解和约束违反度及目标函数值均较优的不可行解,从而有效平衡多样性和收敛性。其次,在变异操作和交叉操作之后进行指数变异,进一步增强算法的局部开发能力。 最后,对拥挤密度估计方式进行改进,只选择部分距离较近的Pareto最优解 1、一维搜索 function f=myfun_yi(x) f=(x-2)^2-1 》》fminbnd(@myfun_yi,1,12) 2、无约束搜索 function f=myfun_wuyueshu(x) f=3*x(1)^2+2*x(1)*x(2)+x(2)^2 >> x0=[1,1] >> [x,fval]=fminunc(@myfun_wuyueshu,x0) 3、约束搜索 min f(x) x 设计变量 b Ax ≤ 线性不等式约束 eq b x A =eq 线性等式约束 ()0≤x C 非线性约束 0=eq C 非线性等式约束 b b u x l ≤≤ 上下限边界约束 例题: ()222 13)(min x x x f +-= ()042211≤-+=x x x g ()012≤-=x x g ()023≤-=x x g 目标函数： function f=myfun_constrain(x) f=(x(1)-3)^2+x(2)^2; 非线性约束函数定义 function [c,ceq]=mycon(x) c=x(1)^2+x(2)-4; ceq=[]; 初始条件及函数调用： %3初始条件 A=[-1,0;0,-1]； b=[0;0]； aeq=[]; beq=[]; lb=[]; ub=[]; x0=[9;9] %函数定义 [x,fval]=fmincon(@myfun_constrain,x0,A,b,aeq,beq, lb,ub,@mycon)%如果x0,A,b,aeq,beq,lb,ub,@mycon中没有某项，用[]代替单纯形法解决无约束优化问题
约束优化算法拉格朗日乘子法
多维无约束优化算法
无约束优化算法：单纯形法
无约束优化方法
无约束优化方法与MATLAB实现
第三章 无约束最优化方法
无约束优化方法(最速下降法_牛顿法)
无约束最优化直接方法和间接方
无约束最优化直接方法和间接方法的异同
优化设计 有约束优化 无约束优化
约束优化算法的关键技术研究及应用
约束优化、一维搜索、无约束优化MATLAB程序语句用法
相关主题
文本预览