最优化方法第一次-PPT幻灯片

前言9/22/20231一、最优化方法简介

最优化方法是一门古老而又年青的学科。这门学科的源头可以追溯到17世纪法国数学家拉格朗日关于求解多元函数极值的Lagrange乘数法。19世纪柯西引入了最速下降法求解非线性规划问题。9/22/20232直到20世纪四、五十年代，最优化理论的研究才出现重大进展。1947年丹奇格提出了求解线性规划的单纯形法；1951年库恩和塔克给出了非线性规划的最优性条件即Kuhn-Tucker条件。20世纪六十年代，随着计算机技术的发展，各种最优化算法应运而生,9/22/20233的决策序列，则归结为“动态规划”；如果可行集是无穷维空间中的连续子集，则归结为“最优控制”。线性规划与非线性规划是最优化方法中最基本、最重要的两类问题。一般来说，各优化分支有其相应的应用领域。线性规划、网络规划、动态规划通常用于管理与决策科学；9/22/20236最优控制常用于控制工程；非线性规划则更多地用于工程优化设计。前面提到的算法是最优化的基本方法，它们简单易行，对于性态优良的一般函数，优化效果较好。但这些经典的方法是以传统微积分为基础的,不可避免地带有某种局限局限性，主要表现为：①大多数传统优化方法仅9/22/20237能计算目标函数的局部最优点，不能保证找到全局最优解。对于多峰值函数，这些方法往往由于过分追求“下降”而陷于局部最优解；②许多传统优化方法对目标函数的光滑性、凹凸性等有较高的要求，对于离散型函数、随机型函数基本上无能为力。20世纪六、七十年代以来，人们9/22/20238将人工智能技术和生物进化机理引入最优化方法，形成了一批完全不同于传统优化方法、令人耳目一新的现代优化方法。例如模拟退火、神经网络、遗传算法、粒子群算法、蚁群算法、免疫算法、协同进化算法等，已被广泛应用于函数优化、组合优化、自动控制、图像与信号处理等领域。9/22/20239二、最优化方法课程主要内容

本门课程的主要内容为常用经典优化方法、现代优化方法简介和运筹优化软件Lingo简介。经典优化方法包括：1.常用的一维搜索方法——黄金分割法和非精确搜索法；2.最速下降法、共轭梯度法；9/22/2023103.牛顿法；4.变尺度法——DFP和BFGS；5.约束优化方法——梯度法、罚函数法、乘子法。现代优化算法仅简要介绍模拟退火算法。Lingo软件只介绍基本功能与基本操作。9/22/202311三、授课方式与课程要求

1.授课方式——自学+提问+讲解首先由学生按教师要求对下次授课内容进行自学，然后教师在课堂上逐一提问，最后由教师对本次授课内容进行讲解、总结，布置作业。学生成绩根据平时回答问题、作业和编程及书面考试情况综合评判。9/22/2023122.课程要求希望掌握优化计算数学工具的工程技术人员可以分为下列三个层次：①不愿意花精力了解优化计算的数学原理，只要能熟练使用一些现成的优化数学软件，如Lingo、Matlab优化工具箱等；②希望大致明白优化计算的数学9/22/202313原理，了解各种算法的优缺点及适用范围，对计算结果有一定的分析判断能力，让自己成为一个有数学素养的优化工具使用者。但也不打算自己编制算法程序；③希望透彻地了解优化计算的数学原理，详细掌握算法的计算步骤，由自己编制质量较高的优化程序。9/22/202314本课程对学生的具体要求为：①理解最优化的基本概念、算法原理和算法结构；②熟悉几种常用的经典优化算法，知晓其优缺点及适用范围；③了解几种现代智能优化算法的基本原理和应用领域；④掌握Lingo的基本功能。9/22/2023153.编程要求基于下列理由，本门课要求学生对2~3个基本优化算法(如一维搜索、梯度法、变尺度法、模拟退火)编制出通用程序，编程工具建议采用C++、Matlab或Maple。①最优化方法是一门实践性特别强的课程，算法众多。如果对于一个9/22/202316算法仅了解其数学原理，不将算法编制成高质量的程序，那么就不能保证你已对此算法有全面、正确的理解，对此算法的优缺点、适用范围就缺乏深刻的体会，更无法体验到最优化方法的精髓；②在一些大型计算中，可能要求优化计算是“实时计算”，即优化计算9/22/202317从前一计算环节获取参数，计算结果后立即传送给后一环节，所有这些计算都是在内存中进行的。显然，现成的工具软件对此无能为力；③Lingo,Matlab优化工具箱等优化软件功能的确强大，但它们也不是万能的。首先，对于某些优化问题，这些工具软件可能都求不出最优解；9/22/202318其次不能保证对任何优化问题都有现成的工具软件，实际上，许多现代优化方法都不可能编制成通用软件；④熟练使用相关科技软件、具有一定的编程水平是工科研究生所必须具有的素养，而编程经验和水平不是凭一朝一夕就可以提高的，要靠大量的编程实践和不断地日积月累。9/22/2023194.参考书目①粟塔山，最优化计算原理与算法程序设计，国防科技大学出版社；②谢金星，优化建模与Lingo软件，清华大学出版社。信箱：austmathmodeling@163.comMM：matlabmaple9/22/202320第1次自学内容

1.梯度的定义、几何意义；等高线的概念，等高线与梯度的关系；梯度为零的点与极值点的关系。2.Hesse矩阵的概念；Hesse矩阵的正定性与函数曲面凹凸性的关系。3.设A为n阶对称矩阵，b,X为n元列向量，c为标量，对二次函数9/22/202321求和。

4.写出二元函数的二阶Taylor展式的矩阵形式。5.凸集的概念。6.凸函数及其两个充要条件；凸函数的极值点有什么特点？9/22/202322第一部分经典优化方法9/22/202323Ch1最优化的基本概念9/22/202324一、预备知识

1.梯度定义1.1对n元可微函数向量9/22/202325称为f在X处的梯度，记为

或，称为Hamilton算子或梯度算子。从几何上讲，的方向是f在X处上升最快的方向，的模是f在X处上升最快的速率。若，则函数曲面在X处的切平面是水平的。9/22/2023262.

二阶导数矩阵定义1.2设n元函数

具有二阶连续偏导数，则f的所有二阶偏导数构成的矩阵9/22/202327称为f在X处的二阶导数矩阵或Hessain矩阵，记为。

显然，是一个对称矩阵。在几何上，反映了函数曲面的弯曲方向。若正定，则函数曲面向上弯曲(凹)；若负定，则函数曲面向下弯曲(凸)。9/22/202328例1.1设A为n阶对称矩阵，b,X为n元列向量，c为标量，对二次函数求和。

解以二元函数为例计算。9/22/2023299/22/2023309/22/2023319/22/202332即对可将算子理解为对向量函数的一阶、二阶导数，易得9/22/2023333.

n元函数的二阶Taylor展式一元函数的Taylor展式：其中9/22/202334二元函数的Taylor展式：9/22/202335其中9/22/202336二元函数的二阶Taylor展式：9/22/202337

若引入矩阵记号

9/22/202338则n元函数的二阶Taylor展式与二元函数的二阶Taylor展式形式类似。9/22/2023394.

凸集与凸函数定义1.3设，若S中任两点的连线都属于S，即对任意，均有，则称S为一个凸集。定义1.4设为定义在凸集S上的函数，若对任意，均有9/22/202340则称为S上的凸函数。若上式改为严格不等式，则称为S上的严格凸函数。9/22/202341定理1.1(一阶判别条件