最优化问题数学基础.ppt

《最优化问题数学基础.ppt》由会员分享，可在线阅读，更多相关《最优化问题数学基础.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于最优化问题数学基础现在学习的是第1页，共67页1.1 二次型与正定矩阵一、二次型与实对称矩阵二次型理论在最优化设计中应用十分广泛应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题推广到n维空间中，二次超曲面的一般方程为现在学习的是第2页，共67页，ninjjiijnnnnnnnnnnnnxxaxaxxaxxaxxaxaxxaxxaxxaxaxxxf11222112222221221112112211121)(现在学习的是第3页，共67页用矩阵表示为其中，矩阵A的元素正是二次型的

2、项的系数的一半，是二次型的项的系数因此，二次型和它的矩阵A是相互唯一决定的，且，AXXxxxAxxxxxaxxxfTninjnnjiijn11212121)()(jiaajiijjixxiia2ixTAA 现在学习的是第4页，共67页 二、正定矩阵 定义2.1 如果二次型 对于任何一组不全为零的数恒有 则称正定，且二次型矩阵A也称为正定 简言之，一个对称矩阵A如果是正定的，则二次型 对于所有非零向量X其值总为正类似可以给出定义，若二次型 则A为半正定矩阵；若，则A为半负定矩阵；若二次型既不是半正定又不是半负定，就称矩阵A为不定的ninjTjiijnAXXxxaxxxf1121)(，nxxx，2

3、10)(21AXXxxxfTn，)(21nxxxf，)(21nxxxf，AXXT0)(21AXXxxxfTn，0AXXT现在学习的是第5页，共67页矩阵A为正定的充要条件是它的行列式的顺序主子式全部大于零，即由此可见，正定矩阵必然是非奇异的例2.1 判断矩阵 是否正定解 ，A是正定的1112121222111211212212000nnnnnnaaaaaaaaaaaaaa，201032124A42142408023013023102，现在学习的是第6页，共67页 一、方向导数 所谓方向导数的概念是作为偏导数的一个推广而引入，它主要研究函数沿任一给定方向的变化率 定义2.2 设 在点 处可微，P

4、是固定不变的非零向量，是方向P上的单位向量，则称极限 (2.1)为函数 在点 处沿P方向的方向导数，式中 是它的记号2.2 方向导数与梯度1:RRfn0XetXfteXfPXft)()(lim)(0000)(Xf0XPXf)(0现在学习的是第7页，共67页定义2.3 设 是连续函数，且 ，若存在 ，当 时都有，则称P为在点处的下降方 向若 ，则称P为在点处的上升方向 由以上两个定义可立刻得到如下的结论：若 ，则 从 出发在 附近沿P方向是下降；若 ，则从出发在附近沿P方向是上升1:RRfn0X0P0),0(t)()(00XftPXf)()(00XftPXf0)(0PXf)(Xf0X0X0)(0

5、PXf现在学习的是第8页，共67页二、梯度定义2.4 以 的n个偏导数为分量的向量称为 在X处的梯度，记为 梯度也可以称为函数 关于向量 的一阶导数以下几个特殊类型函数的梯度公式是常用的：（1）若 （常数），则 ，即 ；（2）证 设 ，则于是 的第 个分量是所以（3）（4）若Q是对称矩阵，则)(Xf)(Xf12()()()()Tnf Xf Xf Xf Xxxx，)(XfXcXf)(0)(Xf0cbXbT)(1212TTnnbb bbXx xx，niiiTxbXb1)(XbTj1()()1 2nTiijijjb Xb xbjnxx，bXbT)(XXXT2)(QXQXXT2)(现在学习的是第9页，

6、共67页 三、梯度与方向导数之间的关系 定理2.1 设 在点 处可微，则 ，其中 是 方向上的单位向量.由这个定理容易得到下列结论：(1)若 ，则P的方向是函数在点 处的下降方向；(2)若 ，则 的方向是函数在点 处的上升方向 方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定绝对值越大，升降的速度就越快，即 1:RRfn0XeXfPXfT)()(00eP0)(0PXfT0)(0PXfT0X0XP现在学习的是第10页，共67页 =1 上式中的等号，当且仅当的方向与的方向相同时才成立由此可得如下重要结论(如图2.1所示）：(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯

7、度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值最速下降方向 00()()Tf Xf XeP 0()f X00(cos(),)()f Xef X 1 现在学习的是第11页，共67页 对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向总是希望它等于或者是靠近于目标函数的负梯度-图2.1的方向，这样才能使函数值下降的最快现在学习的是第12页，共67页 例2.2 试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长后新点的目标函数值 解解 因为 所以最速下降方向是 =这个方向上的单位向

8、量是 故新点是 对应目标函数值为 112fxx222fxx0()f X12102322xxxx06000()1()f Xef X10000312XXe 221()0215f X现在学习的是第13页，共67页2.3 海色矩阵及泰勒展式 一、海色（Hesse）矩阵 前面说过，梯度 是 关于 的一阶导数，现在要问 关于 的二阶导数是什么？定义 2.5 设：:，如果在点 处对于自变量的各分量的二阶偏导数 都存在，则称函数在点处二阶可导，并且称矩阵()f X()f XX()f XXf1RRnnRX 00X现在学习的是第14页，共67页 是 在点 处的Hesse矩阵 在数学分析中已经知道，当 在点 处的所

9、有二阶偏导数为连续时有 因此，在这种情况下Hesse矩阵是对称的 222000211212220002202122222000212()()()()()()()()()()nnnnnf Xf Xf Xxx xx xf Xf Xf Xf Xxxxxxf Xf Xf Xxxxxx f0Xf0X2200()()1 2ijjif Xf Xi jnx xx x ，现在学习的是第15页，共67页例2.3 求目标函数 的梯度和Hesse矩阵解 因为 所以23132221233241432)(xxxxxxxxxXf232131124xxxxxf32122246xxxxf31233246xxxxxf312332

10、1222321312464624)(xxxxxxxxxxxXf现在学习的是第16页，共67页又因为所以 22221213211213222212222331222212462fffxxxxxx xx xfffxxxx xx ，13213122122642412222212)(xxxxxxxxXf现在学习的是第17页，共67页例2.4 设 ，求线性函数在任意点X处的梯度和Hesse矩阵解:设 ,则 （2.2）由式（2.2）进而知 （阶零矩阵）1,RbRXRannbXaXfT)(1212TTnnaa aaXx xx，121()nniiif x xxa xb，1 2iifainx，aaaaXfTn,

11、)(21201 2ijfi jnx x，OXf)(2现在学习的是第18页，共67页例2.5 设 是对称矩阵，求二次函数 在任意点处的梯度和Hesse矩阵解 设 则将它对各变量 求偏导数，得 nnRa1RcRbn，()f X 12TTX AXb Xc1212()TTijn nnnAaXx xxbb bb，121111()2nnnnijijiiijif xxxa x xb xc，(1 2)ix in，111111111()()()nnjjjjjjnnnnjjnnjjjjnf Xa xba xxbf Xf Xba xba xxbAXXf)(现在学习的是第19页，共67页在上式中显然再对它们求偏导数得

12、 以上例子说明，元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵 最后介绍在今后的计算中要用到的向量函数的导数1()1 2nijjijif Xa xbinx，2()1 2ijijf Xai jnx x，AaaaaaaaaaXfnnnnnn2122221112112)(现在学习的是第20页，共67页定义2.6 设 ，记 如果 在点 处于自变量 的各分量的偏导数 都存在，则称向量函数 在点 处是一阶可导的，并且称矩阵1010101220202012000012()()()()()()()()()()n

13、nm nmmmnh Xh Xh Xxxxh Xh Xh XxxxH XhXhXhXxxxnmnRXRRH0，：1()()()TmH Xh XhX，(1 2)ih im，0XTnxxxX,210()(1 2)ijhXjnx，)(XH0X现在学习的是第21页，共67页是在点处的一阶导数或Jacobi矩阵，简记为 由于n元函数 的梯度是向量函数所以 的一阶导数或Jacobi矩阵为00()()m nH XH X 1RRfn：1()()()Tnf Xf Xf Xxx，)(Xf112111222212()()()()()()()()()()nn nnnnnnf Xf Xf Xxxxxxxf Xf Xf X

14、f Xxxxxxxf Xf Xf Xxxxxxx 22221121222222122222212()()()()()()()()()()nnnnnf Xf Xf Xxx xx xf Xf Xf Xf Xxxxxxf Xf Xf Xxxxxx ，现在学习的是第22页，共67页 得到112111222212()()()()()()()()()()nn nnnnnnf Xf Xf Xxxxxxxf Xf Xf Xf Xxxxxxxf Xf Xf Xxxxxxx 22221121222222122222212()()()()()()()()()()nnnnnf Xf Xf Xxx xx xf Xf X

15、f Xf Xxxxxxf Xf Xf Xxxxxx ，)()(2XfXfnn现在学习的是第23页，共67页据此，从上式得知，函数梯度的Jacobi矩阵即为此函数的Hesse矩阵下面给出今后要用到的几个公式：（1），其中 是分量全为常数的 维向量，是 阶零矩阵（2），其中 是维向量，是 阶单位矩阵（3），其中 是 阶矩阵（4）设 ，其中 ，则Oc cnOnnIX XInn()AXAAnm)()(0tPXft111nfRRRR：，：PtPXfPtPtPXftTT)()(,)()(020 现在学习的是第24页，共67页二、泰勒展开式多元函数的泰勒展开在最优化方法中十分重要，许多方法及其收敛性的证明是

16、从它出发，这里给出泰勒展开定理及其证明 定理2.2 设 具有二阶连续偏导数，则 （2.3）其中 ，而 证 设 ，于是对 按一元函数在 点展开，得到其中 令 ，于是 (2.4)1RRfn：PXfPPXfXfPXfTT)(21)()()(2PXX10)()(tPXft(0)()(1)()f Xf X P，)(t0t2)(21)0()0()(tttt 101t)(21)0()0()1(现在学习的是第25页，共67页又因为代入式（2.4）中，所以 式（2.3）还可以写成 2(0)()()()TTf XPPf XP P ，PPXfPPXfXfPXfTT)(21)()()(2)|(|)(21)()()(2

17、2PoPXfPPXfXfPXfTT现在学习的是第26页，共67页2.4 极小点的判定条件函数在局部极小点应满足什么条件？反之，满足什么条件的是局部极小点？这是我们关心的基本问题下面针对多元函数的情形给出各类极小点的定义定义2.7 对于任意给定的实数 ，满足不等式 集合称为点的邻域，记为定义2.8 设 ，若存在点 和数 ，都有 ，则称 为 局部极小点（非严格）0|0XX0,|),(00XXXXN1RRDfn：DX*0X*(,)N XD)()(*XfXf*X)(Xf现在学习的是第27页，共67页 定义2.9 设 ，若存在点 和数 ，但 ，都有 ，则称 为 的严格局部极小点 定义2.10 设 ，若存

18、在点 和数 ，都有 ，则称 为 在D上的全局极小点（非严格）定义2.11 设 ，若存在点 ，但 ，都有 ，则称 为 在D上的严格全局极小点1RRDfn：DX*0X*(,)N XD*XX)()(*XfXf*X)(Xf1RRDfn：DX*0DX)()(*XfXf*X)(Xf1RRDfn：DX*DX*XX)()(*XfXf*X)(Xf现在学习的是第28页，共67页 由以上定义看到，是局部极小点，是指在以为中心的一个邻域中在点处取得最小的值；而是全局极小点，是指在定义域D中在点处取得最小的值全局极小点可能在某个局部极小点处取得，也可能在D的边界上取得实际问题通常是求全局极小点，但是直到目前为止，最优化

19、中绝大多数方法都是求局部极小点的，解决这一矛盾的一种方法是先求出所有的局部极小点，再求全局极小点现在学习的是第29页，共67页 定理2.3 设 具有连续的一阶偏导数若 是 的局部极小点并且是D的内点，则 （2.5）证 设 是任意单位向量，因为 是 的局部极小点，所以存在 ，当 或 时总有 （2.6）引入辅助一元函数 ，此时，由式（2.6）得 又因 1RRDfn：*X)(Xf0)(*Xfe*X)(Xf0|t),(*XNteX)()(*XfteXf)()(*teXft)0()(t*X现在学习的是第30页，共67页 是D的内点，所以与它对应的 是 的局部极小点又根据一元函数极小点的必要条件，得到 ，

20、即 再由单位向量 的任意性得 这里条件（2.5）仅仅是必要的，而不是充分的例如 在点 处的梯度是 ，但 是双曲面的鞍点，而不是极小点（如图2.2所示）0t)(t0)0(0)(*eXfTe0)(*Xf2121),(xxxxf*0,0TX Tf0,0)0,0(TX0,0*现在学习的是第31页，共67页 定义2.12 设 是D的内 点若 ，则称 为 的驻点 定理2.4 设 具有连续二阶偏导数，是D的一个内点若 ，并且 是正定的，则 是 的严格局部极小点*1XRRDfn，：0)(*Xf*X)(Xf1RRDfn：*X0)(*Xf)(*2Xf*X)(Xf现在学习的是第32页，共67页 证 因为 是正定矩阵

21、，则必存在 ，使得对于所有的 都有 （参看高等代数二次型理论）现在将 在点 处按泰勒公式展开，并注意到 ，于是可得)(*2Xf0nRP 2*2|)(PPXfPT)(Xf*X0)(*Xf*2*2*2*21()()()()()(|)2|(|)2Tf Xf XXXf XXXoXXXXoXX现在学习的是第33页，共67页 当 充分接近 （但 ）时，上式左端的符号取决于右端第一项，因此 一般说来，这个定理仅具有理论意义因为对于复杂的目标函数，Hesse矩阵不易求得，它的正定性就更难判定了 X*X*XX)()(*XfXf现在学习的是第34页，共67页 定理2.5 若多元函数在其极小点处的Hesse矩阵是正

22、定的，则它在这个极小点附近的等值面近似地呈现为同心椭球面族 证 设 是多元函数的极小点，并设 是充分靠近极小点 的一个等值面，即 充分小把 在点 展成泰勒表达式，即 右端第二项因 是极小点有 而消失如果略去第4项,那么 又因为 ，所以 （2.7）按假设 正定，由二次型理论知式（2.7）是以 为中心的椭球面方程*X)(Xf*X|*XX)(Xf*X*2*2()()()()1()()()(|)2TTf Xf Xf XXXXXf XXXoXX*X0)(*Xf)()(21)()(*2*XXXfXXXfXfT)(Xf*2*1()()()()2Tf XXXf XXX*2*()()()2()()TXXf XX

23、Xf Xc为常数)(*2Xf*X现在学习的是第35页，共67页2.5 锥、凸集、凸锥 在本节中，给出维Euclid空间 中的锥、凸集和凸锥的定义，以及与其相关的一些概念和性质 一、定义与简单性质 定义2.13 集合 若 ，及任意的数 ，均有 ，则称C为锥 定义2.14 设 是 中的 个已知点若对于某点 存在常数 且 使得 ，则称 是 的凸组合若 且 ，则称 是 的严格凸组合nRnRC CX 0CX lXXX，21nRlnRX 120l，lii11liiiXX1XlXXX，21120l，lii11XlXXX，21现在学习的是第36页，共67页 定义2.15 集合 若 和 ，以及任-意的数 ，均有

24、 则称C为凸集 定义2.16 设 且 ，则集合 称为 中的半空间 特别地，规定：空集是凸集容易验证，空间 、半空间、超平面、直线、点、球都是凸集nRC CX 1CX 20 1，12(1)XXCnRa 0a 1Rb|nRXbaXX，nRnR现在学习的是第37页，共67页 定理2.6 任意一组凸集的交仍然是凸集 证 设 ，其中I是 的下标集，都是凸集任取，则对于任意都是任取 且 ，因 是凸集,有 于是 ，即C是凸集 若集合C为锥，C又为凸集，则称C为凸锥若C为凸集，也为闭集，则称C为闭凸集若C为凸锥，也为闭集，则称C为闭凸锥iIiCC iCiCCXX21，121iCiCXX22111122ii I

25、XXCC现在学习的是第38页，共67页 由数学归纳法不难证明如下的定理2.7和2.8 定理2.7 集合C为凸集的充分必要条件是 ，及任意数 （），有 定理2.8 集合C为凸锥的充分必要条件是 ，及任意数 ,()，均有 定义 2.17 有限个半空间的交 称为多面集,其中 为 矩阵，为 向量CXi0i1 22ikk，kii11kiiiCX1CXi0i1 22ik k，1kiiiXCXAXbnmAbm现在学习的是第39页，共67页 例2.6 集合 为多面集，其几何表示如图2.3画斜线部分 图2.3在多面集的表达式中，若 ，则多面集 也是凸锥，称为多面锥 在有关凸集的理论及应用中，极点和极方向的概念有

26、着重要作用0142212121xxxxxxXS，0b 0X AX 现在学习的是第40页，共67页 定义 2.18 设C为非空凸集，,若 不能表示成 C 中两个不同点的凸组合；换言之，若设 ,必推得 ，则称 是凸集 C的极点 按此定义，图2.4(a)中多边形的顶 点 ，和 是极点，而 和 不是极点图2.4(b)中圆周上的点均为极点由图2.4可以看出，在给定的两个凸集中，任何一点都能表示成极点的凸组合CX X12(1)XXX)10(，21XXXX1X2X3X4X5X6X7X现在学习的是第41页，共67页定义 2.19 设C为 中的闭凸集，P为非零向量，如果对C中的每一个 ，都有射线 ，则称向量P为

27、C的方向又设 和 是的两个方向，若对任何正数 ，有 ，则称 和 是两个不同的方向若C的方向P不能表示成该集合的两个不同方向的正的线性组合，则称p为c的极方向nRXCPX01P2P21PP1P2P现在学习的是第42页，共67页 概括起来，有下列定理：定理2.9（Representation Theorem）设 为非空多面集，则有（1）极点集非空，且存在有限个极点（2）极方向集合为空集的充要条件是C有界若无界，则存在有限个极方向（3）的充要条件是 其中0,XbAXXCCX kjljjjjjPXX11kjj11)21(0kjj，)21(0ljj，现在学习的是第43页，共67页 二、凸集分离定理 凸集

28、分离定理是凸分析中最重要的定理之一，它在最优化理论和模型当中具有重要的应用 所谓集合的分离是指对于两个集合C1和C2存在一个超平面H，使得C1在H的一边，而C2在H的另一边如果超平面方程为 ，那么对位于H某一边的点必有 ，而对位于H另一边的必有 定义2.20 设C1和C2是 中的两个非空集合，是超平面，若对于每一个 都有 ，对于每一个 都有 （或情况恰好相反），则称超平面H分离集合C1和C2TP XTP XTP XnR|THX P X1CX TP X2CX TP X现在学习的是第44页，共67页 定理2.10 若C为闭凸集，则存在 以及数 ，对 ，有 并且存在 ，使得 定理2.11 设C为凸集

29、，则存在 使得 ，有 定理2.12 设C为闭凸集，则C可表为所有包含C的半空间的交，即 其中CX 0nRa0a 1RCX 0TTa Xa XCX 11Ta XCX 0nRa0a CX 0XaXaTT|XaXCTLa1|,0nTaLRX a XS a现在学习的是第45页，共67页2.6 凸函数 一、各类凸函数定义及性质 设函数 定义在凸集R上，其中 定义2.21 若存在常数 ，使得 以及 ，有 则称 为一致凸函数；有 则称为严格凸函数；有 则称为凸函数)(Xf12()TnXx xxd，0RXRX21，(0 1)，12(1)fXX22121|)1()()1()(XXXfXf)(Xf)()1()()

30、1(2121XfXfXXf12(1)fXX)()1()(21XfXf现在学习的是第46页，共67页 定义2.22 设 为可微函数若 满足 都有 则称 为伪凸函数 定义2.23 对 ，且 ，以及 ，若 则称为严格拟凸函数；定义2.24 对 ，以及 ，若 则称为拟凸函数；定义2.25 对 则称为强拟凸函数)(XfRXRX21，212()()0Tf XXX1()f X)(2Xf)(XfRXRX21,)()(21XfXf)1,0()(),(max)1(2121XfXfXXfRXRX21,)1,0(12(1)fXX)(),(max21XfXfRXRX21,)(),(max)1(2121XfXfXXf现在

31、学习的是第47页，共67页 定理2.13 若 为一致凸函数，则为严格凸函数 证：设 为一致凸函数，则 ，及 ，有 即为严格凸函数)(Xf)(XfRX 1RX 221XX(0 1)，12(1)fXX22121|)1()()1()(XXXX)()1()(21XXf现在学习的是第48页，共67页 定理2.14 若为严格凸函数，则为凸函数 定理2.15 设为可微函数若为凸函数，则为伪凸函数 定理2.16 设为伪凸函数，则为严格拟凸函数 定理2.17 设为下半连续的严格拟凸函数，则为拟凸函数 定理2.18 若为严格凸函数，则为强拟凸函数 定理2.19 设为强拟凸函数，则为严格拟凸函数现在学习的是第49页

32、，共67页凸函数与凸集之间有如下关系：定理2.20 设 ，其中C为非空凸集若f是凸函数，则对于任意实数 ，水平集 是凸集证 若 是空集，则 是凸集以下设 非空，任取 ，则 设 且 ，由f是凸函数知即 ，所以 是凸集判定一个函数是否为凸函数，一般说来是比较困难，但当函数可微时，有如下几个定理可供使用1:RRCfn,)(|CXXfXDDDDDXX21,)(,)(21XfXf 1,0,21121122112212()()()fXXf Xf X DXX2211D现在学习的是第50页，共67页定理2.21 设 是可微函数，其中C为凸集则（1）为凸函数的充要条件是，都有 （2.11）（2）为严格凸函数的充

33、要条件是，且 都有证 （1）必要性 已知f是C上的凸函数，要证式 （2.11）由凸函数定义知，对满足 的任意数 都有令 ，则 代入上式中，经移项可得1:RRCfnCXX21,)()()()(12112XXXfXfXfTCXX21,21XX)()()()(12112XXXfXfXfT121 1,0,21)()()(22112211XfXfXXft2t11现在学习的是第51页，共67页 （2.12）令 ，由f的可微性，利用一阶泰勒展式、方向导数定义及式（2.12），可得 这就证明了式（2.11）充分性 任取一对数 且 考虑点 ，根据充分性假设，应有)()()()(121121XfXftXfXXtX

34、f0t)()()()(12121XfXfXXXfT120,1，1212211XXX11()()()()Tf Xf Xf XXX22()()()()Tf Xf Xf XXX现在学习的是第52页，共67页 两式分别乘以 和 后相加，得到 由凸函数定义知,f是C上的凸函数（2）充分性可依照（1）的充分性证得 必要性 因为严格凸函数本身是凸函数，所以 且 ,都有 以下证明式中只能取“”号假设存在 ，且 ，使得 （2.12）1211221122()()()()()Tf Xf Xf Xf XXXX1122()fXXCXX21，21XX)()()()(12112XXXfXfXfTCXX21,21XX)()(

35、)()(12112XXXfXfXfT现在学习的是第53页，共67页 取 ，由的严格凸性，有 （2.13）把式（2.12）代入式（2.13）中，经整理得 根据本定理（1）部分结论得知，此式与是凸函数相矛盾 定理2.22 设 是二次可微函数，C为非空开凸集，则f为c上凸函数的充要条件是，Hesse矩阵 在C上到处半正定 证明略2132/12/1XXX)(21)(21)(213XfXfXf)()()()(13113XXXfXfXfT1RRCfn：)(2Xf现在学习的是第54页，共67页 定理2.23 设 是二次可微函数，C为非空凸集若Hesse矩阵在C上到处正定，则f在C上为严格凸函数 证明略，需要

36、注意，该定理的逆命题不真 例如 为严格凸函数，但是它的Hesse矩阵在点x=0处是半正定的 二、凸规划 定义2.26 设 ，其中C是非空凸集，f是凸函数，则形式为 的问题称为凸规划问题4)(xxf1RRCfn：1RRCfn：min()X Cf X现在学习的是第55页，共67页更进一步，设若 都是 上的凸函数，都是 上的线性函数，则容易验证C是凸集事实上，因为 都是凸函数，根据定理2.20集合 也都是凸集此外，超平面 ，也都是凸集显然，C是 的交集，根据定理2.6，C是凸集于是，在这种情况下凸规划问题又可表示成如下形式：|()01 2()01 2nijCX g XilhXjm XR，；，；lgg

37、g，21nRmhhh，21nRlggg，21|()01 2niiCXg XXRil，mjRXXhXPnjj,1,0)(|,11CCmPP,1min()()01 2.()01 2ijf Xg Xils thXjm，现在学习的是第56页，共67页 定理2.24 设 是凸规划问题的局部极小点，（1）若f是凸函数，则 是凸规划问题全局极小点；（2）若f是严格凸函数，则 是凸规划问题的唯一全局极小点 证（1）使用反证法假设 不是全局极小点，则必存在 使得 对于Z与 的任意凸组合 ，其中 且 ，根据的凸性，有 由此看到，当 充分小时，充分接近 ,注意到此时也有 ,而这与 是局部极小点相矛盾因此 必是全局极

38、小点*X*X*X*XCZ*()()f Zf X*X*21XZX12(0 1)，121)()()()(*21*21XfZfXZfXf)()()(*2*1XfXfXf01X*X)()(*XfXf*X*X现在学习的是第57页，共67页（2）假设 不是唯一全局极小点必存在 但 使得 考虑中点 由f的严格凸性，有 此式与 为全局极小点相矛盾这就证明了唯一性 定义2.27 形式为 （2.14）的函数称为n元二次函数，其中*XCX*XX)()(*XfXfCXXX*2121)()(21)(21)2121()(*XfXfXfXXfXf*XCXbQXXXfTT21)(现在学习的是第58页，共67页这里的Q是对称矩

39、阵，即若Q为正定，则称（2.14）为正定二次函数注意到 ，由定理2.23知，正定二次函数是严格凸函数，在最优化算法构造中它起着特殊的作用定义2.28 形式为 （2.15）的问题称为二次规划问题，其中是矩阵，是矩阵若Q为半正定或正定，则称（2.15）为二次凸规划问题本书不作专门讨论 nnnnnnnbbbbqqqqqqqqqQ21212222111211，QXf)(2dCXPAXtscXbQXXXfTT，.21)(min现在学习的是第59页，共67页 2.7约束问题的最优性条件所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件这种条件对于最优化算法的终止判定和最优化理论推证都

40、是至关重要的最优性必要条件是指，在最优点处满足哪些条件；充分条件是指满足哪些条件的点是最优点本节仅讲述最基本的结论一、约束最优解对约束优化问题的求解，其目的是在由约束条件所规定的可行域内，寻求一个目标函数值最小的点及其函数值这样的解称为约束最优解约束最优点除了可能落在可行域内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同现在学习的是第60页，共67页（一）约束优化问题的类型约束优化问题根据约束条件类型的不同分为三种，其数学模型如下：（1）不等式约束优化问题（IP型）（2.16）（2）等式约束优化问题（EP型）（3）一般约束优化问题（GP型）m

41、in(),.()01 2if Xs t g Xil，min().()01 2jf Xs t h Xjm，min()()01 2.()01 2ijf Xg Xils th Xjm，现在学习的是第61页，共67页（二）约束优化问题的局部解与全局解 按一般约束优化问题，其可行域为 若对某可行点 存在 ，当 与它邻域的点 之距离 时，总有 则称 为该约束优化问题的一个局部最优解 下面以一个简单例子说明设有|()01 2()01 2ijDX g Xil h Xjm，；，*X0*XX|*XX)()(*XfXf*X，09)2()(02)(.)1()(min222122221xxXhxXgtsxxXf现在学习

42、的是第62页，共67页 该问题的几何图形如图2.8所示从图上的目标函数等值线和不等式约束与等式约束的函数曲线可写出它的两个局部最优解 ，这是因为在 点邻域的任一满足约束的点 ，都有 同理，亦然TX0,1*1TX0,5*2*1XX)()(*1XfXf*2X现在学习的是第63页，共67页 对某些约束优化问题，局部解可能有多个在所有的局部最优解中，目标函数值最小的那个解称为全局最优解 在上例中，由于，所以全局最优解为 由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解这与无约束优化问题是相同的现在学习的是第64页，共67页 二、约束优化问题局部解的一阶必要条件 对于约束，我们现在进一步

43、阐明起作用约束与不起作用约束的概念一般的约束优化问题，其约束包含不等式约束 和等式约束 ，在可行点 处，如写有 则该约束 称可行点 不起作用约束对于等式约束，显然在一可行点的等式约束 都是起作用约束 在某个可行点 处，起作用约束在 的邻域内起到限制可行域范围的作用，而不起作用约束在 处的邻域内就不产生影响因此，应把注意力集中在起作用约束上liXgi,2,1,0)(mjXhj,2,1,0)(kX0)(kiXg)(XgikX0)(XhjkXkXkX现在学习的是第65页，共67页（一）IP型约束问题的一阶必要条件图2.9所示具有三个不等式约束的二维最优化问题现在学习的是第66页，共67页感谢大家观看感谢大家观看现在学习的是第67页，共67页