第1讲 最优化理论与方法概述

《第1讲 最优化理论与方法概述》由会员分享，可在线阅读，更多相关《第1讲 最优化理论与方法概述（41页珍藏版）》请在金锄头文库上搜索。

1、第一讲最优化理论与方法概述,主讲冯颖 市场营销系 ,1.1 最优化理论与方法的形成和发展 1.2 最优化问题的定义和数学模型 1.3 最优化问题的分类 1.4 最优化方法的解题步骤 1.5 广义最优化方法的种类 1.6 最优化方法效果举例,主要内容,1.1 最优化理论与方法的形成和发展,公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。 在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。,17世纪，I.牛顿和

2、G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。,第二次世界大战前后，形成了近代最优化方法：以苏联.康托罗维奇和美国G.B.丹齐克为代表的线性规划；以美国库恩和塔克尔为代表的非线性规划；以美国R.贝尔曼为代表的动态规划；以苏联.庞特里亚金为代表的极大值原理等。,古典最优化方法,近代最优化方法,1.1 最优化方法的形成和发展,最优化方法与运筹学的区别与联系,生活中常见的最优化问题,测量云龙湖水深的最大值问题 自驾游旅行的最优路线 城市公共自行车租赁点最佳布局问题 城市交通信号灯配时问题 飞机场

3、停机位分配的问题 月球探测器着陆轨道控制,内容不同。最优化方法包括数学规划、最优控制和计算数学，运筹学主要包含数学规划问题。 侧重点不同。最优化方法侧重于算法，运筹学侧重于数学建模。,1.1 最优化方法的形成和发展,参考书籍,考核方式,最优化理论与方法，袁亚湘，孙文瑜编，科学出版社，1997年版。 运筹学与最优化方法，吴祈宗，侯福均编，机械工业出版社，2013年版。 最优化方法与最优控制，王晓陵，陆军编，哈尔滨工程大学出版社，2008年版。 最优化计算方法及其MATLAB程序实现，马昌凤等编，国防工业出版社，2015年版。,平时成绩（30%）；期末成绩（70%）,1.1 最优化方法的形成和发展

4、,内容章节,第一讲 最优化理论与方法概述 第二讲 线性规划及Matlab求解 第三讲 无约束最优化问题与Matlab求解 第四讲 约束最优化问题的最优性条件 第五讲 约束最优化数值算法 第六讲 启发式算法（模拟退火、遗传算法） 第七讲 最优控制理论,1.1 最优化方法的形成和发展 1.2 最优化问题的定义和数学模型 1.3 最优化问题的分类 1.4 最优化方法的解题步骤 1.5 广义最优化方法的种类 1.6 最优化方法效果举例,主要内容,1.2 最优化方法的定义和数学模型,最优化方法即是解决最优化问题的方法，主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。 最优化问题

5、是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。 最优化方法主要研究数学规划和最优控制两类问题的求解方法。 Optimal method，Optimization of methods，Optimization，Optimum“Opt”,1.2.1 最优化方法的定义,1.2 最优化方法的定义和数学模型,设计向量,目标函数,约束条件,性能指标,1.2.2 最优化方法的数学模型,最优化方法数学模型基本要素,约束条件,约束条件,不等式约束将设计空间划分为两部分，一部分满足约束条件，另一部分不满足约束条件。 可行域：满足约束条件的区域； 非可行域：不满足

6、约束条件的区域，也叫不可行域； 可行点：可行域内的点，对应一个可行方案； 非可行点：非可行域内的点，对应一个不可行方案，也叫不可行点。,约束条件,目标函数,目标函数,最优化问题数学模型的典型形式,1.1 最优化方法的定义 1.2 最优化问题数学模型的构成 1.3 最优化问题的分类 1.4 最优化方法的解题步骤 1.5 广义最优化方法的种类 1.6 最优化方法效果举例,主要内容,按约束条件有无及其约束式的性质分,等式约束 不等式约束,按所包含方程式的特性分 线性规划：目标函数和约束条件均为线性函数关系的最优化问题，即 都是一次函数； 非线性规划：目标函数和约束条件中有一个或一个以上非线性关系函数

7、式的最优化问题。 按目标函数的个数分 单目标最优化问题：只有一个目标函数的最优化问题； 多目标最优化问题：含有多个目标函数的最优化问题。,针对决策变量x1, x2,xn来进行分类,泛函极值 最优控制问题,数值算法,解析方法,精确算法,启发式算法,最优化方法,1.1 最优化方法的定义 1.2 最优化问题数学模型的构成 1.3 最优化问题的分类 1.4 最优化方法的解题步骤 1.5 广义最优化方法的种类 1.6 最优化方法效果举例,主要内容,结果检讨与决策,1.1 最优化方法的定义 1.2 最优化问题数学模型的构成 1.3 最优化问题的分类 1.4 最优化方法的解题步骤 1.5 广义最优化方法的种

