(整理)第2章最优化问题数学基础

1、精品文档精品文档第二章最优化问题数学基础为了便于学习最优化方法，本章将对与优化方法密切相关的数学知识作一简要介绍，而有些数学知识将在讲解各种算法时，随之介绍.§2.1二次型与正定矩阵、二次型与实对称矩阵二次型理论在最优化设计中应用十分广泛.应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题.二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题.推广到n维空间中，二次超曲面的一般方程为f（Xi，X2,，Xn） =anXi2 +a12XX2 +一 + amXiXn用矩阵表示可简记为a2n X2Xn,2an1XnX1an2XnX

2、2annXnn n=工工 aij XiX j 'y jmn nf （Xi, X2,，Xn ） =£ Z aj X Xj =Xi, X2,，Xn Ay j 3XT AX ,X22其中矩阵A的元素aij =aji (i 'J)正是二次型的XiXj项的系数的一半，a"是二次型的Xi项 的系数.因此，二次型和它的矩阵A是相互唯一决定的，且 A = AT .二、正定矩阵定义2.i如果二次型n nf （Xi, X2,，Xn） =£ £ ajXiXj =XTAX对于任何一组不全为零的数i i j dX1> X2>, Xn 恒有MB，Xn）=

3、XTAX,o,非零向量X其值总为正.类似可以给出定义，若二次型f（X1，X2,，Xn） =XTAX 对于所有f（X1,X2,，Xn）=XTAX 之 0 则 A则称"Xi,%,，)正定, 简言之，一个对称矩阵且二次型矩阵 A也称为正定.A如果是正定的，则二次型为半正定矩阵；若 XTAX <0 ,则A为半负定矩阵；若二次型 X T AX既不是半正定又不是半 负定，就称矩阵A为不定的.矩阵A为正定的充要条件是它的行列式 | A |的顺序主子式全部大于零，即a11a12IIIan-a11a12.a21a22IIIa2nan >0,"III，>0a21a22IIII

4、IIHIan1an2IIIann由此可见，正定矩阵必然是非奇异的.4 2 1A= 2 3 0例2.1判断矩阵1 0 2 .是否正定.44 >0,210 =13 >02§2.2 方向导数与梯度一、方向导数所谓方向导数的概念是作为偏导数的一个推广而引入的，它主要研究函数沿任一给定方向的变化率.n1定义2.2设f ： R t R在点X。处可微，P是固定不变的非零向量，e是方向P上的单位向量，则称极限开(X。)f(X0 te) f(X。)二 limcPJ0+t(2.1)开(X0)为函数f(X)在点X0处沿P方向的方向导数，式中 P 是它的记号.定义2.3设f： RnT R1是连续

5、函数，X0三Rn, P- Rn且P#0,若存在6>0, 当tw(0,6)时都有f(X0+tP)<f(X°),则称P为f在点X0处的下降方向.若 f(X0+tP)Af(X0),则称P为f在点X0处的上升方向.由以上两个定义可立刻得到如下的结论：fX2：.0fX2.0若 P ，则f(X)从X0出发在X0附近沿P方向是下降；若 P ，则f(X) 从X0出发在X0附近沿P方向是上升.g：0事实上，若印 ，则当t>0充分小时，根据式(2.1)必有f(X° te) -f(X0) 0t,即f(X)<f(X°),其中X =X0 +te是从X0出发在P方向上

6、的点，说明f(X)是下降的.同理可以说明，若1(0)0P ,则f(X)是上升的.二、梯度定义2.4以f(X)的n个偏导数为分量的向量称为f(X)在X处的梯度，记为"(X)新(X)引X)cf(X)l:X2二 xn梯度也可以称为函数 f(X)关于向量X的一阶导数.以下几个特殊类型函数的梯度公式是常用的：(1)若 f(X) =c (常数)(2) V(bTX)=b.证设 b =b，b2,，bn,则 Vf (X)=O ,即 Vc = O；X = xi, x21，xn ，则是V(bTX)的第j个分量是二 T(b X)Xj所以 V(bTX) =b .(3)RXTX)=2X .(4)若A是对称矩阵，

