当前位置：文档之家 › 第6章 有约束最优化问题的间接法

第6章 有约束最优化问题的间接法

  • 格式：ppt
  • 大小：525.50 KB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

机械优化设计约束优化方法

机械优化设计约束优化方法
根据求解方式的不同，约束优化设计问题可分为:直接 解法、间接解法。
（1）直接法
直接法包括：网格法、复合形法、随机试验法、 随机方向法、可变容差法和可行方向法。
（2）间接法
间接法包括：罚函数法（内点罚函数法、外点罚 函数法、混合罚函数法）、广义乘子法、广义简约梯 度法和约束变尺度法等。
直接解法通常适用于仅含不等式约束的问题，思路是
如前所述，在求解无约束问题的单纯形法中，不 需计算目标函数的梯度，而是靠选取单纯形的顶点并 比较各顶点处目标函数值的大小，来寻找下一步的探 索方向的。在用于求解约束问题的复合形法中，复合 形各顶点的选择和替换，不仅要满足目标函数值的下 降，还应当满足所有的约束条件。
基本思想：在可行域中选取K个设计点 （ n+1≤K≤2n）作为初始复合形的顶点。比较各顶点目标 函数值的大小，去掉目标函数值最大的顶点(称最坏点) ，以坏点以外其余各点的中心为映射中心，用坏点的 映射点替换该点，构成新的复合形顶点。
取次好点和好点连线的中点为X(0)。
令：X(4)= X(0)+α(X(0)-X(H))
称X(4)为映射点，记为X(R)，α为映射系数，通常取 α=1.3，可根据实际情况进行缩减。
一般情况下，映射点的函数值比坏点的函数值要 小，即F(X(R))< F(X(H))。若满足可行域，则用X(R)代替 X(H)构成新的复合形。如此反复迭代直到找到最优解。
（3）计算坏点外的其余各顶点的中心点X(0)。
X0
1 K K1j1
X(j),
j
H
（4）计算映射点X(R)
X (R )X (0 )(X (0 )X (H ))
检查X(R)是否在可行域内。若X(R)为非可行点，将映 射系数减半后再按上式改变映射点，直到X(R)进入可行 域内为止。

约束问题的最优化方法

约束问题的最优化方法
(k ) (k ) m
1 u 1 g ( x ) u
m
其中：gu ( x) 0, u 1,2,...m
1 u 1 g ( x ) u m 1 (k ) (k ) ③ . ( x, r ) f ( x) ru u 1 g u ( x) m 1 (k ) (k ) ④ .( x, r ) f ( x) r 2 u 1 [ g ( x )] u
min . g k x s.t. x Rn gu x g k x gu x 0
0
0
u 1, 2,..., S 1 u S 1,..., m

以求得的设计点作为新初始点，继续其判断可行性，若仍有不
满足的约束，则重复上述过程，直至初始点可行。
的选择：
要求： ①
② 方法： ①
在可行域内；
不要离约束边界太近。 人工估算，需要校核可行性；
②
计算机随机产生，也需校核可行性。
§5.2 内点惩罚函数法
方法： ③ 搜索方法： 任意给出一个初始点； 判断其可行性，若违反了S个约束，求出不满足约束中的最大值： g k ( x 0 ) max{ gu x 0 } u 1,2,..., S； 应用优化方法减少违反约束：
uI


