最优化方法(凸集与凸函数)

1最优化方法补充内容3凸集与凸函数2凸集与凸函数1.凸集（1）凸组合：已知，nRX任取k个点，Xxi如果存在常数0ia，),,2,1(ki11kiia，使得xxakiii1，则称x为ix),,2,1(ki的凸组合。（2）凸集：设集合nRX，如果X中任意两点的凸组合仍然属于X，则称X为凸集。2.凸函数设RRXfn:，任取Xxx21,，如果1,0,2121iiaaa，有)()())((22112211xfaxfaxaxaf，则称f为X上的（严格）凸函数。例子：2)(xxf3凸集的补充内容设nRD是凸集，则任意m个点),,2,1()(miDxi的凸组合仍属于D，即有：Dximii)(1其中0i，mi,,2,1，11mii先想想思路。。。4设nRD是凸集，则任意m个点),,2,1()(miDxi的凸组合仍属于D，即有：Dximii)(1，其中0i，mi,,2,1，11mii原来凸集的性质告诉我们：任意的两个点的凸组合都属于D。现在让我们证明，任意的m个点的凸组合都属于D。咋办？？两个―――多个两个―――三个―――四个―――多个)2(2)1(1xx―――)3(3)2(2)1(1xxx)2(2)1(1xx―――)3(3)2(2)1(1xxx5设nRD是凸集，则任意m个点),,2,1()(miDxi的凸组合仍属于D，即有：Dximii)(1，其中0i，mi,,2,1，11mii如果能出现)1(3＋)3(3x就好了怎么才能出现呢？？)3(3)2(32)1(313)1()1()1(xxx方框是不是属于D呢？？根据凸集的定义1)1(1)1()1()1(333213231问题解决了。证明怎么写？6设nRD是凸集，则任意m个点),,2,1()(miDxi的凸组合仍属于D，即有：Dximii)(1，其中0i，mi,,2,1，11mii证明：归纳法。1．2m显然成立2．假设km结论成立，我们证明结论在1km时结论也成立以下仅仅列出主要步骤，省去很多说明文字，请大家补充完整。)1(1)(1)(11kkikiiikiixxx)1(1)(111)(111)1(kkikikikikiixxx由于kiik111，即1111kiki由归纳假设有：Dxikiki)(111再由凸集的定义，有Dxxkkikikik)1(1)(1111)1(证明完毕。7凸集分离定义（空间想象一下是咋样地？）设nRDD21,为两个非空凸集，若存在非零向量nRa和实数使得xaRxHDTn|1xaRxHDTn|2则称超平面xaRxHTn|分离了集合1D和2D。如果更有xaRxHDTn|01xaRxHDTn|02则称超平面H严格分离1D和2D，其中0H和0H分别表示H和H的内部8点到凸集的投影设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx先想想思路。。。9设nRD是闭凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx下确界，能否取到？怎么取？连续函数在有界闭集上能够取到极值点，但是闭凸集一定是有界闭集吗？？10DSy如何构造闭凸集？请大家使劲的想。。。。。凸集当然不一定是有界集比如区间0Ax有界集和无界集的交集是什么集？有没有看到闭凸集在哪里？11设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx证明：（1）令1|xRxSn则取充分大的0使得)(SyDDs因此连续函数yxxf)(在sD上必定可以取到极小点存在性证明完毕唯一性的证明数学中的常见技巧假设存在两个不相等的投影，证明矛盾即可12设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx假设存在xxDx~,~，使得xyxy~则由范数的三角不等式有xyxyxyxyxxy~2121~21212~由于D是凸集，故有Dxx2~，又因为是集合D到y的最短距离，上式应有等号成立，因此，存在实数xyxy~13设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx又因为xyxy~则有1当1时，xx~当1时，Dxxy2~，因为Dy所以矛盾。14设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx第（2）问的证明，要证充要条件充分性比较容易，留做作业必要性比较的麻烦我们还是先想想思路。。。15设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，DxDyxx夹角小于90度16设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，DxDyxx夹角小于90度xx)1(证明中要用到一个技巧借助与一个凸组合xx)1(17设nRD是凸集，nRy但是Dy，则（1）存在唯一的点Dx，使得集合D到点y的距离最小，即Dxyxyx,inf（2）Dx是点y到集合D的最短距离点的充分必要条件为0yxxxT，Dx设x是D到y距离的最短距离点，即yxyx，Dx令1,0有Dxxxxx)1()(根据这两个式子我们有xxxyxxyxxxxyyxT2)(22222因此对于任意的1,0即0222xxxyxxT令0便可以得到0xxyxT18凸规划（1）Dxtsxf..)(min其中)(xf是凸函数，D是凸集。（2）)(minxf0)(0)(0)(0)(..11xhxhxgxgtskl其中)(,)(xgxfi是凸函数，)(xhj是线性函数。19水平集：fXxxfxD,,)(|{是凸函数}。性质：水平集一定是凸集。3.凸函数的性质定理.凸函数的局部极小点就是全局极小点。4.凸函数的判断条件定理1.)(xf是凸集X上的凸函数的充要条件是Xxx21,，有)()()()(12112xxxfxfxfT.定理2.设)(xf在凸集X上有二阶连续偏导数，则)(xf是凸函数的充要条件是Xx，有)(2xf半正定。例：正定二次函数cxbAxxxfTT21)(，其中A是正定矩阵。画出图形是什么样子的？