最优化方法第一次课件.ppt

1、2022-12-223一一、最优化方法简介最优化方法简介 最优化方法是一门古老而又年青最优化方法是一门古老而又年青的学科。的学科。这门学科的源头可以追溯到这门学科的源头可以追溯到17世世纪法国数学家拉格朗日关于求解多元纪法国数学家拉格朗日关于求解多元函数极值的函数极值的Lagrange乘数法乘数法。19世纪柯西引入了世纪柯西引入了最速下降法最速下降法求求解非线性规划问题。解非线性规划问题。2022-12-224 直到直到20世纪四、五十年代，最优世纪四、五十年代，最优化理论的研究才出现重大进展。化理论的研究才出现重大进展。1947年丹奇格提出了求解线性规划的年丹奇格提出了求解线性规划的单纯单纯

2、形法形法；1951年库恩和塔克给出了非线年库恩和塔克给出了非线性规划的最优性条件即性规划的最优性条件即Kuhn-Tucker条件条件。20世纪六十年代，随着计算机技世纪六十年代，随着计算机技术的发展，各种最优化算法应运而生术的发展，各种最优化算法应运而生,2022-12-225比较著名的有比较著名的有DFP和和BFGS无约束变无约束变尺度法、尺度法、HP广义乘子法和广义乘子法和WHP约束约束变尺度法。变尺度法。最优化问题本质是一个求极值问最优化问题本质是一个求极值问题，几乎所有类型的优化问题都可概题，几乎所有类型的优化问题都可概括为如下模型：给定一个集合括为如下模型：给定一个集合(可行可行集集

3、)和该集合上的一个函数和该集合上的一个函数(目标函数目标函数),要计算此函数在集合上的极值。要计算此函数在集合上的极值。2022-12-226 通常，人们按照可行集的性质对通常，人们按照可行集的性质对优化问题分类。优化问题分类。如果可行集中元素是有限的，则如果可行集中元素是有限的，则归结为归结为“组合优化组合优化”或或“网络规划网络规划”，如图论中最短路、最小费用最大流等；如图论中最短路、最小费用最大流等；如果可行集是有限维空间中的一个连如果可行集是有限维空间中的一个连续子集，则归结为续子集，则归结为“线性或非线性规线性或非线性规划划”;如果可行集中的元素是依赖时如果可行集中的元素是依赖时间间

4、2022-12-227的决策序列，则归结为的决策序列，则归结为“动态规划动态规划”；如果可行集是无穷维空间中的连续子如果可行集是无穷维空间中的连续子集，则归结为集，则归结为“最优控制最优控制”。线性规划与非线性规划是最优化线性规划与非线性规划是最优化方法中最基本、最重要的两类问题。方法中最基本、最重要的两类问题。一般来说，各优化分支有其相应一般来说，各优化分支有其相应的应用领域。线性规划、网络规划、的应用领域。线性规划、网络规划、动态规划通常用于管理与决策科学；动态规划通常用于管理与决策科学；2022-12-228最优控制常用于控制工程；非线性规最优控制常用于控制工程；非线性规划则更多地用于工

5、程优化设计。划则更多地用于工程优化设计。前面提到的算法是最优化的基本前面提到的算法是最优化的基本方法，它们简单易行，对于性态优良方法，它们简单易行，对于性态优良的一般函数，优化效果较好。但这些的一般函数，优化效果较好。但这些经典的方法是以传统微积分为基础的经典的方法是以传统微积分为基础的,不可避免地带有某种局限局限性，主不可避免地带有某种局限局限性，主要表现为：要表现为：大多数传统优化方法仅大多数传统优化方法仅2022-12-229能计算目标函数的局部最优点，不能能计算目标函数的局部最优点，不能保证找到全局最优解。对于多峰值函保证找到全局最优解。对于多峰值函数，这些方法往往由于过分追求数，这些

6、方法往往由于过分追求“下下降降”而陷于局部最优解；而陷于局部最优解；许多传统许多传统优化方法对目标函数的光滑性、凹凸优化方法对目标函数的光滑性、凹凸性等有较高的要求，对于离散型函数、性等有较高的要求，对于离散型函数、随机型函数基本上无能为力。随机型函数基本上无能为力。20 世纪六、七十年代以来，人们世纪六、七十年代以来，人们2022-12-2210将人工智能技术和生物进化机理引入将人工智能技术和生物进化机理引入最优化方法，形成了一批完全不同于最优化方法，形成了一批完全不同于传统优化方法、令人耳目一新的现代传统优化方法、令人耳目一新的现代优化方法。例如模拟退火、神经网络、优化方法。例如模拟退火、

