Lecture最优化演示文稿

Lecture最优化演示文稿目前一页\总数七十二页\编于十四点Lecture最优化目前二页\总数七十二页\编于十四点要求与答疑安排答疑时间：

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

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

或单独约定(欢迎通过邮箱提问)地点：SC1002E总成绩=平时成绩（30%）+期末成绩(70%）目前三页\总数七十二页\编于十四点参考书《最优化理论与算法》陈宝林编著《ConvexOptimization》StephenBoyd,LievenVandenberghe目前四页\总数七十二页\编于十四点第一讲

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

无约束优化:

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

KKT条件；算法

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

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

把某种货物从m个工厂运到n个商店去，其中每个工厂的库存量为a1,a2,…,am,各商店的需求量为b1,b2,…,bn,从工厂i到商店j的运费（每单位货物）为cij,确定从工厂i到商店j的运输量xij(i=1,…,m,j=1,…,n),使在满足供求的条件下，总的运费最小。运输问题目前十五页\总数七十二页\编于十四点总结

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

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

存在一定的约束条件，这些约束条件可以用一组线性（或非线性）等式或线性（或非线性）不等式来表示。目前十六页\总数七十二页\编于十四点基本概念可行点（可行解）：在线性规划和非线性规划中，满足约束条件的点．可行集或可行域S：全体可行点组成的集合．无约束问题：如果一个问题的可行集是整个空间．对于一个规划问题，下面三种情况必占其一：(1)S＝Φ，则称该问题无解或不可行；(2)S≠Φ，但目标函数在S上无界，则称该问题无界；(3)S≠Φ且目标函数有有限的最优值，则称该问题有（有限的）最优解．目前十七页\总数七十二页\编于十四点定义１：设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的局部最优解．目前十八页\总数七十二页\编于十四点

预备知识

线性相关与线性无关：目前十九页\总数七十二页\编于十四点范数目前二十页\总数七十二页\编于十四点集合

内点：

补集：

开集：

闭集：

有界集：

紧集：有界闭集称为紧集．目前二十一页\总数七十二页\编于十四点集合的性质：目前二十二页\总数七十二页\编于十四点函数的展开梯度：Hesse矩阵：目前二十三页\总数七十二页\编于十四点Taylor展开式定理：目前二十四页\总数七十二页\编于十四点二次型的正定性定义：定理：目前二十五页\总数七十二页\编于十四点二次型的半正定性定义：定理：目前二十六页\总数七十二页\编于十四点凸集(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)的凸组合.目前二十七页\总数七十二页\编于十四点H={x|pTx＝a}超平面(hyper-plane)H-={x|pTx≤a}（闭）半空间L={x|x=x(0)+λd,λ≥0}射线目前二十八页\总数七十二页\编于十四点凸集的性质设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}都是凸集。目前二十九页\总数七十二页\编于十四点凸锥和多面体(polyhedron)定义：定义：非空有界的多面体称为多胞形(polytope)目前三十页\总数七十二页\编于十四点极点(extremepoint)定义：凸集凸集极点设则称点．目前三十一页\总数七十二页\编于十四点极方向(extremedirection)定义：目前三十二页\总数七十二页\编于十四点Exampled(1)d(2)目前三十三页\总数七十二页\编于十四点Proof目前三十四页\总数七十二页\编于十四点Proofcontinued目前三十五页\总数七十二页\编于十四点定理：证明：目前三十六页\总数七十二页\编于十四点多面集的表示定理定理：设S={x|Ax=b,x≥0}为非空多面集，则有极点集非空，且存在有限个极点极方向集合为空集的充要条件是S有界；若S无界，则存在有限个极方向的充要条件是M.S.Bazaraa,J.J.Jarvis,LinearProgrammingandNetworkFlows,NewYork:Wiley,1977.目前三十七页\总数七十二页\编于十四点凸集分离定理

定义：目前三十八页\总数七十二页\编于十四点定理1：证明：目前三十九页\总数七十二页\编于十四点定理1：证明：目前四十页\总数七十二页\编于十四点定理1：证明：目前四十一页\总数七十二页\编于十四点Remark：目前四十二页\总数七十二页\编于十四点定理2:证明：目前四十三页\总数七十二页\编于十四点定理3:证明：目前四十四页\总数七十二页\编于十四点推论4:目前四十五页\总数七十二页\编于十四点定理5:证明：目前四十六页\总数七十二页\编于十四点定理6:目前四十七页\总数七十二页\编于十四点目前四十八页\总数七十二页\编于十四点Farkas引理：证明：目前四十九页\总数七十二页\编于十四点目前五十页\总数七十二页\编于十四点目前五十一页\总数七十二页\编于十四点目前五十二页\总数七十二页\编于十四点目前五十三页\总数七十二页\编于十四点凸函数凸函数：设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)目前五十四页\总数七十二页\编于十四点凸函数性质

(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