最优化方法第一次PPT课件

12
本课程对学生的具体要求为： ①理解最优化的基本概念、算法原理和 算法结构； ②熟悉几种常用的经典优化算法，知晓 其优缺点及适用范围； ③了解模拟退火算法和遗传算法的基本 原理； ④能较为熟练地运用Lingo软件求解各种 优化问题。
13
3. 编程要求 基于下列理由，本门课要求学生对2~3个
基本优化算法（如一维搜索、梯度法、变尺 度法、模拟退火、基本遗传算法）编制出通 用 程 序 ， 编 程 工 具 建 议 采 用 C++ 、 Matlab 或 Maple。
前面提到的算法是最优化的基本方法， 它们简单易行，对于性态优良的一般函数， 优化效果较好。但这些经典的方法是以传统 微积分为基础的，不可避免地带有某种局限
5
局限性，主要表现为：①大多数传统优化方 法仅能计算目标函数的局部最优点，不能保 证找到全局最优解。对于多峰值函数，这些 方法往往由于过分追求“下降”而陷于局部 最优解；②许多传统优化方法对目标函数的 光滑性、凹凸性等有较高的要求，对于离散 型函数、随机型函数基本上无能为力。
15
③Lingo、Matlab优化工具箱等优化软件 功能的确强大，但它们也不是万能的。首先, 对于某些优化问题，这些工具软件有都求不 出最优解。其次不能保证对任何优化问题都 有现成的工具软件，实际上，许多现代优化 方法都不可能编制成通用软件；
④熟练使用相关科技软件、具有一定的 编程水平是工科研究生所必须具有的素养， 从某种程度上讲，后者更能反映出个人的能
7
二、《最优化方法》课程主要内容 本门课程的主要内容为常用经典优化方
法、现代优化方法中的模拟退火算法和遗传 算法以及运筹优化软件Lingo简介。
经典优化方法包括： 1.常用的一维搜索方法——黄金分割法、 Fibonacci法和解析法； 2. 最速下降法、共轭梯度法； 3. 牛顿法；
8
4. 变尺度法——DFP和BFGS法； 5. 常用约束优化方法——梯度法、罚函 数法、乘子法。 模拟退火算法包括物理背景、算法过程 以及简单应用等内容。 遗传算法包括基本遗传算法、多峰值函 数优化的小生境遗传算法、多目标优化遗传 算法简介。 Lingo软件只介绍基本功能与基本操作。
9
三、授课方式与课程要求 1. 授课方式——自学+讨论+讲解
首先由学生按教师要求对下次授课内容 自学，然后在课堂上就有关问题与教师进行 简要讨论、交流，最后由教师对本次授课内 容进行扼要讲解、总结，布置作业。
10
2. 课程要求 希望掌握优化计算这个数学工具的工程
技术人员可以分为下列三个层次： ①不愿意花费精力去了解优化计算的数
16
能力，而编程经验和水平不是凭一朝一夕就 可以提高的，要靠大量的编程实践和不断地 日积月累。
17
4. 参考书目 ①粟塔山，最优化计算原理与算法程序设计， 国防科技大学出版社； ②谢金星，优化建模与Lingo软件，清华大学 出版社； ③周明，遗传算法原理及应用，国防工业出 版社。 信箱：austmathmodeling@ MM：matlabmaple
学原理，只要能熟练使用一些现成的优化数 学软件，如Lingo、Matlab优化工具箱等；
②希望大致明白优化计算的数学原理， 了解各种算法的优缺点及适用范围，对计算 结果有一定的分析判断能力，让自己成为一
11
个有数学素养的优化工具使用者。但也不打 算自己编制算法程序；
③希望透彻地了解最优化计算的数学原 理，详细掌握各种算法的计算步骤，由自己 编制质量较较高的优化计算软件。
最 3
短路、最小费用最大流等；如果可行集是有
限维空间中的一个连续子集，则元素是
依赖时间的决策序列，则归结为 “动态规
划” ；如果可行集是无穷维空间中的连续子
集
，
则
归
结为“最优控制”。
线性规划与非线性规划是最优化方法中
最基本、最重要的两类问题。
4
一般来说，各优化分支有其相应的应用 领域。线性规划、网络规划、动态规划通常 用于管理与决策科学；最优控制常用于控制 工程；非线性规划则更多地用于工程优化设 计。
前言
一、最优化方法简介 最优化方法是一门古老而又年青的学科。
这门学科的源头可以追溯到17世纪法国数学家 拉格朗日关于一个函数在一组等式约束条件下 的极值问题 (求解多元函数极值的 Lagrange 乘 数法 )。19 世纪柯西引入了最速下降法求解非 线性规划问题。 直到 20 世纪三、四十年代最
1
优化理论的研究才出现了重大进展，1939年 前苏联的康托洛维奇提出了解决产品下料和 运输问题的线性规划方法；1947年美国的丹 奇格提出了求解线性规划的单纯形法，极大 地推动了线性规划理论的发展。非线性规划 理论的开创性工作是在1951年由库恩和塔克 完成的，他们给出了非线性规划的最优性条 件。随着计算机技术的发展，各种最优化算 法应运而生。比较著名的有DFP 和 BFGS无
2
约束变尺度法、HP广义乘子法和WHP约束变 尺度法。
最优化问题本质是一个求极值问题，几 乎所有类型的优化问题都可概括为如下模型： 给定一个集合(可行集)和该集合上的一个函数 (目标函数)，要计算此函数在集合上的极值。 通常，人们按照可行集的性质对优化问题分 类：如果可行集中的元素是有限的，则归结 为“组合优化”或“网络规划”，如图论中
二十世纪六、七十年代以来，人们将人 工智能技术和生物进化机理引入最优化方法,
6
逐渐形成了一批完全不同于传统优化方法、 令人耳目一新的现代优化方法。例如模拟退 火、神经网络、进化计算、模糊逻辑等，其 中进化计算中的遗传算法以其良好的全局搜 索性成为现代优化算法中最受关注的算法之 一，已被广泛应用于函数优化、组合优化、 自动控制、生产调度、图像与信号处理、机 器人和人工生命等领域。
①最优化方法是一门实践性特别强的课 程，算法众多。如果对于一个算法仅了解其 数学原理，不将算法编制成高质量的程序，
14
那么就不能保证你已对此算法有了全面、正 确的理解，对此算法的优缺点、适用范围就 缺乏深刻的体会，更无法体验到最优化方法 的精髓；
②在一些大型计算中，可能要求优化计 算是“实时计算”，即优化计算从前一计算 环节获取参数，计算结果后立即传送给后一 环节，所有这些计算都是在内存中进行的。 显然，现成的工具软件对此无能为力；