7、神经网络、遗传算法、粒子群算法、蚁群算法、遗传算法、粒子群算法、蚁群算法、免疫算法、协同进化算法等，已被广免疫算法、协同进化算法等，已被广泛应用于函数优化、组合优化、自动泛应用于函数优化、组合优化、自动控制、图像与信号处理等领域。控制、图像与信号处理等领域。2022-12-2211二二、最优化方法课程主要内容最优化方法课程主要内容 本门课程的主要内容为常用本门课程的主要内容为常用经典经典优化方法优化方法、现代优化方法现代优化方法简介和运筹简介和运筹优化软件优化软件Lingo简介。简介。经典优化方法包括：经典优化方法包括：1.常用的一维搜索方法常用的一维搜索方法黄金黄金分割法分割法和和非精确搜索

8、法非精确搜索法；2.最速下降法最速下降法、共轭梯度法共轭梯度法；2022-12-2212 3.牛顿法牛顿法；4.变尺度法变尺度法DFP和和BFGS；5.约束优化方法约束优化方法梯度法、罚梯度法、罚函数法、乘子法。函数法、乘子法。现代优化算法仅简要介绍模拟退现代优化算法仅简要介绍模拟退火算法。火算法。Lingo软件只介绍基本功能与基软件只介绍基本功能与基本操作。本操作。2022-12-2213三三、授课方式与课程要求授课方式与课程要求 1.授课方式授课方式自学自学+提问提问+讲解讲解 首先由学生按教师要求对下次授首先由学生按教师要求对下次授课内容进行自学，然后教师在课堂上课内容进行自学，然后教师

9、在课堂上逐一提问，最后由教师对本次授课内逐一提问，最后由教师对本次授课内容进行讲解、总结，布置作业。容进行讲解、总结，布置作业。学生成绩根据平时回答问题、作学生成绩根据平时回答问题、作业和编程及书面考试情况综合评判。业和编程及书面考试情况综合评判。2022-12-22142.课程要求课程要求 希望掌握优化计算数学工具的工希望掌握优化计算数学工具的工程技术人员可以分为下列三个层次：程技术人员可以分为下列三个层次：不愿意花精力了解优化计算不愿意花精力了解优化计算的数学原理，只要能熟练使用一些现的数学原理，只要能熟练使用一些现成的优化数学软件，如成的优化数学软件，如Lingo、Matlab优化工具箱

10、等；优化工具箱等；希望大致明白优化计算的数希望大致明白优化计算的数学学2022-12-2215原理，了解各种算法的优缺点及适用原理，了解各种算法的优缺点及适用范围，对计算结果有一定的分析判断范围，对计算结果有一定的分析判断能力，让自己成为一个有数学素养的能力，让自己成为一个有数学素养的优化工具使用者。但也不打算自己编优化工具使用者。但也不打算自己编制算法程序；制算法程序；希望透彻地了解优化计算的数希望透彻地了解优化计算的数学原理，详细掌握算法的计算步骤，学原理，详细掌握算法的计算步骤，由自己编制质量较高的优化程序。由自己编制质量较高的优化程序。2022-12-2216 本课程对学生的具体要求为

11、：本课程对学生的具体要求为：理解最优化的基本概念、算法理解最优化的基本概念、算法原理和算法结构；原理和算法结构；熟悉几种常用的经典优化算法，熟悉几种常用的经典优化算法，知晓其优缺点及适用范围；知晓其优缺点及适用范围；了解几种现代智能优化算法的了解几种现代智能优化算法的基本原理和应用领域；基本原理和应用领域；掌握掌握Lingo的基本功能。的基本功能。2022-12-22173.编程要求编程要求 基于下列理由，本门课要求学生基于下列理由，本门课要求学生对对23个基本优化算法个基本优化算法(如一维搜索、如一维搜索、梯度法、变尺度法、模拟退火梯度法、变尺度法、模拟退火)编制编制出通用程序，编程工具建议

