最优化理论与算法完整版.ppt

1、TP SHUAI,1,最优化理论与算法,TP SHUAI,2,提纲,1. 线性规划 对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化 算法设计技巧,使用教材： 最优化理论与算法 陈宝林 参考书 ： 数学规划 黄红选， 韩继业 清华大学出版社,TP SHUAI,3,其他参考书目,Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley 牛顿,1670,欧拉,1755,Min f(x1 x2 xn ) f(x)=0,TP SHUAI,9,欧拉，拉格朗日：无穷维问题

2、，变分学 柯西：最早应用最速下降法,拉格朗日，1797,Min f(x1 x2 xn) s.t. gk (x1 x2 xn )=0, k=1,2,m,TP SHUAI,10,1930年代，康托诺维奇：线性规划 1940年代，Dantzig：单纯形方法， 冯 诺依曼：对策论 1950年代，Bellman：动态规划，最优性原理； KKT条件； 1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展,电子计算机-最优化,TP SH

3、UAI,11,最优化应用举例,具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等. 制造业：钢铁生产，车间调度等 医药生产，化工处理等 电子工程，集成电路VLSI etc. 排版（TEX,Latex,etc.,TP SHUAI,12,1. 食谱问题,我每天要求一定量的两种维生素，Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到,需要确定每天喝奶和吃蛋的量， 目标以便以最低可能的花费购买这些食物， 而满足最低限度的维生素需求量,TP SHUAI,13,1. 食谱问题（续,令x表示要买的奶的量，y为

4、要买的蛋的量。食谱问题可以写 成如下的数学形式,运筹学工作者参与建立关于何时出现最小费用 （或者最大利润）的排序，或者计划，早期被标示为programs。 求最优安排或计划的问题，称作programming问题,Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0,极小化目标函数 可行区域（单纯形） 可行解,TP SHUAI,14,2 运输问题,设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是

5、cij问怎样调运这些物品才能使总运费最小,如果运输问题的总产量等于总销量，即有,则称该运输问题为产销平衡问题；反之，称产销不平衡问题,TP SHUAI,15,令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为,2 运输问题（续,TP SHUAI,16,以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30% 扣除税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为： 50 1000-0.3(50-30

6、)1000-0.150 1000=39000,3 税下投资问题,TP SHUAI,17,我们的目标是要使预期收益最大。 Xi：当前抛出股票i的数量,3 税下投资问题（续,TP SHUAI,18,4 选址问题（1,实例:一组潜在位置（地址）, 一组顾客集合及相应的 利润和费用数据； 解: 设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案； 目标：总的利润最大化,数据与约束 J=1,2,n:放置设施的可能的潜在位置集合 I=1,2,m:顾客集合,其要求的服务需要某设施所提 供,TP SHUAI,19,4 选址问题（2,TP SHUAI,20,4选址问题（3,TP SHUA

7、I,21,5负载平衡(1,实例: 网络G(V,E) 及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量 解: s,d0的一组路由, 即G(V,E) 中m 条s 与 d间的路, 表示连接s与d 的负载流量的路径。 目标:极小化网络负载,TP SHUAI,22,5 负载平衡(2,TP SHUAI,23,6.结构设计问题,两杆桁架的最优设计问题。 由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d,TP SHUAI,24,6.结构

8、设计问题,TP SHUAI,25,6.结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为,桁杆的总重量为,负载2p在每个杆上的分力为,于是杆截面的应力为,圆杆中应力小于等于压杆稳定的临界应力。 由材料力学知：压杆稳定的临界应力为,由此得稳定约束,6.结构设计问题,另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型,6.结构设计问题,TP SHUAI,28,基本概念,在上述例子中,有的目标函数和约束函数 都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划. 在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为

9、可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题,TP SHUAI,29,基本概念,最优化问题可写成如下形式,TP SHUAI,30,基本概念,Df 1. 1 设f(x)为目标函数，S为可行域，x0S,若对每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x), x S的最优解（整体最优解,则称x0为极小化问题min f(x),x S的局部最优解,Df 1.2 设f(x)为目标函数，S为可行域,TP SHUAI,31,Thank you very much for your attendance,优化软件 http:/www-neos.mcs.anl.

10、gov/ /neos/solvers/index.html,TP SHUAI,32,最优化理论与算法,帅天平 北京邮电大学数学系 Email:, Tel:62281308,Rm:主楼814 1 预备知识,TP SHUAI,33,1， 预备知识,1.线性空间 2.范数 3.集合与序列 4.矩阵的分解与校正,TP SHUAI,34,1.线性空间,Df 1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立,则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群( con1 x1+0.25*x4-8*x

11、5-x6+9*x7=0; con2 x2+0.5*x4-12*x5-0.5*x6+3*x7=1; con3 x3+x6=1; end,3.3 退化情形18,1，修正单纯形方法 2，逆的乘积形式,3.4 修正单纯形方法,1，修正单纯形方法,3.4 修正单纯形方法-1,回忆单纯形方法，不妨设初始单纯形表中系数矩阵含有单位阵，即系数矩阵为,3.4 修正单纯形方法-2,3.4 修正单纯形方法-3,这样，有了初始表 (即问题的系数矩阵，费用向量和右端向量子集组成)，当前表*和基B，则修正单纯形方法就可进行下去了,3.4 修正单纯形方法4,修正单纯形方法,4) 把主列置于逆矩阵表的右边，组成下列表,3.4

12、 修正单纯形方法5,例3.4.1，用修正单纯形法解下列LP,3.4 修正单纯形方法-6,约束方程的系数矩阵,3.4 修正单纯形方法-7,第1次 迭代,3.4 修正单纯形方法-8,第二次迭代,3.4 修正单纯形方法-9,计算主列,3.4 修正单纯形方法-10,3.4 修正单纯形方法-11,计算主列,3.4 修正单纯形方法-12,第4次迭代,3.4 修正单纯形方法-13,2 逆的乘积形式 初看起来，用修改的(m+1)(m+1)矩阵代替(m+1)(n+1) 的表，似乎明显的节省了计算量。然而这一方法需要计算 原问题表中的yj和wpj，若对每一个非基序列都要进行这样的计算，则需要m(n-m)次乘法。这

13、个数量并不明显小于原单纯形算法中计算量。然而这个算法重要性在于其精巧和在其他一些问题上的很好应用。下面我们将给出一种改进形式的方法，其基的逆矩阵以乘积形式存储，从而节省了存储空间,3.4 修正单纯形方法-14,3.4 修正单纯形方法-15,由(3.4.8)式得到,由于,3.4 修正单纯形方法-16,3.4 修正单纯形方法-17,下面讨论如何利用初等阵来计算单纯形方法中所需数据,3.4 修正单纯形方法-18,1)用初等阵E右乘一个行向量,2) 用E左乘一个列向量,3.4 修正单纯形方法-19,3)计算有关递推公式,3.4 修正单纯形方法-20,例3.4.2，用改进修正单纯形法解LP,3.4 修正