8、类 1.6 最优化方法效果举例,主要内容,利用古典的微分学、变分学及拉格朗日乘子法等数学工具， 求出函数极值。对于高次非线性问题等复杂问题求解困难。,利用函数局部区域的一些特性及一些点的函数值等条件，通 过数学迭代程序进行计算，逐步调优并逼近函数的最优点。,用几何作图的方法，画出图形，从图形上直接观察，找出函 数的极值点。只适用于容易作图的较简单问题。,通过直接实验，进行结果的比较，获得函数的极值或问题的 最佳参数。,把同一问题的许多可能的典型解进行估计、研究分析，以确 定其最优解。,解析法,数值法,图解法,实验法,情况研究法,1.1 最优化方法的定义 1.2 最优化问题数学模型的构成 1.3

9、 最优化问题的分类 1.4 最优化方法的解题步骤 1.5 广义最优化方法的种类 1.6 最优化方法效果举例,主要内容,车轮轴的优化下料方法,某车辆厂要生产长度为1080、1040及970毫米的轴，其生产数量分别为100、150和600根。现只能用长度为3000毫米的原料钢管。问应该怎样安排下料才能使料头最少？,（mm）,最优化方法 列出所有可能的下料方案，择其方案中料头最短的3种设计成如表的优化下料方案：,（mm）,规格,方案,该数学模型的最优化求解是一个很简单的数学问题，其最优解为： 其最优值是： 优化下料方法与原顺序下料方法相比较，有明显效果： 料头减少为129000-54000=7500

10、0（mm），节约钢材58%,说明和提示,节约的比例数大，效果明显。有的问题，如果基数大，即便节约费用百分之一二，也很有意义，如空间技术； 有一些问题，在求解之前或求解过程中，还要用到数学优化方法以外的其他优化方法，如实验法、情况研究优化，甚至设计者的经验与技能。在前提限制条件确定和总体方案优选以后，才能用数学优化的方法进行参数的优化设计。 一种数学方法可以求解一个最优化问题；而一个最优化问题可以先后用几种数学方法找到最终的最优值。即其数学方法与求解的问题不应视为只有唯一的对应性。为了提高运算速度和求解效果，对有的问题可以相互联系地选用具有不同特点的方法。,数学预备知识,1. 向量与范数,设向量

11、,范数，是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域，是一个函数，其为向量空间内的所有向量赋予非零的正长度或大小。用 表示,-范数,2-范数,1-范数,范数不等式,范数的内积,三角不等式,柯西不等式,2. 多元函数的微分,对于多元函数u=f(x)， ，若在点 处对于自变量 的各分量的偏导数都存在， 则称函数u=f(x)在该点的一阶导数。,(1) 梯度,(2) Hession矩阵,(海塞矩阵),(3) 多元函数的Taylor展开,二阶Taylor展开,或,一阶Taylor展开,3.凸集与凸函数 (在无约束规划中常用到，具有很好的极值性),对任意的,有,则C为凸集,(1) 凸集,

12、凸集,非凸集,(2) 下凸函数：； 下凹函数：,(3) 凸函数的定义：,设f(x)为定义在n维欧氏空间Rn中某个凸集S上的函数，若对任何实数(01)以及S中不同的两点x(1)，x(2)， x(1) x(2)，恒有,则称f(x)为定义在凸集S上的凸函数。,若对每一个(01)，以及 x(1)，x(2) S (x(1) x(2), 恒有,则称f(x)为定义在凸集S上的严格凸函数。,f(x),x,f( x(1) ) +(1- ) f( x(2),f(x(1),f(x(2),x(1),x(2),x(1)+(1- )x(2),f(x(1)+(1- )x(2) ),任意两点的函数值的连线上的点都在曲线的上方,(3) 凸函数的判定准则 一阶判定条件： f(x)在凸集S上具有一阶连续偏导数，则f(x)为S上凸函数的充要条件是,因此，一阶判定的充要条件也可以表述为：任一点x(1)处的切线增量不超过函数的增量。,(3) 凸函数的判定准则,二阶判定条件： f(x)在凸集S上具有二阶连续偏导数，则f(x)为S上凸函数的充要条件是Hession矩阵 在S上处处半正定。,谢谢！,