非线性优化问题

第三专题非线性优化问题 1 非线性优化模型的建立2 非线性优化模型的寻优 非线性优化模型的建立 确定决策变量确定目标 决策准则 确定约束条件 实例分析 1 投资决策问题 P88 2 曲线拟合问题在实验数据处理或统计资料分析中 常常遇到这样的问题 如何利用有关变量的实验数据 资料 去确定这些变量间的函数关系 例如 已知某物体的温度与时间之间有如下形式的经验函数关系 其中是待定参数 通过测试获得n组温度与时间之间的实验数据 试确定参数使理论曲线尽可能地与n个测试点拟合 非线性规划问题的共同特征 都是求一个目标函数在一组约束条件下的极值问题 在目标函数或约束条件中 至少有一个是变量的非线性函数 非线性规划问题 一般形式 向量形式 非线性优化问题的寻优 相关概念及理论一维最优化方法多维无约束最优化方法多维有约束最优化方法 非线性规划的相关概念及理论 一阶导数 二阶导数和n元函数的Taylor公式 定义4 设函数 定义在凸集 上 若对任意的 及任意的 都有 则称函数 为凸集 上的凸函数 定义5 严格凸函数 注 将上述定义中的不等式反向 可以得到 凹函数的定义 凸函数 例1 设 试证明 在 上是严格凸函数 证明 设 且 都有 因此 在 上是严格凸函数 例2 试证线性函数是 证明 设 上的凸函数 则 所以 是凸函数 类似可以证明 是凹函数 凸函数的几何性质 对一元函数 在几何上 表示连接 的线段 表示在点 处的 函数值 所以一元凸函数表示连接函数图形上任意两点 的线段总是位于曲线弧的上方 凸函数的性质 设 设 函数 是凸集 上的凸函数 实数 则 也是 上的凸函数 是凸集 上的凸 实数 则 也是 上的凸函数 设 是凸集 上的凸函数 是实数 则水平集 是凸集 下面的图形给出了凸函数 的等值线的图形 可以看出水平集是凸集 凸函数的判定 定理1 设 上 令 则 1 是定义在凸集 是凸集 上的凸函数的充要条件是对 任意的 一元函数 为 上的凸函数 2 设 若 在 上为严格 凸函数 则 在 上为严格凸函数 该定理的几何意义是 凸函数上任意两点之 间的部分是一段向下凸的弧 一阶条件 定理2 1 设在凸集 上 可微 则 在 上为凸函数的充要条件是对任意的 都有 定理2 2 严格凸函数 充要条件 二阶条件 定理3 设在开凸集 内 二阶可微 则 1 是 内的凸函数的充要条件为 在 内任一点 处 的海色矩阵 半正定 其中 二阶条件 定理3 设在开凸集 内 2 若在 内 正定 则 在 内 二阶可微 则 是严格凸函数 注 反之不成立 例 显然是严格凸的 但在点 处 不是正定的 凸规划 定义6 设 为凸集 为 上的凸函数 则称规划问题 为凸规划问题 定理4 1 凸规划问题的任一局部极小点 是 整体极小点 全体极小点组成凸集 2 若 是凸集 上的严格凸函数 且凸规划问题 整体极小点存在 则整体极小点是唯一的 非线性规划的最优性条件 最优性条件 是指非线性规划模型的最优解所要满足的必要和充分条件 无约束最优性条件约束最优性条件 无约束最优性条件 一 单 元函数的最优性条件 若 为 的局部极小点 则 若 则 为 的严格局部极小点 若 为 的局部极小点 则 多元函数的一阶必要条件 P106 107 定理1 若 为 的局部极小点 且在 内 一阶连续可导 则 注 1 仅仅是必要条件 而非充分条件 2 满足 的点称为驻点 驻点分为 极小点 极大点 鞍点 多元函数的二阶充分条件 定理2 若在 内 二阶连续可导 且 正定 则 为严格局部 极小点 注 如果 负定 则 为严格局部极大点 二阶必要条件和充要条件 定理3 若 为 的局部极小点 且在 内 二阶连续可导 则 半正定 定理4 设 在 上是凸函数且有一阶连续 偏导数 则 为 的整体极小点的充要 条件是 例1 利用极值条件解下列问题 解 令 即 得到驻点 函数 的海色阵 由此 在点 处的海色阵依次为 由于矩阵 不定 则 不是极小点 负定 则 不是极小点 实际上它是极大点 正定 则 是局部极小点 约束最优性条件 p133 p136 定义1 有效约束 若 中的一个可行点 使得 某个不等式约束 变成等式 即 则 称为关于 的有效 积极 约束 非有效约束 若对 则 称为 关于 的非有效 无效 约束 有效集 定义2 锥 的子集 如果它关于正的数乘运算 是封闭的 如果锥也是凸集 则称为凸锥 凸锥关于加法和正的数乘运算是封闭的 一阶必要条件 定理3 5 Kuhn Tucker一阶必要条件 1951 设 在 K T条件 一阶必要条件 定理1 Kuhn Tucker一阶必要条件 互补松弛条件 例2 验证是否满足Kuhn Tucker条件 试验证最优点 为KT点 解 令 所以 即 所以 是KT点 Lagrange函数及K T条件 在一定凸性下的最优性的充分条件 一维最优化方法 线性搜索方法 已知 并且求出了 处的可行下降方向 从 出发 沿方向 求目标函数的最优解 或者选取 使得 问题描述 即 设其最优解为 叫精确步长因子 所以线性搜索是求解一元函数 的最优化问 题 也叫一维最优化问题 我们来求解 于是得到一个新点 一般地 线性搜索算法分成两个阶段 第一阶段确定包含理想的步长因子 或问题最优解 的搜索区间 第二阶段采用某种分割技术或插值方法 缩小这个区间 搜索区间 搜索区间求取方法 进退法 一种简单的确定初始搜索区间方法 基本思想 是从一点出发 按一定步长 试图确定出函数值呈现 高 低 高 的三点 即这里 具体地说 就是给出初始点 初始步长 若 则下一步从新点出发 加大步长 再向前搜索 直到目标函数上升为止 若 则下一步仍以为出发点 沿反方向同样搜索 直到目标函数上升就停止 这样便得到一个搜索区间 这种方法叫进退法 计算步骤 见P96计算框图 见P97 黄金分割法 0 618法 基本思想 它通过对试探点的函数值进行比较 使得包含极小点的区间不断缩短 当区间长度小到精度范围之内时 可以粗略地认为区间上各点的函数值均接近于极小值 设 在 上为下单峰函数 即有唯一 的极小点 在 左边 严格下降 在 右边 严格上升 在 内任取 若 则 若 则 单峰函数 黄金分割法 黄金分割法 若第一次选取的试点为 则下一步保留 的区间为 或 两者的机会是均等的 因此我们选取试点时希望 设 则 另外 我们希望如果缩小的区间包含原来的 试点 则该试点在下一步被利用 若保留的区 我们希望原来的 间为 前一次的试点 在这个区间内 在缩小的区间内成为 新的 我们根据这条件来计算 计算 的公式为 因此我们希望 即 化简得 若保留区间为 我们得到的结果是 一致的 该方法称为黄金分割法 实际计算取 所以黄金分割法又称为0 618法 黄金分割法每次缩小区间的比例是一致的 每次将区间长度缩小到原来的0 618倍 黄金分割法的算法步骤 Step1 给定 以及 令 Step2 Step3 转Step 令 转Step 若 则 停 否则 转Step Step4 若 则 转Step3 黄金分割法的算法步骤 Step5 若 则 转Step3 若 则 转Step3 例1 黄金分割法 用黄金分割法求函数 在区间 上的极小点 要求最终区间长度不大于 原始区间长度的0 08倍 解 函数 在区间 上为下单峰函数 第一次迭代 缩短后区间为 第二次迭代 缩短后区间为 Fibonacci法 为了尽快得到结果 希望区间缩小的尽量小 如果在区间只有一个试点 我们无法将区间缩小 如果知道两个试点 根据 的大 小关系 可以得到缩小的区间 或者 它与0 618法的主要区别之一在于 搜索区间长度的缩短率不是采用0 618 而是采用Fibonacci数 下面我们考虑任给一个 另外一种思维方式为 的单峰区间 如果给定试点的个数 如何使最后确定 最优值的区间尽量的小 按什么方式取点 求 次函数值之后 可最多将多长的原始区间 长度缩小为 设 为试点个数为 最终区间 长度为 时 原始区间 的最大可能长度 的包含 设最初两个试点为 和 若极小点在 内 至多还有 个试点 则 若极小点在 内 包括 在内可以有 个试点 则 因此 如果我们采取合适的技巧 可以使得 另外 显然 从而 满足差分方程 此为Fibonacci数列 一般写为 若原始区间为 要求最终区间长度 则 由此可确定 区间缩短之后与 之前的比依次为 确定之后 最初两个试点分别为 关于 对称 由于 上述过程完成了依次迭代 新区间仍记为 若已经进行了 次迭代 第 次迭代时 还有 个试点 包括已经计算过的函数值的一个 注意 若在一定的误差范围内 则认为 在 内 最后的两个试点的选取方式 例3 1 Fibonacci法 用Fibonacci法求函数 在区间 上的极小点 要求最终区间长度不大于 原始区间长度的0 08倍 解 函数 在区间 上为下单峰函数 由 可知 应取 Fibonacci算法与0 618法几乎完全相同 第一次迭代 缩短后区间为 第二次迭代 缩短后区间为 第三次迭代 缩短后区间为 第四次迭代 缩短后区间为 第五次迭代 取最优解 Fibonacci方法评价 Fibonacci法的优点 如果缩小的区间包含原来的试点 则该 试点在下一步被利用 效率最高 有限个试点的情况下 可将 最优点所在的区间缩小到最小 Fibonacci法的缺点 搜索前先要计算搜索的步数 每次搜索试点计算的公式不一致 1 黄金分割法 0 618法 与Fibonacci法 的区别与联系是什么 2 请读者自己写出算法和程序 二分法 若 的导数存在且容易计算 则线性搜索 的速度可以得到提高 下面的二分法每次将 区间缩小至原来的二分之一 设 为下单峰函数 若 在 内 具有连续的一阶导数 且 取 若 则 为极小点 若 则以 代替 若 则以 代替 二分法每次迭代都将区间缩短一半 故二分法的收敛速度也是线性的 收敛比为1 2 计算步骤 见P105计算框图 见P106 多维无约束最优化方法 最速下降法 阻尼 牛顿法共轭梯度法 最速下降法 问题提出 问题 在点 处 沿什么方向 下降最快 分析 考查 显然当 时 取极小值 因此 结论 负梯度方向使 下降最快 亦即最速 下降方向 最速下降法算法 Step1 给出 Step2 计算 如果 停 Step3 计算下降方向 Step4 计算步长因子 Step5 令 转步 问题 设 是正定二次函数 由精确的线搜索确定的 特别当 例1 用最速下降法求解 解 分析 1 因此 最速下降法是整体收敛的 且是线性收敛的 2 两个相邻的搜索方向是正交的 收敛性分析 定理1 设 在 上存在且一致连续 则最速下降法产生的序列 满足或者对某个 有 或者 证明 对于最速下降法 由以上定理立得 收敛性分析 定理2 设 二次连续可微 且 其中 是个正常数 对任何给定的初始点 最速下降算法或有限终止 或者 或者 证明 用以上的结论 最速下降法优点 1 程序设计简单 计算量小 存储量小 对初始点没有特别要求 2 有着很好的整体收敛性 即使对一般的 目标函数 它也整体收敛 最速下降法缺点 最速下降法是线性收敛的 并且有时是 很慢的线性收敛 原因 仅反映 在 处 的局部性质 相继两次迭代中搜索 方向是正交的 小结 最速下降法是基本算法之一 而非有效 的实用算法 最速下降法的本质是用线性函数来近似 目标函数 要想得到快速算法 需要考 虑对目标函数的高阶逼近 牛顿法 基本思想 利用目标函数 在点 处的二阶Taylor 展开式去近似目标函数 用二次函数的极小点 去逼近目标函数的极小点 算法构造 问题 设 二阶连续可微 海色阵 正定 如何从 因为 正定 则 有唯一极小点 用这个 极小点作为 所以要求 即 因此 这就是牛顿法迭代公式 注 这里 牛顿法算法 Step1 给出 Step2 计算 如果 停 Step3 否则计算 Step4 令 转步 并且求解方程 得出 例1 用牛顿法求解 解 牛顿法收敛定理 定理1 设 二次连续可微 是 的局 部极小点 正定 假定 的海色阵 满足Lipschitz条件 即存在 使得对于所有 有 其中 是海色阵 的 元素 则当 充分靠近 时 对于一切 牛顿迭代有意义 迭代序列 收敛到 并且具有二阶收敛速度 牛顿法优点 1 2 对正定二次函数 迭代一次就可以得到 极小点 如果 正定且初始点选取合适 算法 二阶收敛 牛顿法缺点 1 2 对多数问题算法不是整体收敛的 每次都需要计算 计算量大 3 每次都需要解 方程组有时奇异或病态的 无法确定 或 不是下降方向 4 收敛到鞍点或极大点的可能性并不小 阻尼牛顿法算法 Step1 给出 Step2 计算 如果 停 Step3 否则计算 Step4 沿 并且求解方程 得出 进行线搜索 得出 Step5 令 转Step2 阻尼牛顿法收敛定理 定理2 设 二阶连续可微 又设对任意的 存在常数 使得 在 上满足 则在精确线搜索条件下 阻尼牛顿法产生的点列 满足 1 当 是有限点列时 其最后一个点为 的唯一极小点 2 当 是无限点列时 收敛到 的唯一极小点 阻尼牛顿法收敛定理 定理3 设 二阶连续可微 又设对任意的 存在常数 使得 在 上满足 则在Wolfe不精确线搜索条件下 阻尼牛顿法 产生的点列 满足 且 收敛到 的唯一极小点 例2 用阻尼牛顿法求解 解 显然 不是正定的 但 于是 沿方向 进行线搜索 得其极小点 从而迭代不能继续下去 带保护的牛顿法算法 给出 Step1 若 为奇异的 转Step8 否则 Step2 令 Step3 若 为奇异的 转Step8 否则 则转Step8 否则 Step4 若 则转Step9 否则 Step5 沿方向 进行线搜索 求出 并令 Step6 若 停 Step7 令 转Step1 Step8 令 转Step5 Step9 令 转Step5 例3 用带保护的牛顿法求解 解 显然 不是正定的 但 于是 因为 故令 沿 进行线搜索得 第二次迭代 而 使 故令 沿 进行线搜索 得出 于是 此时 共轭梯度法 问题1 如何建立有效的算法 从二次模型到一般模型 问题2 什么样的算法有效呢 二次终止性 经过有限次迭代必达到极小点的性质 算法特点 建立在二次模型上 具有二次终止性 有效的算法 克服了最速下降法的慢 收敛性 又避免了牛顿法的计算量大和局部收 性的缺点 算法简单 易于编程 需存储空间小等 优点 是求解大规模问题的主要方法 共轭方向及其性质 定义1 设 是 中任一组 非零向量 如果 则称 是关于 共轭的 注 若 则是正交的 因此共轭是 正交的推广 定理1 设 为 阶正定阵 非零向量组 关于 共轭 则必线性无关 推论1 设 为 阶正定阵 非零向量组 关于 共轭 则向量构成 的一组基 推论2 设 为 阶正定阵 非零向量组 关于 共轭 若向量 与 关于 共轭 则 求的极小点的方法共轭方向法算法 Step1 给出 计算 和初始下降方向 Step2 如果 停止迭代 Step3 计算 使得 使得 转Step2 共轭方向法基本定理 定义2 设 维向量组 线性无关 向量集合 为 与 生成的 维超平面 引理1 设 是连续可微的严格凸函数 维向量组 线性无关 则 是 在 上 唯一极小点的充要条件是 定理2 设 为 阶正定阵 向量组 关于 共轭 对正定二次函数 由任意 开始 依次进行 次精确线搜索 则 是 在 上的极小点 推论 当 时 为正定二次函数在 上的极小点 共轭梯度法 记 左乘 并使 得 Hestenes Stiefel公式 取 是一种特殊的共轭方向法 共轭梯度法基本性质 定理3 对于正定二次函数 采用精确线搜索 的共轭梯度法在 步后终止 且对 成立下列关系式 共轭性 正交性 下降条件 系数的其他形式 FR公式 1964 2 PRP公式 1969 FR共轭梯度法算法 Step1 给出 Step2 如果 停 Step5 转Step2 计算 Step4 Step3 由精确线搜索求 计算 例4 用FR共轭梯度法求解 解 化成 形式 1 2 例5 用FR共轭梯度法求解 解 化成 形式 1 2 注意 FR方法中初始搜索方向必须取最速下降方向 才满足二次终止性 FR共轭梯度法收敛定理 定理4 假定 在有界水平集 上连续可微 且有下界 那么采用精确线搜索下的 FR共轭梯度法产生的点列 至少有一个聚点 是驻点 即 1 当 是有穷点列时 其最后一个点是 的驻点 2 当 是无穷点列时 它必有聚点 且任一 聚点都是 的驻点 再开始FR共轭梯度法算法 Step1 给出 Step2 计算 如果 停 Step4 否则 Step3 由精确线搜索求 并令 计算 若 令 转Step2 如果 停 Step5 若 令 转step2 Step6 计算 Step7 如果 令 转step2 否则 转step3 作业 用FR共轭梯度法求解 多维约束最优化方法 惩罚函数法SUMT 序列无约束极小化方法 SequentialUnconstrainedMinimizationTechnique 乘子法 外点法 二次罚函数方法 内点法 内点障碍罚函数法 罚函数法 基本思想 设法将约束问题求解转化为无约束问题求解 具体说 根据约束的特点 构造某种惩罚函数 然后把它加到目标函数中去 将约束问题的 求解化为一系列无约束问题的求解 惩罚策略 企图违反约束的迭代点给予很大的 目标函数值 迫使一系列无约束问题的极小点或 者无限地靠近可行域 或者一直保持在可行域 内移动 直到收敛到极小点 外罚函数法 外点法 引例 求解等式约束问题 解 图解法求出最优解 构造 但是 性态极坏 无法用有效的无约束 优化算法求解 设想构造 其中 是很大的正数 求解此无约束问题得 当 时 有 等式约束问题 构造 其中 为参数 称为罚因子 分析 当 不是可行解时 越大 惩罚越重 因此当 充分大时 应充分小 即 的极小点应充分逼近可行域 进而 逼近 1 的最优解 不等式约束问题 构造 分析 当 不是可行解时 越大 惩罚越重 因此当 充分大时 应充分小 即 的极小点应充分逼近可行域 进而 逼近 2 的最优解 一般约束问题 构造 其中 例1 用外罚函数法求解 解 即 因此 令 得 最优值 当 时 注 1 往往不满足约束条件 都是 从可行域外部趋向于 的 因此叫外罚函数法 2 通过求解一系列无约束最优化问题来求 解约束最优化问题的方法 又称为序列无约束 极小化技术SUMT 外罚函数法 又称SUMT外点法 外罚函数法算法步骤 Step1 给出 可是不可行点 罚因子 放大系数 Step2 以 为初始点求无约束问题 得 Step3 若 则 停 否则转step4 Step4 令 转step2 例2 用SUMT外点法求解 取 求解 迭代过程见下表 收敛性分析 引理1 对于由SUMT外点法产生的点列 则有 设 收敛性分析 定理1 设约束问题 3 和无约束问题 4 的整体 最优解为 和 对正数序列 且 则由SUMT外点法产生的点列 的 任何聚点 必是 3 的整体最优解 证 不妨设 因为 和 分别为 3 和 4 的整体最优解 且 所以有 为单调有界序列 设其极限为 亦为单调有界序列 设其极限为 且 连续 即 为可行解 为最优解 连续 即 为 3 的整体最优解 外罚函数法评价 1 如果有了求解无约束问题的好算法 利用 外罚函数法求解约束问题很方便 2 每个近似解 往往不是可行解 这是某 些实际问题所无法接受的 内罚函数法可以解决 3 由收敛性定理 取越大越好 而 越大将 造成增广目标函数 的Hesse阵条件数越 大 趋于病态 给无约束问题求解增加很大困 难 甚至无法求解 乘子法可解决这个问题 内罚函数法 惩罚策略 在可行域的边界上筑起一道很高的 围墙 当迭代点靠近边界时 目标函数值 陡然增大 以示惩罚 阻止迭代点穿越边界 这样就可以把最优解 挡 在可行域内了 注 惩罚策略只适合于不等式约束问题 并且要求可行域的内点集非空 不等式约束问题 构造 其中 或 分析 为可行域的内点时 为有限正数 几乎不受惩罚 接近边界时 趋于无穷大 施以很重的惩罚 迫使极小点落在可行域内 最终逼近极小点 例3 用内罚函数法求解 解 令 所以 当 时 注 一般 最优解很难用解析法求出 需采用序列无约束最优化方法 内罚函数法算法 Step1 给出 要求是可行点 罚因子 缩小系数 Step2 以 为初始点求无约束问题 得 Step3 若 则 停 否则转step4