运筹学与最优化第一章最优化简介

白敏茹Tel:15211096363Email:[e-mail]第一讲前期课程要求：高等数学、线性代数、Matlab教材1.《数值最优化算法与理论》（第二版）李董辉，童小娇，万中编，科学出版社，2009参考教材1.《NumericalOptimization》（2ed,2006）JorgeNocedal,StephenJ.Wright2．《ConvexOptimization》(2004)StephenBoyd,LievenVandenberghe3．《最优化方法与程序设计》倪勤编，科学出版社，2009考核方式•平时成绩:50%考勤、作业、编程•期末考核:50%问题--〉优化模型--〉计算--〉书面提交LeonhardEuler(1707-1783)由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物都遵循某种最大或最小准则———欧拉Für,dadasGewebedesUniversumsamvollkommenstenunddieArbeiteinesklügstenistSchöpfers,nichtsanfindetimUniversumstatt,indemirgendeineRichtliniedesMaximumsoderdesMinimumsnichterscheint优化问题任何存在/需要决策的问题都是优化问题•力学：（最小重量，最大载重，结构最优）•材料科学；（最小能量）•金融：（最大利润，最小风险）•生命科学：（DNA序列,蛋白质折叠）•信息科学：（DataMining,图像处理）•地学：（反问题－－误差最小）•交通：（最大效益，时刻表，恢复运行）Netflix百万美元奖电影评价电影打分观众ABCDEFMovie1??4?1?Movie225???2Movie3??5335Movie41??4??Movie532?2??Netflix问题从1998年10月到2005年12月搜集数据（请客户给电影打分）•480,189用户•17,770电影•100,480,507分数（1到5）问题：如何填补没有打分的数据？矩阵完整化(MatrixCompletion)给出矩阵A中的一些元素：Aij((i,j)inS)求A的其他元素数学问题：minimizeRank(X)s.t.Xij=Aij(i.j)inS1.1.1(),1,2,,,1,2,,,1,2,,.,1,2,,..ijjinmjiaimjnjcjnibim例食谱问题设市场上可以买到种不同食品，每种食品含有种营养成分。设每单位的第种食品中含第种营养成分的数量为。第种食品的单位价格为再设每人每天对第种营养成分的需求量为试确定在保证营养需求条件下的经济食谱nijijinjjjjxaxgixcxfnjx)()(.,,,j.种营养成分的总量为同时获得第则每天总花费为，的数量为种食品设每天购买第量有关多小则与购买食品的数费需求的花费最小，而花经济食谱是指满足营养解..)(..,,,,..min划问题这是一个简单的线性规的简称受约束于是其中学模型：因此我们得到下面的数toSubjecttsxmibxatsxcjimijijnjjjmibxgii,,,,)(指考虑到满足营养需求是给出其值由表设有观测数据数据拟合问题例1.1),,()(2.1.1kkyx47.502.550.398.201.298542543211.1kkyxk观测数据表系拟合这些数据试用一个简单的函数关xy●●●●●线性拟合图1.1上描出如下解：将观测数据在坐标babaxy,1.1合问题就是求来拟合这些数据点，拟直线直线附近，因此我们用知，这些点大致在一条由图25151(-),()(-),(kkkkkkbaxybafbaxybaf或令2T),(),,(minRbabaf求解二维最优化问题数据拟合问题最后就是拟合问题等还有许多其它的非线性乘问题这样的问题称为最小二例为什么要优化?•优化问题越来越多•优化问题越来越重要•优化问题越来越难1)大规模2)非线性3)多极值最优化问题的数学模型()0,1,...,()0,1,...,injgxipDxRhxjq其中约束集或可行域s.t.)(minDxxfqjxhpixgtsxfji,...,1,0)(,...,1,0)(..)(min::凸集，凸函数，凸优化问题：约束优化问题无约束优化问题DfRDRDnn两个重要主题•最小值的刻画*必要性条件*灵敏性分析*充分性条件*对偶性质*Lagrange乘子理论•算法的计算*迭代下降方法*逼近方法*对偶方法及primal-dual方法•网络路径问题•生产计划问题•资源分配问题•计算机辅助设计问题•均衡模型•数据拟合•自组织行为模型应用领域计算问题•迭代下降•逼近•收敛性分析•收敛速度•使用现有的软件包求解一个最优化问题Matlab，Lingo,Sedumi好的算法的标准•稳定性(robust)•有效性(efficiency)计算时间少，占用存储空间少•精确性(accuracy)最优解的概念•局部最优解：•全局最优解多元函数凸集集合凸性的判别方法（1）应用凸集的定义（2）由简单凸集（超平面、半平面、范数球…）通过保持凸性的运算得到C•集合交集•仿射函数：Ax+b•透视函数•线形分式函数的直线和经过21xx仿设集：包含集合中经过任意两点的直线凸组合有界集合没有方向界集合有方向的集合必定是无凸函数函数凸性的判定方法（1）定义（2）二阶连续可微函数，确定（3）f由简单凸函数通过保持凸性的运算得到*非负权重和*分段最大值函数*复合函数*最小非负权重和及仿射•非负乘数：凸凸•和：凸凸•仿射函数的复合：凸例凸函数分段最大值函数凸函数例的r个最大分量的和集合的支集函数最大距离对称矩阵的最大特征值复合最小值敛和全局收敛算法的收敛性：局部收**0**}{,)()(xxxUxxUxk收敛于点列时，使得当初始点的邻域局部收敛：存在点*0}{,xxxk收敛于点列点时意是某个较大集合中的任全局收敛：当初始点下面三种速度：关于收敛速度，主要有||-||||-||充分大时，成立使得当),1,0(线性收敛：若存在常数**1xxxxkkk**2120,||-||||-||kkpMkxxMxx特别地，当时，我们得到二次收敛，即二次收敛：若存在常数使得当充分大时，成立**1*1*01,||-||||-||||-||lim0||-||PkkkpkkMpkxxMxxxxxx超线性线性收敛：若存在常数及使得当充分大时，成立计算困难或使用方便算法的终止准则哪些是我们常用的？是给定的较小的正数,||-||)1(1kkxx||)(-)(||)2(1kkxfxf||||||-||(3)1kkkxxx|)(||)(-)(||(4)1kkkxfxfxf||)(||(5)1kxf整数是给定的某一较大的正）（KKk,6总结