7、则Q n(Z bxi) =bj, j =1, 2,，n.-：Xj i 1V(XTAX) =2AX三、梯度与方向导数之间的关系定理2.1设f： Rn T R1在点X0处可微，则弩(X0)TecP,其中e是P方向上的单位向量.证明在相应的数学分析中可找到(故略去)由这个定理容易得到下列结论：处的下降方向;处的上升方向.(1)若*(X0)Tp<0,则p的方向是函数f(X)在点X(2)若Vf(X0)Tp0,则P的方向是函数f(X)在点X方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定.绝对 值越大，升降的速度就越快，即=Vf (X0)TeVf(X0)| 118s(Vf(X&#

8、176;), e)0Vf(X0)|上式中的等号当且仅当 e的方向与"f (X0)的方向相同时才成立.由此可得如下重要结论(如图2.1所示)：(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值的最速下降方向.对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向P总是希望它等于或者是靠近于目标函数的负梯度(即一17f (X)的方向，这样才能使函数值下降的最快.22/例2.21式求目标函数f(X)=X1+X2+1在点X。,3处的最速一

9、F降方向，并求沿这个方上再方"彻向移动一个单位长后新点的目标函数值. 解因为2.:x月-3一12XXX1X22 2-这个方向上的单位向量是f (XQ- L)0If故新点是对应目标函数值为Xi - Xo e -_ 2- 2f(Xi)=021=5阳-01Hlf (X)关于X的二阶导数是什么？定义2.5设阶偏导数§2.3海色矩阵及泰勒展式一、海色(Hesse)矩阵前面说过，梯度17f (X)是f (X)关于x的一阶导数，现在要问f ： RnT R1, X。三Rn,如果f在点X。处对于自变量 X的各分量的二都存在，则称函数：2f(X°)：:Xi(i, j =1,2,|M,

10、n)f在点X。处二阶可导，并且称矩阵Fc2f(Xo)V2f(Xo)=-2,X1.2 .二 f ( X o)：X2 ： X1-2 一二 f(X。).：X1：X2.2 .二 f ( X。)-2-X232f(Xo)1CX1CXn一 2 .G f ( X。)：X2：Xn_2 _二 f(X。)明出, 2 _二 f(X。)XnM, 2 _二 f(X。)-2Xn是f在点X。处的Hesse矩阵.在数学分析中已经知道，当产ff在点X。处的所有二阶偏导数为连续时有;：2f比；：Xj ；：Xj fXi因此，在这种情况下 Hesse矩阵是对称的.，i, j =1, 2,，n.43222Hesse矩阵.例 2.3 求目

11、标函数 f(X)=X1 +2x2 +3x3 - x1 x2 +4x2x3 x1x3 的梯度和解因为f 3二4Xi .Xi,：f2=6X22-2x1x2 x3,_=X2 f ：X3=6x3x； +4x3,-4x2 - 2x1x3,4x13 2xiX2-x2所以又因为f (X) = 6x； -x12 +4x3 6x3 +4x2 -2X1X3所以- 2 f f T2X1?f-2X22=12x -2x2)=12 X2 ,12f(X)二- 2 rf f11%;2f>2X3：游3；：2f12x12 -2x22Xi 2x3-2x112x24-2-X3-2x346-2xi= 62xi ,n 、,_ n

12、, 二例2.4设a = R ,X u R力匚R,求线性函数f (X) =aTX b在任意点X处的梯度和解设a=a1，a2；Hesse矩阵.,anT, X =x1, X2,，XnT 则n“为2,，Xn)=£ aixi +b开.xi= ai, i =1, 2,，n ,(2.2)'、f (X) = ai,a2T - ,an - a由式（2.2）进而知；：2f c二0,xi ； Xji, j =1, 2,，n,数 f(X)=.V2f（X） =O（ nMn 阶零矩阵）.例2.5设AW Rn"是对称矩阵，bRn, LR1,求1 TT-X AX b X c2 在任意点处的梯度和

13、Hesse矩阵.解 设 A = (aij)nM, b=bl,b2,，bnT, X=X1,X2,，XnT,则1n nnf(x1, xn)=££ ajxixj+Z bixi + c.2 y j4id将它对各变量xi (i =1，2,，n)求偏导数，得 (X)Cxif(X)=：/ (X)"一Vf (X) = AX +bn工 aijXj +bjanZ anjXj +bnjn£ aijXjjn£ anjXjjbia:bn 一在上式中显然-：Xin=Z aijXj +bi, ji =1,2,，n,再对它们求偏导数得?f=ai, j =1, 2,，n,aii

14、ai2a"2a2ia22a2 nv2f (X);=A Ji A A A A Aanian 2ann .ij，- Xi ： Xj以上例子说明，n元函数求导与一元函数的求导在形式上是一致的,即线性函数的一阶导数为常向量，其二阶导数为零矩阵； 而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵.最后介绍在今后的计算中要用到的向量函数的导数.定义2.6设 H: R= Rm, X°WRn ,记 H(X)刁，(X), MX),，hm(X)T ,如果hi(X) (i =1, 2,，m)在点X0处对于自变量X =Xi, X2,，Xn的各分量的偏导数：hi(Xo)Xj 矩阵(j =i,2,

