最优化理论与方法概述.ppt

第一章最优化问题与凸分析基础 在日常生活中 无论做什么事情 总是有多种方案可供选择 并且可能出现多种不同的结果 我们在做这些事情的时候 总是自觉不自觉的选择一种最优方案 以期达到最优结果 这种追求最优方案以达到最优结果的学科就是最优化 寻求最优方案的方法就是最优化方法 这种方法的理论基础就是最优化理论 而凸分析又是最优化理论的基础之一 1 最优化问题 最优化问题 求一个一元函数或多元函数的极值 在微积分中 我们曾经接触过一些比较简单的极值问题 下面通过具体例子来看看什么是最优化问题 1 1最优化问题的例子 例1对边长为a的正方形铁板 在四个角处剪去相等的正方形以制成方形无盖水槽 问如何剪法使水槽的容积最大 解 设剪去的正方形边长为x 由题意易知 此问题的数学模型为 配料 每磅配料中的营养含量 钙 蛋白质 纤维 每磅成本 元 石灰石谷物大豆粉 0 3800 000 000 0010 090 020 0020 500 08 0 01640 04630 1250 例2 混合饲料配合 设每天需要混合饲料的批量为100磅 这份饲料必须含 至少0 8 而不超过1 2 的钙 至少22 的蛋白质 至多5 的粗纤维 假定主要配料包括石灰石 谷物 大豆粉 这些配料的主要营养成分如下表所示 试以最低成本确定满足动物所需营养的最优混合饲料 解 根据前面介绍的建模要素得出此问题的数学模型如下 设是生产100磅混合饲料所须的石灰石 谷物 大豆粉的量 磅 1 2最优化问题的数学模型 一般形式向量形式其中 目标函数 不等式约束 等式约束 称满足所有约束条件的向量为可行解 或可行点 全体可行点的集合称为可行集 记为 若是连续函数 则是闭集 在可行集中找一点 使目标函数在该点取最小值 即满足 的过程即为最优化的求解过程 称为问题的最优点或最优解 称为最优值 定义1 整体 全局 最优解 若 对于一切 恒有则称是最优化问题的整体最优解 定义2 局部最优解 若 存在某邻域 使得对于一切 恒有则称是最优化问题的局部最优解 其中严格最优解 当 有则称为问题的严格最优解 f X 局部最优解 整体最优解 1 3最优化问题的分类 与时间的关系 静态问题 动态问题是否有约束条件 有约束问题 无约束问题函数类型 线性规划 非线性规划 2 梯度与Hesse矩阵 2 1等值线二维问题的目标函数表示三维空间中的曲面 在空间直角坐标系中 平面与曲面的交线在平面上的投影曲线为取不同的值得到不同的投影曲线 每一条投影曲线对应一个值 所以我们称此投影曲线为目标函数的等值线或等高线 当常数取不同的值时 重复上面的讨论 在平面上得到一族曲线 等值线 等值线的形状完全由曲面的形状所决定 反之 由等高线的形状也可以推测出曲面的形状 例在坐标平面上画出目标函数的等值线 解 因为当目标函数取常数时 曲线表示是以原点为圆心 半径为的圆 因此等值线是一族以原点为圆心的同心圆 如图所示 2 2n元函数的可微性与梯度 梯度 多元函数关于的一阶导数 Hesse矩阵 多元函数关于的二阶偏导数矩阵 例 求目标函数的梯度和Hesse矩阵 解 因为则又因为 故Hesse阵为 下面几个公式是今后常用到的 1 则 2 则 单位阵 3 Q对称 则 4 若 其中f 则 3 多元函数的Taylor展开 多元函数Taylor展开式在最优化理论中十分重要 许多方法及其收敛性的证明都是从它出发的 定理 设具有二阶连续偏导数 则 其中而0 1 多元函数Taylor展开其他形式 凸集和凸函数在非线性规划的理论中具有重要作用 下面给出凸集和凸函数的一些基本知识 5 凸集 凸函数和凸规划 例 规定 欧式空间是凸集 空集是凸集 单点集 x 为凸集 例 证明集合是凸集 其中 A为m n矩阵 b为m维向量 证明 任取 则所以 例 给定线性规划 其中 若令 则是凸集 凸集的性质 有限个凸集的交集仍然是凸集 设是凸集 则是凸集 设是凸集 则是凸集 凸集的和集仍然是凸集 设是凸集 则是凸集 推论 设是凸集 则也是凸集 其中 定义3极点 顶点 设D是凸集 若D中的点x不能成为D中任何线段上的内点 则称x为凸集D的极点 设D为凸集 X D 若X不能用X 1 D X 2 D两点的一个凸组合表示为X X 1 1 X 2 其中0 1 则称X为D的一个极点 定义2 凸组合 设X 1 X 2 X k 是n维欧式空间中的k个点 若存在 1 2 k满足0 i 1 i 1 2 k 使X 1X 1 2X 2 kX k 则称X为X 1 X 2 X k 的凸组合 多边形的顶点是凸集的极点 顶点 圆周上的点都是凸集的极点 顶点 性质1 f x 是凸集D上的凹函数的充要条件是 f x 是D上的凸函数 例 证明线性函数是上的凸函数 同理可证线性函数也是上的凹函数 证明 必要性 即 由Taylor公式 令得 设则 充分性 令 即 所以 同理 定理3 二阶条件 设D是R中非空开凸集 是定义在D上的二次可微函数 则是凸函数的充要条件为对x D 0 即Hesse矩阵半正定 n 证明 必要性 所以 由Taylor公式 令得 因为为开集 由一阶条件 所以 由p的任意性 半正定 充分性 其中 因为半正定 故为凸函数 所以 严格凸函数 充分性 其中 因为正定 故为严格凸函数 所以 例 判断下列函数的凹凸性 1 2 解 定义6 凸规划设D为凸集 是定义在D上的凸函数 则称规划问题为凸规划 例 线性规划是凸规划 例 数学规划易知 与都是凸函数 所以该规划是凸规划 对于一般的规划 P 其局部最优解不一定是全局最优解 其可行集也未必是凸集 但若 P 是凸规划 则有下面的结论 定理4 设规划 P 是凸规划 则 1 P 的可行集R为凸集 2 P 的最优解集合R 是凸集 3 P 的任何局部最优解都