最优化方法第四章(1)概要

第4章约束最优化方法在第2章中已讨论过带有约束的线性规划问题，而本章要讨论的则是带有约束的非线性规划问题，其一般形式为min();..()0,()0.fxstsxhx（4.1）其中1:,:,:nnmnlfRRsRRhRR。这个问题的求解是指，在容许集{()0,()0,}nDxsxhxxR*xxD内找一点，使得对于任意的，都有*()()fxfx点*x称为问题（4.1）的最优解。由于带有了约束，使得对约束最优化问题（4.1）的求解变得比对无约束最优化问题（3.1）的求解复杂得多，也困难得多。本章将讨论求解约束最优化问题常用的两类最优化方法。一类是所谓的容许方向法。它是一种直接处理约束的方法。另一类是所谓的罚函数法。相对前者而言，它是一种直接处理约束问题本身的方法，其主要特点是用一系列无约束问题的极小点去逼近约束问题的最优点。在4.1节中将首先讨论约束问题的最优性条件，为后面算法的终止准则提供理论依据；在4.2-4.3节中将讨论二种容许方向法，包括Zoutendijk容许方向法、Rosen梯度投影法；在4.6-4.8节中将讨论三种罚函数法，它们是外部罚函数法、内部罚函数法和乘子法。4.1最优性条件所谓最优性条件，就是最优化问题的目标函数与约束函数在最优点所满足的充分条件和必要条件。最优性必要条件是指，最优点应该满足的条件；最优性充分条件是指，可使得某个容许点成为最优点的条件。最优性条件对于最优化算法的终止判定和最优化理论的推证都是至关重要的。本节仅讲述最基本的结论。在第2章和第1章中，已经分别讨论过线性规划问题和无约束问题的最优性条件。定理2.9是线性规划问题的最优性充分条件。定理1.15、定理1.17和定理1.18以及推论1.16分别是无约束问题的最优性必要条件、充分条件以及充分且必要条件。本节主要讨论一般约束问题的最优性条件。我们将先从仅含等式约束或不等式约束的问题入手，然后自然过渡到一般约束问题。1.等式约束问题的最优性条件考虑仅含等式约束的问题min();..()0,1,2,,.jfxsthxjl（4.2）这个问题的最优性条件与求解方法在微积分中已从理论上得到了解决，这就是Lagrange定理和Lagrange乘子法。定理4.1（Lagrange定理）P217Lagrange乘子法定义函数121(,,,,)()()lljjjLxfxhx称为Lagrange函数，其中12,,,l称为Lagrange乘子，则求解等式约束问题（4.2）等价于求解无约束问题(4.4)121min(,,,,)()()lljjjLxfxhxLagrange函数（4.4)的梯度是xLLL1()()lxjjjLfxhx其中12(),(),()lTLhxhxhx最优性必要条件****12(,,,)0lLx及()0,1,2,,jhxjl下面的定理给出了（4.2）的最优性二阶充分条件。定理4.2P2182.不等式约束问题的最优性条件（1）几何最优性条件下面将给出约束问题min();..()0,1,2,,.ifxstsxim（4.7）的最优性条件。D{()0,1,2,,},iDxsxim设容许集仍用表示，即以下几个概念是讨论的基础。定义4.1对于约束问题（4.7），设xD。若x使得某个不等式约束有()0isx，则该不等式约束()0isx称为是关于容许点x()0isx的起作用约束；否则，若则该不等式约束称为是关于容许点x的不起作用约束。，例如，不等式约束关于容许集的任意内点都是不起作用约束。只有容许集的边界点才能使某个或某些不等式约束变为起作用约束。CnR定义4.2设是中的非空集，且xCnpR。对于，若当xpC0txtpC时，对于，必有CxC，则集合称为以为顶点的锥。若锥是凸集，则称为凸锥。n12,,,mvvv显然，由维向量的全部非负组合构成的集合1{,0}miiiiCxxv是一个以原点为顶点的凸锥。由于这样的凸锥的边界是（超）平面或直线，所以也称为由12,,,mvvv凸多面锥。张成的DnR定义4.3设是中的非空集，且xDnpR。对于非零向量0(0,)t，若存在，当时，必有xtpDp，则称为点xx的容许方向向量，其方向称为点的容许方向。由点xx*()Cx的全部容许方向向量构成的的容许方向锥，记作集合称为点{()0,1,2,,},ixDxsxim{()0,1,2,,}iIisxim引理4.3设iI()isx；并设当时，在点xiI处可微，当时，()isxx在点处连续。若对于所有的iIp()0Tisxppx，向量使得，则是点的一个容许方向向量。证考虑某个iI()0Tisxpp()isx。因为，所以是在点处的上升方向。根据定义1.10，存在0ix,例如，(0,)it()()0iisxtpsx当时，。iI()0isx再考虑某个。因为()isxx，且在点0i(0,)it()0isxtp处连续，故存在，当时，。1min{}iim(0,)t取，则当i()0isxtp时，对于所有的必有xtpDpx，即。根据定义4.3，即是点的容许方向向量。(){()0,}TiGxpsxpiI()()GxCx记，则依引理4.3可知，。x()0isx由这个引理看到一个事实，若仅使某个约束，例如，变成起作用约束，且()0isx，而其它约束是不起作用约束，则()ipsxx()0isx就是点的一个容许方向向量。换句话说，约束曲面把整个空间分成()isx总是指向包含容许集的那一侧。两部分，梯度，xx由点的所有下降方向向量构成的集合称为点下降方向锥。的1:nfRRxxp定理4.4设在点处可微，则点下降方向向量必满足的()0Tfxp(){()0}TSxpfxp()Sxx()SxnR记，则定理4.4表明，既是点的下降方向锥。显然是中的半空间。下面的定理给出的约束问题（4.7）的最优性条件是仅借助点集的概念给出的，所以称为几何最优性条件。*x*x定理4.5在约束问题（4.7）中，若是局部最优点，处的容许方向锥和下降方向锥的交集是空集。则点这个定理表明：在最优点*x处，一定不存在下降容许方向。换句话说，在最优点*x处，或者不存在下降方向，或者任何下降方向都不是容许方向。定理4.6在问题（4.7）中，假设：*x*{()0,1,2,,};iIisximi）是局部最优点，()fx*xiI()isx*xii）在点处可微；当时，在点iI()isx*x可微，当时，在点处连续。那么，处**()()GxSx证根据引理4.3，若*()pGx*()pCx**()()GxCx，则，从而**()(),CxSx**()()GxSx。又根据定理4.5，有故必有。例4.1P222定理4.5和定理4.6给出的最优性条件仅仅是必要的，而不是充分的。习题4.6和习题4.7可以说明这一点。几何最优性条件直观易懂，但在实际计算中使用起来并不简便。以下讨论的Fritz-John条件和Kuhn-Tucker条件是经常用到的最优性条件。（2）Fritz-John条件首先介绍两个引理，这两个引理本身在最优化理论中处于很重要的地位。12,,,maaabn引理4.7（Farkas）设和是维向量，则满足0,1,2,,Tiapim的向量p也满足0Tbp的充要条件是，存在非负数12,,,m，使得1.miiibaFarkas引理的几何解释：b0,1,2,,TiPpapimmFarkas引理指出，向量与凸多面锥（个半空间的交集）中任意向量都交成锐角或直角的充要条件是，向量b位于凸多面锥121,0,0,,0miimiAbba1bAP之中。例如，见上图，位于中，它与中的任意向量都交成锐角；2bAP2b2pP不在中，它就不与中的所有向量交成与交成钝角。锐角或直角，如12,,,maaanp引理4.8（Gordan）设是维向量，使得则不存在向量0,1,2,,Tiapim成立的必要条件是，存在不全为零的非负数12,,,m使得10miiiap0(1,2,,)Tiapim12,,,maaaGordan引理的几何意义：不存在向量使得在几何上表示向量的某一非负线性组合为零向量。例如，在左下图中，取12311,2,2，可使1122330aaa1234,,,,112233440aaaa右下图中，则找不到不全为零的非负数使得。；在*x12(),(),(),,()mfxsxsxsx*x01,,,m定理4.9（Fritz-John）在问题（4.7）中，设是在点处可微。，使得局部最优解，那么，存在不全为零的实数**01*()()0,()0,1,2,,,0,1,2,,.miiiiiifxsxsximim（4.9）*()0(1,2,,)iisxim*()0isx其中称为互补松弛条件。它表明：若iI0i0i*()0isxiI，即，则必有；若，则，即。必有这个定理给出了问题（4.7）的一个最优性必要条件。（4.9）称为问题（4.7）的Fritz-John条件，满足Fritz-John条件的点称为Fritz-John点。（4.9）中的1,,m也称为Lagrange乘子。例4.2考虑约束问题22122121212min(4)(5);..40,480,0,0.xxxstxxxxx*2,3Tx0[4,0]Tx试验证是Fritz-John点，不是Fritz-John点。*2,3Tx{1,2}I解参看例4.1，在点处，。计算***12**34()[4,4],()[1,1],()[1,2],()[1,0],()[0,1].TTTTTfxsxsxsxsx取012341,4,0，则有4**01*41()()40,41()0,1,2,,4.iiiiifxsxsxi这表明*x是Fritz-John点。0[4,0]Tx{1,4}I再考虑点，这时。计算01040()[0,10],()[2,1],()[0,1].TTTfxsxsx根据（4.11），只须说明不存在不全为零的非负数014,,，使得0140200.10110事实上，（4.12）式可写为（4.12）120014100（4.13a）（4.13b）104010由（4.13a）得，而由（4.13b）有，这04和若取非零值，则必异号。一关系表明，这就是说，014,,不可能存在不全为零的非负数使得（4.12）成立，即0x不是Fritz-John点。Fritz-John条件仅是判断容许点是否为最优点的必要条件，而不是充分条件。看下面的例题。例4.3考虑约束问题221231212min(1)(1);..0,0.xxstxxxx(1)，解显然*11[,]22Tx是此问题的唯一最优点。121xx3112()sxxx（1）因为在直线上，约束关于所有容许点的梯度都等于零，所以当取010,0时，总有011()()0,fxsx（4.14）[1,0]T[0,1]T1()0sx如果除去点和点（这两点的起作用约束不止）121xx11[,]22T，那么（4.14）说明在直线其余的容许点都满足Fritz-John条件。但除了其它的点全不是最优点。上，外，（3）Kuhn-Tucker条件首先讨论一个例题