最优化方法第四章概要课件.ppt

1、第 4 章 约束最优化方法 在第2章中已讨论过带有约束的线性规划问题，而本章要讨论的则是带有约束的非线性规划问题，其一般形式为min();.()0,()0.f xsts xh x（4.1）其中1:,:,:nnmnlfRR s RRh RR。这个问题的求解是指，在容许集()0,()0,nDx s xh xxR *xxD内找一点，使得对于任意的，都有*()()f xf x点*x 称为问题（4.1）的最优解。由于带有了约束，使得对约束最优化问题（4.1）的求解变得比对无约束最优化问题（3.1）的求解复杂得多，也困难得多。本章将讨论求解约束最优化问题常用的两类最优化方法。一类是所谓的容许方向法容许方向

2、法。它是一种直接处理约束的方法。另一类是所谓的罚函数法罚函数法。相对前者而言，它是一种直接处理约束问题本身的方法，其主要特点是用一系列无约束问题的极小点去逼近约束问题的最优点。在4.1节中将首先讨论约束问题的最优性条件，为后面算法的终止准则提供理论依据；在4.2-4.3节中将讨论二种容许方向法，包括Zoutendijk容许方向法、Rosen梯度投影法；在4.6-4.8节中将讨论三种罚函数法，它们是外部罚函数法、内部罚函数法和乘子法。4.1 最优性条件最优性条件 所谓最优性条件最优性条件，就是最优化问题的目标函数与约束函数在最优点所满足的充分条件和必要条件。最优性必要条件是指，最优点应该满足的条

3、件；最优性充分条件是指，可使得某个容许点成为最优点的条件。最优性条件对于最优化算法的终止判定和最优化理论的推证都是至关重要的。本节仅讲述最基本的结论。在第2章和第1章中，已经分别讨论过线性规划问题和无约束问题的最优性条件。定理2.9是线性规划问题的最优性充分条件。定理1.15、定理1.17和定理1.18以及推论1.16分别是无约束问题的最优性必要条件、充分条件以及充分且必要条件。本节主要讨论一般约束问题的最优性条件。我们将先从仅含等式约束或不等式约束的问题入手，然后自然过渡到一般约束问题。1.等式约束问题的最优性条件等式约束问题的最优性条件考虑仅含等式约束的问题min();.()0,1,2,.

4、jf xst h xjl （4.2）这个问题的最优性条件与求解方法在微积分中已从理论上得到了解决，这就是Lagrange定理和Lagrange乘子法。定理定理4.1（Lagrange定理）P217Lagrange乘子法乘子法 定义函数121(,)()()lljjjL xf xh x 称为Lagrange函数函数，其中12,l 称为Lagrange乘子乘子，则求解等式约束问题（4.2）等价于求解无约束问题(4.4)121min(,)()()lljjjL xf xh x Lagrange 函数（4.4)的梯度是xLLL1()()lxjjjLf xh x 其中12(),(),()lTLh xh xh

5、 x 最优性必要条件*12(,)0lL x及()0,1,2,jh xjl下面的定理给出了（4.2）的最优性二阶充分条件。定理定理4.2 P2182.2.不等式约束问题的最优性条件不等式约束问题的最优性条件（1）几何最优性条件下面将给出约束问题min();.()0,1,2,.if xst s xim （4.7）的最优性条件。D()0,1,2,iDx s xim设容许集仍用表示，即以下几个概念是讨论的基础。定义定义4.1 对于约束问题（4.7），设 xD。若x使得某个不等式约束有()0is x，则该不等式约束()0is x 称为是关于容许点 x()0is x 的起作用约束起作用约束；否则，若 则该

6、不等式约束称为是关于容许点x的不起作用约束不起作用约束。，例如，不等式约束关于容许集的任意内点都是不起作用约束。只有容许集的边界点才能使某个或某些不等式约束变为起作用约束。CnR定义定义4.2 设是中的非空集，且 xCnpR。对于，若当 xpC0t xtpC时，对于，必有 CxC，则集合称为以以为顶点的锥为顶点的锥。若锥是凸集，则称为凸锥凸锥。n12,mv vv 显然，由维向量的全部非负组合构成的集合1,0miiiiCx xv 是一个以原点为顶点的凸锥。由于这样的凸锥的边界是（超）平面或直线，所以也称为由 12,mv vv 凸多面锥凸多面锥。张成的DnR定义定义4.3 设是中的非空集，且 xD

