1、1最优化理论与算法2022-12-282提纲1.1.线性规划 对偶定理对偶定理2.2.非线性规划 K-K-T K-K-T 定理定理3.3.组合最优化 算法设计技巧算法设计技巧使用教材：最优化理论与算法最优化理论与算法 陈宝林陈宝林参考书：数学规划数学规划 黄红选，黄红选，韩继业韩继业 清华大学出版社清华大学出版社2022-12-283其他参考书目其他参考书目Nonlinear ProgrammingNonlinear Programming-Theory and AlgorithmsTheory and AlgorithmsMokhtar S.Bazaraa,C.M.ShettyJohn Wi
2、ley&Sons,Inc.1979(2nd Edit,1993，3nd Edit，2006)Linear and Nonlinear ProgrammingLinear and Nonlinear Programming David G.LuenbergerAddison-Wesley Publishing Company,2nd Edition,1984/2003.Convex Analysis R.T.RockafellarPrinceton Landmarks in Mathematics and Physics,1996.Optimization and Nonsmooth Analy
3、sis Frank H.Clarke SIAM,1990.2022-12-284Linear Programming and Network FlowsLinear Programming and Network Flows M.S.Bazaraa,J.J.Jarvis,John Wiley&Sons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性 Combinatorial Combinatorial OptimizationOptimization 蔡茂诚、刘振宏 Algorithms and Complexity Algorithms a
4、nd Complexity 清华大学出版社，1988 Printice-Hall Inc.,1982/1998 其他参考书目其他参考书目2022-12-2851,1,绪论绪论-学科概述学科概述 最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表”模型模型 理论理论 算法算法最优化首先是一种理念最优化首先是一种理念,其次才是一种方法其次才是一种方法.2022-12-286绪论绪论-运筹学（运筹学（Operatio
5、ns Research-Operations Research-OROR）运筹学方法随机过程方法统计学方法最优化/数学规划方法l连续优化：线性规划、连续优化：线性规划、非线性规划、非光滑优非线性规划、非光滑优化、全局优化、变分法、化、全局优化、变分法、二次规划、分式规划等二次规划、分式规划等l 离散优化：组合优化、离散优化：组合优化、网络优化、整数规划网络优化、整数规划等等l几何规划几何规划l动态规划动态规划l不确定规划：随机规不确定规划：随机规划、模糊规划等划、模糊规划等l多目标规划多目标规划l对策论等对策论等l统计决策理论统计决策理论l马氏过程马氏过程l 排队论排队论l更新理论更新理论l仿
6、真方法仿真方法l可靠性理论等可靠性理论等l回归分析回归分析l群分析群分析l模式识别模式识别l实验设计实验设计l因子分析等因子分析等2022-12-287优化树2022-12-288最优化的发展历程最优化的发展历程费马:1638;牛顿,1670min f(x)x:df(x)0dx数欧拉,1755Min f(x1 x2 xn)f(x x)=02022-12-289欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Min f(x1 x2 xn)s.t.gk(x1 x2 xn)=0,k=1,2,m2022-12-28101930年代，康托诺维奇：线性规划1940年代，Dant
7、zig：单纯形方法，冯 诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展 电子计算机-最优化2022-12-2811最优化应用举例 具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等.制造业：钢铁生产，车间调度等 医药生产，化工处理等 电子工程，集成
8、电路VLSI etc.排版（TEX,Latex,etc.）2022-12-28121.1.食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低限度的维生素需求量。2022-12-28131.1.食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。
9、求最优安排或计划的问题，称作programming问题。Min 3Min 3x x+2.5+2.5y y s.t.2 s.t.2x x +4+4y y 4040 3 3x x +2+2y y 5050 x x,y y 0.0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解2022-12-28142 运输问题设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输
10、问题的总产量等于总销量，即有minjjiba11则称该运输问题为产销平衡问题；反之，称产销不平衡问题。2022-12-2815令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：nimjijijxcz11min111,2,.1,2,1,2,01,2,nijijmijjiijxaimstxbjnimxjn2 运输问题（续）2022-12-2816 以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价
11、格买入1000股股票，以每股50元的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150 1000=390003 税下投资问题2022-12-2817niiii=1nnniiiiiiii=1i=1i=1max r(sx)s.t.p x0.30(pq)x0.10p xc 我们的目标是要使预期收益最大。X Xi：当前抛出股票i的数量。3 税下投资问题（续）2022-12-28184 选址问题（1）实例实例:一组潜在位置（地址）,一组顾客集合及相应的 利润和费用数据；解解:设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案；目标：总的利润最大化。目标
12、：总的利润最大化。数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.2022-12-2819ijj c:iI,jJ,ji f :jJ,j利润在 处的设施服务顾客 所得的利润费用打开 处设施的费用4 选址问题（2）jjijjJ0-1 x:x1,open j1,i jy:iI,jJ0,每一变量顾客 由在 的设施服务否则2022-12-28204选址问题（3）ijijjji Ij Jj Jijj Jijjjijmax c yf xs.t.y1 iI;yx,iI,jJ;x0,1,jJ;y0,1,iI,jJ.2022-12-28215负载平衡
13、(1)实例实例:网络网络G(V,E)及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解解:s,d0的一组路由,即G(V,E)中m 条s 与 d间的路,表示连接s与d 的负载流量的路径。目标目标:极小化网络负载极小化网络负载的流量。的流经过边到表示由用),(dsjisdijvvF2022-12-28225 负载平衡(2)sdi,jijs,dsdijs,ds,sdsdijjkikmin L (1)s.t.LLF,(i,j)E (2)F0,or,(i,j)E (3)FFds,d,if sj,if dj (4)0,otherwise 2022-12-28236.结构设计问题结构设计
14、问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。2022-12-2824 1p2pp2hL2 受力分析图圆杆截面图Bp2hL2桁杆示意图d6.结构设计问题结构设计问题2022-12-28256.结构设计问题结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：dBS222hLdBWhhLppp221cosdhBhLsp2211dhBhLp
15、222022-12-28 圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 222228hLBdE082222222dhBhLphLBdE由此得稳定约束：6.结构设计问题结构设计问题2022-12-28TP SHUAI26 minmaxminmax22222222222080.2minhhhddddhBhLphLBdEdhBhLptshLdB另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：6.结构设计问题结构设计问题2022-12-28TP SHUAI2728基本概念基本概念 在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题线
16、性规划问题,而有的模型中含有非线性函数,称之为非线性规称之为非线性规划划.在线性与非线性规划中,满足约束条件的点称为可行点可行点,全体可行点组成的集合称为可行集可行集或可行域可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题无约束问题.2022-12-2829基本概念 最优化问题可写成如下形式:min()-.()0,()0,nx Rijf xstg xiIh xjE目标函数2022-12-2830基本概念Df 1.1Df 1.1 设f(x)为目标函数，S为可行域，x0S,若对每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x),x S的最优解最优解（整体最优解
17、整体最优解）00000N(x)x|xx,0 xSN(x),f(x)f(x)若存在x 的 邻域使得对每个成立则称x0为极小化问题min f(x),x S的局部最优解局部最优解 Df 1.2 Df 1.2 设f(x)为目标函数，S为可行域，2022-12-2831优化软件 http:/www-neos.mcs.anl.gov/http:/neos.mcs.anl.gov/neos/solvers/index.html2022-12-28TP SHUAI32最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼814 1 预备知识2022-12-28TP SHUA
18、I32TP SHUAI331，预备知识1.线性空间2.范数3.集合与序列4.矩阵的分解与校正2022-12-28TP SHUAI33TP SHUAI341.线性空间Df Df 1.31.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:(1),()()(2)0,00(3),G()()0a b cGabcabcGaGaaaaGaaaaa 有使得有-使得则称为一个群群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群阿贝尔群(&交换群交换群)2022-12-28TP SHUAI34TP SHUAI351.线性空间Df Df 1.41.4:给定一非空集
19、合V和一个域F,并定义两种运算加法加法+:VVV以及数乘数乘:FVV.若构成一交换群,且两种运算满足下面性质:,1,(a bVFFaaaaaaaabab以及单位元有 1 ()()()+则称V在域F上关于加法和数乘 运算构成一线性空间线性空间,简称V为F上的线性空间.记为V V(F F).).若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子线性子空间空间.2022-12-28TP SHUAI35TP SHUAI361.线性空间例子1,RR.n是实数域 上的一线性空间2,R RnR.nnxx是系数在实数域 上次数小于 的全体多项式组成的集合,则关于多项式的加法以及数
20、与多项式的乘法构成一线性空间3,RR.m n是实数域 上所有mn矩阵组成的集合,则其关于矩阵加法和数乘运算构成一线性空间2022-12-28TP SHUAI36TP SHUAI371.线性空间1212121212,=|,1,2,1.5 =|,1,2,.iiiS SSSx xS iSSx xxxDfxS iSS设是线性空间V(F)的两个子集,则 分别称为 和 的与交和121212:,S SSSSS设是线性空间V(F)的两个线性子空间,则和都是V(F)的线性命题子空间.121120,0,1,2,.,.,.kkiiiikivvvvFikvvv对于一组向量,.线性无关的向,V(F),若由可得则,.,称
21、为否则称量组线性相关为的向量组2022-12-28TP SHUAI37TP SHUAI381.线性空间1()(),S,(),()|,1,.,1.6 kiiiiiSV FSFL SL SvF vikDfSk线性扩给定所有由 中任意有限个元素在域 上的线性组合构成的集合 称为 的即张 记为Th1.1 线性空间V(F)的非空子集S的线性扩张L(S)是V中包含S的最小子空间.121212,()(),.,kkkSvvvL SL vvvspan v vv=,.,.,称为由该向量组张成的线性子空间 记为2022-12-28TP SHUAI38TP SHUAI391.线性空间121212(),()(d m1i
22、.7)kkkV FvvvVspan vvvvvvV FV FkVkDf，在线性空间中,如果存在一有限的线性无关的向量组,.,使得 ,.,则,.,称为的一组，的维数为，记为基,0nxRx约定：对于单点集的维数为121212121212121212,()dimdimdim()dim()dim()00,L LV FLLLLLLLLLLLLLLLL设是的两子空间，则若，即称为线性子空间 和 的，记为直和。2022-12-28TP SHUAI39TP SHUAI401.线性空间(R),(,):.,(1),(,)0,0(2),(,)(,);(3),(,)(,)(,)(4),(,)(,);(,)()()1.
23、8VVVRVRiffV RV RDf 给定一个实数域 上的线性空间并引进一种二元函数若此函数满足如下性质：,成立；则称为上的。定内积实内积空间.义了内积的实线性空间称为一个 ,|0,1.9 ,nTLRLx x yyLfLLD 给定一线性子空间令则称为 的正交补。2022-12-28TP SHUAI40TP SHUAI412.范数:RR(1),0,00;(2),;(31.10),.nnnnnxRxxxx yRxyxyxDRRxxRf 若函数满足：正定性：三角不等式：齐次性：，=则称范为的数上122 1/221111/1(,.,)2();1max|;(),1;Tnnnniiiinppiipiixx
24、 xxRxxxxxxpxxp：范数 范数；范数 范数 例子2022-12-28TP SHUAI41TP SHUAI422.范数121211221 R()(),1.2R,()()()nnxxN xNxccxTc NNhxNxcx 上的任一范数都是 的连续函数，并且任意两种范数和是等价的，即存在常数，使得有01R,=max 1.)11 (m nxAAxAxAAcond AA ADf 设定义为诱导的矩阵范若 可逆，则定义矩阵数的为条件数2022-12-28TP SHUAI42TP SHUAI432.范数1/2max2max1112 1/21/211R,2-=(),()A=max=max|;=(|)(
25、)()1n nTnijjinijijnnTijFijAAA AAAaAaAFrobeniusatr A Atr A：设常用诱导的矩阵范数：范数(谱范数)其中范数范数范数表示矩阵 的最大特征值。；其中表示A的迹例子2022-12-28TP SHUAI43TP SHUAI443.集合与序列000R()|nxNxxxx：邻域的000,().int(S),.nxSRSNxSSS称为 的，若使得集合 的所有内点的全体称为内点内的部 记为或Sint(),SSS若集合则 称为一个开集；|.nx xS xRSCC集合S的；若集合S的补集S 是开集，则称S补集为闭集；clCclSS集合S的是指包含它的最小闭集，
26、记为或集合S的S=clS闭定义为集合包界S边2022-12-28TP SHUAI44TP SHUAI453，集合与序列R0,MxS xMR nn集合S称为，若使得中的有界闭集也称有界集为紧集。sup()inf(),.nSRRxS xSRxSSSSxS 非空集合，若存在一实数，使得成立则 称为 的一个，若存在一实数，使得成立则 称为 的一个。的是指它的最小上界 其上界下界上确界是指它的最大下确下界界,sup()()0,su()1.3pRxS xSbxhSTxS n(1)若集合S有上界，则S的上确界sup(S)存在，且有(a)2022-12-28TP SHUAI45TP SHUAI463.集合与序
27、列inf,inf()()0,inf()RxS xSbxS xS n(2)若集合S有下界，则S的下确界(S)存在，且有(a)*(3),nkkSRxSxxxS 集合是闭集无穷序列若则(4),inkkSRxSSx 集合是紧集无穷序列必存在收敛于 中的点的子序列2022-12-28TP SHUAI46TP SHUAI473.集合与序列,sup|,inf|,.limsuplim,liminflimknknknnnnknknnnxnNxknxknxx kk给定有界的实数序列对令则序列和分别是单调递减和单调递增的实数序列，且从而都有极限，分别称为上极限和下极限，记为2022-12-28TP SHUAI47T
28、P SHUAI484.矩阵的分解与校正1111,.,(1)1.()4n nkkkkARAaaaaLUALUATLhU 给定矩阵的顺序主子式 都可逆 则存在唯一的单位下三角矩阵主对角元全为和可逆的上三角矩阵，使得称为 的分解Th1.5 若n阶矩阵A可逆，则存在一个排列矩阵P,单位下三角矩阵L和上三角矩阵U，使得PA=LU2022-12-28TP SHUAI48TP SHUAI494.矩阵的分解与校正Th1.6 设A为对称正定矩阵，则（1）矩阵A可唯一的分解成A=LDLT,其中L为单位下三角矩阵，D为对角矩阵（2）存在可逆的下三角矩阵L，使得A=LLT.当L的对角元素为正时，分解是唯一的。(Cho
29、lesky分解)111111111,.(-)1.7n nm mn mTTTTTTARBRU VRBV A UAUVBAUAA UGV AA UGVBGV AGGBThV A U设可逆若矩阵是可逆的，则分快矩阵可逆，且其中 2022-12-28TP SHUAI49TP SHUAI504.矩阵的分解与校正1-1-11111111111-111,.-(-)(-)(-1)(-8).n nm mn mTTTTTTTTARBRU VRBV A UA UB VA UB VAA U B V A UV AB V A UBB VA UB VBhUT 设都可逆则矩阵可逆当且仅当可逆，且其逆矩阵满足111111 ,.
30、1.0111 n nnTTTTARa bRb A aAAAabA ab AAAb A aShermanMorrison设可逆若1则 的秩 校正矩阵可逆，且其逆矩阵可表为推论定理2022-12-28TP SHUAI50TP SHUAI514.矩阵的分解与校正1111111,1.2,.()n nn pTTTTARU VRIV A UAAUVAAA U IV A UV A 设可逆若可逆,则可逆，且其逆矩阵可表为 -推论2022-12-28TP SHUAI51TP SHUAI525.函数的可微性与展开00120:,(,.,),1,0(),()0().(1,2,.,)nniiiiTiiinijifRRx
31、Reijf xtetfxxin设是连续函数 对于和单位向量一元函数在的导数 若存在的话 称为 在点一阶偏关于导的数 11,2,.,().,()()()()(,.,).iTninfxxf xxf xxf xf xf xxx对于任意若 在点 关于 的一阶偏导数存在 则称在 点存在一阶偏导数此时在 点的定义为 梯度000000,0,:()()()lim.nntxRpRpfxpf xf xtpf xpt方向导数对于函数 在点 关于方向 的定义为2022-12-28TP SHUAI52TP SHUAI535.函数的可微性与展开0000(;).(;)()TDf xpfxpfDf xpf xp我们也用表示
32、在点 关于方向 的方向导数当 的一阶偏导连续时有 2221122222122221()()()()()()()()()nnijjinnf xf xxx xf xf xf xf xf xx xx xx xxxf xf xx xx 其中当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为2022-12-28TP SHUAI53TP SHUAI545.函数的可微性与展开101220():,()()()()(),(0,1)()()(),()()()()(),(0,1)1 .9nnTTTTTaylorfRRpRf xpf xf xtppdtf xf xppf xf xpo pff xpf
33、xfThxtppdtf xf xp p 设连续可微 向量则进而 若 二阶连续可微 则2120222()()()()()()(1)()1 ()()(),(0,1)21 ()()()()2TTTTTTTf xf x po pf xpf xf xpt pf xtppdtf xf xppf xp pf xf xppf x po p2022-12-28TP SHUAI54TP SHUAI555.函数的可微性与展开1212(,.,):,()()().()()(,.,()nmnim nFTFnFfffRRfFxFRxFFxJxJacobiFxF xJxfffJacobi 对向量值函数若每个分量函数是 连续
34、可微的，则称函数的。向量函数在 的导数是指它在 点的，记为或为与标量函数梯度对应，定义矩阵的转置为在 点的梯度，记微为是 连续 可矩阵10:,()()()nmnTFF RRx pRF xpF xJxtppdt类似地，设连续可微则2022-12-28TP SHUAI55TP SHUAI565.函数的可微性与展开LipschitzLipsch:,()()Lip1.itschitzLz12nmnnnnG RDfRxRyRG xG yL xyGxxRGR 给定映射点若存在常数L0,使对任意下式成立：则常称 在 是连续的，称为。若上式对,y成立，则称 在内数连续。0,1:,()()()()sup()()
35、LipschitzLLipschitz()()()()21.10nmnFFFtnFFF RRxRF uF vJx uvJvt uvJxuvJRuxvxF uF vJx uvLuvTh设向量值函数连续可微 则对 u,v,有进而，若Jacobi矩阵映射在内是连续的，记 为常数，则2022-12-28TP SHUAI56TP SHUAI57最优化理论与算法帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8142，凸分析与凸函数2022-12-28TP SHUAI57TP SHUAI582.2.凸集与凸函数2.1 凸集与锥凸集与锥(1)(2)(1)(2)(1)(2)(1)(2
36、),0,1,(1-)(2-)11.nSnRxxSxxSSxDxfxx设 为 维欧氏空间中的一个集合。若对任意两点及每个实数有则称 为。称为和的凸集凸组合。2022-12-28TP SHUAI58TP SHUAI592.2.凸集与凸函数-,:2.1TTTTTHx p xpnpHx p xHx p xHx p xHx p x 为凸集，其中 为 维列向量，为实数。此外 下面相对于法向量 的半空间都是凸集 正的闭半空间 负的闭半空间正的开半空间 负的开半空平面间例超2022-12-28TP SHUAI59TP SHUAI602.2.凸集与凸函数x0 xx-x0px0 xx-x0p(0)(0)02.2
37、Lx xxddx 集合，为凸集，其中 为给定的例非零向量，为定点。(0)(0),0Lx xxdx 集合称为,为射线射线的顶点2022-12-28TP SHUAI60TP SHUAI612.2.凸集与凸函数11111,.,1,1,.,.,2.,2mmniimimmmxxRR imxxxDfx 给定 个向量以及满足的非负实数称向量 为的 凸组合.11111,2,.,.,.,12.1,0,1,.,.nmnmmmiiiSRSmRxxRxxSmTR ih 集合是凸集,当且仅当 包含其中任意有限个元素的凸组合,即对任意的有其中2022-12-28TP SHUAI61TP SHUAI62运用定义不难验证如下
38、命题：2.2.凸集与凸函数n12SSR2,1,.设 和为中两个凸集是题实数命则11S x xS 1,为凸集。122SS，为凸集12123SSSS(1)(2)(1)(2)，=x+xx,x为凸集12124SSSS(1)(2)(1)(2)，=x-xx,x为凸集,2.3.nC TDfconCCv TTRT集合的是指所有包含 的凸集的交集 记为 凸包为凸集 2022-12-28TP SHUAI62TP SHUAI632.2.凸集与凸函数0101,.,.,mnmixxxRxxxxm有限点集的凸包称为。若,仿射无关时，对应的凸包称为。向量 称为该单多胞形维单纯形纯形的顶点。多面体多面体(polyhedral
39、 set)是有限闭半空间的交.(可表为 AxAxb b).x4x3x2x1x5xy2022-12-28TP SHUAI63TP SHUAI642.2.凸集与凸函数,.2.4nCRxCxCCDCCf 设有集合若对每一点当 取任何非负数时，都有称 为又若 为凸集，则称 为锥凸锥ii,.,0,i1,2,.,23.k (1)(2)(k)k(i)i=1，向量集的所有非负线性组合构成的集合例.为凸锥。2.2RSn若集合S为凸集，则它的闭包命题也是凸集。2022-12-28TP SHUAI64TP SHUAI65 多面集 x|AxAx0 0也是凸锥，称为多面锥多面锥。2.2.凸集与凸函数由定义可知,锥关于正
40、的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)=x|0,xS是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出突出的,若它不包含一维子空间.约定约定:非空集合非空集合S S生成的凸锥生成的凸锥,是指可以表示成是指可以表示成S S中有限中有限个元素的非负线性组合个元素的非负线性组合(称为凸锥组合称为凸锥组合)的所有点所构的所有点所构成的集合成的集合,记为记为coneS.coneS.若若S S凸凸,则则coneS=K(S)02022-12-28TP SHUAI65TP SHUAI662.2.凸集与凸函数Df Df 2 2.5 非空凸集中的点 x x 称为极点极点,
41、若 x x=x x1+(1-)x x2,(0,1),x x1,x x2 S S,则 x x=x x1=x x2.换言之,x不能表示成S中两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2022-12-28TP SHUAI66TP SHUAI672.2.凸集与凸函数Def 2.6Def 2.6.设非空凸集S SR Rn n,Rn中向量d d 0 0 称为S S的一个一个回收回收方向方向(方向方向),若对每一 x xS S,R(x.d)=R(x.d)=x x+d|d|0 S S.S的所有方向构成的尖锥称为S的回收锥,记为0+S 方向d d1和d
42、d2 称为S S的两个不同的方向不同的方向,若对任意0,都有 d d1d d2；方向d d称为S S的极方向extreme direction,若 d d=d d1+(1-)d d2,(0,1),d d1,d d2 是S的两个方向,则有 d d=d d1=d d2.换言之d不能表成它的两个不同方向的凸锥组合x0 x0ddd2022-12-28TP SHUAI67TP SHUAI682.2.凸集与凸函数1221TTT S(x,x)x|x|(0,1)45(1,1)(1,1)2 4集合凡是与向量夹角的向量都是它的方向。，是其仅有的例.两个极方向Sx Axb,x0,d,dS2d0A0.5d 设是非零向
43、量。证明 是 的方向且例.(Th23P 若多面体 的极点 极方向)存在的话,则极点(极方向)的数目一.定有限.2022-12-28TP SHUAI68TP SHUAI692.2.凸集与凸函数 表示定理表示定理Th2.4Th2.4 若多面体若多面体P P=x xRnRn|AxAxb b,r(,r(A A)=)=n n则则:(1)P的极点集是非空的有限集合的极点集是非空的有限集合,记为记为x kkK则则j(2)记记P的极方向集为的极方向集为d jJ(约定约定P不存在极方向时不存在极方向时J=)|1,0,0,kjkjkjk Kj Jnkkjk KPconv xkKcone djJxxdxRkKjJ
44、(3)(3)指标集指标集J J是空集当且仅当是空集当且仅当P P是有界集合是有界集合,即多胞形即多胞形.2022-12-28TP SHUAI69TP SHUAI702.2.凸集与凸函数表示定理直观描述表示定理直观描述:设 X X 为非空多面体.则存在有限个极点 x x1,x xk,k0.进一步,存在有限个极方向 d d1,d dl,l0 当且仅当 X X 无界.进而,x xX X 的充要条件是 x x 可以表为 x x1,x xk 的凸组合和d d1,d dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论推论2.12.1 若多面体若多面体S=x|Ax=b,xS=x|Ax=b,x00
45、非空非空,则则S S必有极点必有极点.2022-12-28TP SHUAI70TP SHUAI71 2.2 2.2 凸集分离定理凸集分离定理2.2.凸集与凸函数1212121212121212122.7,.,()|,0,nTTTTSSRHx p xxSp xxSp xHSSSSHHSSSHSHHSSSHx p xSHHDfSS ，设 和是中两个非空集合，为超平面。若对有，对于有（或情形恰好相反），则称超平面集合和若则称 正常分离 和。若分离强则称严格分离 和。若则称分离和。2022-12-28TP SHUAI71TP SHUAI722.2.凸集与凸函数(),0,()0()0()08,2.nnT
46、TTSRpRpxSSHx pxxSHx pxxHx pxxSxSHHSxDf ，设，若或者则称 是 在 处的，若则称 为 在支撑超平面正常支撑处的超平面。nx SSRS,Th2.5infx设 为中的闭凸集，yS,则存在唯一的点x使得 y-xy-,(,),)inf-.)22.9(4nnx SSRyRySdist y Sdist y Sy xDf 设非空，则点 与集合 之间的距离定义为 （2022-12-28TP SHUAI72TP SHUAI73证明：令2.2.凸集与凸函数(k)(k)(k)x,xS,yxr.于是,由下确界定义知,存在序列使得x Sinfxr0y-22(k)(m)(k)(m)22
47、2(k)(m)(k)(m)xx(xy)(xy)2 xy2 xy(xy)(xy)(k)(k)xxS.x先证存在极限只须证为柯西数列。2022-12-28TP SHUAI73TP SHUAI74所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.2.凸集与凸函数2(k)(m)22(k)(m)22(k)(m)222(k)2(m)2(xx)2 xy2 xy4y22 xy2 xy4r2(xyr)2(xyr)0(k,m)下证明唯一性2022-12-28TP SHUAI74TP SHUAI752.2.凸集与凸函数xS,xyxyr.1S2111xyxyr,222111rxyxyr222yx(yx)|
48、yx|yx|11,yS,设有由 为凸集，有（x+x）S,由 Schwartz 不等式y-（x+x）再由 的定义y-（x+x）因否则导出矛盾。2022-12-28TP SHUAI75TP SHUAI762.2.凸集与凸函数TTTTTTSyS,Hx|p xHyp y,p xxS.p yyS p yp x,xS.设 为闭凸集，为超平面。分离点若则，令，则 与 分离可表为2.7(),00,nTTThSRySpxSp yp x 设为中的闭凸集，则存在及实数，使得对点有。2.6,(2.4)(-)(-)0nTThSRySxSy xxx 设的非空闭凸集，则点为极小化问题的最优解当且仅且当2022-12-28T
49、P SHUAI76TP SHUAI772.2.凸集与凸函数xpX(i)(x-)(y-)0 对任意 xX.(ii)令 p=y-，=p p.Txxxyx 证明提纲x SxS,|y-x|=inf|y-x|2022-12-28TP SHUAI77TP SHUAI78由此可得2.2.凸集与凸函数222222(1)xx()x(1)x,yxy(x(1)x)yx(xx)yxxx2(yx)(xx)在连线如图 上取一点则2xx2(yx)(xx)002(yx)(xx)0(yx)(xx)0，则 即 2022-12-28TP SHUAI78TP SHUAI792.2.凸集与凸函数 Th2.7表明，S为闭凸集，yS，则y
50、与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理TTTT2p(yx)p(yxxx)p(yx)p(xx)=(yx)(xx)（）nTT2.1CRS,p y0p x推论设 为中的非空闭凸锥集，yC,则存在p(0)使得2022-12-28TP SHUAI79TP SHUAI80证明2.2.凸集与凸函数nTTTh2.8 S()RclS,p yp x 设为中的凸集，yS,则存在p0，使得对点x有。jjjjj(k)(k)(k)(k)(k)(k)T(k)(k)T(k)(k)(k)(k)(k)TT(k)TTjySy,yclSyy.y2.7,p,xclS,pypx.p
