最优化课件Y01_数学基础.pdf

最优化方法 Methods of Optimization 工程学院 胡圣荣 College of Engineering 学时 学时 36 先修 高等数学 程序语言 教材 先修 高等数学 程序语言 教材 0 方世杰 綦耀光 机械优化设计 机械工业出版社 方世杰 綦耀光 机械优化设计 机械工业出版社 2004 参考 参考 1 傅英定等 最优化理论与方法 国防工业出版社 傅英定等 最优化理论与方法 国防工业出版社 2008 2 袁亚湘 孙文瑜 最优化理论与方法 科学出版社 袁亚湘 孙文瑜 最优化理论与方法 科学出版社 1999 3 张光澄 非线性最优化计算方法 高等教育出版社 张光澄 非线性最优化计算方法 高等教育出版社 2005 4 各类优化教材 各类优化教材 理科 运筹学理科 运筹学 美美 Operation s Research 英英 Operational Research 工科 最优化 工科 最优化 Optimization Optimum Optimal method Optimization of methods 史记 史记 高祖本纪 运筹帷幄之中 决胜于千里之外 高祖本纪 运筹帷幄之中 决胜于千里之外 运筹学 运筹学 线性规划 线性规划 LP Linear Programming 非线性规划非线性规划NLP NonLinear 整数规划整数规划 动态规划 动态规划 DP Dynamic Programming 多目标规划多目标规划 随机规划随机规划 模糊规划等模糊规划等 图与网络理论图与网络理论 存储论存储论 排队论排队论 决策论决策论 对策论对策论 排序与统筹方法排序与统筹方法 可靠性理论等可靠性理论等 最优化 本课程 最优化 本课程 线性规划线性规划 非线性规划 线性规划 三 四十年代 二次世界大战 基础是线性变换 非线性规划 起源大约和微积分同步 形成学科体系 非线性规划 线性规划 三 四十年代 二次世界大战 基础是线性变换 非线性规划 起源大约和微积分同步 形成学科体系 1951 库恩和塔克 基础是求导 库恩和塔克 基础是求导 运筹学是一门基础学科 最优化不是一门独立学科 运筹学是一门基础学科 最优化不是一门独立学科 第第1讲 基本概念和数学基础 第 讲 基本概念和数学基础 第2讲 一维搜索 第 讲 一维搜索 第3讲 无约束优化 第 讲 无约束优化 第4讲 共轭方向与共轭梯度法 第 讲 共轭方向与共轭梯度法 第5讲 拟牛顿法 第 讲 拟牛顿法 第6讲 约束优化方法 第 讲 约束优化方法 第7讲 线性规划讲 线性规划 1 1 1 1 优化设计数学模型优化设计数学模型优化设计数学模型优化设计数学模型 1 2 1 2 基本解法基本解法基本解法基本解法 1 3 1 3 方向导数方向导数方向导数方向导数 1 4 1 4 函数梯度函数梯度函数梯度函数梯度 1 5 1 5 凸集凸集凸集凸集 1 6 1 6 凸函数凸函数凸函数凸函数 1 7 1 7 凸规划凸规划凸规划凸规划 1 8 1 8 泰勒展开泰勒展开泰勒展开泰勒展开 1 9 1 9 无约束极值条件无约束极值条件无约束极值条件无约束极值条件 1 10 1 10 有约束极值条件有约束极值条件有约束极值条件有约束极值条件 第1讲 基本概念和数学基础 1 1 优化设计数学模型 优化设计数学模型 即数学规划模型优化设计数学模型 即数学规划模型 MP mathematical programming min 0 1 0 1 i j f X s t g Xip hXjq 目标函数 约束条件 设计变量 目标函数 约束条件 设计变量 1 T n Xxx 三要素三要素 n 22 123 i 1 min iii cc tc t 例 曲线拟合例 曲线拟合 t subject to 线性规划线性规划 f X g X h X 均为线性函数均为线性函数 非线性规划非线性规划 其中有非线性函数 其中有非线性函数 无约束优化 约束优化 无约束优化 约束优化 非线性规划 线性规划 约束问题 维问题 一维问题 非线性问题 线性问题 无约束问题 最优化问题 n 求一维问题的极小点 常称求一维问题的极小点 常称一维搜索一维搜索或或直线搜索直线搜索 重要基础 重要基础 对多维对多维 整数规划整数规划 设计变量只能整数 设计变量只能整数 或离散值或离散值 非整数规划非整数规划 确定性优化 随机性优化 确定性优化 随机性优化 某些设计变量取值带有随机性 某些设计变量取值带有随机性 单目标优化 多目标优化 单目标优化 多目标优化 静态优化静态优化 设计变量与时间无关 设计变量与时间无关 动态优化动态优化 可行域可行域 约束集 约束集 可行解可行解 可行点 可行点 全局最优解全局最优解 g opt global 局部最优解局部最优解 l opt local optimum 严格严格l opt 严格严格g opt l opt 最优解最优解 极小点 极小点X f X f X 严格最优解严格最优解X f X 1超线性收敛 超线性收敛 p 2二阶收敛二阶收敛 线性收敛时必有线性收敛时必有c0 b 0 也是凸函数也是凸函数 若若y f x 是凸函数 则是凸函数 则 x y f x y 是凸集是凸集 x y y x2 5 x y y x2 5 x y y x2 5 哪个是凸集 哪个是凸集 1 7 凸规划 min 0 0 f X s tg X h X 凸规划凸规划 可行域为凸集 目标函数为凸函数 可行域为凸集 目标函数为凸函数 若若g X 为凸函数 为凸函数 h X 为线性函数 则可行域为凸集为线性函数 则可行域为凸集 凸规划的任一局部最优解都是它的整体最优解凸规划的任一局部最优解都是它的整体最优解 1 8 泰勒展开 海森矩阵 2 1 2 kkkk f xf xfxxxfxxx 一元 一元 2 1 2 kkk kk kiiiijj iij f Xf X f Xf Xxxxxxx xx x 多元 多元 11 22 12 k k n k nn xx fffxx xxx xx T kk f XXX T kk f XXX 222 2 1121 11222 222 1122 2122 222 2 12 1 2 nk k kkk nn n k nn nnn fff xx xx x xx fff xx xxxxxx xxxxx xx fff xxxxx 2 1 2 T kkk XXf XXX 梯度 海森矩阵 梯度 海森矩阵 对称对称 二次连续时二次连续时 二阶展开二阶展开 2 2 1 2 TT f Xf Xf XXXXXf XXXo XX T f Xf Xf XXXo XX 一阶展开一阶展开 1 2 TT f XX QXc Xb 线性函数线性函数 T f Xc Xb 2 0f Xcf X ii c xb 二次函数二次函数 1 2 ijijiiji a x xc xb 2 f XQXcf XQ 2 12 sinf Xxx 12 2 12 2sin cos xx f X xx 2122 2 1212 2sin2cos 2cossin xxx f X xxxx 例 例 222 1231 21 312 32345f Xxxxxxxxxx 例 把二次函数化为矩阵向量形式例 把二次函数化为矩阵向量形式 1 2 TT f XX QXc Xb 111213111 123212223212322 333313233 1 2 aaaxxb xxxaaaxcccxb xxbaaa 222 11 1222333121213 132323 111 222 iii a xa xa xa x xa x xa x xc xb 63 140 32 050 10 400 Qcb 与原式比较 得与原式比较 得 2222 11213 2222 21223 2222 31323 fxfx xfx x Qfxxfxfxx fx xfx xfx 0 0 0 b 或 或 63 1 32 0 10 4 4 5 0 c 看看2次项次项 看线性项看线性项看常数项看常数项 1 9 无约束极值条件 0 0fxfx 一元 一元 2 0 f Xf X 正定或负定多元 多元 f 0为极小 为极小 f 0 X 0 XTQX 0 负定 各阶顺序主子式负 正交替负定 各阶顺序主子式负 正交替 A正定正定 奇数阶负 偶数阶正奇数阶负 偶数阶正 22 1212 fx xxx 例 驻点 拐点 鞍点 例 驻点 拐点 鞍点 0f X 22 1212 fx xxx 等值线越密 目标函数变化越快 等值线越密 目标函数变化越快 极值条件的证明极值条件的证明 2 1 2 TT fXfXfXXXXXfXXX 2 1 2 T fXXXfXXX 1 f 0 0 极值时任意方向极值时任意方向S的方向导数为零 的方向导数为零 fT S 0 只有 只有 f 0 2 海森矩阵正定时为极海森矩阵正定时为极 fX 0 2 1 2 f xf xfxxxfxxx 一元时若一元时若f x 0 f x 0则为极小则为极小 2 1 2 kk f xfxxx k f x 定理定理1 1 若 若 2f X 正定 则极值点附近的等值面近似为同心椭球面正定 则极值点附近的等值面近似为同心椭球面 2 1 2 TT fXfXfXXXXXfXXX 2 1 2 T fXXXfXXX 2 1 2 T fXXXfXXXc 证明 故等值面近似为 这是以 证明 故等值面近似为 这是以X 为中心的椭球面 例 求极值 为中心的椭球面 例 求极值 22 1212 487fxxxx 1 1 2 2 240 280 f x x f x x 1 2 2 4 x x 22 2 112 22 2 212 20 02 kk kk f Xf X xx x H f Xf X xxx 正定 故正定 故 2 4 为极小点 配方法 为极小点 配方法 若 若 2f正定 非正定 非X 附近也是椭球面 但中心不为 附近也是椭球面 但中心不为X 见共轭部分见共轭部分 对二次函数有效的算法 对一般函数至少在极小点附近有效 对二次函数有效的算法 对一般函数至少在极小点附近有效 0 1 10 有约束极值条件 1 等式约束 拉格朗日乘子法 等式约束 拉格朗日乘子法 2 不等式约束 拉格朗日乘子法 不等式约束 拉格朗日乘子法 3 混合约束 混合约束 K T条件条件 一 等式约束一 等式约束一 等式约束一 等式约束 12 12 min 0 f x x s th x x 设设X x1 x2 为最优点为最优点 1122 xx txx t 12 12 0 fff x tx t txx 在在l上上f有最优点 有最优点 fh 1 2 12 0 x tff x t xx 最优点处 最优点处 f与切线垂 与切线垂 f与切面垂直与切面垂直 l任意任意 故最优点处 故最优点处 f与 与 h共线共线0fh 或或 l h 0 f 小 即 小 即 拉格朗日乘子法拉格朗日乘子法 构造拉格朗日函数 构造拉格朗日函数 L Xf Xh X 0 0 i L x L 极值条件 极值条件 0fh 0h X f 0 h t 另在另在l上上h 0 h与切线垂直 与切面垂直 在曲面 与切线垂直 与切面垂直 在曲面h上过上过X 作曲线作曲线 含义 含义 1 f h梯度之比梯度之比 2 约束变化引起 目标变化程度 等值面与约束面相切 约束变化引起 目标变化程度 等值面与约束面相切 解 曲面上取点 平面上取点解 曲面上取点 平面上取点 111 x y z 例 求曲面 到平面 的最短距离 例 求曲面 到平面 的最短距离 22 4323zxxyy 222 121212 22 111111 2222 min 32340 410 fxxyyzz s thxx yyz hxyz 41xyz 222 xy z 111 222 11 416 75 2448 xyz xyz 1 122 Lfhh 111 222 12 0 0 0 0 0 0 0 0 LLL xyz LLL xyz LL 2 8 f 二 不等式约束二 不等式约束二 不等式约束二 不等式约束 12 112 212 min 0 0 f x x s tg x x gx x 设设X 为最优点 为最优点 g1 X 0 相当 相当 1122 0fgg 其中其中 2 0 不起作用的约束不起作用的约束 1 0 见后面见后面K T条件条件 g1 0 有效约束有效约束 紧约束紧约束 12 112 min 0 f x x s tg x x 故故 g1 0 为不可行方向 即锥角为不可行方向 若 为不可行方向 即锥角为不可行方向 若 f在锥角内 则表示下降方向是不可行方向 即不能再下降了在锥角内 则表示下降方向是不可行方向 即不能再下降了 极值点极值点 反之 若 反之 若 f不在锥角内 则表示不在锥角内 则表示f还可下降 故不是极值点 还可下降 故不是极值点 uuvv fgh 其中其中 u 0 非负 不起作用的约束非负 不起作用的约束gu 对应对应 为为0 g1 0 g2 含义 含义 f在有效约束面梯度组成的锥角内在有效约束面梯度组成的锥角内 必要条件 对凸规划也是充分条件必要条件 对凸规划也是充分条件 不能判定局部极值还是全局极值不能判定局部极值还是全局极值 g2 0 g1 h