7、npR。对于非零 向量0(0,)t，若存在，当时，必有 xtpDp，则称为点 xx的容许方向向量，其方向 称为点的容许方向。由点 xx*()C x的全部容许方向向量构成的的容许方向锥容许方向锥，记作集合称为点()0,1,2,ixDx s xim()0,1,2,iIi s xim引理引理4.3 设 iI()is x；并设当时，在点 xiI处可微，当时，()is xx在点处连续。若对于所有的iIp()0Tis xppx，向量使得，则是点的一个容许方向向量。证证 考虑某个iI()0Tis xpp()is x。因为，所以是在点处的上升方向。根据定义1.10，存在0i x,例如，(0,)it()()0i

8、is xtps x当时，。iI()0is x 再考虑某个。因为()is xx，且在点 0i(0,)it()0is xtp处连续，故存在，当时，。1min ii m(0,)t取，则当 i()0is xtp时，对于所有的必有 xtpDpx，即。根据定义4.3，即是点的容许方向向量。()()0,TiG xps xpiI()()G xC x记，则依引理4.3可知，。x()0is x 由这个引理看到一个事实，若仅使某个约束，例如，变成起作用约束，且()0is x，而其它约束是不起作用约束，则()ips x x()0is x 就是点的一个容许 方向向量。换句话说，约束曲面 把整个空间分成()is x总是指

9、向包含容许集的那一侧。两部分，梯度，xx由点的所有下降方向向量构成的集合称为点下降方向锥下降方向锥。的1:nfRRxxp定理定理4.4 设在点处可微，则点下降方向向量必满足的()0Tf xp()()0TS xpf xp()S xx()S xnR记，则定理4.4表明，既是点的下降方向锥。显然是中的半空间。下面的定理给出的约束问题（4.7）的最优性条件是仅借助点集的概念给出的，所以称为几何最优性条件几何最优性条件。*x*x定理定理4.5 在约束问题（4.7）中，若是局部最优点，处的容许方向锥和下降方向锥的交集是空集。则点这个定理表明：在最优点*x处，一定不存在下降容许方向。换句话说，在最优点*x处

10、，或者不存在下降方向，或者任何下降方向都不是容许方向。定理定理4.6 在问题（4.7）中，假设：*x*()0,1,2,;iIi s ximi）是局部最优点，()f x*xiI()is x*xii）在点处可微；当时，在点 iI()is x*x可微，当时，在点处连续。那么，处*()()G xS x 证证 根据引理4.3，若*()pG x*()pC x*()()G xC x，则，从而*()(),C xS x*()()G xS x。又根据定理4.5，有故必有。例例4.1 P222 定理4.5和定理4.6给出的最优性条件仅仅是必要的，而不是充分的。习题4.6和习题4.7可以说明这一点。几何最优性条件直观

11、易懂，但在实际计算中使用起来并不简便。以下讨论的Fritz-John条件和Kuhn-Tucker条件是经常用到的最优性条件。（2）Fritz-John条件 首先介绍两个引理，这两个引理本身在最优化理论中处于很重要的地位。12,ma aa bn引理引理4.7（Farkas）设和是维向量，则满足0,1,2,Tia pim 的向量p也满足0Tb p 的充要条件是，存在非负数12,m，使得1.miiibaFarkas引理的几何解释：b0,1,2,TiPp a pim mFarkas引理指出，向量与凸多面锥（个半空间的交集）中任意向量都交成锐角或直角的充要条件是，向量 b位于凸多面锥 121,0,0,0

12、miimiAb ba 1bAP之中。例如，见上图，位于中，它与中的任意向量都交成锐角；2bAP2b2pP不在中，它就不与中的所有向量交成与交成钝角。锐角或直角，如12,ma aa np引理引理4.8（Gordan）设是维向量，使得则不存在向量0,1,2,Tia pim 成立的必要条件是，存在不全为零的非负数12,m 使得10miiiap0(1,2,)Tia pim 12,ma aa Gordan引理的几何意义：不存在向量使得在几何上表示向量 的某一非负线性组合为零向量。例如，在左下图中，取 12311,2,2，可使1 122330aaa 1234,1 12233440aaaa右下图中，则找不到

13、不全为零的非负数使得。；在*x12(),(),(),()mf x s x sxsx*x01,m 定理定理4.9（Fritz-John）在问题（4.7）中，设是在点处可微。，使得局部最优解，那么，存在不全为零的实数*01*()()0,()0,1,2,0,1,2,.miiii iif xs xs ximim（4.9）*()0(1,2,)i is xim*()0is x其中称为互补松弛条件互补松弛条件。它表明：若iI0i0i*()0is xiI，即，则必有；若，则，即。必有 这个定理给出了问题（4.7）的一个最优性必要条件。（4.9）称为问题（4.7）的Fritz-John条件条件，满足Fritz-