14、单纯形方法-21,约束方程的系数矩阵,3.4 修正单纯形方法-22,3.4 修正单纯形方法-23,第二次迭代,3.4 修正单纯形方法-24,计算主列,3.4 修正单纯形方法-25,3.4 修正单纯形方法-26,第3次迭代,最优化理论与算法,帅天平 北京邮电大学数学系 Email:, Tel:62281308, Rm:主楼814 5， 对偶理论与灵敏度分析,第四章 对偶理论与灵敏度分析,对偶理论 对偶单纯形法 原始-对偶算法 灵敏度分析,4. 对偶问题,重新考虑食谱问题。以出售奶和蛋给需要维生素的人的食品杂货商的利益出发，他知道奶和蛋按其维生素Vc和Vb的含量而有一定的价值。他的问题是确定出售维

15、生素Vc的价格x和维生素Vb的价格 y：他不能将价格订得高于奶和蛋的市场流行价，否则将失去他的顾客；他希望商店的总收入为最大,4. 对偶问题（续一,Max 40 x + 50y s.t. 2x + 3y 3 4x + 2y 2.5 x, y 0,极大化目标函数 可行区域（单纯形） 可行解,Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0,极小化目标函数 可行区域（单纯形） 可行解,4. 对偶问题（续二,对比一下从消费者和供应商各自的利益导出的两个问题，我们不难发现两个问题可以通过下述简单的变换，而相互转化,当你把食谱问题的对偶问题解出以后（练习），你

16、会发现一个（重要的）事实：这两个问题的最优值是相等的,思考题：在数学上，是不是还有一些对偶的问题和概念,4. 对偶理论1,4.1 LP的对偶理论,Primal Min cx s.t. Axb, (4.1.1) x0,Dual Max wb s.t. wAc, (4.1.2) w0,4.1.1 对偶问题的表达,1,对称形式的对偶,2,非对称形式的对偶,4. 对偶理论2,3,一般形式的对偶,Primal,化为等价的标准形式,4. 对偶理论3,写成矩阵形式,按非对称 对偶的定义,得上述LP 的对偶问题,4. 对偶理论4,于是原 LP的对偶,Dual,4. 对偶理论5,以上分析可知有如下关系,4. 对

