优化原理与方法1课件

优化原理与方法第1讲主讲人：刘国华1优化原理与方法参考书：汪树玉、刘国华等，系统分析〔第五章优化方法〕，浙江大学出版社；汪树玉等，优化原理、方法与工程应用，浙江大学出版社；甘应爱等，运筹学，清华大学出版社。期末考核方式：闭卷考试2§1根本知识优化VS

优选、方案比选

优化理论：数学规划、运筹学§1.1优化问题的数学模型例1.1生产安排问题有色砖无色砖资源限制产品利润300200机时2110人工3324颜料2083〔一〕设计变量设计变量x：需要通过优化过程选定的根本参数。优化的目的是寻找这些参数值的最优组合。n个设计变量x=[x1,x2,…xi,…,xn]T——n维问题优化计算量随着问题维数n的增加而显著增加多项式算法又称简单算法非多项式算法又称复杂算法一般的优化算法属于复杂算法维数灾难xk代表第k个迭代点；xik代表xk中的第i个分量4〔二〕目标函数目标函数f(x)：衡量一个设计或一种解决方案优劣程度的标准或指标，亦称评价函数。求目标函数极大化，记为max.f(x)；求目标函数极小化，记为min.f(x)；max.f(x)等价于-[min.-f(x)]；本课程统一采用“求极小〞的形式：min.f(x)优化目标标准式；优化目标转换5〔五〕优化技术应用的工作步骤〔1〕将实际问题抽象为优化数学模型〔2〕运用优化方法求解该模型，获得优化结果〔3〕对结果进行分析评估，必要时进一步完善模型重新求解〔4〕解决优化应用问题的关键解决优化问题首先需要塑造适宜的优化数学模型：所选取优化三要素应能够表达问题的实质；简繁适度；充分考虑拟选优化方法的特点和要求鉴于优化的理论、方法及相应软件已有很好的进展，工程应用专家需要做的工作是根据问题的特点选择适宜的优化方法和算法的参数，评估优化的成果8§1.2设计空间、可行域与目标等值线设计空间：n个设计变量x=[x1,

x2,

…

,

xn]T所张成的n维空间可行点：设计空间中满足所有约束条件的设计点：

可行域：设计空间中所有可行点构成的集合：目标等值线(/面)优化问题简洁表达：或或无约束优化：9§1.3全局最优解与局部最优解全局极小点(/最优点)x*：局部极小点(/最优点)x*：其中严格全局极小点(/最优点)x*：严格局部极小点(/最优点)x*：最优解通常指：{x*，f(x*)}，有时仅指x*寻优之难对于许多实际应用问题，常存在局部极小点。一般的优化方法，成功获得局部极小点已属不易；欲获取全局极小点，那么难上加难！研究全局最优问题需要对优化模型进行凸分析10§1.4凸集与凸函数〔一〕凸集凸集的定义：设n维欧氏空间(En)中的子集S，如果对于那么称S为凸集。凸集的几何含义：在凸集中任取两点，连接这两点的线段必亦属于该集合。凸集的内部无“空洞〞，边界不向内凹。凸集的简单例子圆域：平面：半空间：Sx1x211凸组合凸集的性质：两个凸集的交集仍为凸集：假设S1、S2为凸集，那么S1∩S2亦为凸集凸集的数乘仍为凸集假设S1为凸集，那么S=αS1={αx|x∈S1}亦为凸集别离定理、支撑定理〔二〕凸函数凸函数定义：设f(x)是定义在凸集SEn上的函数，如果对于那么称f(x)为凸函数。假设≤改为<，那么为严格凸函数；假设≤改为≥，那么为凹函数；假设≤改为>，那么为严格凹函数。f(x)xλx1+(1-λ)x2x2x1f(x1)f(x2)λf(x1)+(1-λ)

f(x2)f(λx1+(1-λ)x2)凸函数12f(x)x凹函数Sf(x)x非凸非凹函数S凸函数性质：凸函数在定义域内部是连续函数；多个凸函数的非负线性组合所得到的函数是凸函数。凸函数判别：假设函数一阶可微，凸函数的充要条件：假设函数二阶可微，凸函数的充分条件：正半定函数图形位于切线之上f(x)x13S1作业P4025.1