1-2基础知识.ppt

工程优化硕士研究生课程 第一章 基础知识 背景知识 最优化问题举例 优化问题的数学模型及其分类 最优解与极值点 因此，在学习本科程时要尽可能了解如何由实际问题形成最优化的数学模型。 为了便于大家今后在处理实际问题时建立最优化数学模型，下面我们先把有关数学模型的一些事项作一些说明。 优化建模（modeling）：识别出给定问题的目标、 变量和约束的过程。 建立恰当模型：第一步、最重要的一步（太简单—不能给实际问题提供有用的信息；太复杂—不易求解） 选择特定算法：很重要—决定求解速度及质量（无通用优化算法，有求解特定类型优化问题的算法） 例5. 运输问题 已知有m个生产地点Ai, i 1,2,…，m。可供应某种物资，其供应量 产量 分别为ai，i 1，2，…，m，有n个销地Bj，j 1,2,…,n，其需要量分别为bj，j 1,2,…,n，从Ai到Bj运输单位物资的运价 单价 为cij，且求最优运输方案。 特殊运输问题——转运问题 容易计算出正弦曲线与折线间的面积（以此作为衡量误差的大小）为 由定义可知有如下两个定理（练习自证） 定理1：最优化问题的任意全局极小点必为局部极小值点. 定理2：若 为定义在 上的连 续函数,则 （1）以上问题的可行解的集合D为闭集 （2）以上问题的最优解的集合为闭集. 作业：P8, 1.1 作业 P8 1.1 第二章 基础知识 范数及其相关不等式 多元函数中值公式及其极值 二次函数 3. 向量内积：x , y ? Rn x , y 的内积: x, y xT y ? xiyi x1y1+ x2y2+ …+ xnyn x , y 的距离： ||x-y|| [ x-y T x-y ] 1/2 x 的长度： ||x|| [ xTx ] 1/2 三角不等式： ||x + y ||≤||x||＋||y|| 定理：设A为 n 阶对称正定矩阵，m与M分别为A的最小 与最大特征值，则 ，恒有 例：判定矩阵 是否正定. 解：对称矩阵Q的三个顺序主子式依次为： 作业 P38 2.1, 2.2, 2.4, 2.9-14,2.19, 2.20 后 ,2.32, 2.36 判定一个对称矩阵Q是不是正定的，可用Sylvester定理判定。 Sylvester定理：一个n×n对称矩阵Q是正定矩阵的充要条件 是矩阵Q的各阶主子式都是正的。 A是正定矩阵的等价条件 1 存在非奇异矩阵G，使得A GGT; 2 A的所有特征根大于零; 3 A的所有 顺序 主子式＞0; A是半正定矩阵等价条件 1 存在矩阵G，使得A GGT; 2 A的所有特征根非负; 3 A的所有 顺序 主子式非负; 因此知矩阵Q是正定的。 定理： 若二次函数 中Q正定，则它的等值面是同心椭球面族，且中心为 证明：作变换 ,代入二次函数式中： 根据解析几何知识，Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。由于上式中的 是常数，所以 的等值面也是以 为中心的 同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。 注意: 1 这族椭球面的中心 恰是二次目标函数的唯一极小点。 2 前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。 3 特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。 例：把二次函数 化为矩阵向量形式并检验Q是否正定. 如正定, 试用公式 求这个函数的极小点. 注意到： 由上例知Q正定，且 对如下问题 1.向量的几种范数: 椭球范数 A正定 l2范数 l1范数 l∞范数 lp范数 范数及其相关不等式 范数常见不等式 2. 矩阵范数: ||.||为某一向量范数 l1范数 列和的最大者 l∞范数 行和的最大者 l2范数也称谱范数 ATA最大特征值开平方 特别对方阵有 性质: 定义：设Q为n×n对称矩阵,若 ，均有 则称矩阵Q是正 定的。若 ，均有 ，则 称矩阵Q是半正定的。若 ，均有 ，则 称Q是负定的。若 , 均有 ,则称Q是半负定的. 4. 矩阵正定性: 回忆线性代数中正定二次型的讨论！ 判定一个对称矩阵Q是不是正定的，可用Sylvester定理判定。 Sylvester定理：一个n×n对称矩阵Q是正定矩阵的充要条件 是矩阵Q的各阶主子式都是正的。 A是正定矩阵的等价条件 1 存在非奇异矩阵G，使得A G