文档介绍：第五章约束优化方法
第一节概述
第二节随机试验法
第四节可行方向法
第五节罚函数法
第六节增广乘子法
第三节复合形法
第七节广义简约梯度法
第八节约束变尺度法
第一节概述
一、求解问题
二、方法分类
间接法:构造一个新的目标函数,将原约束优化问题,转化为无约束优化问题,通过求解无约束优化问题,间接获得约束优化问题的最优解
直接法:在可行域内,通过构造一定的搜索模式,直接求得约束问题的最优解。
属于直接法的有:随机试验法,随机方向法,约束坐标轮换法,复合形法,可行方向法,简约梯度法,约束变尺度法等。
属于间接法的有:罚函数法,乘子法等。
第二节随机试验法
一、基本思想
又称为Monte-Carlo法。其基本思想就是对于不含等式约束条件的优化问题:
利用计算机产生在可行域D内产生K个可行点,对目标函数值进行排序,记录目标最小值和对应的设计点,完成第一批抽样试验。重复抽样试验,直到每批抽样试验所得的目标最小值和对应的设计点不在明显变动时,则可认为已按概率收敛于最优解。
x2
x1
二、随机点的产生
其中
为[0,1]均匀分布的随机数
第三节复合形法
一、基本思想
复合形法是求解约束优化问题的一种较常用的直接法,基本思想就是对于不含等式约束条件的优化问题:
在可行域D内产生K(=n+1~2n)个可行点,作为顶点,构成复合形,通过对复合形进行翻转、收缩等运算,使其逐渐收敛于约束最优解。
二、几何说明
三、算法流程
输入n,a、b, k, 。
构成初始复合形:{X(1), X(2),…… X(k)}
求最坏点Xh:f(Xh)=max{f(X(i))} i=1,2,…,k
次坏点Xsh:f(Xh)=max{f(X(i))} i=1,2,…,k,ih
最好点XL:f(XL)=min{f(X(i))} i=1,2,…,k
形心点Xc:Xc=(X(i)- Xh)/k (可行)
反射点Xr= Xc+(Xc - Xh) (可行、适用)
以反射点取代最坏点,形成新的复合形
进行收敛性判定,如何复合形足够小,则以最好点作为最优点输出;否则转上一步。
四、构成初始复合形
,作为初始复合形的顶点
,作为初始复合形的顶点。
,其余(k-1)个顶点由程序随机产生。
设已有L可行点,而随机产生的( L +1)个点不可行,则可如下处理
求形心点 Xc: Xc=(X(l))/L
向形心靠近 X(l+1)= Xc+ (X(l+1) -Xc )
五、反射点的进一步说明
反射点 Xr= Xc+(Xc - Xh) 应当可行、适用。若否,则减小。当减小到10-5时,仍无法获得可行、适用的反射点 Xr,则说明方向(Xc - Xh) 不可用,故将次坏点视为最坏点,构造新的反射方向,重新计算,即
反射点 Xr= Xc+(Xc - Xsh)
六、收敛条件
复合形形心点
七、复合形算法框图