最优化方法第一次.ppt

最优化方法第一次
第一页，共36页
前 言
一、最优化方法简介
最优化方法是一门古老而又年青的学科。这门学科的源头可以追溯到17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题 (求解多元函数极值的 Lagrange 乘数法 )。19 世纪柯西引入了最速下降法求解非线性规划问题。 直到 20 世纪三、四十年代最
第二页，共36页
优化理论的研究才出现了重大进展，1939年前苏联的康托洛维奇提出了解决产品下料和运输问题的线性规划方法；1947年美国的丹奇格提出了求解线性规划的单纯形法，极大地推动了线性规划理论的发展。非线性规划理论的开创性工作是在1951年由库恩和塔克完成的，他们给出了非线性规划的最优性条件。随着计算机技术的发展，各种最优化算法应运而生。比较著名的有DFP 和 BFGS无
第三页，共36页
约束变尺度法、HP广义乘子法和WHP约束变尺度法。
最优化问题本质是一个求极值问题，几乎所有类型的优化问题都可概括为如下模型：给定一个集合(可行集)和该集合上的一个函数(目标函数)，要计算此函数在集合上的极值。通常，人们按照可行集的性质对优化问题分类：如果可行集中的元素是有限的，则归结为“组合优化”或“网络规划”，如图论中最
第四页，共36页
短路、最小费用最大流等；如果可行集是有限维空间中的一个连续子集，则归结为“线性或非线性规划”；如果可行集中的元素是依赖时间的决策序列，则归结为 “动态规划” ；如果可行集是无穷维空间中的连续子集，则归
结为“最优控制”。
线性规划与非线性规划是最优化方法中
最基本、最重要的两类问题。
第五页，共36页
一般来说，各优化分支有其相应的应用领域。线性规划、网络规划、动态规划通常用于管理与决策科学；最优控制常用于控制工程；非线性规划则更多地用于工程优化设计。
前面提到的算法是最优化的基本方法，它们简单易行，对于性态优良的一般函数，优化效果较好。但这些经典的方法是以传统微积分为基础的，不可避免地带有某种局限
第六页，共36页
局限性，主要表现为：①大多数传统优化方法仅能计算目标函数的局部最优点，不能保证找到全局最优解。对于多峰值函数，这些方法往往由于过分追求“下降”而陷于局部最优解；②许多传统优化方法对目标函数的光滑性、凹凸性等有较高的要求，对于离散型函数、随机型函数基本上无能为力。
二十世纪六、七十年代以来，人们将人工智能技术和生物进化机理引入最优化方法,
第七页，共36页
逐渐形成了一批完全不同于传统优化方法、令人耳目一新的现代优化方法。例如模拟退火、神经网络、进化计算、模糊逻辑等，其中进化计算中的遗传算法以其良好的全局搜索性成为现代优化算法中最受关注的算法之一，已被广泛应用于函数优化、组合优化、自动控制、生产调度、图像与信号处理、机器人和人工生命等领域。
第八页，共36页
二、《最优化方法》课程主要内容
本门课程的主要内容为常用经典优化方法、现代优化方法中的模拟退火算法和遗传算法以及运筹优化软件Lingo简介。
经典优化方法包括：
——黄金分割法、Fibonacci法和解析法；
2. 最速下降法、共轭梯度法；
3. 牛顿法；
第九页，共36页
4. 变尺度法——DFP和BFGS法；
5. 常用约束优化方法——梯度法、罚函数法、乘子法。
模拟退火算法包括物理背景、算法过程以及简单应用等内容。
遗传算法包括基本遗传算法、多峰值函数优化的小生境遗传算法、多目标优化遗传算法简介。
Lingo软件只介绍基本功能与基本操作。
第十页，共36页