14、John条件的点称为Fritz-John点点。（4.9）中的1,m也称为Lagrange乘子乘子。例例4.2 考虑约束问题22122121212min(4)(5);.40,4 80,0,0.xxxstxxxxx*2,3Tx 04,0Tx 试验证是Fritz-John点，不是Fritz-John点。*2,3Tx 1,2I 解解 参看例4.1，在点处，。计算*12*34()4,4,()1,1,()1,2,()1,0,()0,1.TTTTTf xs xsxs xsx 取012341,4,0，则有4*01*41()()40,41()0,1,2,4.iiii if xs xs xi这表明*x是Fritz

15、-John点。04,0Tx 1,4I 再考虑点，这时。计算01040()0,10,()2,1,()0,1.TTTf xs xs x 根据（4.11），只须说明不存在不全为零的非负数014,，使得0140200.10110 事实上，（4.12）式可写为（4.12）120014100（4.13a）（4.13b）104010 由（4.13a）得，而由（4.13b）有，这04和若取非零值，则必异号。一关系表明，这就是说，014,不可能存在不全为零的非负数使得（4.12）成立，即0 x不是Fritz-John点。Fritz-John条件仅是判断容许点是否为最优点的必要条件，而不是充分条件。看下面的例题。

16、例例4.3 考虑约束问题221231212min(1)(1);.0,0.xxstxxxx(1)，解解 显然*1 1,2 2Tx 是此问题的唯一最优点。121xx3112()s xxx（1）因为在直线上，约束 关于所有容许点的梯度都等于零，所以当取010,0时，总有011()()0,f xs x（4.14）1,0T0,1T1()0s x 如果除去点和点（这两点的起作用约束不止）121xx1 1,2 2T，那么（4.14）说明在直线其余的容许点都满足Fritz-John条件。但除了其它的点全不是最优点。上，外，（3）Kuhn-Tucker条件首先讨论一个例题。例例4.4 P227 总结：Fritz

17、-John条件失效的一个原因是，起作用约束函数的梯度线性相关。为保证*()f x一定在Fritz-John条件中出现，即必须保证 00，这可以通过附加上起作用约束函数的梯度线性无关的条件Kuhn和Tucker提出的条件。实际上，为了保证00，还可以对起作用约束函数的梯度附加其它形式的条件，这样的一些条件在最优化理论中称为约束品性约束品性。定理定理4.10（Kuhn-Tucker）P227 在起作用约束函数的梯度线性无关的前提下，公式（4.15）称为Kuhn-Tucker条条件，而满足此条件的点称为Kuhn-Tucker点点。Kuhn-Tucker条件的几何意义：在公式（4.15）中，删去不起作

18、用约束项（注意，它们的系数是 0()iiIKuhn-Tucker条件可简写为：存在）,0()iiI，使得*()()iii If xs x（4.17）该式在几何上表示：若*x是问题（4.7）的最优点，则根据Farkas引理可知，目标函数在该点的梯度必位于由起作用约束函数的梯度所张成的凸锥之中。例如，书上图4-9显示，在点*x*()f x*1()s x*2()sx处处于由和张成的凸锥之中，因此*x满足Kuhn-Tucker条件，所以它有可能是最优点。如图所示，*x确实是最优点。但在 x()f x处，不在由 1()s x2()sx和所张成的凸锥之中，xKuhn-Tucker条件，因此肯定不是最优点。

19、就不满足例例4.5 说明例4.2中的*2,3Tx 是KuhnTucker点。*2,3Tx 00*12(),()s xsx*x解解 由例4.2中的求解知是Fritz-John点，且。又是线性无关的，所以由是Kuhn-Tucker点。定理4.10可知，3.3.一般约束问题的最优性条件一般约束问题的最优性条件 现在给出一般约束问题（4.1）的最优性条件。它也分Fritz-John条件和Kuhn-Tucker条件。定理定理4.11（Fritz-John）P229定理定理4.12（Kuhn-Tucker）P229例例4.6 P229f1,mss1,lhh*x*x定理定理4.13 在凸规划问题（1.37）中，假设是可微是可微凹函数，是线性函数。是（1.37）的KuhnTucker点，则是（1.37）的凸函数，全局最优点。若