优化原理与方法1

1、1,优化原理与方法,第 1 讲,2,优化原理与方法,参考书： 汪树玉、刘国华 等， 系统分析（第五章 优化方法），浙江大学出版社； 汪树玉 等， 优化原理、方法与工程应用，浙江大学出版社； 甘应爱 等， 运筹学，清华大学出版社。 期末考核方式：闭卷考试,3,1 基本知识,优化 VS 优选、方案比选 优化理论：数学规划、运筹学 1.1 优化问题的数学模型 例1.1 生产安排问题,4,（一）设计变量 设计变量x：需要通过优化过程选定的基本参数。优化的目的是寻找这些参数值的最优组合。 n个设计变量 x =x1,x2,xi ,xnTn维问题 优化计算量随着问题维数n的增加而显

2、著增加 多项式算法 又称 简单算法 非多项式算法 又称 复杂算法 一般的优化算法 属于 复杂算法 维数灾难 xk代表第k个迭代点； xik 代表xk中的第i个分量,5,（二）目标函数 目标函数 f(x)：衡量一个设计或一种解决方案优劣程度的标准或指标，亦称评价函数。 求目标函数极大化，记为 max. f(x)； 求目标函数极小化，记为 min. f(x)； max. f(x) 等价于 -min. - f(x)； 本课程统一采用“求极小”的形式： min. f(x),优化目标标准式； 优化目标转换,6,（三）约束条件 约束条件：衡量一个设计或一种解决方案是否可行的限制条件。一般利用约束函数，通过

3、等式约束和不等式约束表示： 优化的数学模型,优化数学模型三要素： 设计变量 目标函数 约束条件,约束条件标准式； 约束条件转换,7,（四）优化问题分类 （1）按目标函数的个数分 单目标优化 / 多目标优化 （2）按有无约束条件分 无约束优化问题 / 有约束优化问题 （3）按目标与约束函数的类型分 线性规划 / 非线性规划 二次规划、几何规划 （4）按变量的性质分 连续变量优化/0-1规划/整数规划/离散变量优化/组合优化 / 分布参数优化(设计变量为待定函数，目标和约束函数为泛函) （5）按优化阶段的可分性分 (静态)优化 / 动态规划 （6）按设计变量与参数的确定性分 (确定性)优化 / 随

4、机规划 / 模糊优化,8,（五）优化技术应用的工作步骤 （1）将实际问题抽象为优化数学模型 （2）运用优化方法求解该模型，获得优化结果 （3）对结果进行分析评估，必要时进一步完善模型重新求解 （4）解决优化应用问题的关键 解决优化问题首先需要塑造合适的优化数学模型： 所选取优化三要素应能够体现问题的实质； 简繁适度； 充分考虑拟选优化方法的特点和要求 鉴于优化的理论、方法及相应软件已有很好的进展，工程应用专家需要做的工作是根据问题的特点选择合适的优化方法和算法的参数，评估优化的成果,9,1.2 设计空间、可行域与目标等值线 设计空间：n个设计变量x=x1, x2, , xnT所张成的n维空间

5、可行点：设计空间中满足所有约束条件的设计点： 可行域：设计空间中所有可行点构成的集合： 目标等值线(/面) 优化问题简洁表达： 或 或 无约束优化：,10,1.3 全局最优解与局部最优解 全局极小点(/最优点) x*： 局部极小点(/最优点) x*： 其中 严格全局极小点(/最优点) x*： 严格局部极小点(/最优点) x*： 最优解 通常指：x*，f ( x*) ， 有时仅指 x* 寻优之难 对于许多实际应用问题，常存在局部极小点。 一般的优化方法，成功获得局部极小点已属不易；欲获取全局极小点，则难上加难！ 研究全局最优问题需要对优化模型进行凸分析,11,1.4 凸集与凸函数 （一）凸集 凸

6、集的定义：设n维欧氏空间(En)中的子集S，如果对于 则称S为凸集。 凸集的几何含义： 在凸集中任取两点，连接这两点的线段必亦属于该集合。 凸集的内部无“空洞”，边界不向内凹。 凸集的简单例子 圆域： 平面： 半空间：,S,x1,x2,凸组合,12,凸集的性质： 两个凸集的交集仍为凸集： 若S1、S2为凸集，则S1S2亦为凸集 凸集的数乘仍为凸集 若S1为凸集，则S= S1 =x| xS1亦为凸集 分离定理、支撑定理 （二）凸函数 凸函数定义：设f (x)是定义在凸集S En上的函数，如果对于 则称f (x)为凸函数。 若改为，则为严格凹函数。,凸函数,13,凸函数性质： 凸函数在定义域内部是连续函数； 多个凸函数的非负线性组合所得到的函数是凸函数。 凸函数判别： 若函数一阶可微，凸函数的充要条件： 若函数二阶可微，凸函数的充分条件： 正半定,函数图形