第五章+约束优化计算方法

机械优化设计
1. 内点法
这种方法将新目标函数定义于可行域内，序列迭代点在 可行域内逐步逼近约束边界上的最优点。内点法只能用来求解 具有不等式约束的优化问题。
对于只具有不等式约束的优化问题：
min f ( x) s.t. g j ( x) 0 ( j 1,2,L , m) 转化后的惩罚函数形式为：
hj ( x) 0 ( j 1,2,L , p)
机械优化设计
上一章讨论的都是无约束条件下非线性函数的寻 优方法，但在实际工程中大部分问题的变量取值都有 一定的限制，也就是属于有约束条件的寻优问题。
与无约束问题不同，约束问题目标函数的最小值 是满足约束条件下的最小值，即是由约束条件所限定 的可行域内的最小值。只要由约束条件所决定的可行 域必是一个凸集，目标函数是凸函数，其约束最优解 就是全域最优解。否则，将由于所选择的初始点的不 同，而探索到不同的局部最优解上。在这种情况下， 探索结果经常与初始点的选择有关。为了能得到全局 最优解，在探索过程中最好能改变初始点，有时甚至 要改换几次。
产生初始复合形顶点 Xj , j=1,2,…,K
四. 复合形法的 迭代步骤
计算复合形各顶点的函数值 F(Xj), j=1,2,…,K
比较复合形各顶点的函数值 ，找出好点XL，坏点XH
XH=XR
是
满足终止条件？
否
1 K
XC
K
1
Xj,
j 1
j
H
是
X R X C ( X C X H ), FR F ( X R )
若为非可行点，则将α缩小0.7倍，直至可行为止。然 后再重复可行点的步骤。
2.扩张
机械优化设计
3.收缩
机械优化设计
机械优化设计
机械优化设计
三. 终止判别条件
各顶点与好点函数值之差的均方根应不大于误差限
{1 k
k
1
[F ( X ( j) ) F( X L )]2}2
j 1
给定K，δ，α，ε，ai , bi i =1,2,…n
j 1
k 1
加权转化项
将约束优化问题转换为无约束优化问题。求解无约 束优化问题的极小值，从而得到原约束优化问题的最 优解。
机械优化设计
将有约束的优化问题转化为无约束优化问题来求解。 前提：一是不能破坏约束问题的约束条件，二是使它归结 到原约束问题的同一最优解上去。
min f ( x), x Rn
惩罚项必须具有以下极限性质：
m
lim
k
r(
1
k
)
G[gi ( x)] 0
i1
l
lim
k
r( 2
k
)
H[hj ( x)] 0
j1
•
从而有lim k
(
x,
r(Βιβλιοθήκη Baidu
1
k
)
,
r( 2
k
)
)
f (x(k))
0
机械优化设计
根据约束形式和定义的泛函及罚因子的递推方法 等不同，罚函数法可分为内点法、外点法和混合罚 函数法三种。这种方法是1968年由美国学者A．V． Fiacco和G．P．Mcormick提出的，把不等式约束引 入数学模型中，为求多维有约束非线性规划问题开 创了一个新局面。
在可行域内选择一个初始点，利用随机数的概率特性，产 生若干个随机方向，并从中选择一个能使目标函数值下降 最快的随机方向作为搜索方向s。 从初始点x0出发，沿s 方向以一定步长进行搜索，得到新点 X，新点x应满足约束条件且f(x)<f(x0)，至此完成一次迭代。 随机方向法程序设计简单，搜索速度快，是解决小型机械优 化问题的十分有效的算法。
2) 为避免降维, K应取大些; 但过大, 计算量也大.
2. 初始复合形顶点的确定 1) 用试凑方法产生---适于低维情况; 2) 用随机方法产生 ①用随机方法产生K个顶点
机械优化设计
先用随机函数产生 n个随机数 i (0 ,i然后1)
变换到预定的区间 ai中去xi. bi
xi (bi ai )i ai ,i1,2,...,n
值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上 述搜索过程，直至满足收敛条件。
x x S (k1)
(k)
(k) (k)
(k 0,1,2,L )
k -------步长
s(k ) --------可行搜索方向
可行搜索方向:当设计点沿该方向作微量移动时，目标函数 值将下降，且不会越出可行域。
机械优化设计
x(k+1)＝ x(k)+α(k) S(k) (k=0,1,2,…) 逐步趋向最优解，直到满足终止准则才停止迭代。
机械优化设计
直接解法通常适用于仅含不等式约束的问题，思路是在m个不 等式约束条件所确定的可行域内，选择一个初始点，然后决定可行
搜索方向 S且以适当的步长 ，进行搜索，得到一个使目标函数
基本思路如图所示。
机械优化设计
机械优化设计
随机方向探索法的一般迭代计算公式为：
X(k+1)=X(k)+aS(k)
(k=0,1,2,…)
式中a为步长，S(k) 为第k次迭代的随机探索方向。
因此，随机方向探索法的计算过程可归结为：
机械优化设计
5.3 复合形法
复合形法是求解约束非线性最优化问题的一种 重要的直接方法。它来源于用于求解无约束非线性最 优化问题的单纯形法，实际上是单纯形法在约束问题 中的发展。
机械优化设计
直接解法的原理简单，方法实用，其特点是： 1）由于整个过程在可行域内进行，因此，迭代计算不论 何时终止，都可以获得比初始点好的设计点。 2）若目标函数为凸函数，可行域为凸集，则可获得全域 最优解，否则，可能存在多个局部最优解，当选择的初始 点不同，而搜索到不同的局部最优解。 3）要求可行域有界的非空集。
（2）复合形法适用于仅含不等式约束的问题。
机械优化设计
§5-5 惩罚函数法
惩罚函数法是一种很广泛、很有效的间接解法。它 的基本原理是将约束优化问题中的不等式和不等式约 束函数经加权后，和原目标函数结合为新的目标函 数——惩罚函数。
m
l
x, r1, r2 f x r1 G g j x r2 H hk x
机械优化设计
第五章 约束优化计算方法
5.1 引言 5.2 随机方向搜索法 5.3 复合形法 5.4 惩罚函数法
5.1 引言
机械优化设计
机械优化设计中的问题，大多数属于约束优化设 计问题，其数学模型为
min f ( x), x [x1, x2 xn ]T s.t. gi ( x) 0 (i 1,2,L , m)
j 1
k 1
新目标函数
加权因子
然后对新目标函数进行无约束极小化计算。
机械优化设计
5.2 随机方向法
机械优化设计
基本思想：利用计算机产生的随机数所构成的随 机方向进行搜索，产生的新点必须在可行域内，即满 足直接法的特性。
随机方向法，是约束最优化问题的一种常用的直 接求解方法。
机械优化设计
随机方向法的基本思路：
机械优化设计
3）由计算机自动生成初始复合形的所有顶点。
二、复合形法的搜索方法
1.反射 1）计算复合形各顶点的目标函数值，并比较其大小，求出 最好点XL、最坏点XH 及 次坏点XG，即
xL : f xL min f x j j 1, 2,..., k xH : f xH max f x j j 1, 2,..., k xG : f xG max f x j j 1, 2,..., k, j H
机械优化设计
a) 可行域是凸集；b)可行域是非凸集
机械优化设计
间接解法的求解思路：
将约束函数进行特殊的加权处理后，和目标函数结合起来， 构成一个新的目标函数，即将原约束优化问题转化为一个 或一系列的无约束优化问题。
m
l
x, 1, 2 f x 1G g j x 2H hk x
s.t.
g j(x) 0
j 1, 2,L , m
hk ( x) 0 k 1, 2,L ,l
构成一个新的目标函数，称为惩罚函数
m
l
(
x,
r(k
1
)
,
r(k 2
)
)
f
(
x)
r(k
1
)
G[
g
j
(
x)]
r( 2
k
)
H[hk ( x)]
i1
j1
机械优化设计
求解该新目标函数的无约束极小值，以期得到原问题 的约束最优解。按一定的法则改变罚因子r1 和r2的值， 求得一序列的无约束最优解，不断地逼近原约束优化问 题的最优解。
如前所述，在求解无约束问题的单纯形法中，不 需计算目标函数的梯度，而是靠选取单纯形的顶点井 比较各顶点处目标函数值的大小，来寻找下一步的探 索方向的。在用于求解约束问题的复合形法中，复合 形各顶点的选择和替换，不仅要满足目标函数值的下 降，还应当满足所有的约束条件。
机械优化设计
它的基本思路是在可行域内构造一个具有k个顶点的初 始复合形。对该复合形各顶点的目标函数值进行比较，找到 目标函数最大的顶点（最坏点），然后按一定的法则求出目 标函数值有所下降的可行的新点，并用此点代替最坏点，构 成新的复合形，复合形的形状没改变一次，就向最优点移动 一步，直至逼近最优点。
由于复合形的形状不必保持规则的图形，对目标函数和 约束函数无特殊要求，因此这种方法适应性强，在机械优化 设计中应用广泛。
机械优化设计
二.初始复合形的构成
机械优化设计
1. 复合形顶点数K的选择
建议: n 1 K 2n
n 小取大值, n 大取小值
* 1) 为保证迭代点能逼近极小点, 应使
K n1
子 rk 0
时，才能求得在约束边界上的最优解。
这便得到了一个顶点,要连续产生K个顶点.
机械优化设计
初始复合形生成的方法：
1）由设计者决定k个可形点，构成初始复合形。设计变量少 时适用。
2）由设计者选定一个可形点，其余的k-1个可形点用随机法 产生。
xi a ri (b a )
xc
1 L
L
xj
j 1
xL1 xc 0.5 xL1 xc
是
FR<F(XH)
XR∈D
否
否
否
α=0.5α
是
找出次坏点XSH ，XH=XSH
机械优化设计
X*=XL ,F*=F(XL) 结束
机械优化设计
方法特点
（1）复合形法是求解约束非线性最优化问题的一种 直接方法，仅通过选取各顶点并比较各点处函数值 的大小，就可寻找下一步的探索方向。但复合形各 顶点的选择和替换，不仅要满足目标函数值下降的 要求，还应当满足所有的约束条件。
机械优化设计
根据求解方式的不同，约束优化设计问题可分为:直接 解法、间接解法。
（1）直接法 直接法包括：网格法、复合形法、随机试验法、
随机方向法、可变容差法和可行方向法。 （2）间接法 间接法包括：罚函数法、内点罚函数法、外点罚
函数法、混合罚函数法、广义乘子法、广义简约梯度 法和约束变尺度法等。
机械优化设计
间接解法是将约束优化问题转化为一系列无约束优化问题来 解的一种方法。
由于间接解法可以选用已研究比较成熟的无约束优化方 法，并且容易处理同时具有不等式约束和等式约束的问题。 因而在机械优化设计得到广泛的应用。
间接解法中具有代表性的是惩罚函数法。
直接解法的基本思想：
在由m个不等式约束条件gu(x)≤0所确定的可行域φ内，选择 一个初始点x(0)，然后确定一个可行搜索方向S，且以适当的步 长沿S方向进行搜索，取得一个目标函数有所改善的可行的新点 x(1)，即完成了一次迭代。以新点为起始点重复上述搜索过程， 每次均按如下的基本迭代格式进行计算：
m
(x,r) f (x) r(k)
1
i1 gi ( x)
m
或： ( x,r) f ( x) r(k) ln[gi ( x)]
i1
机械优化设计
rk是惩罚因子，它是一个由大到小且趋近于0的正数列， 即:
r0 r1 r2 L rk rk1 L 0
由于内点法的迭代过程在可行域内进行，“障碍项 ”的作用是阻止迭代点越出可行域。由“障碍项”的 函数形式可知，当迭代点靠近某一约束边界时，其值 趋近于0，而“障碍项”的值陡然增加，并趋近于无 穷大，好像在可行域的边界上筑起了一道“高墙”， 使迭代点始终不能越出可行域。显然，只有当惩罚因
机械优化设计
2）计算除去最坏点XH 外的（k-1）个顶点的中心XC
1 L
xc k 1 j1 x j
3）从统计的观点来看，一般情况下，最坏点XH和中心点XC 的连线方向为目标函数的下降方向。
xR xC a xC xH
机械优化设计
4）判别反射点XR的位置
若XR 为可行点，则比较XR 和XH 两点的目标函数值， 如果f(XR) <f(XH)，则用XR取代XH ，构成新的复合形， 完成一次迭代；如果f(XR) >=f(XH),则将α缩小0.7倍，重 新计算新的反射点，若仍不行，继续缩小α，直至f(XR) <f(XH)为止。