12、采用出通用程序，编程工具建议采用C+、Matlab或或Maple。最优化方法是一门实践性特别最优化方法是一门实践性特别强的课程，算法众多。强的课程，算法众多。如果对于一如果对于一个个2022-12-2218算法仅了解其数学原理，不将算法编算法仅了解其数学原理，不将算法编制成高质量的程序，那么就不能保证制成高质量的程序，那么就不能保证你已对此算法有全面、正确的理解，你已对此算法有全面、正确的理解，对此算法的优缺点、适用范围就缺乏对此算法的优缺点、适用范围就缺乏深刻的体会，更无法体验到最优化方深刻的体会，更无法体验到最优化方法的精髓；法的精髓；在一些大型计算中，可能要求在一些大型计算中，可能要求优

13、化计算是优化计算是“实时计算实时计算”，即优化，即优化计算计算2022-12-2219从前一计算环节获取参数，计算结果从前一计算环节获取参数，计算结果后立即传送给后一环节，所有这些计后立即传送给后一环节，所有这些计算都是在内存中进行的。显然，现成算都是在内存中进行的。显然，现成的工具软件对此无能为力；的工具软件对此无能为力；Lingo,Matlab优化工具箱等优优化工具箱等优化软件功能的确强大，但它们也不是化软件功能的确强大，但它们也不是万能的。首先，对于某些优化问题，万能的。首先，对于某些优化问题，这些工具软件可能都求不出最优解；这些工具软件可能都求不出最优解；2022-12-2220其次不

14、能保证对任何优化问题都有现其次不能保证对任何优化问题都有现成的工具软件，实际上，许多现代优成的工具软件，实际上，许多现代优化方法都不可能编制成通用软件；化方法都不可能编制成通用软件；熟练使用相关科技软件、具有熟练使用相关科技软件、具有一定的编程水平是工科研究生所必须一定的编程水平是工科研究生所必须具有的素养，而编程经验和水平不是具有的素养，而编程经验和水平不是凭一朝一夕就可以提高的，要靠大量凭一朝一夕就可以提高的，要靠大量的编程实践和不断地日积月累。的编程实践和不断地日积月累。2022-12-22214.参考书目参考书目粟塔山，最优化计算原理与算法程粟塔山，最优化计算原理与算法程序设计，国防科

15、技大学出版社；序设计，国防科技大学出版社；谢金星，优化建模与谢金星，优化建模与Lingo软件，软件，清华大学出版社。清华大学出版社。信箱：信箱：MM：matlabmaple2022-12-2222第第1次自学内容次自学内容 1.梯度的定义、几何意义；等高梯度的定义、几何意义；等高线的概念，等高线与梯度的关系；梯线的概念，等高线与梯度的关系；梯度为零的点与极值点的关系。度为零的点与极值点的关系。2.Hesse矩阵的概念；矩阵的概念；Hesse矩阵矩阵的正定性与函数曲面凹凸性的关系。的正定性与函数曲面凹凸性的关系。3.设设A为为n阶对称矩阵，阶对称矩阵，b,X为为n元元列向量，列向量，c为标量，对

16、二次函数为标量，对二次函数2022-12-2223求求 和和 。4.写出二元函数的二阶写出二元函数的二阶Taylor 展展式的矩阵形式。式的矩阵形式。5.凸集的概念。凸集的概念。6.凸函数及其两个充要条件；凸凸函数及其两个充要条件；凸函数的极值点有什么特点？函数的极值点有什么特点？12TTfXX AXb Xc fX 2fX 2022-12-2226一一、预备知识预备知识 1.梯度梯度 定义定义1.1 对对n元可微函数元可微函数向量向量 12,nfXfxxx 12,Tnfffxxx2022-12-2227称为称为 f 在在X 处的梯度，记为处的梯度，记为 或或 ，称为称为Hamilton算子或算

17、子或梯度算子。梯度算子。从几何上讲，从几何上讲，的方向是的方向是 f 在在X 处上升最快的方向，处上升最快的方向，的模的模是是f 在在X 处上升最快的速率。处上升最快的速率。若若 ，则函数曲面在，则函数曲面在 X 处的切平面是水平的。处的切平面是水平的。grad fX fX fX fX 0fX2022-12-22282.二阶导数矩阵二阶导数矩阵 定义定义1.2 设设n元函数元函数 具有二阶连续偏导数，则具有二阶连续偏导数，则f 的所有二阶的所有二阶偏导数构成的矩阵偏导数构成的矩阵 12,nfXfxxx 111212122212nnnnnnfffffffff2022-12-2229称为称为f 在