17、偶理论6,引理1 对偶问题的对偶是原始问题 (The dual of the dual is the primal.,4. 对偶理论7,即得原问题,4. 对偶理论9,例4.1.2 设原问题,4. 对偶理论10,例4.1.2 设原问题,4. 对偶理论11,例4.1.3 设原问题,4. 对偶理论12,于是可得对偶问题,4. 对偶理论13,5.1.2 对偶定理 注意到,原问题和对偶问题是由同一数据集(A,b,c)所定义，且对偶问题的对偶即是原问题，因此可以选原始-对偶对中任一为原问题，而另一则自动为对偶。下面讨论两者间的关系,4. 对偶理论14,推论2 对偶规划(4.1.1)和(4.1.2)有最优解

18、的 充要条件 是它们同时有可行解。 推论3 若原问题(4.1.1)的目标函数值在可行域上无下 界,则其对偶问题无可行解;反之,若对偶(4.1.2)的目标 函数值在可行域上无上界,则原问题无可行解,5. 对偶理论,4. 对偶理论15,定理4.1.2 设(4.1.1)和(4.1.2)中有一个问题存在最优解，则另一个问题也存在最优解，且这两个问题的最优目标函数值相等,证明：设(4.1.1)存在最优解。引进松弛变量，将 （4.1.1）写成等价形式,4. 对偶理论16,由于(4.1.12)存在最优解，因此能用单纯形方法求得 一个最优基本可行解。 不妨设此最优解为,相应的最优基为B.此时所有判别数满足,4

19、. 对偶理论17,即,把所有松弛变量在基下对应的判别数所满足的条件(4.1.13)用矩阵表示,得,4. 对偶理论18,4. 对偶理论19,4.1.3互补松弛性质,4. 对偶理论20,4. 对偶理论21,例4.1.3 求解如下LP,4. 对偶理论22,4. 对偶理论23,4. 对偶理论对偶单纯形法 1,4.2 对偶单纯形法 4.2.1对偶单纯形法基本思想,4. 对偶理论对偶单纯形法2,注:对偶可行的基本解不一定是原问题的可行解.若还是原问题的可行解,则此解即为最优解,回忆(修正)单纯形法的基本思路是保持原问题的可行性和互补松弛条件下,在它的最优解上寻求对偶问题的可行性,类似的,对偶单纯形法的基本

20、思路是:在保持对偶可行性和互补松弛条件下,在它的最优解上寻求原问题的可行性,4. 对偶理论对偶单纯形法 3,4. 对偶理论对偶单纯形法 4,下面分析如何选取离基变量和进基变量.设在某次迭代中得到如下表,4. 对偶理论对偶单纯形法 5,4. 对偶理论对偶单纯形法 6,4. 对偶理论对偶单纯形法 7,下面说明上述转换能改进对偶可行的基本解,2)主元消去后仍然保持对偶可行性,即所有判别数都小于或等于0(对极小化问题,4. 对偶理论对偶单纯形法 8,4. 对偶理论对偶单纯形法 9,即对偶问题的目标函数值在迭代过程中单调增(非减,对偶问题的可行解w越来越接近最优解.原问题的对偶可行的 基本解将向着满足可

21、行性方向转化而接近原问题最优解,4. 对偶理论对偶单纯形法 10,4. 对偶理论对偶单纯形法 11,例1,4. 对偶理论对偶单纯形法12,4. 对偶理论对偶单纯形法 13,4. 对偶理论对偶单纯形法 14,4. 对偶理论对偶单纯形法 15,4. 对偶理论对偶单纯形法16,4.2 初始对偶可行的基本解,对偶单纯形法中要求先给出一个初始的对偶可行的 基本 解.这个解未必直接能求出,因此需要引进一个方法与单 纯形法中类似,我们也是通过解一个辅助问题-扩充问题 来求解.扩充问题的构造,扩充问题的构造:先给出(4.2.1)的一个基本解(这很容易). 不妨设A的前m列线性无关,由这m列构成基矩阵B.于是

22、(4.2.1)可改写成,4. 对偶理论对偶单纯形法17,4. 对偶理论对偶单纯形法18,在(4.2.10)中以系数矩阵的前m列和第n+1列组成的m+1阶单位矩阵为基,则得一个基本解,4. 对偶理论对偶单纯形法19,上述做法是正确的,因为主元消去运算前后判别数之间有如下关系,综上立明,4. 对偶理论对偶单纯形法20,注意到(4.2.10)的对偶问题有可行解,故用对偶单纯形方法 求解(4.2.10)时,仅有如下两种情况发生,1)扩充问题无可行解,则原问题亦无可行解.(反证,4. 对偶理论对偶单纯形法21,例2.2,4. 对偶理论对偶单纯形法22,于是得扩充问题,构作单纯形表,4. 对偶理论对偶单纯

23、形法23,4. 对偶理论对偶单纯形法24,4. 对偶理论对偶单纯形法25,例2.3,4. 对偶理论对偶单纯形法 26,把约束矩阵置于单纯形表中,4. 对偶理论对偶单纯形法27,4. 对偶理论对偶单纯形法28,4. 对偶理论对偶单纯形法 29,4.3 原始对偶算法1,基本思想 这一方法实际上是由某些网络问题的一个特殊算法发展起 来的,构造对偶问题,考虑原问题,互补松弛条件是:如果x和分别是P和D的可行解,则它们 是最优解的充要条件是对一切的i和j有,由于P是标准形式,故对任意可行解 x,(1)总是成立的,4.3 原始对偶算法2,下面我们集中讨论关系式(2) 假定是对偶问题D的可行解,若能设法找出

24、P的一个可行解x,使得满足关系式(2),即,则这个 x(及)是最优的,4.3 原始对偶算法3,对给定求这样一个x的思想,导致了原始对偶算法.给 定,要找这样一个x,可以通过解由 所确定的辅助问 题(称为限制的原始问题RP)而得到.当这样的x没有搜 索到, 那么就得到RP的对偶信息(RP的对偶记为DRP), 此信息告诉我们如何修改 ,于是得到新的 .重复此过 程,在有限步内就收敛到最优解,4.3 原始对偶算法4,算法开始时是D的可行解且始终保持对偶可行性.在c0时可直接取=0为初始对偶可行解. 当c不是非负的时候,应用Beale等人的方法很容易的找出可行解,4.3 原始对偶算法5,原始对偶算法,

25、显然增加约束后不会改变原问题P的解,此时新的原 始问题的对偶为,4.3 原始对偶算法6,中将有一些取严格不等式,而另一些取等式.设取等式的约束指标集为J,4.3 原始对偶算法7,因此不妨设D有一可行解,则不等式约束,这即相当于求一个x,使得满足,4.3 原始对偶算法8,称J为允许列集合.为找出这样的x,构造新的LP,称为限制的原始问题(RP,利用单纯形法求解此RP:若最优值为0则已找到(6)的解,因此也是P的最优解.若最优值大于0,如何处理,4.3 原始对偶算法9,为解决此问题,需要考察限制的原始问题RP的对偶DRP,4.3 原始对偶算法10,现在我们处于这样的情形:试图只应用允许列来找出 一

26、个可行解x,但由于RP的最优值0,所以努力失败了,这就可能考察利用原来的和新得到的 来校正,4.3 原始对偶算法11,因为RP和DRP是一对相互对偶的规划,所以它们的 最优值相等.因此有,但是我们得到了RP的最优解及其对偶的最优解,所以我们应该选取0,从而改进D的费用,4.3 原始对偶算法12,为维持可行性,只需考察下述不等式,4.3 原始对偶算法13,此时,可行性准则变为,于是有,4.3 原始对偶算法14,当解限制的原始问题并达到了改进D的解的时候,我们 重新定义集合J,然后重复上述过程直到或者opt=0并因 此得到P的最优解,或者由定理1知P无可行解,Procedure primal-du

27、al,4.3 原始对偶算法15,begin infeasible:=no, opt:= no let be feasible in D(comment:possible by(3) ); while infeasible:=noand opt:= no do begin set solve RP by the simplex algorithm if opt=0 then opt:= yes else if then infeasible:=yes else end end,4.3 原始对偶算法16,我们运用表格形式进行迭代。初始表结构如下,此表中原来变量xj 中仍属于限定问题中.即 jJ,则

28、用在上方标注.解RP的进离基运算在标的列和y的列进行,限定原始问题达到最 优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可,4.3 原始对偶算法17,4.3 原始对偶算法18,限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可”的理由,下面求解上述LP。首先找出对偶问题的一个可行解。例4.3.1 的对偶是,4.3 原始对偶算法19,于是得一阶段问题,显然w=(0,0)是一个可行解，此时有,4.3 原始对偶算法20,变量上方的标识符表示该变量属于RP,4.3 原始对偶算法21,按照前述给定的格式，得初表如下,4.3 原始对偶算法22,4.3

29、 原始对偶算法23,J=2,用单纯形法解 RP：x2进基,y1离基. 经主元消去得下表 (注：解RP时第4行 不变,RP的判别数均非正, 达到最优，Z0=20 修改对偶问题的可行解,4.3 原始对偶算法24,此时J=1，2， 再解RP： x1进基，y2离基. 经主元消去得下 表,4.3 原始对偶算法25,RP问题达到最优，最优值Z0=0，因此得原问题的最优解 x*=(x1,x2,x3)=(2,1,0) 目标函数的最优值fmin=5,对偶问题的最优解w=(0,1,335,4.4 灵敏度分析,1，引入 2，改变系数向量 3，改变右端向量 4，改变约束矩阵 5，增加新的约束,336,前面讲的线性规划

30、问题中，都假定问题中 是已知常数。但实际上这些数往往是一些估计和预测的数字,市场条件变化，价值变量 cj就会变化,aij是随工艺技术条件的改变而改变,而值bi则是根据资源投入后能产生多大经济效益来决定的 一种决策选择,在大多数实际问题中。不仅要求求出问题的最优解，而且还希望知道当问题中的某些参数改变时最优解怎样变动。参数的变化可分为离散的和连续的两种。 灵敏度分析是指对系统或事物因周围条件离散变化显示出来的敏感程度的分析，即对最优解的影响进行分析研究。而参数规划则是研究参数连续的 变化时对最优解的影响,1 引入,337,这就是灵敏度分析所要研究解决的问题,因此就会提出以下问题,当这些参数中的一

31、个或几个发生变化时，问题的最优解会有什么变化,这些参数在一个多大范围内变化时，问题的最优解变不变,影响最优解的参数有如下几类： 改变费用系数cj 改变右端费用bi 改变约束方程的系数矩阵A 加入新的约束,参数变化后的结果 最优解不变：最优 基及其取值不变 基变量不变但取值 改变 基变量改变，取值 亦改变,338,重新解新线性规划问题,重新计算发生变化的个别系数,判断问题现状,采取如下措置,339,考虑标准LP问题为,RHS,0,假定得到最优单纯形表如下,4.4.1,2 改变系数向量 c,340,当价值向量c改变时, 在单纯形表里受影响的只是检验数,和目标函数值，其它没有改变,因而只需计算新的检

32、验数,和目标函数值,如果检验数非正，则原最优解依然是最优解,否则是基本可行解,以此为初始基可行解按单纯形法进行迭代,就可以求出新问题的解,341,1、情形I: 是非基变量,改变非基变量的价值向量,若,由单纯形法计算公式知，只有检验数 起变化,则原最优解依然是最优解,否则,由此进行单纯形迭代,即价值向量只有一个分量,新的检验数,342,2、情形II: 是基变量,基变量对应的约束为第 L个, 即,改变基变量 的价值向量,问题最后一张单纯形表中,新检验数(因基变量检验数要求0,新目标函数值,把单纯形表上的第L行元素乘以 加到检验数行上,总之,343,例1,最优解:(x1,x2,x3,x4,x5,x6

33、)=(5,3,1,0,0,0,344,检验数仍非负, 问题原最优解仍是此时最优解,更多信息,对非基变量的价值系数在某范围变化最优解都不发生改变,最优解都不发生改变,最优解都不发生改变,同理,最优解都不发生改变,非基变量,345,若检验数向量非负数，而右端向量没变，故仍最优解,否则用单纯形算法即可,基变量,把最优单纯形表的第3行乘以 1-(-1) 加到检验数行上,再令,得到对应新问题的单纯形表,346,1. 基本思想,如果 ，则已发现新问题的最优解,否则利用对偶单纯形算法求解新问题,3 改变右端向量 b,347,其中 为 的第 r 列,当只改变一个分量时,如果 ，则已发现新问题的最优解,因新问题

34、的单纯形表检验数向量不变,仍有,否则，单纯形表对应新问题的一个基本(不可行)解和,故可用对偶单纯形法继续求解,对偶问题的一个可行解,348,b3由3变成5时,续上例,仍是最优基本可行解,349,b3由3变成11时,单纯形表对应新问题的一个基本(不可行)解和,故可用对偶单纯形法继续求解,对偶问题的一个可行解,此时单纯形表,350,4 改变约束矩阵A,有如下两种情形,351,此时情况较复杂，若只有少数列发生变化可用如下方法,352,353,5 加入新的约束,设原有约束为Ax=b，在此基础上，我们增加一个新的约束,2)若原问题的最优解不满足新的约束，则需要把新的约束条件增加到原来的最优表中再解新问题

35、,设原来的最优基为B。最优解为,354,355,356,357,358,359,360,361,362,总结,当原问题只有个别数据改变, 特别是变化幅度不大时, 用灵敏度分析比对新问题重新求解简单,在现实中市场因素(价值系数) , 生产资料(右端向量), 生产技术(矩阵元素)随时在变化, 而参数的变化必然 引起模型的变化,最优化理论与算法,帅天平 北京邮电大学数学系 Email:, Tel:62281308, Rm:主楼814 7， 最优性条件,第七章 最优性条件,无约束问题的极值条件 约束极值问题的最优性条件 对偶及鞍点,7.1无约束问题的极值条件,考虑非线性规划问题,1，无约束极值问题,称

36、为无约束极值问题（UNLP,7. 最优性条件-无约束1,7. 最优性条件-无约束2,Th7.1.1(非极小点的充分条件) 设f(x)在点x*处可微, 若存在方向d(0)Rn,使得f(x*)d0, 使得对任意(0,),有f(x*+d)f(x*).此时,我们称 d 为f(x)在x*的一个下降方向,证明. 由 f(x) 在 x* 可微, 则 f(x*+d)=f(x*) + f(x*)d+|d|(x*;d), 其中 (x*;d) 0(当 0,2，必要条件,7. 最优性条件-无约束3,移项且两边同除以( 0),得 （f(x*+d)f(x*)）/ f(x*)d+|d|(x*;d) 由于 f(x*)d 0

37、使得对 任意(0, ), f(x*)d+|d|(x*;d)0 .定理立明,定理7.1.2-3(极小点的必要条件)设x*处是问题(UNLP)的局部极小点. 当 f(x) 在 x*可微时,则梯度 f(x*)=0. 当f(x) 在 x*二次可微时. 则 f(x*)=0 且 Hessian 矩阵 H(x*) 是半正定的,7. 最优性条件-无约束4,证明(1). 若f(x*)0, 作 d=f(x*). 则有 f(x*) d 0 使得 f(x*+d)f(x*)， (0, ), 此与 x* 为局部极小相矛盾，故 f(x*)=0,7. 最优性条件-无约束5,由(II), 显见,对充分小的 成立 , 对 0取极

38、限, 则有 dH(x*)d 0, 从而,H(x*) 半正定,定义1 若f(x)在点x*处可微,且f(x*)=0,则称x*为f(x)的一个驻点或平稳点.d(0)Rn, 既不是极大点也不是极小点的驻点称为鞍点,Th7.1.4 (二阶充分条件). 假设 f(x) 在 x*点二次可微,若 f(x*)=0 且 Hessian 矩阵 H(x*) 是正定的,则 x* 是(UNLP)的一个(严格)局部极小点,3，二阶充分条件,7. 最优性条件-无约束6,7. 最优性条件-无约束7,4，充要条件,定理7.1.5 (充要条件). 假设 f(x):RnR 是 可微的凸函数,则x* 是(UNLP)的全局最小点当且仅当

39、f(x*)=0,7. 最优性条件-无约束8,7. 最优性条件-无约束9,7. 最优性条件-无约束10,7. 最优性条件-有约束1,7.2约束极值问题的最优性条件,1，约束极值问题,7. 最优性条件-有约束2,2，可行方向和下降方向,Def7. 2.1. 设 f(x) 定义在Rn上的实值函数. x* Rn, d0, 若存在 0 使得 f(x*+d)f(x*)（ (0, )）,则 d 称为 f(x) 在 x*的下降方向(decedent direction,设 f(x) 在 x*可微. 若存在向量 d 满足 f(x*)d0, 则 由Th7.1.1, d 是 f(x) 在 x*.的下降方向。记所有这

40、样的向量集合为,7. 最优性条件-有约束3,由可行方向定义和下降方向知， 从点 x*, 沿可行方向 dD(x*) 作一个很小的移动还是可行点. 进一步，由 Th 7.1.1, 若 f(x*)d0 ，则d 是f在 x*的下降方向。下面定理将说明 若 x* 是局部最优且 f(x*)d0, 则 dD(x*).即不是可行方向,Theorem 7.2.1. (必要条件) 考虑极小化问题： min f(x) ，subject to xS, 其中 S 是 Rn 中非空集合，设 f(x) 在 x*可微。若 x* 是局部极小点，则 F0(x*)D=,其中 F0(x*)=d |f(x*)d0 ， D 是 S 在

41、x*的可行方向锥,7. 最优性条件-有约束4,证明：反证法，设存在向量 dF0(x*)D.由Th7.1.1知 （1）：存在 10, f(x*+d)0， x*+dS ， (0, 2) 此与局部极小矛盾,379,7. 最优性条件-不等式约束1,为把最优性的几何条件用代数来表示，引入起作用约束的概念。问题的约束条件在点x*S处有两种情形,3 不等式约束的一阶最优性条件,1，I= i| gi(x*)=0在x*处起作用约束 2， gi(x*)0. iI在x*处不起作用约束 G0(x*)=d |gi(x*)d0 , iI,380,7. 最优性条件-不等式约束2,证明概要. 设 dG0(x*).因 S 为开

42、集，则存在 10 使得对 (0, 1)， x* +d S。 另外存在 20使得对 (0, 2) ，iI. gi(x*+d)0,最后存在 30 使得对任意 (0, 3) and iI有gi(x*+d)gi(x*), 从而 dD, D 是 x*处的可行方向锥. 于是G(x*)D. 由Th 7.2.1, 立明,Th7.2.2. (必要条件) 考虑极小化问题 min f(x) subject to gi(x)0， i=1, m ，xS, 其中 S 是 Rn中的非空开集。 设 x* 为可行点， I= i| gi(x*)=0. 进一步假设， f(x) 和 gi(x) （ iI ）在 x* 可微， gi （

43、 iI） 在 x*连续. 若 x* 是局部最优解，则 F0(x*)G0(x*)=, 其中F0(x*)=d |f(x*)d0， iI,7. 最优性条件-不等式约束3,7. 最优性条件-不等式约束4,x*=(2, 1) g1(x*)=(-4, -2), g2(x*)=(-1, -1), f(x*)(-2, -2,7. 最优性条件-不等式约束5,384,7. 最优性条件-不等式约束6,证明. 由Th7.2.2, 不存在向量 d 同时满足 f(x*)d0 和 gi(x*)d0 ，( iI). 设 A 是其行由 f(x*) 和 gi(x*)(iI)组成的矩阵. 则 Ad0 无解. 由Godan定理, 必

44、存在非零向量 p0 使得 Ap=0. 记 p 的分量为 u0 和 ui ( iI ), 则定理第一部分得证。 第二部分让 ui =0 （ iI）立明,在 Fritz John 条件中, u0, ui 称为 Lagrangian 乘子. 而 条件 uigi(x*)=0 称为互补松弛条件( complementary slackness condition,385,7. 最优性条件-不等式约束7,386,7. 最优性条件-不等式约束8,387,7. 最优性条件-不等式约束9,388,7. 最优性条件-不等式约束10,7. 最优性条件-不等式约束11,若 Lagrangian 乘子 u0 =0, 则

45、 Fritz John 条件 不包含 f(x)的任何信息，它仅仅是表明可以把起作用约束的梯度作一个非负的非平凡的线性组合而成为零向量。从而对我们的最优解没有多少实用价值,为保证u00,可以对约束强加某种限制，这种限制条件叫做约束规格或约束品性( constraint qualifications).已有很多的约束规格，特别的, Karush 1939, MS Thesis, Dept of Math, Univ of Chicago , Kuhn 和 Tucker 1951 独立给出的最优性必要条件恰是 Fritz John 条件加上 u00,7. 最优性条件-不等式约束12,7. 最优性条件

46、-不等式约束13,Karush-Kuhn-Tucker 条件可写成向量形式 f(x*)-ug(x*)=0, ug(x*)=0, u0,这表明 f(x*) 属于 起作用约束的这些约束的梯度所形成的锥中,7. 最优性条件-不等式约束14,7. 最优性条件-不等式约束15,7. 最优性条件-不等式约束16,7. 最优性条件-不等式约束17,396,7. 最优性条件-不等式约束18,Th7.2.5. (Karush-Kuhn-Tucker 充分条件)考虑极小化问题 min f(x) subject to gi(x)0， i=1, m ，xS, 其中 S 是 En.中非空开集. 设 x* 为可行点, I

47、= i| gi(x*)=0. 设 f(x)和诸 gi 是凸的， 进一步假设 f(x) 和 gi(x)( iI )在 x* 可微, gi ( iI) 在 x*连续. 若 K-K-T条件在 x*成立，则x*是全局最优解,证明略,7. 最优性条件-等与不等式约束1,4.一般约束问题的一阶最优性条件,记,7. 最优性条件-等与不等式约束2,7. 最优性条件-等与不等式约束3,7. 最优性条件-等与不等式约束4,证明略,7. 最优性条件-等与不等式约束5,7. 最优性条件-等与不等式约束6,7. 最优性条件-等与不等式约束7,7. 最优性条件-等与不等式约束8,7. 最优性条件-等与不等式约束9,7.

48、最优性条件-等与不等式约束10,现定义两集合,7. 最优性条件-等与不等式约束11,7. 最优性条件-等与不等式约束12,例,7. 最优性条件-等与不等式约束13,例,7. 最优性条件-等与不等式约束14,7. 最优性条件-等与不等式约束15,KKT最优性必要条件（Th2.4）加以推广。这是通过增加约束规格来实现的,前面FJ条件中w0不一定为正, 在下面定理中。我们将前面提到的,7. 最优性条件-等与不等式约束16,若采用矩阵和向量记号,则KKT可如下简洁表示,7. 最优性条件-等与不等式约束17,则KKT条件可表为,7. 最优性条件-等与不等式约束18,7. 最优性条件-等与不等式约束19,

49、7. 最优性条件-等与不等式约束20,5.二阶条件,7. 最优性条件-等与不等式约束21,为此,我们考虑函数的二阶导数,首先给出如下定义,7. 最优性条件-等与不等式约束22,例,7. 最优性条件-等与不等式约束23,7. 最优性条件-等与不等式约束24,现在我们考虑问题(7.2.1,7. 最优性条件-等与不等式约束25,7. 最优性条件-等与不等式约束26,7. 最优性条件-等与不等式约束27,7. 最优性条件-等与不等式约束28,7. 最优性条件-等与不等式约束29,7. 最优性条件-等与不等式约束30,7. 最优性条件-等与不等式约束31,7. 最优性条件-等与不等式约束32,为给出局部

50、最优解的二阶充分条件，我们定义集合,7. 最优性条件-等与不等式约束33,7. 最优性条件-等与不等式约束34,7. 最优性条件-等与不等式约束35,下面分两种情况讨论,7. 最优性条件-等与不等式约束36,7. 最优性条件-等与不等式约束37,7. 最优性条件-等与不等式约束38,7. 最优性条件-等与不等式约束39,例7.2.7 考虑下列非线性规划问题,检验以下各点是否为局部最优解,7. 最优性条件-等与不等式约束40,记目标函数和约束函数分别为f(x),g(x),h(x),他们在 点x处的梯度分别是,Lagrange函数是,Lagrange函数关于x的Hessian矩阵是,7. 最优性条

51、件-等与不等式约束41,7. 最优性条件-等与不等式约束42,7. 最优性条件-等与不等式约束43,后两点请自行验证之,7. 最优性条件-等与不等式约束44,例7.2.8 考虑下列非线性规划问题,记目标函数和约束函数分别为f(x), h(x),他们在点x处的梯度分别是,7. 最优性条件-等与不等式约束45,例,7. 最优性条件-等与不等式约束46,7. 最优性条件-等与不等式约束47,Ch7.3 对偶理论1,7.3.1 对偶形式,Ch7.3 对偶理论2,其对偶形式(对偶问题)定义如下,Ch7.3 对偶理论3,于是(LP)问题(*)的对偶形如,Ch7.3 对偶理论4,Ch7.3 对偶理论5,7.

52、3.2 对偶定理,对于上面的两例我们有原问题与对偶问题的最优值相等.对一般形式的非线性规划问题,是否也对?即,1. 弱对偶定理,Ch7.3 对偶理论6,Ch7.3 对偶理论7,2. 凸规划与Slater约束规格,Ch7.3 对偶理论8,Ch7.3 对偶理论9,3. 强对偶定理,Ch7.3 对偶理论10,证明:先证第一部分:(1)无解=(2)有解. 令集合,Ch7.3 对偶理论11,Ch7.3 对偶理论12,Ch7.3 对偶理论13,Ch7.3 对偶理论14,例 考虑如下约束优化问题,显然该问题无最优解,但目标函数的下确界fmin=0. 该问题的Lagrange对偶函数,Ch7.3 对偶理论15

53、,7.3.3 鞍点定理,Ch7.3 对偶理论16,1 鞍点与最优解,Ch7.3 对偶理论17,Ch7.3 对偶理论18,对于(2),在假设条件成立时,根据强对偶定理5.11, 对于问题(PNLP)的最优解 ,存在 ,使得,Ch7.3 对偶理论19,2. 鞍点与KKT点,最优化理论与算法,帅天平 北京邮电大学数学系 Email:, Tel:62281308, Rm:主楼814 8， 算法,第八章 算法,算法概念 算法收敛问题,ch8 算法-概念,8.1.1 算法映射,下降，即对某个函数，在每次迭代中后继点处的 函数值要有所减小,迭代下降算法,考虑极小化问题 f(x) s.t. xS 这里f是目标

54、函数，S是可行域。对于求解这一问题的解答程序或算法可以看作是一个迭代过程，这过程按照规定的一组 指令和终止准则一起产生一个点序列,ch8 算法概念,Df 8.1.1 算法A是定义在空间X上的点到集映射,即对每一个点xX,给定一个子集A(x)X,Ch8 算法-概念,ch8 算法概念,如图所示,应用算法A时,经A作用得到一个闭区间,从此区间中 任取一点作为后继点,重复这个过程,得一由算法产生得点列, 在一定条件下,它收敛于问题的解.如 3,2,3/2,5/4, 3,3/2,9/8,33/32, etc,ch8 算法概念,8.1.2 解集合,为了求解上述问题，要求使用的算法具有这样的性质： 由算法产

55、生的点列收敛于整体最优解 然而，在许多情形下，要满足这一点很难做到。事实上 由于非凸性，问题的规模和其它一些困难，达到整体最优 几乎不可能，因此当达到属于预定集的某一点达到，则可 以停止迭代，这个预定集就称之为解集合 常用的解集合有如下几种类型,Ch8 算法概念,ch8 算法概念,8.1.3 下降函数,Ch8 算法概念,8.1.4 闭映射,Ch8 算法概念,设是整体最优解的集合，即=1。考虑算法映射， 定义为,映射在下图中说明,Ch8 算法概念,此例表明算法在区间(-,2)上 收敛于集中点，而在2，) 上却不收敛于中点， 从而算法不是闭的,显然对任何初始点x12, 由映射A产生的任何序列都收敛

56、于点 x*=2，对初始点x12, 由映射A产生的任何序列都收敛于点 x=1,Ch8 算法概念,评注：上面例子表明初始点x1选取的重要性：若x1 2则达到收敛于中的点，否则就不能实现。另注意到，在上例中都满足如下条件,但对任何x12都不收敛于 x*=1 ,即算法不是闭的,1，给出一可行点xk 1,任何后继点xk也是可行的,即xk+1 1 2，给出一个不在解集内的可行点xk,任何后继点xk+1满足 f(xk+1)f (xk), 其中f(x)=x2. 即目标函数严格下降。 3，给出一在内的可行点xk(=1),任何后继点xk+1也在内,即 xk+1 =1,Ch8 算法概念,8.1.5, 合成映射,Ch

57、8 算法概念,Ch8 算法概念,Ch8 算法-收敛定理,8.2.1收敛定理,Ch8 算法-收敛定理,Ch8算法-收敛定理,Ch8 算法-收敛定理,Ch8 算法-收敛定理,Ch8 算法-收敛定理,8.2.2实用收敛准则,正如在收敛定理中所指出，若我们达到解集中的一个点时，就终止算法。然而，在大多数情形下，收敛于中 的点仅仅出现在极限意义上，因此我们必须依靠终止迭代过程的某些实际规则，下面给出一些常用的终止规则。这里0和正整数N是预先给定的,xk+Nxk| 如果应用映射A的N次后移动的距离小于时，算法终止,Ch8 算法-收敛定理,Ch8 算法-收敛定理,8.2.3 收敛速率,最优化理论与算法,帅天

58、平 北京邮电大学数学系 Email:, Tel:62281308, Rm:主楼814 9， 一维搜索,第九章 一维搜索,一维搜索的基本概念 试探法 函数逼近法,9. 一维搜索-概念1,最优化方法的基本结构： 给定初始点x0 确定搜索方向dk，即按照一定规则，构造f在xk点处的下降方向 作为搜索方向; (b)确定步长因子k，使目标函数值有某种意义下的下降; (c)令 xk+1 = xk +kdk 若xk+1满足某种终止条件 则停止迭代，得到近似最优解xk+1， 否则，重复上述步骤,9.1 一维搜索概念,9. 一维搜索-概念2,9. 一维搜索-概念3,一维搜索算法的闭性,假设一维搜索是以x为起点,

59、沿方向为d的进行的,并定义为算法映射M,9. 一维搜索-概念4,Th9.1.1 设f是定义在Rn的连续函数,d0,则(9.1.4)定义的算法映射M在(x,d)处是闭的,9. 一维搜索-概念5,9. 一维搜索-试探法1,9.2.1, 0.618法,9. 一维搜索-试探法2,单峰函数具有一些很有用的性质:如果f是a,b上单峰函数,则可通过计算此区间内两不同点的函数值,就能确定一个包含极小点的子区间,从而缩小了搜索区间,单峰函数的一个等价定义,9. 一维搜索-试探法3,9. 一维搜索-试探法4,证明:仅证(1),反证,如若不然,存在点x*a, x(1),使,9. 一维搜索-试探法5,0.618法的基

60、本思想:通过取试探点使包含极小点的区间(不确定区间)不断缩小,当区间长度小到一定程度时,区间上各点的函数值均接近极小值,此时该区间内任一点都可以作为极小点的近似值,9. 一维搜索-试探法6,由( 2.3)和(2.4)得到,9. 一维搜索-试探法7,今考虑( 2.1)的情形,此时新的搜索区间为,9. 一维搜索-试探法8,9. 一维搜索-试探法9,这样,计算公式(2.5)(2.6)可写为,9. 一维搜索-试探法10,其几何意义:黄金分割率对应的点在单位长区间0,1中的位置相当于其对称点1-在区间0,中的位置,9. 一维搜索-试探法11,算法(0.618法,9. 一维搜索-试探法12,9. 一维搜索