工程优化约束直接法PPT课件

1、约束直接搜索方法约束直接搜索方法直接法直接法: : 直接沿一序列方向、在满足约束条件下的一维直接沿一序列方向、在满足约束条件下的一维搜索，最后达到优化解。主要适用于仅含不等式约束搜索，最后达到优化解。主要适用于仅含不等式约束的优化问题的优化问题. . 新的迭代点必须限制在不等式约束构成新的迭代点必须限制在不等式约束构成的可行域内的可行域内, ,且保证目标函数的稳定下降且保证目标函数的稳定下降. .1. 随机实验法随机实验法2.2. 随机方向法随机方向法3.3. 复合形法复合形法4.4. 可行方向法可行方向法5.5. 梯度投影法梯度投影法6.6. 简约梯度法简约梯度法第1页/共54页约束直接搜索

2、方法约束直接搜索方法一一. .随机实验法随机实验法( (Monte-CarloMonte-Carlo法法) )(1) 算法思想通过逐步随机取样通过逐步随机取样, ,逼近最优解逼近最优解. .每步随机取样得到一组点上的函数值每步随机取样得到一组点上的函数值, ,通过比较确定最优解通过比较确定最优解的较小范围的较小范围. .下一步在上一步确定的范围内再随机取样下一步在上一步确定的范围内再随机取样, ,确定确定更小的最优解范围更小的最优解范围, ,如此下去如此下去, ,不断逼近最优解不断逼近最优解. .不断缩小最优解不断缩小最优解的范围的范围第2页/共54页随机实验法随机实验法( (Monte-Ca

3、rloMonte-Carlo法法) )(2) 算法第3页/共54页随机实验法随机实验法( (Monte-CarloMonte-Carlo法法) )(3) 算法分析约束直接搜索方法约束直接搜索方法1.1. 算法简单算法简单, , 容易实现容易实现. .2.2. 依概率收敛依概率收敛, ,即以概率为即以概率为1 1收敛到最优解收敛到最优解, ,但采样点需要无穷多但采样点需要无穷多. .3.3. 采样点多采样点多, ,运算量大运算量大, ,效率低效率低. .第4页/共54页约束直接搜索方法约束直接搜索方法二二. .随机方向法随机方向法(1) 算法思想通过在当前点的附近随机采样，确定最速下降方向，进行

4、有通过在当前点的附近随机采样，确定最速下降方向，进行有约束的一维搜索，找到新的点。约束的一维搜索，找到新的点。第5页/共54页约束直接搜索方法约束直接搜索方法二二. .随机方向法随机方向法(2) 算法-初始点生成第6页/共54页约束直接搜索方法约束直接搜索方法二二. .随机方向法随机方向法(2) 算法-搜索方向生成第7页/共54页约束直接搜索方法约束直接搜索方法二二. .随机方向法随机方向法(2) 算法-步骤第8页/共54页约束直接搜索方法约束直接搜索方法三三. .复合形法复合形法(1) 算法思想对于对于n n维变量空间维变量空间, ,单纯形是单纯形是n+1n+1个顶点个顶点. .复合形法是多

5、个单纯形合并成的超多面体复合形法是多个单纯形合并成的超多面体, ,顶点数顶点数 n+1.n+1.复合形法与复合形法与单纯形无约束直接搜索法单纯形无约束直接搜索法极为相似极为相似, ,其不同之处其不同之处: :1.1.复合形法不限制顶点个数为复合形法不限制顶点个数为n+1,n+1,复合形法顶点个数是复合形法顶点个数是k, k, 2n 2n k k n+1.n+1.2.2.复合形法需要检查顶点的可行性复合形法需要检查顶点的可行性, , 即是否满足约束即是否满足约束. .第9页/共54页初始复合形法生成初始复合形法生成1.1.随机测试找到一个可行点随机测试找到一个可行点2.2.随机生成其它点随机生成

6、其它点3.3.计算可行点的中心点计算可行点的中心点4.4.中心点不可行时中心点不可行时, ,不计最远点不计最远点 重新计算中心重新计算中心5.5.将不可行点向中心拉靠将不可行点向中心拉靠6.6.初始复合形初始复合形第10页/共54页初始复合形法生成初始复合形法生成第11页/共54页复合形法复合形法(2) 算法XhXgXlXcXhXgXlXcXr第12页/共54页XhXgXlXcXr1.1.Xc是是可行点时可行点时, ,在可行域内在可行域内找反射点找反射点2. 2. Xc是非是非可行点时可行点时, , 重新构造复合形重新构造复合形, , 并转步骤并转步骤(1)(1)XhXgXlXcXhXgXlX

