优化原理与方法1

优化原理与方法第1讲主讲人：刘国juliu@163.com1优化原理与方法参考书：汪树玉、刘国华等，系统分析（第五章优化方法），浙江大学出版社；汪树玉等，优化原理、方法与工程应用，浙江大学出版社；甘应爱等，运筹学，清华大学出版社。期末考核方式：闭卷考试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（三）约束条件约束条件：衡量一个设计或一种解决方案是否可行的限制条件。一般利用约束函数，通过等式约束和不等式约束表示：优化的数学模型优化数学模型三要素：设计变量目标函数约束条件约束条件标准式；约束条件转换6（四）优化问题分类（1）按目标函数的个数分单目标优化/多目标优化（2）按有无约束条件分无约束优化问题/有约束优化问题（3）按目标与约束函数的类型分线性规划/非线性规划二次规划、几何规划（4）按变量的性质分连续变量优化/0-1规划/整数规划/离散变量优化/组合优化/分布参数优化(设计变量为待定函数，目标和约束函数为泛函)（5）按优化阶段的可分性分(静态)优化/动态规划（6）按设计变量与参数的确定性分(确定性)优化/随机规划/模糊优化7（五）优化技术应用的工作步骤（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)是定义在凸集S

En上的函数，如果对于则称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