文档介绍：第五章约束优化方法
7/13/2017
1
§5-1 优化方法的类型
2)间接法
1)直接法
---将迭代点限制在可行域内(可行性),步步降低目标函数值(下降性),直至到达最优点.
常用方法有:约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等.
---通过变换,将约束优化问题转化为无约束优化问题求解.
常用方法有: 罚函数法,拉格朗日乘子法等.
(可解IP型问题)
(可解各类问题)
(按对约束条件的处理方法分)
7/13/2017
2
§5-2 约束坐标轮换法
①可取定步长、加速步长和收缩步长,但不能取最优步长;
---e1,e2,…,en方向搜索;
.
②对每一迭代点均需进行可行性和下降性检查.
7/13/2017
3
7/13/2017
4
有时会出现死点, 导致输出“伪最优点”.
* 为辨别真伪, 要用K-T条件进行检查.
7/13/2017
5
§5-3 约束随机方向法
基本思路
②若该方向适用、可行,则以定步长前进;
坐标轮换法有时会输出“伪最优点”,用随机方向法可克服这一缺点.
①若该方向不适用、可行,则产生另一方向;
③若在某处产生的方向足够多,仍无一适用、可行,则采用收缩步长;
④若步长小于预先给定的误差限则终止迭代。
搜索方向----采用随机产生的方向
7/13/2017
6
(X)产生n个随机数
2. 将(0,1)中的随机数变换到(-1,1)中去;
3. 构成随机方向
变换得:
于是
例: 对于三维问题:
7/13/2017
7
X0=X, F0=F
α=α0, F0=F(X0)
F=F(X)
j =1
K=K+1
的迭代步骤
是
K=0, j=0
产生随机方向
α=
否
F<F0
j =0
K< m
α≤ε
结束
X*=X0 ,F*=F0
是
否
是
否
是
否
X∈D
是
否
7/13/2017
8
§5-4 复合形法
基本思路
在可行域内选取若干初始点并以之为顶点构成一个多面体(复合形),然后比较各顶点的函数值,去掉最坏点,代之以好的新点,并构成新的复合形,以逼近最优点.
有两种基本运算:
1) 映射---在坏点的对侧试探新点:先计算除最坏点外各顶点的几何中心, 然后再作映射计算.
2) 收缩---保证映射点的“可行”与“下降”
X1为最坏点
---映射系数
常取
若发现映射点不适用、可行, 则将减半后重新映射.
7/13/2017
9
1. 复合形顶点数K的选择
建议:
小取大值, 大取小值
2) 为避免降维, K应取大些; 但过大, 计算量也大.
* 1) 为保证迭代点能逼近极小点, 应使
7/13/2017
10