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)