最优化方法全部ppt课件

开始 最优化方法 最优化课件研制组 退出 主讲 张京 最优化方法 最优化方法为了使系统达到最优的目标所提出的各种求解方法称为最优化方法 最优化方法是在第二次世界大战前后 在军事领域中对导弹 雷达控制的研究中逐渐发展起来的 最优化方法解决问题一般步骤 1 提出需要进行最优化的问题 开始收集有关资料和数据 2 建立求解最优化问题的有关数学模型 确定变量 列出目标函数和有关约束条件 3 分析模型 选择合适的最优化方法 4 求解方程 一般通过编制程序在电子计算机上求得最优解 5 最优解的验证和实施 随着系统科学的发展和各个领域的需求 最优化方法不断地应用于经济 自然 军事和社会研究的各个领域 第1章预备知识 1 1经典极值问题1 例子 2 数学模型 第一 无约束极值问题 或 解法 解方程组 第二 仅含等式约束的极值问题 或 解法 Lagrange乘子法 1 2实例数据拟合问题原料切割问题运输问题营养配餐问题分配问题 1 3基本概念1 最优化问题的向量表示法设 则 1 以向量为变量的实值函数定义向量间的序关系 定义1 1 等于 小于 严格小于 由此 2 以向量为变量的实向量值函数最优化问题的一般形式 3 2 最优化问题的分类 试验问题 用于检验 比较最优化方法优劣的一些最优化问题 3 术语 目标函数 等式约束 不等式约束 容许解 点 容许集 求解问题 3 是指 在容许集 中找一点 目标函数 在该点取极小值 即对于容许集中的任 总有 意一点 最优点 极小点 最优值 最优解 严格极小点 局部 非严格极小点 严格极小点 非严格极小点 全局 使得 到目前为止 大多数最优化算法求到的都是局部极小点 为了求得全局极小点 一种解决办法是 先求出所有的局部极小点 然后再从中找出全局极小点 4 极大值问题与极小值问题的关系 1 4二维问题图解法 二维极值问题有时可以用图解的方式进行求解 有明显的几何解释 例求解 图解法的步骤 显然 取 并画出相应的曲线 称之为等值线 确定极值点位置 并用以往所学方法求之 易知本题的极小值点 再复杂点的情形见P13上的例1 7 虽然三维及以上的问题不便于在平面上画图 图解法失效 但仍有相应的等值面的概念 且等值面具有以下性质 有不同函数值的等值面互不相交 因目标函数是单值函数的缘故 等值面不会在区域的内部中断 除了极值点所在的等值面以外 这是由于目标函数是连续函数的缘故 令 等值面稠密的地方 目标函数值变化得比较快 等值面稀疏的地方 目标函数值变化得比较慢 在极值点附近 等值面 等值线 一般近似地呈现为同心椭球面族 椭圆线族 1 5梯度和Hesse矩阵 本段讨论都基于对函数 以下及今后的讨论中还经常要用到以下一些向量的知识 可微的假定 与 记作 向量也常用希腊字母 等表示 向量内积的性质 对称性 线性性 当且仅当 时 正定性 向量的内积设 则 称为向量 的内积 其实 向量的长 单位向量 向量的夹角 向量的正交 正交性 1 可微 定义1 7设 如果存在 维向量 对于可任意小的 维非零向量 总有 在点 那么称函数 处可微 若令 便得到 1 9 的等价形式 1 10 2 梯度 定理1 1若 在点 处可微 则 在该点关于各个变量的一阶偏导数存在 并且 定义1 8以函数 的 个偏导数为分量的向量 称为 在点 处的梯度 记为 梯度也称为函数 关于变量 于是 1 10 可写为 这个公式与一元函数展开到两项的Taylor公式是相对的 梯度的性质 当梯度 连续时 第一 若 则 必垂直于 过点 处的等值面 的一阶偏导数 第二 梯度方向是函数具有最大变化率的方向 下面以 为例来解释这个性质 上图是该函数的等值线图 今考虑一点 不妨取坐标为 设想有 出发沿某个方向移动到了点 其坐标 那么目标函数值将产生如下变化量 一动点从 设为 假定 试问 动点沿哪个方向移动会使 目标函数值有最多的下降或上升 从图上看 这相当于问 在以点 为圆心 以1为半径 的圆周上 哪一个点具有最大的或最小的目标函数值 为了一般地描述函数 在点 处沿 情况及变化速度 须引入上升方向和下降方向及方向导数的概念 方向的变化 函数 在点 处沿 方向的变化反映的是函数 在一条直线上的变化 空间中由一点 和一方向 所确定的直线方程为 上升方向和下降方向设 是连续函数 若存在 对于 都有 则称 方向是 在点 处的上升方向 若存在 对于 都有 则称 方向是 在点 处的下降方向 定义1 9设 在点 处可微 是非 方向上的单位向量 如果极限 零向量 存在 则称其为函数 在点 处沿 方向的方向导数 记作 思考 与 的异同 若 则 方向是 在点 处的上升方向 根据极限理论 易见 若 则 方向是 在点 处的下降方向 因此 方向导数的正负决定了函数值的升降 定理1 2设 在点 处可微 则 其中 是非零向量 方向上的单位向量 定理1 2又表明 只要 则 方向是 在点 处的上升方向 只要 则 方向是 在点 处的下降方向 函数值升降的快慢则是由方向导数绝对值的大小决定的 绝对值越大 升或降的速度就越快 绝对值越小 升或降的速度就越慢 这是因为 据此有 等号成立当且仅当 与 同方向或与 同方向 且当 与 同方向时 取到最大值 当 与 同方向时 取到最小值 若 是锐角 则 若 是钝角 则 因此 方向导数又可以称为函数 在点 处沿 方向的变化率 使函数值下降最快的方向称为最速下降方向 最速下降方向为 例1 8P19 几个常用函数的梯度公式 1 若 则 即 2 3 4 2 Hesse矩阵 问 函数 关于变量 的二阶导数又是什么 先来看什么是向量值函数的可微 定义1 11设 若 的所有分量 在点 都可微 则称向量值函数 在点 处可微 定义表明 在点 处可微 则 成立 其用向量形式可简单地表示为 其中 称为向量值函数 在点 处的导数 而 称为向量值函数 在点 处的Jacobi矩阵 设 具有二阶连续偏导数 且 则矩阵 称为函数 关于变量 的二阶导数 简记为 也称为多元实值函数 的Hesse矩阵 例1 9P21 几个特殊的向量值函数的导数公式 1 2 3 4 设 其中 则 利用 4 可得多元函数展开到三项的Taylor公式 1 29 或 1 31 这个公式与一元函数展开到三项的Taylor公式是相对应的 多元函数的Taylor展开式在最优化方法中十分重要 许多方法及其收敛性的证明都是从它出发的 1 凸集 1 6凸函数与凸规划 直观上 凸集就是空间中内部无 洞 边界又不向内凹的一些点的集合 其基本特征是该集合中任意两点间的线段仍然属于这个集合 非凸集 凸集 空间中两点间的线段是由点的凸组合定义的 定义1 12设 是 中的 个已知点 点 若存在满足 的非负实数 对于 使得 则称 是 的一个凸组合 又若 是满足 的正实数 则称 是 的一个严格凸组合 两点 的凸组合 恰是连接两点的 的线段 线段 而严格凸组合是不含端点 定义1 13设集合 如果 中任意两点的 那么集合 称为凸集 任意凸组合仍然属于 规定 空集是凸集 思考 空间中三个不同点的凸组合的集合 空间中四个不同点的凸组合的集合 常见的凸集有超平面 直线 球 定理1 5凸集的交集是凸集 2 凸函数 定义1 16设 其中 为凸集 若对于 中的任意互异两点 和任意一对满足 的非负实数 总有 则称 是定义在凸集 上的凸函数 又若对于任意 的正实数 总有 一对满足 则称 是定义在凸集 上的严格凸函数 若 是凸集 上的 严格 凸函数 则称 是凸集 上的 严格 凹函数 凸函数有以下重要性质 定理1 6 1 若 是定义在凸集 上的凸函数 是 也是 上的凸函数 任意的非负实数 则 2 若 是定义在凸集 上的凸函数 则 也是 上的凸函数 由定理1 6易见 定义在凸集上的任意有限个凸函数的任意非负组合仍然是凸函数 例1 10 定理1 7设 其中 为非空凸集 若 是凸函数 则对于任意实数 水平集 是凸集 证若 是空集 则是凸集 以下设 非空 任取 则 又设 但 根据 的凸性 必有 即 因此 是凸集 判断一个函数是否为凸函数 一般说来 是比较困难的 但当函数可微时 有以下几个判定定理 定理1 7设 定理1 8设 是可微函数 其中 为 凸集 则 为凸函数的充要条件是对于 中的任意两点 都有 为严格凸函数的充要条件是对于 中的任意 都有 两个互异点 定理1 8有明显直观的几何解释 可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面 切线 都不在曲面 曲线 的上方 右图画出了一维的情形 定理1 9设 是二次可微函数 为非 空开凸集 则 为 上凸函数的充要条件是Hesse矩阵 在 上处处半正定 定理1 10设 是二次可微函数 为非 空凸集 若 的Hesse矩阵 在 上处处正定 则 是 上的严格凸函数 这个命题的逆命题不真 例如 在 上为严格凸函数 在 处是半正定的 但是它的Hesse矩阵 3 凸规划 设 是定义在非空凸集 上的凸函数 则形式为 1 36 的最优化问题称为凸规划问题 简称凸规划 换言之 定义在凸集上的凸函数的极小化问题是凸规划问题 若 都是 上的凹函数 都是 上的线性函数 容易验证集合 是凸集 在这种情况下 凸规划 1 36 可以表示成如下形式 1 37 下面的定理指出了凸规划的一些重要性质 定理1 11设 是凸规划 1 36 的局部极小点 则 i 是 1 36 的全局极小点 ii 当 是严格凸函数时 是 1 36 的唯一极小点 iii 1 36 的全部极小点的集合是凸集 定理1 12设 是可微凸函数 是非空 凸集 则 是凸规划 1 36 的极小点的充要 中任意一点 总有 条件是 对于 定理1 12表明 凸规划 1 36 在最优点处的任何容许方向 定义4 3 都不是下降方向 推论1 13设 是可微凸函数 是非空 凸集 若 使得 则 是凸规划 1 36 的全局极小点 4 二次函数与二次规划 函数 1 38 称为 元二次函数 其中 是对称矩阵 若 是正定的 则 1 38 称为正定 二次函数 注意到 于是由定理1 10得知 正定二次 函数是严格凸函数 在最优化算法构造中 正定二次函数起着特殊的作用 本书的许多章节都要涉及它 形式为 1 39 的最优化问题称为二次规划问题 简称二次规划 若 是半正定的或正定的 则 1 39 称为二次凸规划 定理1 14 一个 对称矩阵 为正定矩阵的充 要条件是 的各阶主子式皆大于零 开始 最优化方法 最优化课件研制组 退出 主讲 张京 最优化方法 1 7极小点的判定条件 函数 在局部极小点满足什么条件 反之 满足 什么条件的点是 的局部极小点 定理1 15设 具有一阶连续偏导数 是 的内点 若 是 的局部极小点 则 1 40 注意 条件式 1 40 不是充分的 仅仅是必要的 例如 在点 处的梯度是 但是点 是这个双曲抛物面的鞍点 而 不是极小点 根据定理1 15与推论1 13 容易得到凸规划问题全局极小点的一个一阶充分且必要条件 推论1 16设 是可微凸函数 是非空开凸集 则 是 1 36 的全局极小点的 充要条件是 定义1 17设 可微 若 则 称为 的驻点 驻点包括极大值点 极小值点和鞍点 定理1 17设 具有二阶连续偏导数 且 若 正定 则 是 的严格局部极小点 一般来说 这个定理仅具有理论意义 因为对于复杂的目标函数 Hesse矩阵不易求得 其正定性也很难判定 定理1 18设 具有二阶连续偏导数 且 若存在 的 邻域 使得 对于 都半正定 则 必是 的局部极小点 利用上节和本节的定理不难说明下面的两个论断 i 对于正定二次函数 是它的唯一极小点 ii 若多元函数在极小点处的Hesse矩阵是正定的 则在这个极小点附近其等值面近似地呈现为同心椭球面族 推证如下 i 首先求出二次函数的驻点 令 因为 是正定矩阵 所以解出唯一驻点为 1 41 因此根据推论1 13可以断定 是唯一的极小点 ii 设 是多元函数的极小点 并设 是充分 的一个等值面 靠近极小点 即 充分小 把 在点 处按Taylor公式展开 得到 上式右端第二项因为 是极小点而消失 再略去 第四项 那么二次曲面 1 42 就是等值面 的近似曲面 按假设 是正定的 因此 为中心的椭球面 1 42 是以 方程 这正是我们所要说明的 1 下降迭代算法 1 8算法及有关概念 在集合 上的迭代算法是指 开始 选定一个初始点 置 然后按某种规则 把第 次迭代点 映射为新的一点 记为 并置 这称为完成了第 次迭代 这个过程无限地进行下去 因此 规则 称为算法 就会产生一个点列 若点列 收敛于 则称算法 在 上是收敛的 否则 称算法 在 上是发散的 特别地 当 问题 1 6 的容许集时 若除满足计算终止准则的迭代点 是最优化 外 对于每个 都有 则称 为下降迭代 许多最优化方法都采用将多维问题转化为一维问题的处理方式 下面以无约束问题为例 说明采用这种方式时的下降算法的基本迭代格式 设第 次迭代点 已求得 若它不满足终止准则 对于可微目标函数 即 那么在该点必存在下降方向 是满足 的 按某种规则选取一个 例如 再沿这个方向适当地前进一步 即在直线 上确定一个新点 使得 这就完成了第 迭代 上式中的 称为搜索方向 称为步长因子 不过 计算机只能进行有限次迭代 因此 一般说来 数值计算不能求到精确解 而只能得到近似解 当迭代点满足事先给定的精度要求时 就终止计算 并把这个迭代点当作问题的最优解 在上数述迭代过程中 有两个规则需要确定 一个是 的选取规则 一个是步长因子 的选取规则 下降方向 不同的规则对应着不同的最优化方法 综上所述 无约束问题下降算法的基本迭代格式如下 选定初始点 置 按某种规则确定下降方向 按某种规则确定 使得 置 判定 是否满足终止准则 若满足 则打印 和 否则 置 转 算法流程图见P34图1 18 2 直线搜索及其性质 在搜索方向 已经确定的前提下 选取步长因子的 方法有多种 例如 取步长因子为某个常数 但在实际计算中 最常用的方法是直线搜索 又称一维搜索 即选取 使得 1 43 按这种方法确定的步长因子称为最优步长因子 这种选取方法是很自然的 既然下降方向已经确定 就应该沿这个方向找到使目标函数取极小值的点 2 直线搜索及其性质 在搜索方向 已经确定的前提下 选取步长因子的 方法有多种 例如 取步长因子为某个常数 但在实际计算中 最常用的方法是直线搜索 又称一维搜索 即选取 使得 1 43 按这种方法确定的步长因子称为最优步长因子 这种选取方法是很自然的 既然下降方向已经确定 就应该沿这个方向找到使目标函数取极小值的点 同时这又是容易办到的 因为 是以 为变量的一元函数 求一元函数极小点的迭代法称为直线搜索或一维搜索 许多最优化方法都采用将多维问题转化为一维问题的处理技术 因此可以说 一维搜索是最优化方法的一个重要支柱 这种方法的优点是 它使目标函数值在搜索方向上下降得最多 缺点是 计算量较大 在第3章的3 1节中将全面介绍直线搜索 为简便起见 今后用记号 1 44 表示从点 出发沿 方向对目标函数 作直线 在目标函数 确定的条件下 搜索得到极小点 1 44 等价于 1 45 直线搜索的一个重要性质 定理1 19设目标函数 具有一阶连续偏导数 若 则 证使用反证法 假设 则 或 1 47 1 48 1 47 表明 是点 处的下降方向 1 48 表明 是点 处的下降方向 这都与 相矛盾 故必有 1 46 的几何意义是明显的 若 是从点 出发沿 方向对目标函数 搜索得到的极小点 则 1 46 指出 梯度 搜索方向向量 正交 作直线 必与 又因为 与目标函数过点 的等值面 等直线 正交 所以搜索方向向量 与这个等值面 等直线 在点 处相切 3 计算终止准则 设某个算法产生的点列 收敛于 1 6 的最优解 现在的问题是 在计算机上计算时 计算到哪一个 迭代点才有把握地说它就是所求问题的 近似 最解 显然 当 小于预先给定的误差限时就可以 就是所求的最优解 认为 但事实上 是未知的 因而 无法计算 不过 由极限理论知道 当 与 都很小时 也必然很小 于是 在 数值计算中 可以用 1 51 作为计算终止的一个判定条件 其中 是预先给定的计算 终止的界限 今后称为终止限 但是 用 1 51 作为终止准则是不可靠的 因为 很小并不能保证 很小 下面图1中画出了一条一元目标函数的曲线及其有关的点 从图中可以看到 相邻两个迭代点 和 已经很 靠近了 但它们距极小点 却都很远 而且这两点的 目标函数值 和 还由极限理论知道 当 相差很大 很小时 也必然很小 因此 如果加上 1 52 这个条件 那么可靠性就会加强 上图2指出了只采用 1 52 也是不可靠的 虽然 与 相差很小 可 是相应的两个迭代点 和 却相距很远 它们距极 也很远 小点 需要注意的是 实际应用中 由于 和 所取的量 纲有时太大 这时如果仍然以 1 51 和 1 52 作为终止准则就太严格了 结果要么是用更多的计算才能使得 1 51 和 1 52 得到满足 而这是不划算的 要么是永远不能满足 解决这个问题的办法是 先对 和 作无量纲处理 然后再结合 1 51 和 1 52 给出 1 53 和 1 54 作为终止准则 此外 有一类无约束最优化方法在求解过程中利用了梯度 由于 为极小点的必要条件是 因此 当 满足 1 55 时 一般可以认为 就是所要求的最优解 由于条件不是 充分的 所以单独以 1 55 作为终止准则也是不可靠的 最后的结论是 对于使用导数的最优化方法 可按书上图所示的判别过程作为终止准则 对于不使用导数的最优化方法 则只需把图中涉及 的部分去掉 今后 统称为Himmelblau计算终止准则 简称H终止准则 例1 已知 求 解 例2 用图解法求解 解 画出目标函数 的等值线 画出等式约束 的图形 它是一条抛物线 画出不等式约束所代表的区域 容许集为抛物线的一段 最优解为目标函数的等值线与容许集的切点 即最优点满足方程 公切线平行 轴 切点为 代入得 解得 或 得切点 不在容许集上 最优点为 最优值点 交点 例3 用图解法求解 画出目标函数 的等值线 画出等式约束 解 的图形 它是一条抛物线 画出不等式约束所代表的区域 容许集为抛物线的一段 最优解为抛物线的端点 即方程 的解 最优值 目标函数的等值线与容许集的切点 即最优点满足方程 切点 点 不在容许集上 最优解 例4 设目标函数为 从点 出发 沿 的方向 作直线搜索 试求搜索到的极小点 并验证 解 例5 判别最优化问题是否为凸规划 解 正定 并用图解法求出最优点 从图上可判别出容许集为淡绿色区域 此区域为凸集 故此最优化问题为凸规划 用解析方法也可证明容许集为凸集 都为半平面 它们的交集为凸集 以下判别 为凸函数 各阶主子式非负 为凸函数 为凸集 即容许集为凸集 用一阶导数判别 的凸性 为凸函数 即容许集为凸集 为凸集 由图解法可求得局部极小点 它一定是此最优化问题的全局最优点 最优点满足条件 解得 为全局最优点 开始 最优化方法 最优化课件研制组 退出 主讲 张京 最优化方法 在最优化中 目标函数和约束函数皆为线性函数的优化问题称为线性规划 LP 它是相对简单的最优化问题 本章是有关线性规划的理论与求解方法的内容 第二章线性规划 2 1线性规划的各种形式 1 标准形式和典范形式 如下形式的线性规划 称为线性规划的标准形式 其中各 称为价格系数 各 采用向量 矩阵表示法 标准形式可以简写为 2 1 称为右端项 2 2 在进行理论分析时 有时需要把 表示成 这样 2 2 中的 又可写成 若 中有 个列向量可以合并成为单位矩阵 且 例如 如下线性规划 此时 2 2 则称为线性规划的典范形式 就呈现为典范形式 因为 和 可合并 成单位矩阵 不失一般性 假定单位矩阵位于前 列 即典范 形式呈现为 2 3 其中 用向量 矩阵表示法 那么 2 3 可简写成 2 4 2 一般形式 线性规划 2 5 3 一般形式与标准形式的关系 1 松弛变量 考虑 约束中的第 个不等式 2 6 引入非负变量 迫使 使不等式约束 2 6 变为等式约束 2 7 的非负变量 称为松弛变量 2 剩余变量 考虑 约束中的第 个不等式 2 7 2 8 引入非负变量 迫使 引入非负变量 迫使 使不等式约束 2 8 变为等约束 2 9 的非负变量 2 9 称为剩余变量 在引入 个松弛变量 个剩余变量后 线性规划 2 5 可化成标准形式 2 10 它含有 个变量 个等式约束 注意 新引入变量的价格系数全部设为零 因此 在 2 10 的目标函数中没有出现新变量 下面说明线性规划 2 5 与其标准形式 2 10 是等价的 首先 它们的容许点是一一对应的 且对应的容许点的函数值相等 因为若 是 2 5 的一个容许点 那么按 公式 2 7 和 2 9 引入非负的松弛变量和剩余变量 后 显然 将是 2 10 的 容许点 反之亦然 故 2 5 的容许点 与 2 10 的容许点 一一对应 又 2 5 与 2 10 的目标函数相同 且都只是 的函数 所以 2 5 与 2 10 所对应的容许点 的函数值相等 其次 若 是 2 10 的最 优点 它所对应的最优值为 那么 由前面的 证明可知 其前 个分量组成的向量 也一定 2 5 的最优点 反之亦然 因此 线性规划 2 5 与其标准形式 2 10 是等价的 该结论表明 可以只讨论标准线性规划 例2 1将线性规划 化为标准形式 并用图解法求解原问题 给出标准形式的解 解对第1个约束引入松弛变量 对第2个约束引入 于是 该线性规划的标准形式为 剩余变量 图解法求解原线性规划如下 最优解 在直线 与 的交汇处 即 相应的标准形式的最优解为 3 自由变量 以上讨论都考虑变量的取值是非负的 当变量的取值非正 那么它的负变量的取值即是非负的 实际中 如果某些变量没有这种约束 也就是说 某些变量可以任意取值 那么这些变量称为自由变量 自由变量可以通过以下两种方法把它消除 例如 假若 是自由变量 第一种方法 引入两个非负变量 和 令 2 11 将其代入到线性规划的目标函数和约束函数中 自由变量 就消除了 注意 求出新线性规划的最优点后 再利用 2 11 便可以定出 第二种方法 取一个包含 的等式约束 例如 由此解出 2 12 将此式代入到线性规划的目标函数和其他约束函数中 自由变量 也消除了 求出新线性规划的最优点后 利用 2 12 再定出 第一种方法将增加变量的数目 导致问题的维数增大 第二种方法正好相反 2 2基本定理 考虑标准线性规划 2 2 即 记容许集 不妨假定 1 极点与基本容许解 定义2 2有限个半空间的交称为凸多面体 半空间是凸集 故凸多面体是凸集 边界为直线或平面是多面体的几何特征 多面体 凸多面体 定义2 3有界的的凸多面体称为凸多胞形 凸多面体 凸多胞形 定理2 1线性规划 2 2 的容许集 是凸多面体 2 凸集的极点 与凸集相关的另一个重要概念是凸集的极点 定义2 5若凸集 中的某个点 不能表示为这个集合 中另外两个不同点的严格凸组合 即 则 称为凸集 的极点 3 基本容许解 当 2 2 的容许解又是 的基本解 时 就 称其为 2 2 的基本容许解 方程组 满足 基本 条件的的解称为 的基本解 的基本解是如何定义的呢 将 表示成向量形式 因为 故 中必含有 阶的可逆矩阵 称为 基 基 的每个列向量称为基向量 的其余列向量称为 非基向量 与基向量对应的变量称为基变量 与非基向量对应的变量称为非基变量 若基是单位矩阵 则称为标准基 非基变量取值皆为0的 解称为基本解 满足 的基本解称为线性规划 2 2 关于基 的基本 容许解 不失一般性 设 则 令 若 得基本解 么该基本解是关于基 的基本容许解 那 例2 3P48 定义2 10基变量取值皆不为0的基本解称为非退化的 否则称为退化的 若 2 2 的所有基本容许解都是非退化的 则线性规划 2 2 称为非退化的 否则称为退化的 例2 4P49 3 基本容许解与极点的关系 引理2 2设 则 是基本容许解 的正分量所对应的 的列向量线性 无关 定理2 3设 则 是 2 2 的基本容许解 是 的极点 从几何角度讲 例2 3中的约束条件 表示空间一条直线在第一象限中的直线段部分 如图所示 红线部分为容许集 有两个极点 和 它们恰恰是两个基本容许解 例2 4如图所示 有两个极点 和 推论2 4容许集 的极点个数有限 2 线性规划基本定理 引理2 5设 不妨设 且 线性相关 那么一定存在最多有 个正 分量的容许解 定理2 7线性规划 2 2 若有容许解 则必有基本 容许解 定理2 8线性规划 2 2 若有最优解 则必有最优基本容许解 从几何上看 解线性规划存在以下几种可能情形 唯一解无穷多解解无界无解 2 3单纯形法 由前述知 2 2 的容许集 是凸多面体 中的 极点个数有限 2 2 若有容许解 则必有基本容许解 若有最优解 则必有最优基本容许解 据此 对于线性规划 我们只关心基本容许解即可 因此 一个显而易见的求解方法是求出全部基本容许解 极点 比较目标函数值就能确定最优解 可是 当 数值较大时 这种 法的计算量相当大 逆矩阵也不易求 Dantzig给出的单纯形法基本上解决了这个问题 单纯形法的基本思想是 首先找到 求出 一个极点 基本容许解 并依据最 优性准则判断其最优性 如非最优 则沿凸多面体 条棱找到 迭代到 的一 使目标值降低 不找比 的 的下一个极点 基本容许解 的目标值高 数是有限的 所以在一定的条件下 总可以找到 迭代到 因为极点个 最优极点 最优基本容许解 或者说明解无界 如图所示 Dantzig单纯形法的思想涉及以下三个具体问题 有最优点解无界 一 初始基本容许解的产生 二 最优性准则 三 基本容许解的改进 1 最优性准则 考虑标准线性规划 2 21 设 为容许基 并不妨设 将 2 21 改写为 2 22 令 得关于 的基本容许解 目标函数值 设 为任一容许解 则由 2 22 解出 代入目标函数中得 令 于是 2 26 故 因为 因此 只要 必有 由此得到判断基本容许解是最优解的一个充分条件 定义2 11在标准线性规划 2 21 中 设 是一个 基 则 称为变量 关于基 的判别数 判别数的向量形式为 易知 定理2 9 线性规划最优性准则 在标准线性规划 2 21 中 设 是容许基 若所有变量关于基 的判别 数皆非正 则关于基 的基本容许解是最优解 定义2 12在标准线性规划 2 21 中 若关于基 基本容许解是最优解 则称 是最优基 例2 5考虑标准线性规划 试分别求关于基 和 的基本解 若是 容许解 则判别其最优性 解 关于 的基变量取值 故关于 的基本解 是基本容许解 计算 最优性准则未满足 因此不能断定 是否是最优解 因此关于 的基变量取值 故关于 的基本解 也是基本容许解 计算 最优性准则满足 因此断定 是最优解 2 基本容许解的改进 1 Gauss Jordan方程组 假定 是 2 21 的一个基 由 得等价方程组 记 则 2 28 可写成 2 28 2 29 2 29 称为关于基 的Gauss Jordan方程组 G J方程组 典范线性规划的主约束即是一个G J方程组 G J方程组的性质 一个基决定唯一的G J方程组 若 是容许基 则由其G J方程组可得出关于 的基本容许解 在G J方程组中 基变量的系数向量构成单位矩阵 性质 说明求新的基本容许解的过程实质上就是不同基的G J方程组间的转化过程 这个转化过程很容易实现 设 是新基 是用非 基向量 替换 中的 得到的矩阵 这时G J方程组间的 转化过程就是要将非基变量 的系数向量 变为单位 向量 性质 要实现这个过程 则必须有元素 称为主元 转化过程显示如下 关于基 的Gauss Jordan方程组 关于基 的 Gauss Jordan方程组 为保证解的改进 替换须满足以下两个条件 第一 容许性条件 即保证 的G J方程组的右端项 非负的条件 第二 下降性条件 即保证 的基本容许解的目标函 的基本容许解的目标函数值的条件 数值小于 i 容许性条件 由 即主元还必须为正 结论是 为保证 的G J方程组的右端项非负 2 36 主元 必须是满足 的正数 如果主元不存在 则线性规划解无界 定理2 12 例2 6考虑例2 5中的线性规划 关于 的 G J方程组 试把 和 分别引入基 求新的基本 容许解 下降性条件 新解 中只有 其余分量皆为0 于是 由 2 26 式得 2 37 由于 所以只要 则 特别当 时 只要 必有 结论是 引入判别数为正的变量 将保证 的基本 的基本容许解的目标函数值 容许解的目标函数值不大于 引理2 10 定理2 11 单纯形法基本定理 在标准线性规划 2 21 中 假设 是容许基 关于 的基本容许解 是非退化的 即 非基变量 的判别数 是用公式 2 36 确定的一个 行标 用 替换 中的 而其余基向量不变 构成 矩阵 那么 是容许基 且关于 的基本容许解的 目标函数值小于关于 的基本容许解的目标函数值 定理2 12在标准线性规划 2 21 中 假设 是容许基 非基本变量 的判别数 那么线性规划 2 21 存在可以使目标函数值任意减小的容许解 2 单纯形表 以上过程都可以清晰地在一张表 单纯形表上进行 称之为表上作业法 假设已知 容许 基 那么关于 的信息全部反映在以下两个式子 线性规划的两个关键数学式 中 称之为关于基 的增广G J方程组 增广G J方程组其实可由线性规划 2 21 的原始数据经初等行变换得到 原有 2 45 式左乘 即得 2 43 式 2 43 式再左乘 加到 2 46 式上便得 2 44 式 隐去增广G J方程组中的变量和 的系数向量 将 其余数据列成表 2 51 称为关于基 的单纯形表 若 是最优基 则称为最优表 单纯形表是增广G J方程组的简单表示 表 称为线性规划的准备表 类似前面的推导 由准备表容易导出单纯形表 至此 含有标准基的线性规划问题的求解彻底解决 归纳见 3 例2 7求解例2 5中的线性规划 P64 55 3 典范线性规划的解法 考虑典范线性规划 是标准容许基 典范线性规划含有标准容许基 它的准备表既是单纯形表 因此单纯形法可以直接启动 算法2 1 单纯形法 P65 单纯形法本质上是求解典范线性规划的算法 定理2 13在使用单纯形法 算法2 1 求解典范线性规划时 若各次迭代出的基本容许解皆是非退化的 则算法在有限步终止 推论2 14典范线性规划或者存在最优基本容许解 或者解无界 对于如下形式的线性规划 其中 先引入非负变量 将其化为典范形式 然后就可以启动单纯形法 例2 8求解线性规划P66 3 初始基本容许解的产生 对于标准线性规划 2 54 引入 个人工变量 求解辅助线性规划 一个典范线性规划 2 55 其中 显然 2 55 不可能无解 设 2 55 的最优值为 显然 设最优表 对应的G J方程组为 2 56 注意 与 等价 2 54 与 2 55 的关系 若 则 2 54 无解 若 则由 2 56 可得到 2 54 的一个初始基本 容许解 以下讨论在 下进行 分两种情形 1 在最优表中人工变量已全部退出基变量 表现为 中不存在基向量 这时 与 等价的 中有了标准基 表明 2 54 有了初始基本容许解 这时可以开始求解 2 54 见下面的4 1 即 2 在最优表中至少还有一个人工变量是基变量 表 中有基向量 现为 假设第 个人工变量 仍是基变量 那么它的取值为 因为 所以 考虑 2 56 的第 个方程 2 58 以下分两种情形 若 则 2 58 实质上成为 的第 个方程是多余方程 这表明 从而 的第 个方程也多余 划去第 个方程 人工变量 将彻底消失 若 至少有一个不为0 不妨设 以 为主元在最优表上进行换基运算 人工变量 就会从基变量中消失 重复以上步骤 直到人工变量全部从基变量中消失 最终的G J方程组为 这时与 等价的 中也有了标准基 从而 2 54 也有了初始基本容许解 于是可以开始求解 2 54 见下面的4 2 4 标准线性规划的解法 按3 求出 2 54 的初始基本容许解之后 接下来求解 2 54 与3 中的 1 2 对应 分别为 1 求解线性规划 2 求解线性规划 总结 一般来说 解线性规划主要分为两大步 第一步 化标准形 有时不需要 第二步 启动两阶段单纯形法 当标准形是典范线性规划时 直接进入第二阶段 例求解线性规划 例2 9求解线性规划 例2 10求解线性规划 2 4退化的处理 在非退化假定下 单纯形法 算法2 1 具有有限终止性 定理2 13 取消非退化假定 情况会是怎么样 第一 算法2 1可能发生无限循环 求不到最优解 第二 适当修改选主元的规则 则可以保证单纯形法仍具有有限步终止性 1 选主元规则 单纯形法的核心是换基运算 而换基运算的首要步骤是选主元 选取主元列标的规则称为进基规则 选取主行标的规则称为退基规则 进基规则和退基规则合称选主元规则 选主元规则有多种多样 常用的进基规则有以下两种 最大正判别数进基规则 正判别数最小下标进基规则 选取正判别数中最小的下标作为主元的列标 算法2 2和算法2 3就采用这种进基规则 常用的退基规则是最小行标退基规则 在使用公式 2 36 确定主元行标 若最小比值在多行上取得 则从中选取最小的行标作为主元的行标 选取最大判别数的下标作为主元的列标 若同时有多个等值的最大正判别数 则选取其中最小的下标为主元的列标 最大正判别数进基规则与最小行标退基规则合称Dantzig规则 算法2 1采用的就是这种规则 计算实践表明 在各种选主元规则中 Dantzig规则效果较好 在求解同一线性规划问题时 迭代次数相对较少 它的缺点是 在求解退化问题时 算法可能产生无限循环 求不到最优解 2 避免循环的规则 这里介绍一种最简单的避免循环的规则 Bland规则 Bland规则设在单纯形法的迭代过程中 当前容许基是 关于 的基容许解不是最优解 则 主元列标和行标分别由如下两个规则确定 Bland进基规则 采用正判别数最小下标进基规则 即主元列标是 由此确定 进基 Bland退基规则 假定 设 又设 则主元行标 由式 确定 由此确定 退基 换句话说 在所有可能的 退基向量中 选取下标最小的向量退基 Bland证明 使用带有Bland规则的单纯形法求解典范线性规划 不会发生基的循环 2 5修正单纯形法 修正单纯形法是计算机实现的单纯形法 注意到 包含全部信息的单纯形表 中的数据完全由基 实际是 及原始数据决定 可以 就有一切 说有 举例说明修正单纯形法的概貌 例如求解 解建立单纯形表如下 开始 最优化方法 最优化课件研制组 退出 主讲 张京 最优化方法 第三章无约束最优化方法 从本章起 以后两章将讨论非线性规划问题 本章首先讨论无约束最优化问题 其一般形式为 3 1 其中 求解无约束问题的最优化方法可以分为两大类 一类是根据目标函数的梯度 即一阶导数 有时还要根据Hesse矩阵 即二阶导数 提供的信息构造出来的方法 导数方法 本章介绍其中的最速下降法 Newton法 共轭梯度法和拟Newton法 另一类是不使用导数 仅仅利用目标函数值的信息构造出来的方法 直接方法 本章将介绍其中的步长加速法 方法加速法和单纯形替换法 两类方法各有利弊 前者收敛速度快 但需要计算梯度 甚至需要计算Hesse矩阵 后者不涉及导数 适应性强 但收敛速度慢 一般的经验是 在可以求得目标函数导数的情况下 尽可能使用导数方法 3 1直线搜索 直线搜索 一维搜索 是指求解如下一元函数极小化问题 3 3 的迭代方法 其中 在微积分中 解决问题 3 3 的范围一般限于方程 3 4 可以直接解出的情况 而这里介绍的直线搜索对 严格的要求 当然 对于可以求出导数的情况 相应的求解方法一般也会简单些 不作 直线搜索 理论上 分为精确的和不精确的 精确的直线搜索方法主要分为两类 一类为区间收缩法 另一类为函数逼近法 本节将相应地介绍两种常用的精确的直线搜索方法 适用于一般函数的黄金分割法和适用于一般连续函数的抛物线插值法 最后还将介绍实用的不精确一维搜索技术 精确的直线搜索算法的实现通常是在所谓的搜索区间上进行的 1 搜索区间的确定 在以下讨论中 总假定一元函数 是单谷函数 定义3 1设 是 在L上的全局 极小点 如果对于L上任意的两点 当 时 当 时 那么称 是区间L上的单谷函数 下图给出了单谷函数的基本图形 定义3 2设 是 在L上的 全局极小点 如果能够找到 使得 那么闭区间 就称为 极小点的一个搜索区间 记为 搜索区间有时也记作 其中 显然 单谷函数的定义域区间是搜索区间 单谷函数的性质 定理3 1设 是单谷函数 极小点的一个搜索区 间 在 内任取两点 若 则 是 极小点的一个搜索区间 若 则 是 极小点的一个搜索区间 直线搜索算法的第一步一般得先确定 的一个 初始 搜索区间 根据定理3 1 可以给出确定搜索区间的如下算法 算法3 1 确定搜索区间 已知 目标函数 选定初始点 和步长 计算 若 则置 转 否则转 置 计算 若 则转 否则转 置 即为 搜索区间 计算结束 上述过程开始时 必须选定初试点 和步长 对于 任意给定的 一般来说 无固定选取模式 但对于在下降算法模式中所引入的 而言 可选取 等于0 理论上 或接近0 实际计算中 而对于 如果选得过小 那么需要迭代许多次才能找到一个搜索区间 如果选得太大 虽然很少几步就可能把极小点包括进来 但是这又会给下一步搜索极小点的过程增加负担 下面是确定的一种比较合理而有效的方法 第一次迭代 即从 到 的迭代 时 的初始步长可取为1 或根据问题中出现的数据的数量级估计选定 而以后各次迭代的初始步长可按公式 3 5 计算 3 5 其中 这是因为从到的距离一般比从到的距离小或接近 所以把按 3 5 算出的作为下一次迭代的初始步长是合适的 在实际计算中 当较小时 相应的可取得小些 而随着的增大 相应的可取得接近1 2 直线搜索的方法 1 黄金分割法 黄金分割法属于区间收缩法 它适用于任何单谷函数求极小值问题 对函数除 单谷 外 不作其它要求 甚至可以不连续 因此这种方法的适用面相当广 黄金分割法的思想是 在每次迭代中 合理地设置两个插入点的位置 以使得在计算函数值次数同样多的条件下 将区间缩小得最快 设区间的长为1 在距点分别为和的地方插入和 为了确定和 提出以下条件 第一 希望和在中的位置是对称的 按这一条件 有 即 3 6 这样无论删去哪一段 总保留长为 的区间 第二 删掉一段 例如删掉 在保留下来的区间 使得 里再插入一个点 在 中的位置与 在 中的位置具有相同的比例 从而保证每次迭代都能 缩小区间 按这一条件 有 以同一比率 即 或 3 7 把 3 7 代入 3 6 中 得到关于 的一元二次方程 其合理的根是 3 8 代回 3 6 得 在古代 人们认为按比率0 618分割线段是最协调的 胜似黄金 故称黄金分割 因此 上述按比率0 618缩小搜索区间的迭代方法称为黄金分割法或0 618法 算法3 2 黄金分割法 P145 2 抛物线插值法 抛物线插值法属于函数逼近法 它适用于连续的单谷 函数求极小值问题 抛物线插值法的思想是 设 在搜索区间 上连续 记 和 如果 3 9 与 3 10 两等号不同时成立 同时成立 那么可以过 和 三点作抛物线插值 设抛物线方程为 3 11 其实是在区间 上对 所作的一个 曲线拟合 记 的极小点为 则根据 提供的信息 我们可以将搜索区间 缩小 然后在缩小了的区间上 再作抛物线插值 如此下去 最终可以求到 在 中的极小点 令 3 12 解出 3 13 根据插值条件 和 列出关于 和 的线性方程组 由此解出 并代入 3 13 中 得 3 14 这个公式的使用条件仅仅是 和 三点不共线 可以证明 习题3 5 在 3 9 和 3 10 两等号不同时成立 同时成立的条件下 由 3 14 所确定的 是 的极小点 并且 以下讨论算法的终止准则和缩小搜索区间的方法 按 3 14 计算出 由极限理论知道 如果 与 都很小 那么 也必然很小 当然 也应该很小 计算经验指出 可以采用 3 15 作为终止准则 当终止准则满足时 取 和 中函数值较小的点 提供的 缩小 这个过程如下 作为极小点 当终止准则未满足时 则需要利用 信息将原来的搜索区间 比较 和 的大小 有两种情况 若 则 转 否则 转 若 则置 转 若 则 转 置 若 则置 转 若 则 转 置 转向计算新的搜索区间 上的插值抛物线 的极小点 算法流程图见书上图3 5 包括黄金分割法和抛物线插值法在内的许多一维问题的迭代方法全部依赖于函数单谷性的假设 但在许多问题中 这一假设不成立或难以验证 解决这一困难的办法 尤其当初始搜索区间很大的时候 是将搜索区间分成若干个较小区间 然后在每个子区间上寻求极小 最后又在所有子区间的极小中选取最小的一个作为问题的最优解 3 不精确一维搜索技术 精确的一维搜索过程往往需要花费很大的计算量才有可能求到符合精度要求的最优步长因子 当多维问题的迭代点距极小点较远时 显然精确地求解一维子问题对求解多维问题本身没有太大的意义 另外很多最优化方法 如Newton法和拟Newton法 其收敛速度也并不依赖于精确的一维搜索过程 因此 在实际计算中 只要选取的步长因子能够保证目标函数在每一步的迭代中都有 满意的 下降就可以了 这样 既会大大地节省计算量 同时还会从整体上加快计算进程 考虑由多维问题引出的一维问题 3 16 其中 具有一阶连续偏导数 Goldstein 1965年 和Powell 1975年 给出了用来设计 3 16 不精确一维搜索过程的两个条件 3 17 3 18 其中 使得 而 是给定 的常数 通常取 条件 表示应使新迭代点 的函数值相对上一迭代点 的函数值的下降幅度须不低于 某个量 而条件 则表示目标函数 在新迭代点 处沿 方向的方向导数应不小于 在上一迭代点 处沿 方向的方向导数的 倍 换句话说 若 满足 条件 则认为在点 处已获得 满意的 函数值的下降 而若 满足条件 这时有两种可能性 要么 已是点 方向 处的上升方向 要么 方向虽然还是点 下降方向 处的 但函数 在点 处沿 方向的下降率已低于 处沿 方向的下降率 在点 倍 这时若继续沿 方向作一维搜索 只会徒增计算量 而不会再获得函数值的较大下降量 因此 一旦 满足条件 就需要确定 新的搜索方向 以上分析表明 在实际计算中 选取满足 3 17 和 3 18 的 作为确定 的步长因子是合适的 即 一般地 越小 一维搜索越精确 但计算量也越大 不精确的一维搜索不要求过小的 而 越小 条件 越容易满足 在实际计算中 通常取 或更小的值 值的选取不太敏感 由此得出的解通常对 算法3 3 不精确一维搜索 已知 且 给定 通常取 初始 可取1或参照 3 5 给出 步长 计算 置 计算 若 3 18 成立 则转 否则 置 然后转 若 3 17 成立 则打印 计算结束 否则 然后转 置 算法说明 第 步中若 3 18 不成立 则表明沿 方向 有继续前进的必要 第 步中若 3 17 不成立 这表明当前步长过大 需缩小搜索范围 不精确一维搜索的算法流程图 3 2最速下降法 最速下降法是最早的求解多元函数极值的