最优化方法第一次综述

《最优化方法第一次综述》由会员分享，可在线阅读，更多相关《最优化方法第一次综述（44页珍藏版）》请在金锄头文库上搜索。

1、最优化方法最优化方法 2019/11/261 前前 言言 2019/11/262 一、最优化方法简介 最优化方法是一门古老而又年青 的学科。 这门学科的源头可以追溯到17世 纪法国数学家拉格朗日关于求解多元 函数极值的Lagrange乘数法。 19世纪柯西引入了最速下降法求 解非线性规划问题。 Date3 直到20世纪四、五十年代，最优 化理论的研究才出现重大进展。1947 年丹奇格提出了求解线性规划的单纯 形法；1951年库恩和塔克给出了非线 性规划的最优性条件即Kuhn-Tucker 条件。 20世纪六十年代，随着计算机技 术的发展，各种最优化算法应运而生, Date4 比较著名的有DFP

2、和BFGS无约束变 尺度法、HP广义乘子法和WHP约束 变尺度法。 最优化问题本质是一个求极值问 题，几乎所有类型的优化问题都可概 括为如下模型：给定一个集合(可行 集)和该集合上的一个函数(目标函数), 要计算此函数在集合上的极值。 Date5 通常，人们按照可行集的性质对 优化问题分类。 如果可行集中元素是有限的，则 归结为“组合优化”或“网络规划”，如 图论中最短路、最小费用最大流等； 如果可行集是有限维空间中的一个连 续子集，则归结为“线性或非线性规 划”; 如果可行集中的元素是依赖时间 Date6 的决策序列，则归结为“动态规划”； 如果可行集是无穷维空间中的连续子 集，则归结为“最

3、优控制”。 线性规划与非线性规划是最优化 方法中最基本、最重要的两类问题。 一般来说，各优化分支有其相应 的应用领域。线性规划、网络规划、 动态规划通常用于管理与决策科学； Date7 最优控制常用于控制工程；非线性规 划则更多地用于工程优化设计。 前面提到的算法是最优化的基本 方法，它们简单易行，对于性态优良 的一般函数，优化效果较好。但这些 经典的方法是以传统微积分为基础的, 不可避免地带有某种局限局限性，主 要表现为： 大多数传统优化方法仅 Date8 能计算目标函数的局部最优点，不能 保证找到全局最优解。对于多峰值函 数，这些方法往往由于过分追求“下 降”而陷于局部最优解； 许多传统

4、优化方法对目标函数的光滑性、凹凸 性等有较高的要求，对于离散型函数 、随机型函数基本上无能为力。 20 世纪六、七十年代以来，人们 Date9 将人工智能技术和生物进化机理引入 最优化方法，形成了一批完全不同于 传统优化方法、令人耳目一新的现代 优化方法。例如模拟退火、神经网络 、遗传算法、粒子群算法、蚁群算法 、免疫算法、协同进化算法等，已被 广泛应用于函数优化、组合优化、自 动控制、图像与信号处理等领域。 Date10 二、最优化方法课程主要内容 本门课程的主要内容为常用经典 优化方法、现代优化方法简介和运筹 优化软件Lingo简介。 经典优化方法包括： 1.常用的一维搜索方法黄金 分割法

5、和非精确搜索法； 2. 最速下降法、共轭梯度法； Date11 3. 牛顿法； 4. 变尺度法DFP和BFGS； 5. 约束优化方法梯度法、罚 函数法、乘子法。 现代优化算法仅简要介绍模拟退 火算法。 Lingo软件只介绍基本功能与基 本操作。 Date12 三、授课方式与课程要求 1. 授课方式自学+提问+讲解 首先由学生按教师要求对下次授 课内容进行自学，然后教师在课堂上 逐一提问，最后由教师对本次授课内 容进行讲解、总结，布置作业。 学生成绩根据平时回答问题、作 业和编程及书面考试情况综合评判。 Date13 2. 课程要求 希望掌握优化计算数学工具的工 程技术人员可以分为下列三个层次：

6、 不愿意花精力了解优化计算的 数学原理，只要能熟练使用一些现成 的优化数学软件，如Lingo、Matlab 优化工具箱等； 希望大致明白优化计算的数学 Date14 原理，了解各种算法的优缺点及适用 范围，对计算结果有一定的分析判断 能力，让自己成为一个有数学素养的 优化工具使用者。但也不打算自己编 制算法程序； 希望透彻地了解优化计算的数 学原理，详细掌握算法的计算步骤， 由自己编制质量较高的优化程序。 Date15 本课程对学生的具体要求为： 理解最优化的基本概念、算法 原理和算法结构； 熟悉几种常用的经典优化算法 ，知晓其优缺点及适用范围； 了解几种现代智能优化算法的 基本原理和应用领域