18、在X处的二阶导数矩阵或处的二阶导数矩阵或Hessain矩阵，记为矩阵，记为 。显然，显然，是一个对称矩阵。是一个对称矩阵。在几何上，在几何上，反映了函数曲面反映了函数曲面的弯曲方向。若的弯曲方向。若 正定，则函数正定，则函数曲面向上弯曲曲面向上弯曲(凹凹)；若；若 负定，则负定，则函数曲面向下弯曲函数曲面向下弯曲(凸凸)。2fX 2fX 2fX 2fX 2fX 2022-12-2230 例例1.1 设设A为为n阶对称矩阵，阶对称矩阵，b,X为为n元列向量，元列向量，c为标量，对二次函数为标量，对二次函数求求 和和 。解解 以二元函数为例计算。以二元函数为例计算。12TTfXX AXb Xc f

19、X 2fX 2022-12-2231 11121121222211221,2,aaxfXxxaaxxb bcx 22111222121211221122a xaxa x xb xb xc2022-12-22321111221112122222,fa xa xbxfa xaxbx 11111221122222,faffafa 12,TfffXxx2022-12-2233 11112211212222,Ta xa xb a xaxb111211122222aaxbaaxbAXb 11121112212222122ffafXAaaaff2022-12-2234即对即对可将算子可将算子 理解为对向量函

20、数的理解为对向量函数的一阶、二阶导数，易得一阶、二阶导数，易得2,12TTfXX AXb Xc fXAXb 2fXA2022-12-22353.n元函数的二阶元函数的二阶Taylor展式展式一元函数的一元函数的Taylor展式：展式：其中其中 000()200()()()()()2!nnnf xxf xfxxfxfxxxRn (1)10(),(1)!01nnnfxxRxn 2022-12-2236二元函数的二元函数的Taylor展式：展式：000000(,)(,)(,)f xx yyf xyxyf xyxy 200001(,)2!1(,)!nnxyf xyxyxyf xyRnxy 2022-1

21、2-2237其中其中 1001(1)!,01nnRxynxyfxx yy 2022-12-2238二元函数的二阶二元函数的二阶Taylor展式：展式：00000000(,)(,)(,)(,)12!f xx yyf xyf xyf xyxyxy 22200002222000022(,)(,)(,)(,)f xyf xyxx yx yxf xyf xyy xyRy xy 2022-12-2239 若引入矩阵记号若引入矩阵记号 0000,TTXx yXxyXXX 000()(),Tf Xf XbfXxy 220022022002()()()()()f Xf Xx yxAf Xf Xf Xy xy 2

22、022-12-2240则则 n元函数的二阶元函数的二阶Taylor展式与二展式与二元函数的二阶元函数的二阶Taylor展式形式类似。展式形式类似。0020212TTfXfXfXXXXXR 0212TTfXbXX A XR2022-12-22414.凸集与凸函数凸集与凸函数 定义定义1.3 设设 ，若，若S中任两点的中任两点的连线都属于连线都属于S，即对任意，即对任意 ，均，均有有 ，则称，则称S为一个凸集。为一个凸集。定义定义1.4 设设 为定义在凸集为定义在凸集S上上的函数，若对任意的函数，若对任意 ，均有，均有nSR 12,XXS 12(1),01XXS()f X12,XXS 2022-1

23、2-2242则称则称 为为S上的凸函数。若上式改上的凸函数。若上式改为严格不等式，则称为严格不等式，则称 为为S上的严上的严格凸函数。格凸函数。1212(1)(1)(01)fXXfXfX()f X()f X2022-12-2243 定理定理1.1(一阶判别条件一阶判别条件)一阶可微函数一阶可微函数 在开凸集在开凸集S上上为凸函数为凸函数 对任意对任意 ，均，均有有()f X12,XXS 21121TfXfXfXXX2022-12-2244 定理定理1.2(二阶判别条件二阶判别条件)二阶连续可微函数二阶连续可微函数 在开凸在开凸集集S上为凸上为凸 对任意对任意 ，半正定。半正定。严格凸严格凸 正定。正定。()f XXS 2fX()f X 2fX