运筹学规划的数学基础.pdf

Lchming 优化设计就是借助 优化设计就是借助最优化数值计算方法最优化数值计算方法 最优最优 化原理和方法化原理和方法 与与计算机技术 计算机技术 求取工程问题的求取工程问题的最最 优设计方案优设计方案 最优设计参数最优设计参数 包括 包括 1 建立数学建立数学 模型模型 2 运算求解运算求解 一 设计变量 参数 可一 设计变量 参数 可以以 进行进行调整和优选的独立参数调整和优选的独立参数 连续变量和离散变量连续变量和离散变量 二 约束条件 对设计变量的二 约束条件 对设计变量的 取值加以某些限制的条件取值加以某些限制的条件 三 目标函数 设计中所三 目标函数 设计中所 追求的目标 且可由设计追求的目标 且可由设计 变量表示的函数变量表示的函数 12 min 0 1 0 1 可行域 T n n uv xxx F stgumhvpn xxRxxR x x xxxx 设计变量的数目称为优化问题的维设计变量的数目称为优化问题的维 数数 设计空间 设计空间 由由n个设计变量为坐标所组成个设计变量为坐标所组成 的实空间 所有设计点的集合 的实空间 所有设计点的集合 等值线或等值面 具有相等目标等值线或等值面 具有相等目标 函数值的设计点构成的线或面 函数值的设计点构成的线或面 可行域可行域 在设计空间中 由满足所有在设计空间中 由满足所有 约束条件的设计点组成的区域 约束条件的设计点组成的区域 寻优思路 寻优思路 k k kk kkkk s s x x x x 2 1 2 1 1 2 1 1 Sxx 新点的可行性条件 适用性条件 新点的可行性条件 适用性条件 收敛精度收敛精度指相邻两次寻优的设计点或指相邻两次寻优的设计点或 目标函数值的接近程度 考察两设计点目标函数值的接近程度 考察两设计点 的最短距离或两目标函数值的落差 绝的最短距离或两目标函数值的落差 绝 对或相对值 其允许最小值称为收敛对或相对值 其允许最小值称为收敛 精度值 精度值 第第2章章 优化设计的数学基础优化设计的数学基础 优化设计问题多数是求解多变量非线性函数优化设计问题多数是求解多变量非线性函数 的极值问题 可见 是建立在多元函数的极的极值问题 可见 是建立在多元函数的极 值理论基础上的 值理论基础上的 2 1 函数的方向导数与梯度函数的方向导数与梯度 2 2 凸集 凸函数与凸规划凸集 凸函数与凸规划 2 3 无约束优化问题的极值条件无约束优化问题的极值条件 2 4 约束优化问题的极值条件约束优化问题的极值条件 2 1 函数的方向导数与梯度函数的方向导数与梯度 一 方向导数一 方向导数 一个二元函数一个二元函数F x 在点在点处的偏导数处的偏导数 函数沿坐函数沿坐 标轴的变化率标轴的变化率 沿某一方向沿某一方向 d 的变化率 称为沿该方向的方向导数的变化率 称为沿该方向的方向导数 2 0 2 0 12 0 2 0 1 0 2 0 1 0 2 0 1 0 21 0 1 0 1 0 lim lim 2 1 x xxFxxxF x F x xxFxxxF x F x x x x 0 2 0 10 x x x 00000 112212 0 lim FF xx xxF xx x S 000000 112211212 xx xxxx xxx S 沿某一方向沿某一方向 d 的变化率 称为沿该方向的方向导数的变化率 称为沿该方向的方向导数 00000 112212 0 00000000 112121122112 12 00 12 00 12 12 0000 123 123 lim limlim coscos coscoscos FF xx xxF xx F xx xF xxF xx xxF xx x xx xx FF xx FFFF xxx x S xx xxxx S S n元函数在点元函数在点 x0 处沿处沿d d 方向的方向导数方向的方向导数 0000 0 12 12 1 coscoscos cos n n n i i i ffff xxx f x xxxx x S O x2 x1x10 x20 x0 x1 x2 S x S 1 2 二 函数的梯度二 函数的梯度 函数在该点的梯度 函数在该点的梯度 grads 为 为 设设 S 是单位向量 则 是单位向量 则 000 12 12 coscos FFF xx xxx S 000 1 212 cos cos FFF xx xxx d T x F x F F 2 0 1 0 xx x 12 coscos T d 0 cos T F FFF x xSxSxS S 1 2 cos cos S O x2 x1 x0 变化率为零的方向 最速下降方向 下降方向 上升方向 最速上升方向 f x0 f x0 梯度方向是函数值增加最快的方向 而梯度梯度方向是函数值增加最快的方向 而梯度 的模就是函数变化率的最大值的模就是函数变化率的最大值 梯度方向与等值线的关系 0 00 cos T f fff x xSxS S 设 设 则有则有 为单位向量为单位向量 0 kTk f xS 0 kTk f xS 多元函数的梯度多元函数的梯度 0 0 1 20 12 T n n f x f fff xf xxx f x x x x 00 00 1 cos cos n T i i i ff fSff x xx xxS S 梯度梯度模 模 函数的梯度方向与函数等值面相垂直 也就是和函数的梯度方向与函数等值面相垂直 也就是和 等值面上过等值面上过 x0 的一切曲线相垂直 的一切曲线相垂直 由于梯度的模因点而异 即函数在不同点处的最由于梯度的模因点而异 即函数在不同点处的最 大变化率是不同的 因此 梯度是函数的一种局部大变化率是不同的 因此 梯度是函数的一种局部 性质 性质 梯度是一个向量梯度是一个向量 梯度方向是函数具有最大变 梯度方向是函数具有最大变 化率的方向 梯度方向是函数值的最速上升方化率的方向 梯度方向是函数值的最速上升方 向 而向 而负梯度方向是函数值的最速下降方向负梯度方向是函数值的最速下降方向 0 1 2 2 0 1 n i i f f x x x 0 f x 上机时间 上机时间 周日周日1 2节 节 3月月8 15 22 29日 日 上机地点 上机地点 4 4211 上机内容 进退法 黄金分割法上机内容 进退法 黄金分割法 负梯度法 负梯度法 Powell法法 Powell法法 惩罚函数法惩罚函数法 例题例题 2 0求函数求函数在在 点点 3 2 T 的的 梯度 梯度 解解 在点在点x 1 3 2 T处的梯度为 处的梯度为 22 121 44fxxx x 11 2 2 24 2 f xx f xf x x 1 1 1 2 24 2 2 4 x x f x x 2 2 5 3 3 5 4 1 1 5 2 2 5 3 0 5 10 15 22 533 54 1 1 5 2 2 5 3 x1 x2 2 2 4 4 4 6 6 6 6 8 8 8 8 10 10 figure B卷试题2 x1 x2 meshgrid 6 0 1 10 6 0 1 6 z x1 5 2 x2 2 v 10 25 49 64 81 100 c h contour x1 x2 z v clabel c h hold on x1 x2 meshgrid 5 0 1 5 5 0 1 5 z x1 2 x2 2 v 25 c h contour x1 x2 z v plot 0 0 0 6 plot 6 0 0 0 stop 6 4 20246810 6 4 2 0 2 4 6 10 10 10 10 25 25 25 25 25 25 25 49 49 49 49 49 64 64 64 81 81 81 100 100 100 x 1 x 2 2 2 12 22 112 21 32 min 5 250 0 0 fxx stg xxx gx gx x x x 绘出过该绘出过该 点的目标点的目标 函数等值函数等值 线 其法线 其法 线为该点线为该点 处梯度方处梯度方 向 向 例例2 1求二元函数求二元函数在在 1 1 点沿点沿和和的方向导数的方向导数 同一函数在不同方向同一函数在不同方向 上的方向导数不同 上的方向导数不同 4 2 2 1 xxF x 4 4 2 1 1 S 6 3 2 1 2 S 4 2 代入 4 2 0 2 1 21 2 0 1 0 x xx xF x xx x F x F F T 666 1 cos cos 2 1 2 0 1 0 1 0 x F x FFxx S x 465 1 2 0 S xF 2 2 凸集 凸函数与凸规划凸集 凸函数与凸规划 如在整个可行域内有多个极值点 则每个称为如在整个可行域内有多个极值点 则每个称为局局 部极值点部极值点 其函数值最小的称为 其函数值最小的称为全域极值点全域极值点 一 一 凸集凸集 其中任意两点的连线整个包含其中其中任意两点的连线整个包含其中 12 1D xx 二 凸函数二 凸函数 定义在凸集定义在凸集D上的函数上的函数F 如满足以下条件 如满足以下条件 则 则 F为为D上的凸函数 如不等式反向 则为上的凸函数 如不等式反向 则为 凹函数凹函数 凸函数的性质 凸函数的性质 1 在在D上也是凸函数 上也是凸函数 2 F为凸函数的充分必要条件是 为凸函数的充分必要条件是 即即函数切线永远在曲线以下函数切线永远在曲线以下 2121 11xxxxFFF xF 21 xxFF 12112 xxxxx T FFF 凸函数的函数切线永远在曲线以下 凸函数的函数切线永远在曲线以下 最优点最优点 极小点极小点 处于谷底 对于某个设计变处于谷底 对于某个设计变 量 目标函数为单峰函数 量 目标函数为单峰函数 任何方向上的任何方向上的 寻优区间为单峰区间 寻优区间为单峰区间 设计方法都是在这一设计方法都是在这一 条件下提出的 条件下提出的 三 凸规划三 凸规划 如果如果目标函数和不等式约束函数都是凸目标函数和不等式约束函数都是凸 函数函数 则该约束优化问题为凸规划 则该约束优化问题为凸规划 性质 性质 1 可行域为凸集 可行域为凸集 2 任何局部最优解都是全局最优 任何局部最优解都是全局最优 解 解 3 最优解的充分必要条件是 最优解的充分必要条件是 0 xxx T F 由于工程问题数学模型的性态比较复杂 难以证明其是否为凸由于工程问题数学模型的性态比较复杂 难以证明其是否为凸 规划 因此 通常从几个初始点出发 看是否能收敛于同一点规划 因此 通常从几个初始点出发 看是否能收敛于同一点 上 否则从中选取最好的方案 作为最优设计的结果 即从局上 否则从中选取最好的方案 作为最优设计的结果 即从局 部最优解中选取全局的 部最优解中选取全局的 定义定义1 1 对于问题对于问题 1 1 设 设 若存在 若存在 使得对一切使得对一切 且 且 都有 都有 则称 则称X X 是是f X f X 在在D D上上 的局部极小值点 局部最优点 特别地当的局部极小值点 局部最优点 特别地当时 时 若若 则称 则称X X 是是f X f X 在在D D上的严格局部极小值点 严上的严格局部极小值点 严 格局部最优点 格局部最优点 DX 0 DX XX XX XfXf XfXf 定义定义2 2 对于问题对于问题 1 1 设设 对任意的对任意的 都有都有 则称则称X X 是是f X f X 在在D D上的全局极小值点 全域最优点 特别地当上的全局极小值点 全域最优点 特别地当 时 若时 若 则称 则称X X 是是f X f X 在在D D上的严格全局极小值上的严格全局极小值 点 严格全域最优点 点 严格全域最优点 DX DX XfXf XX XfXf 四四 全域最优点全域最优点 当目标函数是凸函数当目标函数是凸函数 约束区域是凸集时约束区域是凸集时 才才 能保证取得全域最优点能保证取得全域最优点 但工程实际问题往往不是凸但工程实际问题往往不是凸 规划问题规划问题 所以采用常用的优化方法一般得到的是局所以采用常用的优化方法一般得到的是局 部最优点部最优点 对一个复杂的工程优化问题对一个复杂的工程优化问题 往往难于判断其往往难于判断其 是否为凸规划问题是否为凸规划问题 故求解工程优化问题大多从多个故求解工程优化问题大多从多个 初始点出发初始点出发 进行迭代进行迭代 如果不同的初始点都收敛于如果不同的初始点都收敛于 同最优点同最优点 这该点就是全局最优点这该点就是全局最优点 如果得到一些不如果得到一些不 同最优点同最优点 则它们都是局部最优点则它们都是局部最优点 应通过比较这些应通过比较这些 局部的最优点局部的最优点 取其目标函数最小的为全局最优点取其目标函数最小的为全局最优点 四 二次函数 二次型及正定矩阵四 二次函数 二次型及正定矩阵 二次型二次型 xTG x 标准二次型标准二次型 222 123121 323 123 23648 57910 xfxxxx xx xx x xxx 1 2 3 132 32457910 243 T x xf x xxxxx 1 2 xx Gxb x TT fc 222 2 1121 222 2 2122 222 2 12 n n nnn fff xx xx x fff x xxx x fff x xx xx G 正定即要求其各阶主子式均大于零 正定即要求其各阶主子式均大于零 判定矩阵正定与负定的方法一般是检验矩阵的各阶判定矩阵正定与负定的方法一般是检验矩阵的各阶顺序顺序 主子式主子式 如均为大于零 则矩阵正定 如呈负 正交替 如均为大于零 则矩阵正定 如呈负 正交替 变化 则矩阵负定 变化 则矩阵负定 1 1121n 1 11221222n 1 1 2122 n1n2nn aaa aaaaa a0 0 0 aa aaa 222 2 1121 222 2 2122 222 2 12 n n nnn fff xx xx x fff x xxx xc fff x xx xx f H H x xx xBxx 正定即要求正定即要求各阶主子式均大于零 各阶主子式均大于零 判定矩阵正定与负定的方法一般是检验矩阵的各阶判定矩阵正定与负定的方法一般是检验矩阵的各阶顺序顺序 主子式主子式 如均为大于零 则矩阵正定 如呈负 正交替 如均为大于零 则矩阵正定 如呈负 正交替 变化 则矩阵负定 变化 则矩阵负定 xH 222 123122331 123 246810 35713 fxxxx xx xx x xxx x 1 1121n 1 11221222n 1 1 2122 n1n2nn aaa aaaaa a0 0 0 aa aaa 海森矩阵海森矩阵 2 3 无约束优化问题的极值条件无约束优化问题的极值条件 一 多元函数的泰勒展开式一 多元函数的泰勒展开式 一元函数在一元函数在xk点的点的泰勒展开式泰勒展开式为 为 N元函数在点元函数在点xk的的泰勒展开式泰勒展开式则为 则为 用矩阵形式表示 用矩阵形式表示 2 2 1 kkkkk xxxFxxxFxFxF n ji k jj k ii ji k n i k ii i k k xxxx xx F xx x F FF 1 2 1 2 1xx xx kkTk T k k nn k k n kkk n i k ii i k FF xx xx xx x F x F x F xx x F xxxxxx xxxx 22 11 21 1 kk T k k nn k k n k n k n k n kkk n kkk T k nn k k n ji k jj k ii ji k F xx xx xx x F xx F xx F xx F x F xx F xx F xx F x F xx xx xx xxxx xx F xxxxx xxx xxx xxx x 2 22 11 2 2 2 2 1 2 2 2 2 2 2 12 2 1 2 21 2 2 1 2 22 11 1 2 kk T kkkTk FFFFxxxxxxxxxx 2 2 1 目标函数在极值点附近是二次函数目标函数在极值点附近是二次函数 多元函数泰勒展开多元函数泰勒展开 000 1 2 TT fffxxxxx H xx 0 0 12 T n fff f xxx x x 0 222 2 1121 222 22 212200 222 2 12 n n nnn fff xx xx x fff x xxx xf fff x xx xx x xH x 二 二 无约束优化问题的极值条件无约束优化问题的极值条件 1 在在处取得极值 其处取得极值 其必要条件必要条件是是 即在极值点处函数的梯度为即在极值点处函数的梯度为n维零向量 维零向量 为了判断从上述必要条件求得的为了判断从上述必要条件求得的是否是极值点 需是否是极值点 需 建立极值的充分条件 建立极值的充分条件 根据函数在根据函数在点处的泰勒展开式 考虑上述极值必要点处的泰勒展开式 考虑上述极值必要 条件 可得相应的充分条件 条件 可得相应的充分条件 海森海森赛赛矩阵矩阵Hessian 12 T n fff f xxx x x0 x x x 0 2 2 xF dx xFd 2 xHx F 12 min T n xxx F x x x x 处取得极值充分条件处取得极值充分条件 222 2 1121 222 2 2122 222 2 12 n n nnn fff xx xx x fff x xxx x fff x xx xx H x x正定 即要求即要求各阶主子式均大于零 各阶主子式均大于零 判定矩阵正定与负定的方法一般是检验矩阵的各阶判定矩阵正定与负定的方法一般是检验矩阵的各阶顺序顺序 主子式主子式 如均为大于零 则矩阵正定 如呈负 正交替 如均为大于零 则矩阵正定 如呈负 正交替 变化 则矩阵负定 变化 则矩阵负定 xH x 1 1121n 1 11221222n 1 1 2122 n1n2nn aaa aaaaa a0 0 0 aa aaa 例题例题2 附加附加 3322 12121 339fxxxxx x 用泰勒展开将函数用泰勒展开将函数 在点在点简化成线性函数与二次函数 简化成线性函数与二次函数 1 1 1 T x 1 x 1 3f x 1 2 11 1 2 22 0369 336 xx f xx x x 1 12 1 2 660120 06600 x f x x x 解 函数在点解 函数在点的函数值 梯度和二阶导数矩阵 的函数值 梯度和二阶导数矩阵 11 1 22 11 11 xx xx xx 简化为线性函数 简化为线性函数 二次二次 1 1 1 22 33 1 36 T fffxxxxxxx 1 1 1 1 2 1 1 1 2 TT fffxf xxxxxxxxx 22 21112 366 1 6123 xxxxx 0 0 5 1 1 5 2 0 0 5 1 1 5 2 6 4 2 0 2 4 6 0 0 5 1 1 5 2 0 0 5 1 1 5 2 6 4 2 0 2 4 6 例例2 2求函数的极值求函数的极值 得驻点 得驻点 2 2 在 在 0 0 展开展开 海森矩阵正定 所以海森矩阵正定 所以 2 4 为极小点 为极小点 对应的目标函数值为极小值 对应的目标函数值为极小值 22 1212 min447fxxxx x 04 20 02 02 20 02 H 12 T ff f xx x x0 0 2 2 12 00 2 2 1 0 0 f x f f x x xH x 在在 0 0 展开展开 000 1 2 20 1 744 022 TT T fff xxxxx H xx xxx 0 2 2 12 00 2 2 1 0 20 02 0 f x f f x x xH x 22 1212 min447fxxxx x 写成矩写成矩 阵形式阵形式 10 744 01 T f xxxx 2 4 约束优化问题的极值条件约束优化问题的极值条件 判断和检验某可行点是否为不等式约束多元函数判断和检验某可行点是否为不等式约束多元函数 的约束极值点的的约束极值点的必要条件必要条件是库恩是库恩 塔克 塔克 Kuhn Tucker 条件 对于凸规划问题 条件 对于凸规划问题 K T条件又是条件又是 充分条件 而判别所找到的极值点是全域还是局充分条件 而判别所找到的极值点是全域还是局 部极值点尚无统一而有效的方法 部极值点尚无统一而有效的方法 1 库恩 库恩 塔克条件塔克条件 K T条件 条件 对于多元函数不等式的约束优化问题 对于多元函数不等式的约束优化问题 min 01 2 01 2 n u v FR stgu hv m p xx x x 可行域 其中 其中 或 或 称为拉格朗日乘子 称为拉格朗日乘子 库恩库恩 塔克条件表明 如点塔克条件表明 如点是函数是函数的极值点 的极值点 要么要么 此时 此时 要么 要么目标函数的梯目标函数的梯 度等于起作用 不 等式约束梯度的非负线性组合度等于起作用 不 等式约束梯度的非负线性组合 K T条件条件 0f x 0 j x f x 11 0 0 0 0 0 0 0 0 uuvv uv uv u uu v pm u Fgh g g h xxx x x x 不起作用约束起作用的0 不起作用约束对应 等式约束才是可行点 不限制 0 uv v 0 u 同时具有等式和不等式约束的优化问题同时具有等式和不等式约束的优化问题 min f x 0 1 2 j st gjm x 0 1 2 k hkp x 1 0 1 2 0 0 0 p j k jk j Jk iii j j k g hf in xxx gjJ jJ h x x K T条件 该点在约束边界上 如 果不在边界 则为无约 束优化问题的极值 二维问题二维问题K T条件的几何意义 条件的几何意义 目标函数负梯度方向位于各约束函数负梯度方向之间 目标函数负梯度方向位于各约束函数负梯度方向之间 K K T T条件主要用以检验设计点条件主要用以检验设计点 1 0 1 0 T T是否为是否为 约束极值点或局部最优点 并用以判断和消除那约束极值点或局部最优点 并用以判断和消除那 些不再起作用的约束条件 以保证在迭代中维持些不再起作用的约束条件 以保证在迭代中维持 正确的起作用的约束集合正确的起作用的约束集合 例例2 2 3S 3S 库恩库恩 塔克 塔克 K K T T 条件应用举例 条件应用举例 22 12 min 2 fxx x 2 112 22 31 1 0 0 0 gxx gx gx x x x s t 判断判断 1 0 T 是否为约束最优点 是否为约束最优点 11 1 2 0 1 2 0 2 2 2 0 2 f xx f fx x x x x x x 1 1 1 0 22 11 x g x x 2 0 1 g x 1 当前点当前点为可行点 因满足约束条件为可行点 因满足约束条件 1 10 T x 1 1 1 2 1 3 0 0 10 g g g x x x 2 在在起作用约束起作用约束为为 g1 和和 g2 因因 1 10 T x 3 各函数的梯度各函数的梯度 1122 0fgg xxx 12 220 0 011 1 2 10 10 4 求拉格朗日乘子 求拉格朗日乘子 由于拉格朗日乘子由于拉格朗日乘子均为非负均为非负 说明 说明 满足满足K T条件 是一个局部最优点 条件 是一个局部最优点 1 10 T x 22 12 min 2 fxx x 2 112 22 31 1 0 0 0 gxx gx gx x x x s t x1 f 0 25 g3 x 0 g3 0 1 2 x2 f 5 f 4 f 2 25 f 1 g1 x 0 g2 x 0 g1 g2 f f C g2 g3 g1 A B f 图 8