7、； 掌握Lingo的基本功能。 Date16 3. 编程要求 基于下列理由，本门课要求学生 对23个基本优化算法(如一维搜索、 梯度法、变尺度法、模拟退火)编制 出通用程序，编程工具建议采用C + 、Matlab或Maple。 最优化方法是一门实践性特别 强的课程，算法众多。 如果对于一个 Date17 算法仅了解其数学原理，不将算法编 制成高质量的程序，那么就不能保证 你已对此算法有全面、正确的理解， 对此算法的优缺点、适用范围就缺乏 深刻的体会，更无法体验到最优化方 法的精髓； 在一些大型计算中，可能要求 优化计算是 “实时计算”，即优化计算 Date18 从前一计算环节获取参数，计算结果

8、 后立即传送给后一环节，所有这些计 算都是在内存中进行的。显然，现成 的工具软件对此无能为力； Lingo, Matlab优化工具箱等优 化软件功能的确强大，但它们也不是 万能的。首先，对于某些优化问题， 这些工具软件可能都求不出最优解； Date19 其次不能保证对任何优化问题都有现 成的工具软件，实际上，许多现代优 化方法都不可能编制成通用软件； 熟练使用相关科技软件、具有 一定的编程水平是工科研究生所必须 具有的素养，而编程经验和水平不是 凭一朝一夕就可以提高的，要靠大量 的编程实践和不断地日积月累。 Date20 4. 参考书目 粟塔山，最优化计算原理与算法程 序设计，国防科技大学出版

9、社； 谢金星，优化建模与Lingo软件， 清华大学出版社。 信箱：austmathmodeling MM：matlabmaple Date21 第1次自学内容 1. 梯度的定义、几何意义；等高 线的概念，等高线与梯度的关系；梯 度为零的点与极值点的关系。 2. Hesse矩阵的概念；Hesse矩阵 的正定性与函数曲面凹凸性的关系。 3. 设A为n阶对称矩阵，b,X为n元 列向量，c为标量，对二次函数 Date22 求 和 。 4. 写出二元函数的二阶Taylor 展 式的矩阵形式。 5. 凸集的概念。 6. 凸函数及其两个充要条件；凸 函数的极值点有什么特点？ Date23 第一部分第一部分

10、经典优化方法经典优化方法 2019/11/2624 Ch1Ch1 最优化的基本概念最优化的基本概念 2019/11/2625 一、预备知识 1. 梯度 定义1.1 对n元可微函数 向量 Date26 称为 f 在X 处的梯度，记为 或 ， 称为Hamilton算子或 梯度算子。 从几何上讲， 的方向是 f 在X 处上升最快的方向， 的模 是f 在X 处上升最快的速率。 若 ，则函数曲面在 X 处的切平面是水平的。 Date27 2. 二阶导数矩阵 定义1.2 设n元函数 具有二阶连续偏导数，则f 的所有二阶偏 导数构成的矩阵 Date28 称为f 在X处的二阶导数矩阵或Hessain矩 阵，记

11、为 。 显然， 是一个对称矩阵。 在几何上， 反映了函数曲面 的弯曲方向。若 正定，则函数 曲面向上弯曲(凹)；若 负定，则 函数曲面向下弯曲(凸)。 Date29 例1.1 设A为n阶对称矩阵，b,X为 n元列向量，c为标量，对二次函数 求 和 。 解 以二元函数为例计算。 Date30 Date31 Date32 Date33 即对 可将算子 理解为对向量函数的一 阶、二阶导数，易得 Date34 3. n元函数的二阶Taylor展式 一元函数的Taylor展式： 其中 Date35 二元函数的Taylor展式： Date36 其中 Date37 二元函数的二阶Taylor展式： Date

12、38 若引入矩阵记号 Date39 则 n元函数的二阶Taylor展式与二 元函数的二阶Taylor展式形式类似。 Date40 4. 凸集与凸函数 定义1.3 设 ，若S中任两点的 连线都属于S，即对任意 ，均 有 ，则称S 为一个凸集。 定义1.4 设 为定义在凸集S上的 函数，若对任意 ，均有 Date41 则称 为S上的凸函数。若上式改 为严格不等式，则称 为S上的严 格凸函数。 Date42 定理1.1 (一阶判别条件) 一阶可微函数 在开凸集S上 为凸函数 对任意 ，均有 Date43 定理1.2 (二阶判别条件) 二阶连续可微函数 在开凸集 S上为凸 对任意 ， 半正定。 严格凸 正定。 Date44