工程优化约束直接法

工程优化设计黄正东二0一二年九月内容提要工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统约束直接搜索方法直接法:直接沿一序列方向、在满足约束条件下的一维搜索，最后达到优化解。主要适用于仅含不等式约束的优化问题.新的迭代点必须限制在不等式约束构成的可行域内,且保证目标函数的稳定下降.随机实验法随机方向法复合形法可行方向法梯度投影法简约梯度法约束直接搜索方法一.随机实验法(Monte-Carlo法)(1)算法思想通过逐步随机取样,逼近最优解.每步随机取样得到一组点上的函数值,通过比较确定最优解的较小范围.下一步在上一步确定的范围内再随机取样,确定更小的最优解范围,如此下去,不断逼近最优解.不断缩小最优解的范围随机实验法(Monte-Carlo法)(2)算法随机实验法(Monte-Carlo法)(3)算法分析约束直接搜索方法算法简单,容易实现.依概率收敛,即以概率为1收敛到最优解,但采样点需要无穷多.采样点多,运算量大,效率低.约束直接搜索方法二.随机方向法(1)算法思想通过在当前点的附近随机采样，确定最速下降方向，进行有约束的一维搜索，找到新的点。约束直接搜索方法二.随机方向法(2)算法-初始点生成约束直接搜索方法二.随机方向法(2)算法-搜索方向生成约束直接搜索方法二.随机方向法(2)算法-步骤约束直接搜索方法三.复合形法(1)算法思想对于n维变量空间,单纯形是n+1个顶点.复合形法是多个单纯形合并成的超多面体,顶点数

n+1.复合形法与单纯形无约束直接搜索法极为相似,其不同之处:1.复合形法不限制顶点个数为n+1,复合形法顶点个数是k,2n

k

n+1.2.复合形法需要检查顶点的可行性,即是否满足约束.初始复合形法生成1.随机测试找到一个可行点2.随机生成其它点3.计算可行点的中心点4.中心点不可行时,不计最远点重新计算中心5.将不可行点向中心拉靠6.初始复合形初始复合形法生成复合形法(2)算法XhXgXlXcXhXgXlXcXrXhXgXlXcXr1.Xc是可行点时,在可行域内找反射点2.Xc是非可行点时,重新构造复合形,并转步骤(1)XhXgXlXcXhXgXlXc此情况还需分子情况处理复合形法(2)算法XcXl转（3）f(Xr)<f(Xh)XhXgXlXcXrf(Xr)>f(Xh)XhXgXlXcXr对第1种情况，即Xc可行时此情况还需分子情况处理f(Xr)>f(Xh)的子情况XhXgXlXcXrXhXgXlXcXrf(Xc)>f(Xh)XhXgXcXr由Xg替代Xh在可行域内找反射点Xr,代替Xh.如果仍然找不到小的反射点,将复合形向Xl收缩.f(Xc)<f(Xh)将Xr向Xc拉靠复合形法(2)算法约束直接搜索方法三.复合形法(3)算法分析1.适应性强,无需导数.2.程序较简单.3.当变量与约束较多时,计算效率显著降低.4.当n5时,可取k=2n,当n>5时,可取k<2n.约束问题间接求解方法四。可行方向法（Zoutendijk’sMethod）算法思想针对不等式约束问题，在线性化约束的限制下，求解线性规划问题确定最速可行下降方向。minf(x)s.t.gi(x)≤0,i=1,2,…,pFeasibleDomaing1(x)g2(x)dx0gi(x)为取作用的约束可行方向法（Zoutendijk’sMethod）s.t.可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）约束问题间接求解方法改进可行方向法（ModifiedMethodofFeasibleDirections）minf(x)s.t.gi(x)≤0,i=1,2,…,pFeasibleDomaing1(x)g2(x)dx0gi(x)为取作用的约束约束问题间接求解方法算法初始化x=x0,k=0;计算

f(xk)和

gi(xk),

gi为取作用约束;如果

f(xk)和gi(xk)满足K-T条件,结束;否则,解min{dTf(xk)|dTgi(xk)<=0,dTd<=1},求d;一维搜索xk+1=xk+ak

d

:minf(xk+ak

d);k=k+1,转步2.Step4具体有后页的细节处理。带有圆约束的线性规划问题可通过修改单纯形法求解。为DV之一约束问题间接求解方法算法分析约束问题间接求解方法五。梯度投影法（Rosen’sGradientProjectionMethod）梯度向约束面或多约束面的交线上的投影

g1

g2d

fb设b=

f-d=x

g1+y

g2,则

g1Tb=

g1T

f=x

g1T

g1+y

g1T

g2

g2Tb=

g2T

f=x

g2T

g1+y

g2T

g2(x,y)T=[GTG]-1GT

fb=G(x,y)T=G[GTG]-1GT

f当计算得S=0时，程序不一定停止，因为去掉一个取作用约束g，f(x)还可以下降。﹥0S=0需要对所有取作用g，有：梯度投影法（Rosen’sGradientProjectionMethod）1.该方法适合线性不等式约束；2.对非线性不等式约束优化问题效果不佳。六。简约梯度法算法思想将一般非线性约束优化问题转化为目标函数为非线性，约束函数为线性的优化问题。通过求解线性约束，分离出因变量和自变量，对自变量求导得出简约梯度，并沿负简约梯度方向进行搜索。基本思想是线性规划中单纯形法的推广（Wolfe）。分

简约梯度法（ReducedGradientMethod）--约束线性

广义简约梯度法（GeneralizedReducedGradientMethod）

--约束非线性简约梯度法简约梯度确定初步搜索方向minf(x)s.t.Ax=b,x≥0xN

为独立变量minF(xN)s.t.B-1b-B-1CxN≥0

xN≥0由X>0,调整搜索方向由X>0,调整搜索步长模型更新方法与线性规划单纯形法类似.1.选择可行的初始点

x0=(xB,0,xN,0)>0,k=0,eps>0;2.计算

g(xN,k)和

dk;3.如果|dk|<eps,结束，得最优解xk;

否则，作一维搜索：4.如果|xk+1-xk|<eps,结束，得最优解xk+1；否则，转下步；5.如果xB,k+1>0,则基本变量不变，k=k+1,转（2）；

否则，对某下标j,xjB,k+1=0,将该分量与xN,k+1最大分量

xiN,k+1

交换，形成新的基本变量与非基本变量，k=k+1,转（2）；简约梯度法-算法步骤：一般非线性模型广义简约梯度法引入松弛变量规范化的非线性模型广义简约梯度法用泰勒展式将约束变为线性：分基本变量与非基本变量：广义简约梯度法广义简约梯度广义简约梯度法-算法步骤：广义简约梯度法-算法步骤：例子见课本P418约束问题间接求解方法六。简约梯度法算法分析1。适合具有非线性约束的问题；2。不太适合具有非光滑约束的问题（需要线性逼近）；3。对于中小型，大型约束优化问题均适用，且计算稳定性好