7、c此情况还需分子情况处理此情况还需分子情况处理第13页/共54页复合形法复合形法(2) 算法XcXl转（转（3）第14页/共54页f(f(Xr)f(Xh)XhXgXlXcXr对第对第1种情况，即种情况，即Xc可行时可行时此情况还需分子情况处理此情况还需分子情况处理第15页/共54页f(f(Xr)f(Xh) 的子情况的子情况XhXgXlXcXrXhXgXlXcXrf(f(Xc)f(Xh)XhXgXcXr由由Xg替代替代Xh在可行域内找反在可行域内找反射点射点Xr, ,代替代替Xh.如果仍然找不到小的反射点如果仍然找不到小的反射点, ,将复合形向将复合形向Xl收缩收缩. .f(f(Xc)5n5时时

8、, ,可取可取k2n.k2n.第18页/共54页约束问题间接求解方法约束问题间接求解方法000000)()()()()()(xxdxgdxgxgxfdxfxfiTiiT四。四。可行方向法（可行方向法（Zoutendijks Method）算法思想算法思想针对不等式约束问题，在线性化约束的限制下，针对不等式约束问题，在线性化约束的限制下，求解线性规划问题确定最速可行下降方向。求解线性规划问题确定最速可行下降方向。min f(x)s.t. gi(x)0, i=1,2,pTnikTiiTddddnkdxfdxgdts),.,(, 0;,.,2 , 1 , 11- 0)( 0)( . .- min21

9、00Feasible Domaing1(x)g2(x)dx0g gi i(x)(x)为取作用的约束为取作用的约束第19页/共54页可行方向法（可行方向法（Zoutendijks Method）s.t.第20页/共54页可行方向法（可行方向法（Zoutendijks Method）第21页/共54页可行方向法（可行方向法（Zoutendijks Method）第22页/共54页可行方向法（可行方向法（Zoutendijks Method）第23页/共54页可行方向法（可行方向法（Zoutendijks Method）,.,2 , 1, 0)(|sup, 0*mjSXgiij第24页/共54页可行

10、方向法（可行方向法（Zoutendijks Method）第25页/共54页可行方向法（可行方向法（Zoutendijks Method）第26页/共54页可行方向法（可行方向法（Zoutendijks Method）第27页/共54页可行方向法（可行方向法（Zoutendijks Method）第28页/共54页约束问题间接求解方法约束问题间接求解方法000000)()()()()()(xxdxgdxgxgxfdxfxfiTiiT改进改进可行方向法（可行方向法（Modified Method of Feasible Directions）min f(x)s.t. gi(x)0, i=1,2,

11、p1 0)( . .)( min00ddxgdtsxfdTiTTFeasible Domaing1(x)g2(x)dx0g gi i(x)(x)为取作用的约束为取作用的约束第29页/共54页约束问题间接求解方法约束问题间接求解方法算法算法1.1. 初始化初始化 x=xx=x0 0,k=0;,k=0;2.2. 计算计算 f(xf(xk k) )和和 g gi i(x(xk k), g), gi i为取作用约束为取作用约束; ;3.3. 如果如果 f(xf(xk k) )和和 g gi i(x(xk k) )满足满足K-TK-T条件条件, , 结束结束; ;4.4. 否则否则, ,解解min dm

12、in dT T f(xf(xk k)|d)|dT T g gi i(x(xk k)=0,d)=0,dT Td=1,d0, X0, 调整搜索方向调整搜索方向由由X0, X0, 调整搜索步长调整搜索步长0|min,0 : is for constraint theSo,. if 0 is there, 0when ; 0 is there, 0when 0* 0 , * *otherwise)(-0)(, 0when 00 , 0 , 0)(*maxmax1111,1,1,1,1,kjkjkjkjkjkjkjkjkjkjkjkjkkNkBTkNkBkkkkkNkNkNkNjkNkNjkNjkNkN

13、kNkNddxdxxdxddxxxCdBdddddxxdxxxgxgxdxxgxx第42页/共54页模型更新方法与线性规划单纯形法类似模型更新方法与线性规划单纯形法类似. .1. 选择可行的初始点 x0=(xB,0,xN,0)0, k=0, eps0;2. 计算 g(xN,k) 和 d k;3. 如果|d k|eps, 结束，得最优解xk; 否则，作一维搜索：4.如果|xk+1-xk|0, 则基本变量不变，k=k+1,转（2）； 否则，对某下标j, xjB,k+1=0, 将该分量与xN,k+1最大分量 xiN,k+1 交换，形成新的基本变量与非基本变量，k=k+1,转（2）；kkkkkkkkk

14、dxxdxfdxf*:)*(min)*(10max简约梯度法简约梯度法- -算法步骤：算法步骤：第43页/共54页一般非线性模型一般非线性模型广义简约梯度法广义简约梯度法引入松弛变量引入松弛变量规范化的非线性模型规范化的非线性模型第44页/共54页广义简约梯度法广义简约梯度法用泰勒展式将约束变为线性：用泰勒展式将约束变为线性：分基本变量与非基本变量：分基本变量与非基本变量：第45页/共54页广义简约梯度法广义简约梯度法广义简约梯度广义简约梯度第46页/共54页广义简约梯度法广义简约梯度法- -算法步骤：算法步骤：第47页/共54页广义简约梯度法广义简约梯度法- -算法步骤：算法步骤：第48页/

15、共54页第49页/共54页第50页/共54页例子例子 见课本见课本 P418第51页/共54页约束问题间接求解方法约束问题间接求解方法六。六。简约梯度法简约梯度法算法分析算法分析1 1。适合具有非线性约束的问题；。适合具有非线性约束的问题；2 2。不太适合具有非光滑约束的问题（需要线性逼近）；。不太适合具有非光滑约束的问题（需要线性逼近）；3 3。对于中小型，大型约束优化问题均适用，且计算稳定性好。对于中小型，大型约束优化问题均适用，且计算稳定性好。4 4。收敛快，精度高，求解范围广，明显优于罚函数法，是。收敛快，精度高，求解范围广，明显优于罚函数法，是 目前最优秀的约束优化方法之一。目前最优秀的约束优化方法之一。第52页/共54页约束直接搜索方法约束直接搜索方法总结总结Monte-CarloMonte-Carlo法法-程序简单，程序简单，应用较广应用较