运筹学——非线性规划.pdf

第六章 非线性规划第六章 非线性规划 运 筹 学 运 筹 学 Prof 梁军梁军 jliang 0571 87953883 6 1 非线性规划问题与数学模型6 1 非线性规划问题与数学模型 先看两个例子 先看两个例子 如果目标函数或约束条件方程中存在任何非线性因子存在任何非线性因子 则问题为非 线性规划 非 线性规划 非线性规划在工程 军事 经济等许多领域都得到广泛 的应用 1 非线性规划的提法非线性规划的提法 例例 2 8 设平面上有设平面上有 m 个点 找覆盖这个点 找覆盖这 m 个点的最小园 盘 个点的最小园 盘 解解 设设 m 个点为个点为 1 2 i p im 则平面上任一点 则平面上任一点x到这到这 m 个点的距离最大者满足个点的距离最大者满足 1 max i i m f xxp 2 28 则以则以x为园心 为园心 f x 为半径的园盘必覆盖这为半径的园盘必覆盖这 m 个点 于是问题 转化为求解最小半径的园盘问题 个点 于是问题 转化为求解最小半径的园盘问题 1 minmax i i m xp 2 29 这是一个无约束的非线性规划问题 这是一个无约束的非线性规划问题 非线性规划的一般形式为非线性规划的一般形式为 min f x 2 33 0 1 2 0 1 2 i j stg xim hxjl 2 34 式中 目标函数式中 目标函数 f x 不等式约束条件 不等式约束条件 i g x 和等式约束条件和等式约束条件 j hx 至少一个是非线性函数 当不存在约束条件 即决策变量至少一个是非线性函数 当不存在约束条件 即决策变量x可取 任意点时 可取 任意点时 min f x 2 35 称为无约束非线性规划问题 称为无约束非线性规划问题 非 线 性 规 划 的 约 束 条 件 有 时 写 成 域 约 束 形 式 令非 线 性 规 划 的 约 束 条 件 有 时 写 成 域 约 束 形 式 令 0 1 2 0 1 2 ij Sx g xim hxjl 称称 S 为可行域 为可行域 S 中 的点为可行点 上述约束非线性规划问题 中 的点为可行点 上述约束非线性规划问题 2 33 2 34 等价于 等价于 min f x stxS 2 36 而无约束非线性规划问题等价于而无约束非线性规划问题等价于 min n f x x 2 37 n 是是 n 维欧氏空间 维欧氏空间 非线性规划问题的非线性规划问题的求解一般通过两种途径求解一般通过两种途径来实现 一种是基于目标函数和约束条件的函数分析性质直接加以求解的 来实现 一种是基于目标函数和约束条件的函数分析性质直接加以求解的解析解 法 解析解 法 多适用于具有良好函数解析性质的少数非线性规划问题 另一种是基于循环迭代算法的 多适用于具有良好函数解析性质的少数非线性规划问题 另一种是基于循环迭代算法的数值求解数值求解法 适用于大部分非线性规划问题 在进一步讨论 法 适用于大部分非线性规划问题 在进一步讨论解析解法解析解法之前 先引入非线性规划问题之前 先引入非线性规划问题全局最优解全局最优解和和局部最 优解 局部最 优解的定义 的定义 2 非线性规划的基本性质非线性规划的基本性质 定义定义 2 1 全局最优解全局最优解 设设 f x为目标函数 为目标函数 S 为可行域 为可行域 x S 若对每一个 若对每一个xS 都有都有 f xf x 则称则称 x为极小化问题 为极小化问题 2 3 6 的全局最优解 最小 定义 的全局最优解 最小 定义 2 2 局部最优解局部最优解 设设 f x为目标函数 为目标函数 S 为可行域 为可行域 x S 若存在 若存在 x的一个的一个 邻 域 邻 域 S 使得对每一个 使得对每一个x S 都有都有 f xf x 则称则称 x 为极小化问题 为极小化问题 2 36 的局部最优解 最小 的局部最优解 最小 凸规划是非线性规划中一种重要的特殊情况 具有许多良好 的解析性质 可以用解析解法求解 凸规划是非线性规划中一种重要的特殊情况 具有许多良好 的解析性质 可以用解析解法求解 定义定义 2 3 设设 S 为为 n 中的一个集合 若对中的一个集合 若对 S 中任意两点 连接它们的线段仍属于 中任意两点 连接它们的线段仍属于 S 即对 即对 S 中任意两点中任意两点12 x x 及每个实数及每个实数 1 0 都有 都有 12 1 xxS 则称则称 S 为凸集 为凸集 12 1 xx 称为称为 1 x 和和2 x 的凸组合的凸组合 定义 2 4 设 S 为定义 2 4 设 S 为 n 中的非空凸集 中的非空凸集 f 是定义在 S 上的实 函数 如果对任意的 是定义在 S 上的实 函数 如果对任意的12 x x S 及每个数 S 及每个数 0 1 都有 0 1 都有 1212 1 1 fxxf xf x 则称 则称 f 为 S 上凸函 数 如果对任意相异的 为 S 上凸函 数 如果对任意相异的12 x x S 及每个数 S 及每个数 0 1 都有 0 1 都有 1212 1 1 fxxf xf x 则称 则称 f 为 S 上的严格凸函 数 如果 为 S 上的严格凸函 数 如果 f 为 S 上的凸函数 则称为 S 上的凸函数 则称 f 为 S 上的凹函为 S 上的凹函数 定义 2 5 若式 2 33 的定义 2 5 若式 2 33 的 f x 是凸函数 式 2 34 的是凸函数 式 2 34 的 i g x 是凹函数 是凹函数 j hx 是线性函数 则求凸函数在凸集上的极小点问 题称为凸规划 凸规划的解析解具有以下性质 引理 2 1 设 S 是 是线性函数 则求凸函数在凸集上的极小点问 题称为凸规划 凸规划的解析解具有以下性质 引理 2 1 设 S 是 n 中的凸集 中的凸集 f是定义在是定义在 S 上的凸函数 则 上的凸函数 则 f 在 S 的内部连续 引理 2 2 设 在 S 的内部连续 引理 2 2 设 f 是一个凸函数 是一个凸函数 x n 在 在x处处 f x 取有限 值 则 取有限 值 则 f 在在 x 处沿任何方向都存在右侧导数和左侧导数 包括 处沿任何方向都存在右侧导数和左侧导数 包括 定义定义 2 6 设函数设函数 n f x x 存在一阶偏导数 则称向 量 存在一阶偏导数 则称向 量 12 T n fff f x xxx 为为 f x 在点在点 12 T n xx xx 处的梯度 处的梯度 为方便非线性规划的求解 还要引入函数梯度和为方便非线性规划的求解 还要引入函数梯度和Hesse矩阵概念 矩阵概念 定义定义 2 7 设函数设函数 f x 存在二阶偏导数 则称矩阵存在二阶偏导数 则称矩阵 222 2 1211 222 2 2122 222 2 12 n n nnn fff x xx xx fff H xxxxxx fff xxxxx 为为 f x 在点在点 12 T n xx xx 处的处的 Hesse 矩阵 矩阵 由梯度和由梯度和 Hesse 矩阵的上述定义 无约束非线性规划问题 矩阵的上述定义 无约束非线性规划问题 2 37 的局部极小点的解析解可由以下定理求出 的局部极小点的解析解可由以下定理求出 引理引理 2 3 局部极小点的一阶必要条件局部极小点的一阶必要条件 设函数设函数 f x 在点在点 x 处可微 若处可微 若 x 是局部极小点 则梯度是局部极小点 则梯度 0 xf 引理引理 2 4 局部极小点的二阶必要条件局部极小点的二阶必要条件 设函数设函数 f x 在点在点 x 处二次可微 若处二次可微 若 x 是局部极小点 则梯度是局部极小点 则梯度 0 xf 并且 并且 Hesse 矩阵矩阵 H x 是半正定的 是半正定的 上述条件均非充分条件 当上述条件均非充分条件 当x满足这些条件时无法判定满足这些条件时无法判定x是 否确为极小点 要实现这一目的需要 是 否确为极小点 要实现这一目的需要 Hesse 矩阵的正定性条件 矩阵的正定性条件 3 非线性规划的解析求解非线性规划的解析求解 定理定理 2 2 设函数设函数 f x 在点在点 x 处二次可微 若梯度处二次可微 若梯度 0 xf 且且 Hesse 矩阵矩阵 H x 正定 则正定 则 x 是局部极小点 是局部极小点 应该指出 解析法求解非线性规划问题 不论是无约束还是有约束 一般均只能求解低维空间中较为简单的问题 对于较复杂的非线性规 划问题 更有效的是数值迭代算法 对于较复杂的非线性规 划问题 更有效的是数值迭代算法 4 非线性规划问题的数值求解非线性规划问题的数值求解 4 有约束非线性规划问题的求解有约束非线性规划问题的求解 对于有约束的非线性规划问题 通常用以下三个方法三个方法处处理其约束条件进而实 现数值迭代求解 第一种方法是将迭代点序列严格控制在可行域内将迭代点序列严格控制在可行域内 从而执行的迭代过程实际 上为无约束优化过程 第二种方法称为序列无约束优化方法序列无约束优化方法 简称SUMT方法 该方法通过将约束项 处理成制约函数项加入到目标函数中形成新的广义目标函数 将约束项 处理成制约函数项加入到目标函数中形成新的广义目标函数 从而将有约束问题 化为广义目标函数下的无约束问题 再利用前述的无约束优化迭代算法求解 拉 格朗日乘子法就是这类方法的一个特例 第三种是在迭代点附近的序列线性化或序列二次函数逼近方法在迭代点附近的序列线性化或序列二次函数逼近方法 通过运用迭 代点附近的台劳展