15、，n)都存在，则称向量函数 H(X)在点Xo处是一阶可导的，并且称"hi(Xo)-h(Xo)m,n H (X0 ) =：Xi:hUXo)III力m(Xo)：:XiX2FhUXo)：X2IH:hm(Xo)；：X2IIIIIIIIIIII力i(Xo) 1二 Xn力2(Xo)区HIWlm(Xo):X是H (X)在点X。处的一阶导数或 Jacobi矩阵，简记为'H(Xo)八 mnH(Xo)ni .由于n兀函数f： R t R的梯度是向量函数物)=产,3CX,cx2CXn -所以17f (X)的一阶导数或Jacobi矩阵为JL幽0迤力的I法/酪&终jiHl III III I-

16、h身修-22XXi川.(臾)_ 一赤戈1、'nn"(X)”:产 f(X)-：Xi %-f (X)-III f(X):Xn ：羌f(X)川HIHIIII£什(宫)智ff(XQ)旅2§Xn三对 f fXX),IIIfX)：v22汉2 1烝&%Xn J/据此，从上式得知，函数梯度的Jacobi矩阵即为此函数的 Hesse矩阵.下面给出今后要用到的几个公式：(1) $C = O ,其中c是分量全为常数的n维向量，。是nMn阶零矩阵.(2) X=I,其中X是n维向量，I是nMn阶单位矩阵.(3) WAX) = A，其中A是mMn阶矩阵.(4)设中= f(X&

17、#176;+tp),其中 f: RnT R1,中：R1t R1,则TT 2中(t) =Vf(X°+tP) P,邛(t) = PV f(X0+tP)P二、泰勒展开式多元函数的泰勒展开在最优化方法中十分重要，许多方法及其收敛性的证明是从它出发的，这里给出泰勒展开定理及其证明.n 1定理2.2设f： R t R具有二阶连续偏导数，则f (X P) -f(X) f(X)TP -PT 2f(X)P2,(2.3)其中X =X +中，而0<1 .证设平代)=£力+正)，于是9(0) = f(X), *(1)=f(X+P).对中(t)按一元函数在t=0点展开，得到1 ：(t)/0)：

18、'(0)t ："(才)t22,其中0 mH <1 .令t =1 ,于是1 (1) = (0)'(0)一"2.(2.4)_ T.T 2 一又因为叫0)=f(X) P,=P V f(X +8P)P，代入式(2.4)中，所以_- T_1_T_ 2 -. _ _f (X P) = f (X) T f (X)T P PTV 2 f (X 1P)P 2.式(2.3)还可以写成f (X P) = f(X) t f(X)TP -PTV 2f (X)P o(| P|2) 2.§2.4极小点的判定条件函数f (X)在局部极小点应满足什么条件？反之，满足什么条件的

