最优化方法课程教学课件.ppt

研究生课程《工程数学》之“最优化方法” 第一章 基本概念 一、最优化方法的基本概念 1. 什么是最优化？(Optimization) 最优化就是在复杂环境中遇到的许多决策中，挑选最优决策的一门科学。 2. 什么是最优化方法？ 最优化方法就是寻找最优决策的方法。 * 一、最优化方法的基本概念 3. 数学规划(Mathematical Programming) 数学规划是最优化理论的一个重要分支，它是指n个变量对单目标或多目标函数求极大或极小，而这些变量本身也可能受到某些条件(等式方程或不等式方程)的约束，其数学表达式为： min：求极小值，s.t.：约束条件 Subject to x是n维向量，x1, x2,…xn,决策变量 f(x)：目标函数(Objective function) 约束可以是等式，也可以是非等式 * * 一、最优化方法的基本概念 f(x)，Ci(x) ，均为线性函数 (1) 线性规划(Linear Programming, LP) * 一、最优化方法的基本概念 f(x)，Ci(x) ，其中之一均为线性函数 (2) 非线性规划(Nonlinear Programming, NLP) 没有约束条件Ci(x) (3) 无约束最优化问题(Unconstraint Optimization Problem) * 一、最优化方法的基本概念 主要是针对决策变量x1, x2,…xn来进行分类： 4 数学规划模型的分类 连续型 线性规划 LP (有、无约束) 非线性规划NLP (有、无约束) 离散型 整数规划 动态规划 图论与 网络优化 其它 决策论 对策论 排队论 * 二、数学预备知识 设向量 1. 向量与范数 范数，是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域，是一个函数，其为向量空间内的所有向量赋予非零的正长度或大小。用 表示 -范数 2-范数 1-范数 * 二、数学预备知识 范数不等式 范数的内积 三角不等式 柯西不等式 2. 多元函数的微分 对于多元函数u=f(x)， ，若在点 处对于自变量 的各分量的偏导数 都存在，则称函数u=f(x)在该点的一阶导数。 * 二、数学预备知识 (1) 梯度 (2) Hession矩阵 (黑塞矩阵) * 二、数学预备知识 (3) 多元函数的Taylor展开 一阶Taylor展开 二阶Taylor展开 或 * 二、数学预备知识 3.凸集与凸函数 (在无约束规划中常用到，具有很好的极值性) 对任意的 有 则C为凸集 (1) 凸集 凸集 非凸集 * 二、数学预备知识 (2) 下凸函数：∪； 下凹函数：∩ (3) 凸函数的定义： 设f(x)为定义在n维欧氏空间Rn中某个凸集S上的函数，若对任何实数α(0α1)以及S中不同的两点x(1)，x(2)， x(1) ≠ x(2)，恒有 则称f(x)为定义在凸集S上的凸函数。 * 二、数学预备知识 若对每一个α(0α1)，以及 x(1)，x(2) S (x(1) ≠ x(2)), 恒有 则称f(x)为定义在凸集S上的严格凸函数。 f(x) x f(x(1)) x(1) x(2) f(x(2)) 二、数学预备知识 * ?x(1)+(1- ?)x(2) f(?x(1)+(1- ?)x(2) ) f(x) x f(x(1)) x(1) x(2) f(x(2)) * 二、数学预备知识 f(x) x ?f( x(1) ) +(1- ?) f( x(2)) f(x(1)) f(x(2)) x(1) x(2) ?x(1)+(1- ?)x(2) f(?x(1)+(1- ?)x(2) ) * 二、数学预备知识 任意两点的函数值的连线上的点都在曲线的上方 f(x) x ?f( x(1) ) +(1- ?) f( x(2)) f(x(1)) f(x(2)) x(1) x(2) ?x(1)+(1- ?)x(2) f(?x(1)+(1- ?)x(2) ) * 二、数学预备知识 * 二、数学预备知识 (3) 凸函数的判定准则 一阶判定条件： f(x)在凸集S上具有一阶连续偏导数，则f(x)为S上凸函数的充要条件是 f(x) f(x(1)) x(1) x(2) f(x(2)) 因此，一阶判定的充要条件也可以表述为：任一点x(1)处的切线增量不超过函数的增量。 * 二、数学预备知识 (3) 凸函数的判定准则 二阶判定条件： f(x)在凸集S上具有二阶连续偏导数，则f(x)为S上凸函数的充