1、工程优化设计黄正东二0一二年九月内容提要 工程优化问题建模工程优化问题建模 优化数学理论优化数学理论 一维搜索方法一维搜索方法 无约束问题直接搜索方法无约束问题直接搜索方法 无约束问题间接接搜索方法无约束问题间接接搜索方法 约束问题直接搜索方法约束问题直接搜索方法 线性规划与二次规划问题求解线性规划与二次规划问题求解 约束问题间接搜索方法约束问题间接搜索方法 启发式算法启发式算法 优化软件系统优化软件系统优化数学理论一一. .优化模型优化模型min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,p x=(x1,x2,xn)TRn, f, gi, hi: Rn
2、-R1 二二. .约束相关概念约束相关概念(1) (1) 可行点可行点( (Feasible Point), Feasible Point), x0 满足满足hi(x0)=0, i=1,2,mgi(x0) 0, i=m+1,p优化数学理论(2) (2) 可行域可行域(Feasible Region)(Feasible Region)g1(x)=9x1+4x2-3600g2(x)=3x1+10 x2-300 0g3(x)=4x1+5x2-200 0g4(x)=-x1 0g5(x)=-x2 0优化数学理论优化数学理论(2) (2) 可行域可行域(Feasible Region)(Feasible
3、Region)F= x | hi(x)=0, i=1,2,m gi(x)0, i=m+1,p 例子例子: h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0 g4(x)=-x3 0 x2x1x3F=ABCABCDE优化数学理论(3) (3) 有效约束有效约束, ,或取作用约束或取作用约束( (Active Constraint)Active Constraint)可行域边界点所在约束为该点的有效约束可行域边界点所在约束为该点的有效约束，其他约束为不取作用约束（ Inactive constraint ）。 X(1): g1(x)0X(2): g1(x)0,
4、g2(x)0X(3): 无优化数学理论(3) (3) 有效约束有效约束, ,或取作用约束或取作用约束( (Active Constraint)Active Constraint) h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0, g4(x)=-x3 0 x2x1x3F=ABCABCDE对于约束对于约束gi(x)0, 若若gi(x0)=0, 则则gi是是x0的有效约束的有效约束. 如如g3是是D的有效约束的有效约束.对于约束对于约束gi(x) 0, 若若gi(x0) aTx1= aTx0= aT(y-x0)0 - aTy aTx0= aT(x-x0) 0
5、- aTx aTx0= 优化数学理论四四. . FarkasFarkas引理引理 ( (线性不等式定理线性不等式定理) )设设A Rmxn, b Rn, 则下述两组方程中仅则下述两组方程中仅有一组有解有一组有解: (1) Ax 0, bTx0(2) ATy=b, y 0这里这里x Rn, y Rm,02121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x 0, 0, a ai i与与x x的的夹角夹角 9090o oATy=(a1,a2,am)y=y1a1+ y2a2+ ymam=bb b是是a a1 1,a,a2 2, ,a,am m的正线性组合的正线性组合揭示了揭示了m
6、m个向量与个向量与另一向量的线性组另一向量的线性组合合, , 与它们定义的半与它们定义的半空间交集的联系空间交集的联系. .02121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x 0, 0, a ai i与与x x的的夹角夹角 9090o o优化数学理论ATy=(a1,a2,am)y=y1a1+ y2a2+ ymam=bb b是是a1,a2,am的正线性组合的正线性组合 b属于属于D0情况情况1:1:a2a2Tx 0a1Tx 0a1b=y1a1+y2a2, y10, y20, (2)有解 bTx0D2D1D1D2=, 所以 (1)无解.D1=x | a1Tx 0, a2Tx
7、 0D2=x | bTx0D002121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x 0, 0, a ai i与与x x的的夹角夹角 9090o o优化数学理论ATy=(a1,a2,am)y=y1a1+ y2a2+ ymam=bb b是是a1,a2,am的正线性组合的正线性组合情况情况2:2:a2a2Tx 0a1Tx 0a1bbTx0D1D0不包含b, 所以 ATyb (2)无解.D1D2 , (1)有解D1=x | a1Tx 0, a2Tx 0D2=x | bTx0D2D0a1a4a3a202121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x0, 0,
8、 所有所有a ai i都在以都在以x x为法向的为法向的平面的反侧平面的反侧优化数学理论ATy=(a1,a2,am)y=y1a1+ y2a2+ ymam=0存在三角形存在三角形a ai ia aj ja ak k包含原点包含原点表明表明a ai i在大于等于在大于等于180180o o的扇区内的扇区内. .GordanGordan择一定理择一定理: :设设A Rmxn, 则则或者存在或者存在x Rn, 使使Ax 0,或者存在或者存在y Rm, 使使ATy =0, y 0, y 0( (分量不全为零分量不全为零) )且两者不能同时成立且两者不能同时成立.xa1a4a3a2b=0优化数学理论函数等
9、高线函数等高线Stop here last time优化数学理论优化数学理论几何方法找最优点几何方法找最优点优化数学理论几何方法找最优点几何方法找最优点解在解在D D的内点、边界、顶点处，求解难度不一样！的内点、边界、顶点处，求解难度不一样！优化数学理论函数梯度函数梯度 f(x(2) f(x(1)优化数学理论函数函数HessianHessian矩阵矩阵例子例子优化数学理论二次函数与二次函数与正定正定矩阵矩阵正定条件正定条件负定条件负定条件XXff优化数学理论梯度向约束面或多约束面的交线上的梯度向约束面或多约束面的交线上的投影投影 g1 g2d fb设设b b = = f-d=x g1+y g2
10、, 则则 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=GGTG-1GT f优化数学理论五五. . 凸函数凸函数凸函数定义凸函数定义: f(x)的定义域的定义域D Rn是凸的是凸的,且对于任意且对于任意x,y D有有 f( x+(1- )y) f(x)+(1- )f(y), 0 1则称则称f(x)为凸函数为凸函数.若若 f( x+(1- )y) f(x)+(1- )f(y), 0 0,m0,使使 u uT T 2 2f(x)u f(x)u m |u|2, x D, u
11、Rn则水平集则水平集L(x0)=x D | f(x) f(x0)是有界闭凸集合是有界闭凸集合.优化数学理论六六. . 一般最优性必要条件一般最优性必要条件f(x)是定义域是定义域D Rn上的连续函数上的连续函数,对于方向对于方向s, 如果如果0, 使使 f(x0+ s) f(x0), 0 则称则称s是是f(x)在在x0处的下降方向处的下降方向. x0处的所有下降方向记为处的所有下降方向记为D(x0).(1).(1).下降方向定义下降方向定义定理定理: 如果如果f(x)可微可微, 且且 f(x)Ts0, sk-s, 则称则称s是在是在x0处的一个可行方向处的一个可行方向.x0处的所有可行方向记为
12、处的所有可行方向记为F(x0).(1).(1).可行方向定义可行方向定义一般最优性必要条件一般最优性必要条件定理定理: 若若x*是优化问题的局部最优解是优化问题的局部最优解,则则F(x*) D(x*)=.Fss极限下的可行方向极限下的可行方向一般可行方向一般可行方向skFDUsable feasible direction优化数学理论七七. . 一阶最优性必要条件一阶最优性必要条件(1).(1).线性化可行方向定义线性化可行方向定义 h(x)s设设x0 F, F为可行域为可行域, s Rn, 且且 sT hi(x0)=0, i=1,2,m sT gi(x0)0, i A(x0), 有效不等式约
13、束集合有效不等式约束集合则称则称s是在是在x0处的线性化可行方向处的线性化可行方向. x0处的所有线性化可行方向记为处的所有线性化可行方向记为L(x0).sh(x)=0 g(x)g(x) 0FF七七. . 一阶最优性必要条件一阶最优性必要条件(2) (2) 约束线性化定理约束线性化定理若所有约束若所有约束hi(x)和和gi(x)在在x0 F处连续可微处连续可微, 则则 (1) F(x0) L(x0) (2) 如果或者所有如果或者所有hi(x),i=1,2,m, gi(x), i A(x0) 是线性函数是线性函数 或者约束梯度之间（包括或者约束梯度之间（包括 hi(x)和和 gi(x)）线性无关
14、线性无关, 则则F(x0) =L(x0)成立成立.解释解释: (1) : (1) 说明说明L(xL(x0 0) )比实际可行方向定义松比实际可行方向定义松. . (2) (2) 一些极端情况下一些极端情况下, , F(x0) L(x0).sg1(x)0g2(x) 0F g1(x)sT g1(x0)0sT g2(x0)0 g2(x)s属于属于L(x0),但不属于但不属于F(x0)LICQ: Linear Independent Constraint Qualification优化数学理论七七. . 一阶最优性必要条件一阶最优性必要条件(2).(2).一阶最优性必要条件定理一阶最优性必要条件定理(
15、 (Kuhn-TuckerKuhn-Tucker条件条件) )设设hi(x)和和gi(x)一阶连续一阶连续,如果或者所有如果或者所有hi(x), i=1,2,m, gi(x), i A(x*) 是线性函数是线性函数, 或者约束梯度之间或者约束梯度之间（包括包括 hi(x)和和 gi(x)）线性无关线性无关, 则存在则存在=( 1, 2, p ), 使使pmixgpmixgxhxfiiipmiiimiii,.,1, 0*)(,.,1, 00*)(*)(*)(11解释解释:(1):(1)当全为等式约束时当全为等式约束时, ,只有第一、二项只有第一、二项, , 可正可负可正可负. . (2)(2)当
16、全为不等式约束时当全为不等式约束时, ,只有第一、三项只有第一、三项, ,约束中约束中 i 0, iA(x*)和和 i =0, iI-A(x*), I=m+1,phi(x)=0 hi(x) fi(x)FFhi(x)=0 hi(x) fi(x)优化数学理论七七. . 一阶最优性必要条件一阶最优性必要条件当当i I-A(x*)时时, gi(x*)0, 所以所以, 有有 i=0. 当当i A(x*)时时, gi(x*)=0, 且且 i 0. 从一式知从一式知, - f 是是 g的正向组合的正向组合.g1(x)=0 g1(x) fi(x)Fg2(x)=0 g2(x)pmixgpmixgxhxfiiip
17、miiimiii,.,1, 0*)(,.,1, 00*)(*)(*)(11解释解释: :(2)(2)当全为不等式约束时当全为不等式约束时, ,只有第一、三项只有第一、三项, ,约束中约束中 i 0, iA(x*)和和 i =0, iI-A(x*), I=m+1,p- - fi(x)此项等价于求和条件此项等价于求和条件只考虑取作用约束！只考虑取作用约束！优化数学理论七七. . 一阶最优性必要条件一阶最优性必要条件优化数学理论七七. . 一阶最优性必要条件一阶最优性必要条件X X* *是最优解吗是最优解吗? ? 如果是如果是, ,为什么为什么必要条件不成立必要条件不成立? ?注意线性化要求的检查注
18、意线性化要求的检查! !优化数学理论七七. . 一阶最优性必要条件一阶最优性必要条件证明证明: : 由约束线性化定理知由约束线性化定理知, , F(xF(x* *)=L(x)=L(x* *) ) 一般最优性条件是一般最优性条件是F(x*) D(x*)= , 即即L(x*) D(x*)= D(x*): f(x*)Ts0A=(- h1(x*) - hm(x*) h1(x*) hm(x*) gi(x*), i A(x0)由由Farkas引理知引理知, As 0, - f(x*)Ts0 无解等价于无解等价于: ATy=- f(x*), y 0, 有解有解. 即即:)()3(1)2()1(*)(*)()
19、(*)(xAiiimiiiixgyxhyyxf I (正负不限正负不限) i 0优化数学理论八八. . 一阶最优性充分条件一阶最优性充分条件定理定理若优化问题是凸规划问题若优化问题是凸规划问题,且且f(x), hi(x), gi(x) 连续可微连续可微, 当当K-T条件满足时条件满足时, x*是全局最优解是全局最优解. 优化数学理论九九. . 二阶最优性必要条件二阶最优性必要条件定理定理设设x*是最优解是最优解,且且f(x), ci(x)二阶连续可微二阶连续可微, 所有所有hi(x), i=1,2,m, gi(x),i A(x*)或者是线性函数或者是线性函数, 或者梯度或者梯度 hi(x)、
20、gi(x)线性无关线性无关, 从而存在从而存在 使使K-T条件成立条件成立,则则sT 2xxL(x*, *)s 0对一切满足对一切满足sT hi(x*)=0, i=1,2,m, sT gi(x*)=0, i A(x*)的方向的方向s均成立均成立. 这里这里L(x, )=f(x)- ihi(x)+ igi(x) 解释解释: :对指向对指向F内部内部 的方的方向向s一般不成立一般不成立. .FssFssf(x)f(x)对双可行方向对双可行方向s s优化数学理论十十. . 二阶最优性充分条件二阶最优性充分条件定理定理设设f(x), hi(x)二阶连续可微二阶连续可微, 所有所有hi(x), i=1,
21、2,m, gi(x), i A(x*)或者或者是线性函数是线性函数, 或者梯度或者梯度 hi(x*)、 gi(x*)线性无关线性无关, 若若: (1) 存在存在 使使K-T条件成立条件成立; (2) sT 2xxL(x*, *)s 0, 对一切满足对一切满足sT hi(x*)=0, i=1,2,m, sT gi(x*)=0, i A(x*)的方向的方向s均成立均成立. 则则x*是是严格严格局部最优解局部最优解.解释解释: : （1 1） 通常一阶条件通常一阶条件( (K-T)K-T)保证保证x x* *是平稳点是平稳点, ,即极点、拐点或鞍点。即极点、拐点或鞍点。通过二阶条件才能保证通过二阶条
22、件才能保证x x* *是极点。是极点。 （2 2）排除拐点或鞍点的方法是考察两个相反方向上）排除拐点或鞍点的方法是考察两个相反方向上f(x)f(x)的凸性，的凸性，所以，只有在边界切方向和所以，只有在边界切方向和F内点才能有两个相反可行方向。内点才能有两个相反可行方向。 （3 3）对于）对于x x* *是是F内点的情况内点的情况, ,问题转化为无约束，问题转化为无约束， 2xxL= 2f, 二阶二阶条件是条件是 2f 正定，即正定，即sT 2f(x*)s 0, 对所有对所有s. 为什么是为什么是sT 2xxL(x*, *)s 0 而不是而不是sT 2xxf(x*)s 0 ?右图例子右图例子:
23、f(x)=y, h(x)=x2+y2-1, *=-1/2, x*=(0,-1), s=(0,1)sT 2xxfs=0, sT 2xxLs=10 x*h(x)=0f(x)=y现对较简单的问题现对较简单的问题min f(x,y), s.t. h(x,y)=0证明以上结论证明以上结论:H(x)=h(x,y(x) 0H(x)=hx+hyy 0 y=-hx/hyH”(x)=hxx+hxyy+(hxy+hyyy)y+hyy”=hxx+2hxyy+hyyy2+hyy”0 y”=2hxyhx/hy2-hxx/hy-hyyhx2/hy3F(x)=f(x,y(x)=0, F(x)=fx+fyy=(1,y) f=(
24、1,-hx/hy) f =(hy,-hx) f/hy= 0所以所以， 存在存在 使使 f- h=0 一阶条件证毕一阶条件证毕F”(x)=fxx+2fxyy+fyyy2+fyy”=fxx-2hxfxy/hy+hx2fyy/hy2+fy2hxyhx/hy2-hxx/hy-hyyhx2/hy3=(1/hy2) hy2fxx-2hxhyfxy+hx2fyy (fy/hy3)hxxhy2-2hxhyhxy+hyyhx2= 二阶条件证毕二阶条件证毕yyTxyxxTxyyyyyxyxyxyxyxxxxxyhfhhsLsshhhfhfhfhfhh/,2如何使用最优性条件如何使用最优性条件?K-T条件将原问题条
25、件将原问题 min f(x), s.t. h(x)=0 转化为转化为 min L(x), s.t. h(x)=0, 这里这里 L(x)=f(x)- *h(x), 假设假设 *已知已知.两问题有同样的解两问题有同样的解, , 这样处理的优点在于这样处理的优点在于: :(1)(1) 最优解最优解满足满足 xL=0、 2xxL正定（在流形正定（在流形h(x)上）上）, ,与无约束问题的与无约束问题的最优性条件形式上相似最优性条件形式上相似. .(2)(2) 而而 xf=0、 2xxf正定正定（在流形（在流形h(x)上），不能成为解的条件。上），不能成为解的条件。不足之处不足之处： （1 1）由于）由
26、于 *事实上不知道，直接优化事实上不知道，直接优化L(x, *)不可能不可能。（2 2）即使）即使 *知道知道，优化优化L(x, *)时还是要考虑时还是要考虑h约束约束。一般使用方法一般使用方法：（1）由方程由方程 xL= xf- xh=0和和h(x)=0, 求解求解x*和和 *。（2）用用 2xxL在在h(x)=0上的正定性，确定上的正定性，确定x* 是否是最优解是否是最优解。优化数学理论总结：总结：1 1。可行区域。可行区域F F，可行方向可行方向F(x),F(x),下降方向下降方向D(x)D(x)， 有效约束有效约束A(x)A(x)，线性下降方向线性下降方向L(x)L(x)。2 2。凸集合与凸函数。凸集合与凸函数。3 3。FarkasFarkas引理与引理与GordanGordan定理。定理。4 4。一般最优性条件。一般最优性条件5 5。一阶最优性条件（。一阶最优性条件（K-TK-T条件）条件）6 6。二阶最优性条件（。二阶最优性条件（HesseHesse矩阵正定或半正定）矩阵正定或半正定）
