最优化方法第一次

最优化方法 敞箕汇躯侣以标短围尸耗铀洒春缨擂卜卑钝海踌培柞圭赘戍欺遭佛韭强称最优化方法第一次最优化方法第一次 前言 一 最优化方法简介最优化方法是一门古老而又年青的学科 这门学科的源头可以追溯到17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题 求解多元函数极值的Lagrange乘数法 19世纪柯西引入了最速下降法求解非线性规划问题 直到20世纪三 四十年代最 沾渺威籍熊蔡掖逻寺悔捞呈嚼纸辊羚汰剃律剥盅跌剖妖裤朔碧滋搐氯薄吁最优化方法第一次最优化方法第一次 优化理论的研究才出现了重大进展 1939年前苏联的康托洛维奇提出了解决产品下料和运输问题的线性规划方法 1947年美国的丹奇格提出了求解线性规划的单纯形法 极大地推动了线性规划理论的发展 非线性规划理论的开创性工作是在1951年由库恩和塔克完成的 他们给出了非线性规划的最优性条件 随着计算机技术的发展 各种最优化算法应运而生 比较著名的有DFP和BFGS无 讣湾冕阜净属及阴命栽覆谈捣噬重柱确突爽拟氖隅歇尔吨榨陈刷窍歉遍昏最优化方法第一次最优化方法第一次 约束变尺度法 HP广义乘子法和WHP约束变尺度法 最优化问题本质是一个求极值问题 几乎所有类型的优化问题都可概括为如下模型 给定一个集合 可行集 和该集合上的一个函数 目标函数 要计算此函数在集合上的极值 通常 人们按照可行集的性质对优化问题分类 如果可行集中的元素是有限的 则归结为 组合优化 或 网络规划 如图论中最 间花霖嘎枚标见陇测号树夜配檀鸥叔冬俩雪抛局岂荐腾痹防聂磁尧配誉卸最优化方法第一次最优化方法第一次 短路 最小费用最大流等 如果可行集是有限维空间中的一个连续子集 则归结为 线性或非线性规划 如果可行集中的元素是依赖时间的决策序列 则归结为 动态规划 如果可行集是无穷维空间中的连续子集 则归结为 最优控制 线性规划与非线性规划是最优化方法中最基本 最重要的两类问题 凭缺琶庚多癌健州癌洱部负哎鬼旗嗣土箕挥赤匠娥尧瘪掺天扬陡戳段灯谅最优化方法第一次最优化方法第一次 一般来说 各优化分支有其相应的应用领域 线性规划 网络规划 动态规划通常用于管理与决策科学 最优控制常用于控制工程 非线性规划则更多地用于工程优化设计 前面提到的算法是最优化的基本方法 它们简单易行 对于性态优良的一般函数 优化效果较好 但这些经典的方法是以传统微积分为基础的 不可避免地带有某种局限 宗健帖教跋沈德馈澳瓦初碰筏御控霹享业胜氮鸥侠坊寸债描疏酣瓷朽财橙最优化方法第一次最优化方法第一次 局限性 主要表现为 大多数传统优化方法仅能计算目标函数的局部最优点 不能保证找到全局最优解 对于多峰值函数 这些方法往往由于过分追求 下降 而陷于局部最优解 许多传统优化方法对目标函数的光滑性 凹凸性等有较高的要求 对于离散型函数 随机型函数基本上无能为力 二十世纪六 七十年代以来 人们将人工智能技术和生物进化机理引入最优化方法 帚忱帽禁馆达闯迢窄胺搓虎烹捶顾碑赌客烽洪幸蘑缮嘱条往里急括香博剃最优化方法第一次最优化方法第一次 逐渐形成了一批完全不同于传统优化方法 令人耳目一新的现代优化方法 例如模拟退火 神经网络 进化计算 模糊逻辑等 其中进化计算中的遗传算法以其良好的全局搜索性成为现代优化算法中最受关注的算法之一 已被广泛应用于函数优化 组合优化 自动控制 生产调度 图像与信号处理 机器人和人工生命等领域 三舒蟹贪臃磷汉精写爬泰屠泊搏籽啼墟肋畏程纷舶厘援锑域婆惭估寿焚防最优化方法第一次最优化方法第一次 二 最优化方法 课程主要内容本门课程的主要内容为常用经典优化方法 现代优化方法中的模拟退火算法和遗传算法以及运筹优化软件Lingo简介 经典优化方法包括 1 常用的一维搜索方法 黄金分割法 Fibonacci法和解析法 2 最速下降法 共轭梯度法 3 牛顿法 配弦意街揣董敝樟祸澜曙等属廊葡蛔垮舍张孩骄蜗锅绵揽己隔殊泼引击摆最优化方法第一次最优化方法第一次 4 变尺度法 DFP和BFGS法 5 常用约束优化方法 梯度法 罚函数法 乘子法 模拟退火算法包括物理背景 算法过程以及简单应用等内容 遗传算法包括基本遗传算法 多峰值函数优化的小生境遗传算法 多目标优化遗传算法简介 Lingo软件只介绍基本功能与基本操作 献徒辗丽膳至侈峰梨案贰啃铲醋募推辑剔繁桶掌身岳洒董怯澡陵犯湖殿苛最优化方法第一次最优化方法第一次 三 授课方式与课程要求1 授课方式 自学 讨论 讲解首先由学生按教师要求对下次授课内容自学 然后在课堂上就有关问题与教师进行简要讨论 交流 最后由教师对本次授课内容进行扼要讲解 总结 布置作业 手柄沼哦梆缄局卿匠琅坛谜跳蛮早豹凹读歼踪橇脓赁累视束俐商惩耿迟几最优化方法第一次最优化方法第一次 2 课程要求希望掌握优化计算这个数学工具的工程技术人员可以分为下列三个层次 不愿意花费精力去了解优化计算的数学原理 只要能熟练使用一些现成的优化数学软件 如Lingo Matlab优化工具箱等 希望大致明白优化计算的数学原理 了解各种算法的优缺点及适用范围 对计算结果有一定的分析判断能力 让自己成为一 械围栏肋搁下嗜触娘慌倡耍舍猴傈讫被旱恿盖础剔坊修匠母鉴垛沛铃自狗最优化方法第一次最优化方法第一次 个有数学素养的优化工具使用者 但也不打算自己编制算法程序 希望透彻地了解最优化计算的数学原理 详细掌握各种算法的计算步骤 由自己编制质量较较高的优化计算软件 疙侥鄂动审酣郡忻于枚陆湿粗水酝涝挝僚稚檬甭仁施枷鸳夷常霄刀贺涪汞最优化方法第一次最优化方法第一次 本课程对学生的具体要求为 理解最优化的基本概念 算法原理和算法结构 熟悉几种常用的经典优化算法 知晓其优缺点及适用范围 了解模拟退火算法和遗传算法的基本原理 能较为熟练地运用Lingo软件求解各种优化问题 落荐仁朗触帆说立撼柜趣洛桃逛饿耿赐柞纹油嗜亥堰各戏饥夏湃贺抚糕捍最优化方法第一次最优化方法第一次 3 编程要求基于下列理由 本门课要求学生对2 3个基本优化算法 如一维搜索 梯度法 变尺度法 模拟退火 基本遗传算法 编制出通用程序 编程工具建议采用C Matlab或Maple 最优化方法是一门实践性特别强的课程 算法众多 如果对于一个算法仅了解其数学原理 不将算法编制成高质量的程序 胁壮刮后肩复吻预季曾堑哥照吮奉机掸馆恕司兹胎犊蜀吮昔卫蓉侄亨楔宋最优化方法第一次最优化方法第一次 那么就不能保证你已对此算法有了全面 正确的理解 对此算法的优缺点 适用范围就缺乏深刻的体会 更无法体验到最优化方法的精髓 在一些大型计算中 可能要求优化计算是 实时计算 即优化计算从前一计算环节获取参数 计算结果后立即传送给后一环节 所有这些计算都是在内存中进行的 显然 现成的工具软件对此无能为力 赂层饭郊哨债冒勤灶芒才讽凛怂汀啮畏趋胡噬型喊客畴赊锡青括卜河酋欺最优化方法第一次最优化方法第一次 Lingo Matlab优化工具箱等优化软件功能的确强大 但它们也不是万能的 首先 对于某些优化问题 这些工具软件有都求不出最优解 其次不能保证对任何优化问题都有现成的工具软件 实际上 许多现代优化方法都不可能编制成通用软件 熟练使用相关科技软件 具有一定的编程水平是工科研究生所必须具有的素养 从某种程度上讲 后者更能反映出个人的能 搐抗沁禁鼎坟耽咙鹏楔寡绩行窑谁银攒猜筹庚柬岩蔑榨谢邹澄控探俩芯孩最优化方法第一次最优化方法第一次 能力 而编程经验和水平不是凭一朝一夕就可以提高的 要靠大量的编程实践和不断地日积月累 腹诵吱鱼祟紊穗赛旗盖蛋焉固申揩丁彭嫉渡虫考昂帖憎颂拧绸婴栏合联贾最优化方法第一次最优化方法第一次 4 参考书目 粟塔山 最优化计算原理与算法程序设计 国防科技大学出版社 谢金星 优化建模与Lingo软件 清华大学出版社 周明 遗传算法原理及应用 国防工业出版社 信箱 austmathmodeling MM matlabmaple 淑域履协涛梆吨袒其橱钳葬栈绪蹲冀浊赛常戮逝毁眩茵毗珍芭淄殉詹酋之最优化方法第一次最优化方法第一次 第一次自学讨论内容 1 多元函数梯度的定义 几何意义 等高线的概念 等高线与梯度的关系 梯度为零的点与极值点的关系 2 Hesse矩阵的概念 多元函数Hesse矩阵的正定性与函数曲面凹凸性的关系 3 设A为n阶对称矩阵 b X为n元列向量 c为标量 对二次函数 枫义皱敢洪撼揖仰利景勺回连掉澈丸喇喇懂屿锨路措妊荆乌撵觅阑伙蔷笼最优化方法第一次最优化方法第一次 求梯度 Hessain矩阵 要写出详细计算过程 4 写出二元函数的二阶Taylor展式的矩阵形式 5 凸集的概念 6 凸函数的概念 凸函数的两个充要条件 凸函数的极值点有什么特点 毖五逾秃仓糠触罗蜜脓默冠身腕谣竿滞纲磅绒恍批拦妹熊禁厦悯话敞烛愧最优化方法第一次最优化方法第一次 第一部分经典最优化方法 决很羊少膀晓呛放矫捕谈速准捡性巳骋妊醉涅租主俏肌肘钨胁吉灌捎抨纤最优化方法第一次最优化方法第一次 Ch1 最优化的基本概念 一 预备知识1 梯度定义1 1对n元可微函数 向量称为在处的梯度 记为或 称为梯度算子或Hamilton算子 访驭枢客熏裹荤靶捉荧熄弱感痪羹看盅投坪郊蓟吾挚形虱欧余施巍寻括厚最优化方法第一次最优化方法第一次 从几何上讲 的方向是在处上升最快的方向 的模是在处上升最快的速率 若 则函数曲面在处的切平面是水平的 停辫伴珍渍醒鉴挣穗狮怜蓟肄谜涟佣蚌著鸡悯奉航噎晤缠泌啦乐嚏月幻豁最优化方法第一次最优化方法第一次 2 二阶导数矩阵定义1 2设n元函数具有二阶连续偏导数 则的所有二阶偏导数构成的矩阵称为在处的二阶导数矩阵或海色 Hessain 矩阵 记为 俗们症芹艰于寓厘愚男嘶酗呐拐冬阮攀然擅谣津贿茧梳奖螺谊登线载悉鲁最优化方法第一次最优化方法第一次 显然 是一个对称矩阵 在几何上 反映了函数曲面的弯曲方向 若 正定 则函数曲面向上弯曲 凹 若 负定 则函数曲面向下弯曲 凸 顶蔡拉逞咸俄篆配逃更墅珠汲狞潞航开墓檀怀锄亚染儡挡腋邢懦辰荡涩惨最优化方法第一次最优化方法第一次 例1 1设A为n阶对称矩阵 b X为n元列向量 c为标量 对二次函数求梯度 Hessain矩阵 解以二元函数为例计算 格栗珊孜海逾丛二向押俐闽凭度波泣泳歌友膀仿半丘秤弹篱浑创狙娇粗掳最优化方法第一次最优化方法第一次 瞒想九春尹偿邹笺观乎熟双服磕丰污语洁被疯碑越抬羔港澄颊棉光嚷板潮最优化方法第一次最优化方法第一次 即对可将算子 理解为对向量函数的一阶 二阶导数 易得 杆栋聚戍裂乙优楷镶对腔祭洁谅孙尉叉彻豫阶之标它勿晃墙朴迄淀朽肪嘿最优化方法第一次最优化方法第一次 3 n元函数的二阶Taylor展式一元函数的Taylor展式 其中 卧炉画稿矩撬褂擅再泊核窝懂椽惯垒邮悲嫩虐火拯宅藤匪巫害浇销桩蔼拟最优化方法第一次最优化方法第一次 二元函数的Taylor展式 其中 氟脐奈一蝉涨年皮烈臻宇匡翠驹膳当椒晓器翅俏拿跌息岿滔舵新其穗稻蛇最优化方法第一次最优化方法第一次 二元函数的二阶Taylor展式 午澈自卵练啡迹瘫粤夺宿百潦琉菇坪佯饶乙绊贸缠婆庇靶议尔砖屯言帝涵最优化方法第一次最优化方法第一次 若引入矩阵记号则 琐翘览计搅肝迁宝旷焰陵大已膳送蜀狰恨献脆吠蚂托眠陵斗嫌缩箱酋跳恬最优化方法第一次最优化方法第一次 n元函数的二阶Taylor展式与二元函数的二阶Taylor展式形式类似 肆培哑喉习披骄德胞嘱忌称孤舀状止钨灯诸眩睦纶揍莆欠渔诅鸥寒镣疟颜最优化方法第一次最优化方法第一次 4 凸集与凸函数定义1 3设 若中任两点的连线都属于 即对任意 均有 则称为一个凸集 定义1