Lecture最优化演示文稿

Lecture最优化演示文稿现在是1页\一共有72页\编辑于星期一Lecture最优化现在是2页\一共有72页\编辑于星期一要求与答疑安排答疑时间：

周一晚上8：00--10：00

周五下午2：00--4：00

或单独约定(欢迎通过邮箱提问)地点：SC1002E总成绩=平时成绩（30%）+期末成绩(70%）现在是3页\一共有72页\编辑于星期一参考书《最优化理论与算法》陈宝林编著《ConvexOptimization》StephenBoyd,LievenVandenberghe现在是4页\一共有72页\编辑于星期一第一讲

最优化方法的主要内容线性规划线性规划的基本性质；单纯形法；对偶理论非线性规划

无约束优化:

最优性条件；算法约束优化:

KKT条件；算法

现在是5页\一共有72页\编辑于星期一一、运筹学（OR）发展简介运筹学在国外英国称为OperationalResearch美国称为OperationsResearch起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。二战后运筹学应用于经济管理领域（LP、计算机）1948年英国首先成立运筹学会；1952年美国成立。1952年，Morse和Kimball出版《运筹学方法》1959年成立国际运筹学联合会现在是6页\一共有72页\编辑于星期一运筹学在国内中国古代朴素的运筹学思想1956年成立运筹学小组1958年提出运输问题的图上作业法1962年提出中国邮路问题1964年华罗庚推广统筹方法我国于1982年加入国际运筹学联合会，并于1999年8月组织了第15届大会现在是7页\一共有72页\编辑于星期一二、运筹学的定义运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience现在是8页\一共有72页\编辑于星期一三、运筹学的工作步骤明确问题建立模型设计算法整理数据求解模型评价结果简化？

满意？YesNoNo明确问题建立模型设计算法整理数据求解模型评价结果现在是9页\一共有72页\编辑于星期一运筹学的主要特点：运筹学研究和解决问题的基础是最优化技术，并强调系统整体最优。运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性。5.运筹学具有强烈的实践性和应用的广泛性。4.运筹学研究和解决问题的效果具有连续性。运筹学研究和解决问题的方法具有显著的系统分析特征，其各种方法的运用，几乎都需要建立数学模型和利用计算机进行求解。现在是10页\一共有72页\编辑于星期一ModelClassificationsOptimizationproblemsaregenerallydividedintoLinearandNonlinearproblemsbasedupontheobjectiveandconstraintsoftheproblemLinearOptimization:IfboththeobjectiveandtheconstraintsarelinearoraffinefunctionsLinearlyConstrainedOptimization:IftheconstraintsarelinearoraffinefunctionsNonlinearOptimization:IfboththeobjectiveandtheconstraintscontainnonlinearfunctionsTherearevarioussub-classificationsamongnonlinearproblemse.g.quadratic,convex,etc.Thereareintegerprogram,constrained,unconstrained,etc.现在是11页\一共有72页\编辑于星期一Whatdoyoulearn?Models---theart:HowwechoosetorepresentrealproblemsTheory---thescience:Whatweknowaboutdifferentclassesofmodels;e.g.necessaryandsufficientconditionsforoptimalityAlgorithms---thetools:Howweapplythetheorytorobustlyandefficientlysolvepowerfulmodels现在是12页\一共有72页\编辑于星期一PortfolioManagementLetrdenotetheexpectedreturnvectorandVdenotetheco-variancematrixofaninvestmentportfolio,andletxbetheinvestmentproportionvector.Then,onemanagementmodelis:whereeisthevectorofallones.Thisisaquadraticprogram.现在是13页\一共有72页\编辑于星期一RobustPortfolioManagementInrealapplications,randVmaybeestimatedundervariousscenarios,sayriandVifori=1,2,...,m.Thisiscalledquadraticallyconstrainedoptimization.现在是14页\一共有72页\编辑于星期一

把某种货物从m个工厂运到n个商店去，其中每个工厂的库存量为a1,a2,…,am,各商店的需求量为b1,b2,…,bn,从工厂i到商店j的运费（每单位货物）为cij,确定从工厂i到商店j的运输量xij(i=1,…,m,j=1,…,n),使在满足供求的条件下，总的运费最小。运输问题现在是15页\一共有72页\编辑于星期一总结

目标函数用决策变量的线性（或非线性）函数来表示。按问题的不同，要求目标函数实现最大化和最小化。最优化问题的共同特征：

每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案。

存在一定的约束条件，这些约束条件可以用一组线性（或非线性）等式或线性（或非线性）不等式来表示。现在是16页\一共有72页\编辑于星期一基本概念可行点（可行解）：在线性规划和非线性规划中，满足约束条件的点．可行集或可行域S：全体可行点组成的集合．无约束问题：如果一个问题的可行集是整个空间．对于一个规划问题，下面三种情况必占其一：(1)S＝Φ，则称该问题无解或不可行；(2)S≠Φ，但目标函数在S上无界，则称该问题无界；(3)S≠Φ且目标函数有有限的最优值，则称该问题有（有限的）最优解．现在是17页\一共有72页\编辑于星期一定义１：设f(x)为目标函数，S为可行域，x0∈S，若对∀x∈S,有f(x)≥f(x0),则x0称为极小化问题minf(x)，x∈S的全局最优解．定义２：设f(x)为目标函数，S为可行域，若存在x0的ε邻域

使得对∀x∈S∩Nε(x0)，有f(x)≥f(x0),则x0称为极小化问题minf(x)，x∈S的局部最优解．现在是18页\一共有72页\编辑于星期一

预备知识

线性相关与线性无关：现在是19页\一共有72页\编辑于星期一范数现在是20页\一共有72页\编辑于星期一集合

内点：

补集：

开集：

闭集：

有界集：

紧集：有界闭集称为紧集．现在是21页\一共有72页\编辑于星期一集合的性质：现在是22页\一共有72页\编辑于星期一函数的展开梯度：Hesse矩阵：现在是23页\一共有72页\编辑于星期一Taylor展开式定理：现在是24页\一共有72页\编辑于星期一二次型的正定性定义：定理：现在是25页\一共有72页\编辑于星期一二次型的半正定性定义：定理：现在是26页\一共有72页\编辑于星期一凸集(convexset)定义：设x,y为欧式空间En中相异的两个点，则点集

P={λx+(1-λ)y|λ∈R}

称为通过x和y的直线.定义：设S⊆En,若对∀x(1),x(2)∈S及∀λ∈[0,1],都有

λx(1)+(1-λ)x(2)∈S

则称S为凸集.

设x(1),x(2)，…,x(k)∈S,称

λ1x(1)+λ2x(2)+…+λkx(k)(其中λ1+λ2+…+λk=1)为x(1),x(2),…,x(k)的凸组合.现在是27页\一共有72页\编辑于星期一H={x|pTx＝a}超平面(hyper-plane)H-={x|pTx≤a}（闭）半空间L={x|x=x(0)+λd,λ≥0}射线现在是28页\一共有72页\编辑于星期一凸集的性质设S1和S２为En中的两个凸集，β是实数，则(1)

βS1

={βx|x∈S1}(2)

S1∩S2(3)

S1+S２={x(1)+x(2)|x(1)∈S1，x(2)∈

S2}(4)

S1-S２={x(1)-x(2)|x(1)∈S1，x(2)∈

S2}都是凸集。现在是29页\一共有72页\编辑于星期一凸锥和多面体(polyhedron)定义：定义：非空有界的多面体称为多胞形(polytope)现在是30页\一共有72页\编辑于星期一极点(extremepoint)定义：凸集凸集极点设则称点．现在是31页\一共有72页\编辑于星期一极方向(extremedirection)定义：现在是32页\一共有72页\编辑于星期一Exampled(1)d(2)现在是33页\一共有72页\编辑于星期一Proof现在是34页\一共有72页\编辑于星期一Proofcontinued现在是35页\一共有72页\编辑于星期一定理：证明：现在是36页\一共有72页\编辑于星期一多面集的表示定理定理：设S={x|Ax=b,x≥0}为非空多面集，则有极点集非空，且存在有限个极点极方向集合为空集的充要条件是S有界；若S无界，则存在有限个极方向的充要条件是M.S.Bazaraa,J.J.Jarvis,LinearProgrammingandNetworkFlows,NewYork:Wiley,1977.现在是37页\一共有72页\编辑于星期一凸集分离定理

定义：现在是38页\一共有72页\编辑于星期一定理1：证明：现在是39页\一共有72页\编辑于星期一定理1：证明：现在是40页\一共有72页\编辑于星期一定理1：证明：现在是41页\一共有72页\编辑于星期一Remark：现在是42页\一共有72页\编辑于星期一定理2:证明：现在是43页\一共有72页\编辑于星期一定理3:证明：现在是44页\一共有72页\编辑于星期一推论4:现在是45页\一共有72页\编辑于星期一定理5:证明：现在是46页\一共有72页\编辑于星期一定理6:现在是47页\一共有72页\编辑于星期一现在是48页\一共有72页\编辑于星期一Farkas引理：证明：现在是49页\一共有72页\编辑于星期一现在是50页\一共有72页\编辑于星期一现在是51页\一共有72页\编辑于星期一现在是52页\一共有72页\编辑于星期一现在是53页\一共有72页\编辑于星期一凸函数凸函数：设S是En中的非空凸集，f(x)是定义在S上的实函数，如果对于每一对x1，x2S及每一个a，0≤a≤1,都有

f(ax1+(1－a)x2)≤af(x1)+(1－a)f(x2)则称函数f(x)为S上的凸函数．上式中，若≤变为<，则称为严格凸函数。若-f(x)为S的凸函数，则称f(x)为S上的凹函数．(a)严格凸x凸x非凸x(b)(c)现在是54页\一共有72页\编辑于星期一凸函数性质

(1)

设f1(x)，f2(x)是凸集S上的凸函数，则函数f1(x)+f2(x)在S上也是凸函数。(2)

设f(x)是凸集S上的凸函数，则对任意的a≥0，函数af(x)是凸的。推广：设f1(x)，f2(x),…,fk(x)是凸集S上的凸函数，ai≥0,则a1f1(x)+a2f2(x)+…+akfk(x)也是凸集S上的凸函数.(3)

设f(x)是凸集S上的凸函数，对每一个实数c，则集合(levelset)Sc＝{x|xS，f(x)c}是