19、是局部极小点？这是我们关心的基本问题.下面针对多元函数的情形给出各类极小点的定义.定义2.7对于任意给定的实数0 >0,满足不等式|X -Xo |<6 的X的集合称为点 X0的邻域，记为N(X0, 6)=X| |X -Xo 卜 6,6 >0n1*定义2.8设f ： D - R R ,若存在点X WD和数每A0,VXWN(X，a) I D *、都有f (X ) « f (X ),则称X为f (X)的局部极小点(非严格).n1*定义2.9设f： D± R t R，若存在点X w D和数每A0, VX w N(X，勾 D *、但X #X，都有f (X ) <

20、; f (X ),则称X为f (X)的严格局部极小点.n 1*定义 2.10 设 f： D£R T R ,若存在点 X WD, VXWD 都有 f(X )E f(X), 则称X*为f (X)在D上的全局极小点(非严格).定义2.11设f： D = Rn T R1 ,若存在点 X* w D , VX W D但X = X* ,都有 *、f(X )<f(X),则称X为f(X)在D上的严格全局极小点.由以上定义看到，X*是局部极小点，是指在以X*为中心的一个邻域中f(X)在点X*处 取得最小的值；而X*是全局极小点，是指在定义域 D中f(X)在点X*处取得最小的值.全 局极小点可能在某

21、个局部极小点处取得，也可能在D的边界上取得.实际问题通常是求全局极小点，但是直到目前为止， 最优化中绝大多数方法都是求局部极小点的，解决这一矛盾的一种方法是先求出所有的局部极小点，再求全局极小点.定理2.3设f： D三RnT R1具有连续的一阶偏导数.若 X*是f(X)的局部极小点 并且是D的内点，则f(X )=O.(2.5)证 设e是任意单位向量，因为X*是f(X)的局部极小点，所以存在6>0,当1t|<6 或X +teu N(X , 6)时总有 _ * . . _ *f(X +te) 2 f (X ).(2.6)*引入辅助一元函数中=f (X +，此时，由式(2.6)得中之中.

22、又因X是D的 内点，所以与它对应的t =0是中的局部极小点.又根据一元函数极小点的必要条件，得* T*到中=0 ,即Wf (X ) e = 0 .再由单位向量e的任意性得Vf (X ) = O .*T这里条件(2.5)仅仅是必要的，而不是充分的.例如f (x1, x2)=x1x2在点X -0, 0 T*T处的梯度是Vf =0，0,但X =0, 0是双曲面的鞍点，而不是极小点(如图2.2所示).n1*定义2.12设D U R t R，X是d的内*、点.若Vf (X ) =O ,则称X*为f (X)的驻点.n1定理2.4设f： D三R t R具有连续二阶偏导*、数，X*是D的一个内点.若Vf(X)

23、=°,并且-2*、7 f(X )是正定的，则X *是f (X )的严格局部极小点.2*证 因为 f (X )是正定矩阵，则必存在 九> 0 ,使得对于所有的P w Rn都有PTk 2f(X*)P 一 |P|2图2.2(参看高等代数二次型理论).现在将f(X)在点X*处按泰勒公式展开，并注意到Vf(X ) =O,于是可得_*1*TO_*f(X)-f(X)=2(X-X 12f(X )(X-X) o(l1X-X 12)-|X -X*|2 o(|X -X* |2).当X充分接近 X* (但X ¥X* )时，上式左端的符号取决于右端第一项，因此 _ _ *一般说来，这个定理仅具

24、有理论意义.它的正定性就更难判定了.定理2.5若多元函数在其极小点处的 等值面近似地呈现为同心椭球面簇.证 设X *是多元函数的极小点，并设 *因为对于复杂的目标函数，Hesse矩阵不易求得,Hesse矩阵是正定的，则它在这个极小点附近的f (X)='是充分靠近极小点 X*的一个等值面,即|X-X H充分小.把f(X)在X*点展成泰勒公式，即 * t*f (X) = f (X ) Y f (X ) (X - X )f(X)>f(X ).1* T . 0 -*9+ (X -X )TV2f (X )(X - X ) +o(|X -X |2).2*、右端第二项因X*是极小点有7f (X

25、 )=O而消失.如果略去第 4项，那么1f(X) ： f (X ) -(X -X 严 2 f (X )(X -X )2,又因为f (X) = 丫，所以f (X*) +1(X X*)TV2f (X*)(X X*)之¥,2(2.7)(X -X*)TV2f(X*)(X X*)之2(>f(X*) =c (c为常数).2*按假设V f(X )正定，由二次型理论知式(2.7)是以X*为中心的椭球面方程.§2.5锥、凸集、凸锥在本节中，给出n维Euclid空间Rn中的锥、凸集和凸锥的定义，以及与其相关的一些 概念和性质.一、定义与简单性质定义2.13集合C uRn .若VX三C及任

26、意的数0>0,均有九X乏C ,则称C为锥.定义2.14 设X1，X2,，Xl是Rn中的i个已知点.若对于某点 xwRn存在常数 ll' 'i =1 x = " 'iXi九 1,他,九之0且i 使得 i ，则称X是X1, X2, ,Xl的凸组合,若 lc "'i = 14, ，2,薪>0且i,则称X是X1, X2， ，Xl的严格凸组合.定义2.15集合CuRn .若卡X1 WC和/X2W C，以及任意的数人W 0 ,们，均有 X1 （1-）X2 C,则称C为凸集.定义2.16设aWRn且a#0, bw R1 ,则集合X | aTX

27、>b, X e Rn称为Rn中的 半空间.特别地，规定空集是凸集.容易验证，空间 Rn、半空间、超平面、直线、点、球都是 凸集.定理2.6任意一组凸集的交仍然是凸集.C = C证设 i i,其中1是弓的下标集，Ci都是凸集.任取X1，X2=C,则对于任意"I都是X1, X21i .任取W且兀+乂=1 ,因Ci是凸集，有 ，乂 . , V p 1X1 ' '2X2 ,: Ci CA1X1+A2X2 -Ci.于是归，即C是凸集.若集合C为锥，C又为凸集，则称 C为凸锥.若C为凸集，也为闭集，则称 C为闭凸 集.若C为凸锥，也为闭集，则称 C为闭凸锥.由数学归纳法不难

28、证明如下的定理2.7和2.8.定理2.7 集合C为凸集的充分必要条件是"产C ,及任意数、之0 kki - 1 二.上i Xi C（1=1,2，k，k “）,以 ，有 y,定理2.8集合C为凸锥的充分必要条件是藜Xi三C ,及任意数Zi -0（i =1, 2,，k, k >2）,均有 k v iXi C定义2.17有限个半空间的交X 1Ax ±b称为多面集，其中 A为mMn矩阵，b为 m维向量.例2.6集合S =X x1+2x2 M4,x1 - x2 M1, x1, x2 叫为多面集，其几何表示如图2.3画斜线部分.在多面集的表达式中，若b = 0,则多面集 X 1A

29、x <0也是凸锥，称为多面锥.在有关凸集的理论及应用中，极点和极方向的概念 有着重要作用.定义2.18设C为非空凸集，X w C ,若x不 能表示成C中两个不同点的凸组合；换言之，若假设 X=ZXi 十(1九)X2,九w(0,1), Xi, X2WC,必推得 X =X1 =X2,则称X是凸集C的极点.按此定义，图2.4 (a)中多边形的顶点X1，X2，X3, 是极点.图2.4(b)中圆周上的点均为极点.由图2.4可以看出，在给定的两个凸集中，任何一点 都能表示成极点的凸组合.定义2.19设C为Rn中的闭凸集，P为非零向量， 如果对C 中的每一个X , 都有射线 X +7P?l>0C

30、 ,则称向量p为C的方向.又设P 和H是C的两个方向，若对任何正数九，有R # KP2 ,则称p和p2是两个不同的方向.若C的方向P不能表示图2.3X4和X5是极点，而 X6和X7不成该集合的两个不同方向的正的线性组合，则称P为C的极方向.例2.7如图2.5所示，对于集合C = X1 泾X2 至 xj凡是与向量0,1T夹角小于或等于 45二的向量，都是它的方向.1,1T和-1,1T是C的两个极方向.C的其它方向都能表示成这两个极方向的正线性组合.例2.8设C =X AX也X *为非空集合，p是非零向量.证明P为C的方向的充要条件是 P20且AP =0证 按照定义2.19, P为C的方向的充要条

31、件是对每一个X 十九P九至0仁C根据集合C的定义，由式(2.8)可得A(X + KP) = b ,图2.5X w C ,有(2.(8)(2.(9)X +KP 2 0 .(2.10)由于AX = b, X之0及九可取任意非负数，因此由式(2.9)和式(2.10)知AP = 0对于有界多面集，它的每一个点可用极点的凸组合来表示，反之，由极点的凸组合表 示的点一定属于这个多面集.对此可简要说明如下：设有多面集C=X AX W,如图2.6(a)所示.若X乏C ,则X = X1 (1-)Y=X1 (1 -')X4 (1 -)X3=X1 (1 -'尸X4 ( )(1 -)X3,其中儿,(1

32、Q2,(1 -Q(12)均为非负数,且儿+(1_.)2+(1K)(1 2)=1,即X为极点X1 , X3和X4的凸组合.反之，设55X 八 iXi V i =10, y，儿i 兰0,5AX 八iAXi <b则 一，即X wC.,只用极点来表示是如果多面集是无界的，那么对于该多面集中的任一点(极点除外)不行的，还需要用极方向.如图2.6(b)所示，这时有X = X1 (1 - )X3 - JP1其中九是(。中某个数，N是某一个非负数.图2.6概括起来，有下列定理：定理 2.9 设 C =X AX =b，X -0为非空多面集，则有C有界.若C无界，则存在有限个极方向(1)极点集非空，且存在有

33、限个极点X1, X2,，Xk-(2)极方向集合为空集的充要条件是P，F2,，P.(3) X w C的充要条件是klX =、，jX j 一二, j Pjj 1j 1其中k.二.兀 j= 1j 1% >0(j =1,21，k)方 >0(j =12，l)关于上述定理的证明参见参考文献6.二、凸集分离定理凸集分离定理是凸分析中最重要的定理之一，它在最优化理论和模型当中具有重要的应用.所谓集合的分离是指对于两个集合 Ci和C2存在一个超平面 H,使得Ci在H的一边， 而C2在H的另一边.如果超平面方程为 PTX 5 ,那么对位于 H某一边的点必有 PTX之口，而对位于H另一边的必有 PTX

34、<« .定义2.20设Ci和C2是Rn中的两个非空集合，H=X|P X=叼是超平面，若 对于每一个X三Ci都有PTX之口，对于每一个X三C2都有PTX(或情况恰好相反)， 则称超平面H分离集合Ci和C2.定理2.10若C为闭凸集，X0 5 C，则存在a w Rn , a#0 ,以及数a运R1 ,对yX e C , 有a X >a > a X0,并且存在Xi三C，使得a Xi =a定理2.11设C为凸集，Xo乏C ,则存在aw Rna#。，使得vx WC ,有aTX 之 aTX0定理2.12设C为闭凸集，则C可表为所有包含 C的半空间的交，即C = 1 X |aTX

35、_ ： 其中L = «Rn卡XaTX 至0( nC, a*0上述定理的证明过程参见参考文献6.文6 凸函数一、各类凸函数定义及性质设函数f(X)定义在凸集C上，其中X =X1,X2，Xn .定义2.21若存在常数a >0，使得VX1, X2-C,以及 找w(0,1),若有 f ( X1(1 - )X2) _ f (X1) (1 - )f (X2) -(1 - ) | X1 - X2 |2则称f(X)为一致凸函数；若有f (1X1 +(1 -X)X2)<Xf (X1) + (1-1)f(X2),则称f(X)为严格凸函数；若有f(KX1 +(1-九)X2)W f(X1) +

36、(1-九)f(X2)则称f(X)为凸函数.定义2.22设f(X)为可微函数.若VX1, X2WC,当'、 f(X2)T(X1 -X2) - 0都有f(X”f(X2)则称f(X)为伪凸函数.定义 2.23 对VX1, X2",且 f(X1)#f(X2),以及 a0,1),若f (人X1 +(1-K)X2)(maX f(X) f(X2),则称f(X)为严格拟凸函数；定义2.24对VXn X2C,以及410,1),若f (九X1 +(1-K)X2) WmaX f(X) f(X2),则称f(X)为拟凸函数；定义 2.25 对 VX1, X2C,且 X-X2,以及 V/(0,1),若f

37、( X1 (1- )X2) ； max f(X) f(X2),则称f(X)为强拟凸函数.定理2.13若f(X)为一致凸函数，则 f(X)为严格凸函数.证：设f (X)为一致凸函数，则 ”,X2 e C , X1 # X2 ,及 W 9G ,有 2f( X1 (1 - -)X2) < f(X1) (1 - - ) f(X2) -： (1 - ) | X1 - X2 |<kf(Xl)+(1-k)f(X2), 即”*)为严格凸函数.定理2.14若f(X)为严格凸函数，则 f(X)为凸函数.定理2.15设f(X)为可微函数.若f(X)为凸函数，则f(X)为伪凸函数.定理2.16设f(X)为

38、伪凸函数，则f(X)为严格拟凸函数.定理2.17设f(X)为下半连续的严格拟凸函数，则f(X)为拟凸函数.定理2.18若f(X)为严格凸函数，则 f(X)为强拟凸函数.定理2.19设f(X)为强拟凸函数，则 f(X)为严格拟凸函数.下半连续的定义及定理 2.14一定理2.19的证明过程参见参考文献6.上述几种凸函数 有图2.7所示的关系.一致凸严格凸一*凸伪凸严格想西加I凸.强搜凸-<* >表示当H乃 为可徽;(*)表示当/ 为下半连绫铤数图2.7凸函数与凸集之间有如下关系： n1定理2.20设f： CG R T R ,其中C为非空凸集.若f是凸函数，则对于任意实数P,水平集Dp=

39、X|f(X)EP, XW6是凸集.证若DP是空集，则DP是凸集.以下设DP非空，任取Xi，X2 * DP ,则 f(XJ MP, f(X2)EP .设%, %10,1)且%+%=1,由 f 是凸函数知f1X +ot2X2)Wa1f(X1)+o(2f(X2)Mo(1P +a2P = P ,即。二1 +c(2X2三Dp所以DP是凸集.判定一个函数是否为凸函数，一般说来是比较困难，但当函数可微时， 有如下几个定理可供使用. n1定理2.21设f： CG R T R是可微函数，其中 C为凸集.则(1) f为凸函数的充要条件是 VXi, X2 w C ,都有f(X2).f(X1)+Vf(X1)T(X2

40、X1)；(2.11)(2) f为严格凸函数的充要条件是 VXi, X2 W C ,且Xi ¥ X2 ,都有f(X2)- f(X1)+Vf(X1)T(X2 Xi)证 (1)先证必要性 .已知f是C上的凸函数，要证式(2.11).由凸函数定义知， 对满足% +% =1的任意数%, % w (0,1)都有f(%X1+%X2) W%f(X1)+%f(X2),令4,则% =1 t .代入上式中，经移项可得f(X1 t(X2-X1)-f(X1).： - f (X2) - T (X1)t.(2.12)令tT 0,由f的可微性，利用一阶泰勒展式、方向导数定义及式(2.12),可得Vf(Xi)T(X2

41、 Xi) 4f(X2) f(Xi).这就证明了式(2.11).再证充分性.任取一对数 %，口2 W (0，1)且% +。2 =1.考虑点X =QiXi +5X2, 根据充分性假设，应有f(Xi)>f(X)+Vf (X)T(Xi-X)f (X2) - f (X) f (X)T(X2 -X)两式分别乘以1ai和口2后相加，得到>f (Xi)+.= 2f (X2) _ f (X) If (X)T(二 iXi H/S2X2 -X)=f (： iXi )2X2)由凸函数定义知，f是C上的凸函数.(2)充分性可依照(D的充分性证得，下证必要性.因为严格凸函数本身是凸函数，所以VXi, X2 W

42、 C ,且Xi =X2 ,都有f(X2)- f(Xi) Vf(Xi)T(X2-Xi)(2.(12)(2.(13)以下证明式中只能取“ >”号.假设存在Xi, X2 W C ,且Xi #X2 ,使得 f(X2) = f(Xi)+Vf(Xi)T(X2-Xi).取X3 =(Xi *X2)/2 ,由f的严格凸性，有 i i f(X3) <-f(Xi) - f(X2)22.把式(2.i2)代入式(2.i3)中，经整理得f(X3):二 f (Xi)l f(Xi)T(X3 -Xi)根据本定理(i)部分结论得知，此式与f是凸函数相矛盾.ni定理2.22设f： C三R t R是二次可微函数，C为非空

43、开凸集，则 f为C上凸函2数的充要条件是 Hesse矩阵7 f (X)在C上任意点均半正定.证明略.n i定理2.23设f： C三R t R是二次可微函数，C为非空凸集.若 Hesse矩阵在C 上任意点均正定，则 f在C上为严格凸函数.证明略，需要注意，该定理的逆命题不真.422例如f(x)=x在R上为严格凸函数，但是它的Hesse矩阵"f(x)=i2x在点x = 0处是半正定的.二、凸规划定义2.26设f ： C三Rn t N ,其中c是非空凸集，f是凸函数，则形式为 miCf(X) 的问题称为凸规划问题.更进一步，设C =X |gi(X)之0, i =i,2,，l; hj(X)

44、= 0, j =i,2,，m; XW Rn,若_g，_g2,，_gl都是Rn上的凸函数，几，h2,，hm都是Rn上的线性函数，则容易验证 C是凸集.事实上，因为一5，一g2,，一gi都是凸函数，根据定理2.20集合 Ci =X | -gi(X) w0, X三Rn,i f2,，1也都是凸集.此外，超平面 Pj =X | hj (X) =o, X 匚 R , j =1, 2, ，m ,也都是凸集.显然，C 是 Ci，5,，G, P1, P2,，pm的交集，根据定理 2.6, C是凸集.于是，在这种情况下凸规划问题又可表示成如下形式:min f(X),Igi(X)之0, i =1,2,H|,l, s

45、. t.Q(X)=0, j =1, 2 H|,m.如下定理指明凸规划的一个重要性质.定理2.24设X是凸规划问题的局部极小点，(1)若f是凸函数，则X*是凸规划问题全局极小点；(2)若f是严格凸函数，则 X*是凸规划问题的唯一全局极小点.*.证(1)使用反证法.假设X不是全局极小点，则必存在Z W C使得f (Z) < f (X ).对 *于Z与X*的任意凸组合X=%Z+a2X，其中%, 0(2 U (0,。且%十口2 =1,根据f的凸性，有* *f(X) = f (： 1Z ： 2X ) < 二 1f (Z) ： 2f (X )* * *:二：1f (X )七2 f (X ) =

46、 f (X )* .由此看到，当叫 A0充分小时，X充分接近X ,注意到此时也有f(X)< f(X ),而这*.与X是局部极小点相矛盾.因此 X必是全局极小点._*.(2)假设X不是唯一全局极小点.必存在X w c但XX*使得f (X ) = f (X ).考11*-由 f 的严格凸性， 有X X X c虑中点 22.11 *f(X) = f(2X2X )1.1.*.*.此式与X为全局极小点相矛/(X) 5f(X) = f(X)盾.这就证明了唯一性.定义2.27形式为1 TTf (X) = X AX b X c(2.14)2的函数称为n元二次函数,这里的A是对称矩阵，即 若A为正定，则称

47、(其中&1弘a"bla=a21a22a2 n,b =b2aaman2ann_1 1bn 一,aj = a ji2.14)为正定二次函数.注意到 V2f(X) = A,由定理2.23知,正定二次函数是严格凸函数，在最优化算法构造中它起着特殊的作用.定义2.28形式为1 min f (X) XtAX bTX c, 2(2.15),QX 至 P,s.t./HX =d的问题称为二次规划问题，其中Q是m父n矩阵，H是l Mn矩阵.若A为半正定或正定，则称(2.15)为二次凸规划问题.本书不作专门讨论. 解.§2.7约束问题的最优性条件所谓最优性条件就是最优化问题的目标函数与约

48、束函数在最优点处满足的充要条件.这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的.最优性必要条件是指在最优点处满足哪些条件； 充分条件是指满足哪些条件的点是最优点. 本节仅讲述最 基本的结论.一、约束最优解对约束优化问题的求解，其目的是在由约束条件所规定的可行域D内，寻求一个目标*函数值最小的点 X*及其函数值f(X ).这样的解(X , f(X D称为约束最优解.约束最优点除了可能落在可行域 D内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同.(一)约束优化问题的类型约束优化问题根据约束条件类型的不同分为三种，其数学模型如下：

49、(1)不等式约束优化问题(IP型)min f (X),(2.16)s.t. gi(X)>0),i=1,2J|J.(2)等式约束优化问题(EP型)min f(X),s.t. hj(X) = 0, j =1,2,11,m.(3) 一般约束优化问题(GP型)min f(X),lgi(X)>0,i =1,2,川,l,s.t.hj(X) = 0,j=1,2JH,m.(二)约束优化问题的局部解与全局解按一般约束优化问题，其可行域为D =X |gi(X)>0, i=1,2,，l; hj(X) = 0, j=1,2,，m* .若对某可行点 X存在6 A 0,当X与它邻域的点 X之距离|X -

50、X |K名时，总有*.f(X ) < f(X)则称X为该约束优化问题的一个局部最优解.下面以一个简单例子说明.设有min f(X) = (x1 7)2 x2,s. t.&X)=X2+2 之0, 白(X) =(x1 -2)2 -x2 -9 = 0.该问题的几何图形如图 2.8所示.从图上的目标函数等值线和不等式约束与等式约束的函数曲*T *T*线可写出它的两个局部最优解X1 =-1,0，X2 =5, 0 .这是因为在X1点邻域的任一满*足约束的点X ,都有f (X) > f (X1 )；同理，X2亦然.图2.8对某些约束优化问题，局部解可能有多个.在所有的局部最优解中，目标函

51、数值最小 的那个解称为全局最优解. *在上例中，由于f (X1 ) =4 f (X2) =16,所以全局最优解为(X1, f (X1) .由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解.这与无约束优化问题是相同的.二、约束优化问题局部解的一阶必要条件对于约束，现在进一步阐明起作用约束与不起作用约束的概念.一般的约束优化问题，其约束包含不等式约束 gi(X)*0, i=1,2L/ 和等式约束 hj(X) =0, j =1,2,，m ,在可行点Xk处，如果有gi(Xk) =0 ,则该约束gi(X)称可行 点Xk的起作用约束；而如果有 gi(Xk)A°,则该约束gi(X)

52、称可行点Xk的不起作用约 束.对于等式约束hj(X) =° ,显然在任意可行点处的等式约束都是起作用约束.在某个可行点 Xk处，起作用约束在 Xk的邻域内起到限制可行域范围的作用，而不起 作用约束在Xk处的邻域内就不产生影响.因此，应把注意力集中在起作用约束上.(一)IP型约束问题的一阶必要条件图2.9所示为具有三个不等式约束的二维最优化问题.图2.9图2.9 (a)是最优点X在可行域内部的一种情况.在此种情形下，X点的全部约束*函数值gi(X )均大于零(i =1, 2, 3),所以这组约束条件对其最优点X*都不起作用.换句、一、一 " 一一 ，一* 、 ， 一一 ， &

53、quot;.一 、_, * _ _ *话说，如果除掉全部约束，其最优点也仍是同一个X点.因此这种约束优化问题与无约束优化问题是等价的.图 2.9 (b)所示的约束最优点 X*在g1(X)的边界曲线与目标函数等值 *线的切点处.此时，g1(X ) =0 g2(X )>0，g3(X )>0 ,所以g1(X)是起作用约束， 而其余的两个是不起作用约束.既然约束最优点X*是目标函数等值线与g1(X) 边界的切点，则在 X*点处目标函数的 *梯度vf(X )与约束函数梯度矢量7g1(X )必共线，而且方向一致.若取非负乘子心之0, *则在X处存在如下关系_ * 一 *Vf(X )-W(X )=0.另一种情况如图2.9 (c)所示.当前迭代点 Xk在两约束交点上，