Z
I为违反约束的集合。
g u x ， 当 g u x 0时， maxg u x ,0 { 0 ，当g u x 0时， x, r

(k )
{
f x r k maxg u x ,0 f x
uI
Z
Z一般取2。
k
k
(k )
H [h ( x

第六章约束优化方法

第六章约束优化方法
1 m j=1 g x j
或∅ x，r = f x − r
m [ −g j j=1 ln⁡
x ]
r 为惩罚因子，要求 r0>r1>…>0; 初始点 x0 的选取：在可行域内，避免在边界上 惩罚因子初值 r0 的选取 r0=1~50，一般取 r0=1,经验公式：r0 = 丨 惩罚因子缩减系数 c 的选取，rk=crk-1，r=0.1~0.7 收敛条件：
约束优化方法 第一节 概述 直接法和间接法 a 直接法：仅含不等式约束的问题或等式约束函数不是复杂的隐函数，且易于消元。 思路：在可行域内按照一定的原则直接探索出它的最优点，xk+1=xk+α kdk。 b 间接法: 同时具有等式和不等式约束的优化问题。 思路： 将原目标函数和约束函数加权处理为新目标函数， 使约束优化问题转为无约束优化问 题，∅ x，μ1 ，μ2 = f x +
j
m j=1 ma x
0，gj x
2
+r
l k=1[hk
x ]2 ； r0<r1< … ∞ ； c=5~10 ；
x0 f x0
•
混合惩罚函数法 1 1 ∅ x，r = f x − r + 1 [hk x ]2 gj x r2 k=1 j=1 参数均可按内点法取值
m l
第六节—第十一节（略）
∅ x k ，r k −∅ x k −1 ，r k −1 ∅ x k −1 ，r k −1 f （x 0 ）
1 m j=1 g x 0 j
丨
≤ ε ； x k − x k −1 ≤ ε
•
外点惩罚函数法（从可行域外部逼近原目标函数的约束最优解） ∅ x，r = f x + r r0 j = mg

约束最优化

约束最优化
混合法是综合外点法和内点法的优点建立的一种算法，对不等式约束条件按内 点法建立惩罚项，对等式约束条件按外点法建立惩罚项，由此得到惩罚函数：
m 1 2 X , rk1 , rk 2 f X rk1 rk 2 hv X u 1 g u X v 1 p
解：① 构造惩罚函数，转化为无约束最优化问题：
x1 x2 (可行域内) min X , rk 2 2 2 x x r x x r x 2 k 1 1 2 k 1


(可行域外)
② 求解无约束最优化问题，因为惩罚函数构造简单，可以直接用极值条件求解， 即令惩罚函数的一阶导数等于零：
李实cselisujneducn1教1007室济南大学控制科学与工程学院最优化方法61惩罚函数法63序列二次规划法64多目标最优化方法65matlab求解约束最优化问题66约束最优化问题应用实例济南大学控制科学与工程学院最优化方法33约束最优化方法是用来求解如下非线性约束最优化问题的数值迭代算法
第六章 约束最优化方法
f X 1 1.09
r2 0.25, rk 0,
f X 2 0.466
f X* 0

济南大学控制科学与工程学院
最优化方法
16
外点法的迭代路线如下图所示，向约束问题的最优点[0, 0]T逐步逼近 虚线②所示。
济南大学控制科学与工程学院
最优化方法
17
6.1.3 混合法
解，如惩罚函数法、乘子法、序列二次规划法。
济南大学控制科学与工程学院
最优化方法
2
6.1 惩罚函数法
惩罚函数法是一种将约束最优化问题转化为无约束最优化问题求解的算法。 对于约束最优化问题：

约束问题的最优化方法

约束问题的最优化方法

m
⑤ .Φ ( x, r ) = f ( x) − r ∑ ln[− g u ( x)]
(k )
其中：惩罚（加权）因子 降低系数 c：
r ( 0 ) > r (1) > ....r ( k )
0< c <1
r ( k −1) ⋅ c = r ( k )
xk * → x *
当lim r ( k ) → 0
x ∈ D ⊂ Rn s.t. g u ( x ) ≥ 0, u = 1,2,..., p hv ( x ) = 0, v = 1,2,..., q min F ( x )
一. 约束优化问题解法分类： 约束优化方法按求解原理的不同可以分为直接法和间接法两类。
直接解法：随机方向搜索法、复合形法、可行方向法
其中：g u ( x) ≥ 0, u = 1,2,...m
③ .Φ ( x, r ) = f ( x) − ∑ ru ( k )
(k ) u =1
m
1 g u ( x)
④ .Φ ( x, r ) = f ( x) + r
(k )
(k )
(k )
1 ∑ 2 u =1 [ g u ( x )]
m u =1
k →∞
则Φ ( x, r ( k ) ) → f ( x) ,
) x12 + x22 例： 用内点法求 min f ( x=
s.t. g ( x ) = 1 − x1 ≤ 0
的约束最优解。
2 解: 首先构造内点惩罚函数:φ ( x , r ) = x12 + x2 − r k ln( x1 − 1)
(k ) u =1 m
lim r2 H [hv ( x ( k ) )] = 0

第6章约束优化方法

第6章约束优化方法

设计变量x1 2.0 1.117 1.024 0.717
-2.998 -3.0
目标函数值 6.0 1.196 1.025 0.730
-2.997 -3.0
机械优化设计
§第三节 复合形法
一. 单纯形法：
定义：在n维空间中，由n+1个点组
成的图形称单纯形。
X(3)
X(5)
基本思想：以一个目标函数值较小的 新点，代替原单纯形中目标函数值最 大的顶点，组成新的单纯形，不断地 迭代，逐渐逼近最优点。
(j) i
=
αi+ri(j)(bi-ai)，重新构成复合形，转
步骤2
5. 计算映射点： x (R) =x (S)+a(x (S)-x (H))
检查是否在可行域内
是，转步骤6 否， a=0.5a,重新计算反射点
机械优化设计
f(x(R)) < f(x(H)) ，以x(R)代替x(H) 重构复合形后转步骤2 6. 计算f(x(R))，若
则可行搜索方向为： d x L x0
四、搜索步长的确定
步长由加速步长法确定：
τ为步长加速系数，一般取1.3
机械优化设计
五. 计算步骤 1) 选择一个可行的初始点x0; 2) 产生k个n维随机单位向量e j ( j = 1, 2, …, k);
3) 取试验步长0，计算出k个随机点x j ;
机械优化设计
×
第六章 约束优化方法
机械优化设计
6.1 概 述 6.2 随机方向法 6.3 复合形方法 6.4 可行方向法 6.5 惩罚函数法 6.6 增广乘子法
6.7 非线性规划问题 的线性化解法—线性 逼近法
6.8广义简约梯度法
6.9 二次规划法

8约束优化间接解法

n
但 dxl 1 , dxl 2 ,, dxn应是任意的量，则应有
h h h h f 1 1 2 2 3 3 l l 0 x j x j x j x j x j
j l 1, l 2,, n
i 1, 2,, n
n
在约束最优点x'附近的一切微小位移S [dx1 , dx2 , , dxn ]， f 如果不想使函数值增加，需要f ( x ) S dxi 0 i 1 xi
* T n
另外，x*需要满足约束条件，即S需要与hk x* 的梯度垂直， hk 即hk ( x ) S dxi 0 i 1 xi
对于复杂问题，例如多维多等式问题，需要用到前面 学习过的各种无约束寻优方法进行迭代计算。这时， 惩罚乘子可以对所有约束在同一次迭代中取同一值， 且在迭代开始时可以取小一点的值，随后逐渐增大，即 M ( 0 ) M (1) M ( 2 ) M ( k ) 0 第p次迭代时的惩罚函数为： ( x, M ( p ) ) f ( x) M ( p ) hk ( x) 2
k 1 F 0 1,2, , n) (i xi
F 0 1,2, , l ) (k k
条件是 hk x 0 k 1, 2,, l 的 l 个等式约束方程。 * * * * T 为了求出f x 的可能的极值点x x1 x2 xn ， 引入非零拉格朗日乘子 k k 1, 2,, l ，并构成一 个新的目标函数
l 2 k 1 k k
任何仅仅当约束条件得到满足时才等于零的 非负函数都可以当作惩罚项，可以根据具体情 况选择。
四、惩罚函数法
将约束最优化问题 min f x f x1 , x2 , , xn s.t. g j x g j x1 , x2 , , xn 0 hk x hk x1 , x2 , , xn 0 转化为形如： min x, r ( j 1,2, , m) (k 1,2, , l )

第六章 约束优化方法

x0 2）选可行初始点
j 3） 产生k个n维随机单位向量： e =
r1 j j 1 r2 n ⋮ j 2 ∑ (ri ) rnj i =1
(j =1，2，…，k) 4）取试验步长α 0 ，计算k个随机点
x j = x 0 + α 0e j
( j = 1,2, ⋯ , k )
0
综上所述，产生可行搜索方向的条件可概括为，当 满足：
g j ( x L ) ≤ 0 ( j = 1,2, ⋯, m) j f ( x L ) = min f ( x ) j =1,⋯k f (xL ) < f (x0 )
xL
{
}
d = xL − x 0 则搜索方向为：
特点： 直接解法原理简单，方法实用，特点如下： 1）由于整个求解过程在可行域内进行，因此，迭代不论 何时终止，都可以获得一个比初始点好的设计点。 2）若目标函数为凸函数，可行域为凸域，则可保证获得 全域最优解。此时，可在可行域内选择几个差别比较大的 初始点分别进行计算，以便从求得的多个局部最优点钟选 择更好的最优点。 3）要求可行域为有界的非空集，即在有界可行域内存在 满足全部约束条件的点，且目标函数有定义。
二 、复合形法的搜索方法
初始复合形 法则 新点 替换最坏点 新复合形
1、反射 反射（最主要的方法） 反射 1）计算复合形各顶点的目标函数值，求出： 最好点： xL 最差点：
xH
f（ x L） = min { f ( x j )|j =1 ,2 ,⋯ ,k }
f H = f（xH）= max { f (x j ) j =1,2 ,⋯,k } |
5）在k个随机点 x j 中，找出 x L
x L 满足： g j ( x L ) ≤ 0 ( j = 1,2, ⋯ , m ) 若

第6章多维约束优化方法

3构成新的复合形 计算映射点目标函数，并与坏点函数值相 比较，若优于坏点，则替换，否则缩半映射系数。M次缩短 后仍不优，则改用次坏点映射方向。
4判断终止条件：
四、特点
（1）复合形法是求解约束非线性优化问题的 一种直接方法，仅通过选取各顶点并比较各点 处函数值的大小，就可寻找下一步的探索方向 。但复合形各顶点的选择和替换，不仅要满足 目标函数值下降的要求，还应当满足所有的约 束条件。
srand(seed1); seed1+=57; seed1=seed1%10001; dum=random(101)50;
相关技巧为：以累加素数的方法保证每个随机数对应的seed均不同 ，为保证seed不超出unsigned数据类型的范围将其限制在一定范围 之内，以减去中间值的方法保证随机数为正和为负的机率相同。
• 复合形的收缩：因映射系数不断减半，各顶点的距离逐渐缩短
二、初始复合形的构成
随机产生，逐一调入可行域
三、复合形法的迭代步骤
1初始复合形。计算各顶点函数值，确定坏点、次坏点、好点 ；
2计算中心点X0，计算映射点，并检查是否在可行域内。若为 非可行点，将映射系数缩半后改变映射点，直到映射点进入 可行域内；
（１）由randomize(void)、rand(void)产生[0,32767]区间的随机整 数。该方法产生的随机数与时钟有关，适合于两个随机数相差时间 较长的情况，如集中给出随机数，则在当前计算机的运算速度下会 产生相同的随机数。因此随机方向法不能采用这种方法产生随机数 。
（２）由srand(unsigned seed)、random(int num)产生[0,num-1]区 间的随机整数（该随机数与seed的数值有关），可用于随机方向法 。方向列阵的元素不能都是大于零的，因此可由以下程序段产生[50，50]区间内的随机数：

运筹学与最优化方法 第6章约束最优化方法


第六章
如果x

6.1 Kuhn-Tucker 条件

三、一般约束问题的Kuhn-Tucker 条件 (续)
l .opt .那么u i 0, i I , v j R, j 1,2, , l f ( x )

u i g i ( x )
iI
ㄡ ▽h(ㄡ )
最优性条件即：
▽h(x*)
f ( x*) j h j ( x*)
* j 1
h
6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： 考虑问题 min f(x) (fg) s.t. gi(x) ≤0 i=1,2, …,m 设 x*∈S={x|gi(x) ≤0 i=1,2, …,m} 令 I={i| gi(x*) =0 i=1,2, …,m} 称I为 x*点处的起作用集（紧约束集）。 如果x*是l.opt. ,对每一个约束函数来说，只有当它是起作用约 束时，才产生影响，如：
* 1 3
u1
*
1 3
u2
* 2 3
2 3
使

g 1 ( x )
g 2 ( x ) 0
用K-T条件求解：
2( x1 3) 2 x1 , g 1 ( x ) f ( x ) 2( x 2) 2x 2 2 1 0 , g 4 g 3 ( x ) 0 1 1 , g 2 ( 2) 2

定理： 问题( fgh)，x S {x | g ( x) 0, h( x) 0}, I为起作用集。

设g i ( x)(i I )在x 可微, g i ( x)(i I )在x 连续，h j，（j 1,2, , l） 在x 的某邻域内连续可微。（CQ, 约束规格）。 向量组{，g i ( x )(i I ), , h1 ( x ), , hl ( x )}线性无关。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

6-5 外点惩罚函数法（外点法）
外点法是将惩罚函数定义在可行域之外，并在整个 Rn中进行参数寻优。初始点可以任选，既可在可行 域中，亦可在域外，这给设计人员和实际计算带来 极大的便利。由于外点法是从约束可行域外逐步逼 近约束极值点的，故它很适合于具有等式约束或不 等式约束条件的优化问题。
1.惩罚函数的Βιβλιοθήκη 式外点法只适用于最优点在约束边界上的情况，因为惩罚函数 仅定义于可行域外部。若约束最优点在可行域内部，则由于 搜索点不可能进入可行域内部而无法寻找最优点，此时可采 用内点法。 无论内点法还是外点法，为了解一个约束问题，都需要进行 一系列的无约束优化计算。这样工作量就很大，要花费很多 计算时间，而且罚因子的选取对收敛速度影响较大；因此人 们提出了许多改进的方法，如无参数惩罚函数法、采用外插 技术加速收敛和构造精确惩罚函数法及乘子法等等。
6-3 惩罚函数的基本概念
惩罚函数法是将约束优化问题转化为一个等价的无约束优 化问题的间接寻优方法。它类似于拉格朗日乘子法，在构 造惩罚函数时，需要引入一个或几个可调整的惩罚因子， 将原目标函数和约束条件经过加权处理组合成新的目标函 数——惩罚函数。 对各新的目标函数进行一系列的无约束最优化计算，使各 新目标函数的最优解逐步逼近原约束优化问题的最优解。 可以证明，这种序列无约束最优化问题的解的极限，就是 原来约束极小化问题的解。
第6章 有约束优化问题的间接法
拉格朗日乘子法 内点惩罚函数法（内点法） 外点惩罚函数法（外点法） 混合惩罚函数法（混合法）
6-1 引 言 间接法基本思路为：将有约束的优化问题通过 一定形式的变化转化为无约束最优化问题，再 用无约束最优化方法求其最优解。由于这类算 法可以选择较为有效的无约束优化方法，且易 于处理同时含等式和不等式约束的优化问题， 因此在实际中得到了广泛应用。
2.外点法的迭代步骤
3．内点法与外点法的比较
内点法要求给出的初始点必须是可行点，而且一系列 无约束最优点是从可行域内趋向约束最优点，每一迭 代点都是可行点。所以对于工程设计，只要给出一个 初始可接受的设计点后，它能产生一系列逐步改进的 设计方案供设计者选择。 外点法对于初始点及每一迭代得到的迭代点都不要求 是可行点，在迭代过程中也不能保证得出的点是可行 的；但是可使非可行点逐步向可行域界面靠近，最后 在可行域界面上得到约束最优点。
6-4 内点惩罚函数法（内点法）
内点法是将惩罚函数定义在可行域内，并从可行域内某一初 始点出发，在可行域内进行迭代的方法。它的最大特点是在 给定一个初始可行的方案之后，通过迭代寻优，可以得到一 系列可行的、逐步改进的及可任意选取的设计方案。
这对决策人员具有很大的可选灵活性，他既可以选择约束最 优解 x * ，也可以根据具体情况，选择其中任何一个无约束最 优解 x *(r ( k ) ) 。由于内点法的所有迭代点始终是在可行域内部 进行的，因而它不能处理具有等式约束条件的优化问题。
内点法只能处理不等式约束条件问题，对等式约束条件问 题是不适用的；而外点法对处理等式约束和不等式约束问 题都是适用的。 内点法中的惩罚项在界面上的可微阶数与目标函数、约束 条件的可微阶数是相同的，因此其在求惩罚函数的最优解 时，不受此方法对惩罚函数可微阶数要求的限制，原则上 任何无条件极值的方法都可使用；而外点法在边界上可微 性很差，其惩罚项的一阶偏微商存在，而且是连续的，但 其二阶偏微商在边界上却不存在，所以在选择无约束优化 方法上受到一定限制。
6-2 拉格朗日乘子法 拉格朗日乘子法是一种将有约束优化问题转化 为无约束优化问题的间接优化方法。它通过引 入一些称为乘子的待定系数，把给定的约束条 件与待定乘子相结合，添加到原有的目标函数 中，构成一个无约束优化问题的新目标函数 （拉格朗日函数），根据函数的极值必定发生 在它的一阶导数等于零处的原理，求出原问题 的极小值或极大值。
6-6 混合惩罚函数法（混合法）
内点法容易处理具有不等式约束条件的优化问题， 而外点法则容易处理具有等式或不等式约束条件的 优化问题。内点法和外点法有各自的优缺点，如将 两者结合起来，则可以更好地同时处理既具有等式 约束条件，又具有不等式约束条件的优化问题，这 就是混合惩罚函数法，简称混合法。