最优化问题总论课件

《最优化问题总论课件》由会员分享，可在线阅读，更多相关《最优化问题总论课件（30页珍藏版）》请在金锄头文库上搜索。

1、最优化方法,济南大学控制科学与工程学院,授课教师：李实,cse_ 1教1007室,2,课程结构,3,教材与参考资料,教材： “最优化方法”，施光燕，钱伟懿，庞丽萍，高等教育出版社，第二版，2007-08 参考书目： “工程最优化设计”，李元科，清华大学出版社，第一版，2006-08 “最优化方法及其应用”，郭科，高等教育出版社，第一版，2007-07 “精通MATLAB最优化计算”，龚纯，王正林，电子工业出版社，2009-04.,4,考核方式,17周考试 考试70%+平时30%（作业+点名） 课堂要求： 将课件下载打印，上课记好笔记，尤其是习题课。 遵守课堂纪律，聊天的同学请上台讲,5,第一章

2、 最优化问题总论,1.1 引言 1.2 最优化设计举例 1.3 最优化问题的数学模型 1.4 最优化问题的图解法 1.5 最优化问题的下降迭代解法 1.6 最优化算法分类 1.7 MATLAB优化工具箱介绍,6,1.1 引言,最优化方法：从所有可能的方案中，选择出最合理的，达到最优目标的方案，搜寻最优方案的方法就是最优化方法。 工程设计：如何选择参数，使设计满足要求又能降低成本。 资源分配：满足各方面的基本要求，获得好的经济效益。 生产计划：提高产值，提高利润。 原料配比：选择何种成分比例，提高质量、降低成本。 城建规划：如何安排工厂、学校、医院、商店、住宅的合理布局。 最优化研究的是求解最优

3、化问题的理论和方法，它是当前计算数学和运筹学领域中的一个十分活跃的分支。随着电子计算机的普及，最优化方法已广泛应用于化工、航空、机械、建筑、无线电技术等许多工程技术部门另外，在生产组织、资源分配等管理科学方面，在现代军事指挥系统中，最优化方法也成为一种重要的决策手段因此，最优化是一门应用广泛、实用性很强的交叉学科。,7,最优化的发展历程,早在十七世纪，费马，1638；牛顿，1670， 就已提出了函数的极值问题 在1847年，法国数学家Cauchy对无约束最优化问题提出了最速下降法，而对约束极值的求解，则出现了Lagrange乘子法 但是，在上世纪三十年代以前，这个古老的课题并未取得实质性的进展

4、由于近几十年来，生产和科学研究的迅猛发展以及电子计算机的广泛应用，不仅使求解最优化问题成为一种迫切需要，而且也有了求解这一问题的强有力的工具因此，最优化的理论和方法得以迅速发展，并不断完善，逐步形成了一门系统的学科迄今为止，在这个学科中已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、不可微规划、网络流等许多分支. 本课程主要介绍线性规划和非线性规划（包括无约束和有约束）的基本方法，它是最优化理论的最基本部分,8,1.2最优化设计举例,例1.1 用一块边长为3米的正方形薄板，在四角各裁去一个大小相同的方块，做成一个无盖的箱子。试确定如何裁剪可以使做成的箱子具有最大的容积。,解：设裁去

5、的边长为x，则做成的箱子容积为：,可将问题转化为求函数f(x)最大值的数学问题。X为变量，函数f(x)为目标函数。由于目标函数为非线性函数，无约束条件，此类问题称为非线性无约束最优化问题。,根据函数的极值条件，令,最优解：,9,例1.2 某工厂生产甲、乙两种产品，生产每种产品所需的材料、工时、用电量和可以获得的利润，以及每天能够提供的材料、工时、用电量见表，试确定该厂两种产品每天的生产计划，以使得每天获得的利润最大。 这是一个简单的生产计划问题，可以归结为在满足各项生产条件下，合理安排每天的甲乙产品生产量，以使利润最大化的最优化设计问题。,10,设每天生产甲x1件，乙x2件。每天获得的利润：,

6、满足条件,材料约束,工时约束,电能约束,变量非负约束,目标函数,由于目标函数和约束函数都是线性的，所以该类问题成为线性最优化问题，也叫线性规划，无法用高等数学的极值条件直接求解。,11,例1.3 某单位拟建一排四间的停车房，平面位置如图所示。由于资金及材料的限制，围墙和隔墙的总长度不能超过40米，为使停车面积最大，应如何选择长、宽尺寸？,x2,x1,设停车房长为x1，宽为x2. 由题意知面积为：,约束条件：,该类问题为非线性约束最优化问题,12,1.3最优化问题的数学模型,变量：x1, x2, , xn 极小化目标函数：f(x1,x2,xn) 满足约束条件：,不等式约束,等式约束,向量X属于n

7、维实欧式空间,s. t. (subject to) 表示“满足于”,数学模型可以表示为：,13,最优化问题也称数学规划问题。根据数学模型中目标函数和约束函数的性质可将优化问题分为线性最优化（规划）问题和非线性最优化（规划）问题。 当数学模型中的目标函数和约束函数全部是设计变量的线性函数时，称此问题为线性最优化问题或线性规划问题；当目标函数和约束函数中至少有一个是非线性函数时，称这样的问题为非线性最优化问题或非线性规划问题。 线性规划和非线性规划是数学规划的两个重要分支，生产计划和经济管理方面的问题一般可归结为线性规划问题，工程设计问题可归结为非线性规划问题。,14,约束条件与可行域,约束条件除

8、有等式约束和不等式约束之分外，还可分为边界约束和性能约束，起作用约束和不起作用约束等。 边界约束：对设计变量本身所加的直接限制，如 性能约束：对设计问题的某一项技术性能指标或性能参数所加的限制，如例1.2中关于材料、工时和用电量的约束。 对于一个最优化问题，满足所有约束条件的部分一般是由多个约束边界所围成的一个封闭区域，记做&。可行域可以看作满足所有约束条件的设计点的集合：,15,由例1.2得到的5个约束方程分别是：,&,可行域为封闭五边形OABCD,16,给出如下约束条件：,17,目标函数与等值线,目标函数是衡量设计方案优劣的定量标准。不同的最优化设计问题有不同的方案评价标准，一般选择某几个

9、重要的技术经济指标来构成目标函数，如利润、成本、功率、重量等。 求解最优化问题的目的就是找出最优解所代表的设计方案。对于一个具体的设计问题，是否有最优解？有几个最优解？最优解在什么位置？这些问题都决定于目标函数和约束函数的形态及其变化规律。 令函数f(X)等于常数c，满足该条件的点X在设计控制定义了一个点集。 当c=2时，点X在设计空间内为一条直线或曲线 当c3时，点集为设计空间内的一个平面、曲面或超曲面。 称这种线或面为函数的等值线或等值面,18,例1.2中目标函数的等值线族，从左下向右上方逐渐减少,19,1.4 最优化问题的图解法,对于简单的二维最优化问题，可以用作图的方法。在设计平面中划

10、出约束可行域和目标函数的一族等值线，并根据等值线与可行域的相互关系确定出最优点的位置，进而得到问题的近似最优解。图解法的步骤如下： 确定设计空间。 画出由约束边界围成的约束可行域。 做出1到2条目标函数的等值线，判断目标函数的下降方向。 判断并确定最优点。 一般来说，线性规划问题的约束可行域是由线性约束边界围成的凸多边形或凸多面体，等值线（面）是一族平行的直线（平面），故最优点必定位于可行域的某个顶点上。而非线性最优化问题的最优点通常位于某个约束边界上。 图解法只适用于一些极其简单的最优化问题，很少有使用价值，但对于理解最优化的基本概念和原理是很有意义的。,20,例1.2是一个二维线性规划问题

11、，用图解法求解最优解,等值线向右上移动，目标函数值下降，点C为可行域内的最优点，即数学模型的最优解。最优方案为：每天生产甲产品20件，乙产品24件，获得最大利润4080元。,21,例1.4：用图解法求解最优化问题：,在可行域内使目标函数取最小值的点就是点A。对应的最优解：X=0.58,1.34，f=2.98。,22,1.5 最优化问题的下降迭代解法,在经典级值问题中，解析法只适用于简单或特殊问题的寻优，对于复杂的工程问题通常无能为力，随着电子计算机的迅速发展，数值迭代算法广泛的用于最优化设计。 最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭

12、代的一个搜索方向和适当的步长，从而到达一个新点。由于数学模型定义的是极小化问题，因此数值解法称为下降迭代解法。一般采用如下算式：,S为搜索方向，为步长因子，每一步（k）都寻找最优的搜索方向和步长因子，新的迭代点Xk+1从当前点Xk出发，沿方向Sk跨出k步长得到。 序列迭代点的目标函数值必须满足如下关系：,23,下图为迭代过程示意图,构成一个下降迭代解法必须解决3个基本问题： （1）选择合适的搜索方向Sk，不同的搜索方向构成不同的下降迭代算法 （2）寻找最优步长因子k，一般采用一维搜索算法 （3）给定适当的终止判断准则,24,下降迭代解法的基本框图：,25,算法的收敛速度与计算终止准则,收敛速度

13、 当迭代算法产生的点列所对应的函数值严格地单调递减，并且最终收敛于最优化问题的极小点时，称此迭代算法具有收敛性。点列向极小点逼近的速度称为算法的收敛速度。 收敛速度定义：对于与迭代次数无关的常数（0 1），如果存在数1，使下式成立：,当=1时，称算法具有线性收敛性，或者说算法具有线性收敛速度； 当12时，称算法具有超线性收敛性； 当=2时，称算法具有二次收敛性。 一般来说，具有二次收敛性的算法是收敛速度最快的算法，具有线性收敛性的算法速度较慢。后面介绍的算法中，梯度法（最速下降法）具有线性收敛性，牛顿法具有二次收敛性，其他算法都只具有超线性收敛性。,26,终止准则 因为不可能让两个实数完全相等

14、，所以精确的最优解是永远也不可能达到的。但从工程角度考虑，一个精确度过高的最优解在计量和实施过程中是无法实现的和没有必要的。因此，最优化计算只要求得到满足一定精度的近似最优解，而非精确最优解。判断迭代点是否达到给定精度要求的判别式称为最优化算法的终止（收敛）准则。 常用的终止准则 点距准则：当相邻迭代点的距离充分小时，可认为迭代终止。 一般取收敛精度=10-610-4 值差准则 或 梯度准则 由极值理论知，多元函数在某点取得极值的必要条件是函数在该点的梯度等于零。在迭代过程中，梯度值不可能绝对等于零，因此取梯度模小于给定精度即是函数的近似最优点。,27,1.6 最优化算法分类,根据目标函数和约

15、束函数的性质可以将最优化问题分为线性和非线性问题，对应的数值求解算法称为线性最优化算法和非线性最优化算法。 根据是否具有约束条件，还可以分为无约束问题和约束问题，对应的数值解法称为无约束算法和约束算法。 根据设计变量的多少可以把最优化算法分为单变量算法和多变量算法，单变量的数值解法即一维搜索法。 根据目标函数可以分为单目标最优化问题和多目标最优化问题，也叫单目标规划和多目标规划。,28,29,数学规划 以上提到的线性规划和非线性规划都属于数学规划，即数学最优化问题：具有等式和不等式约束，求目标函数的极大或极小值的数学优化模型。数学规划是本课讲述的内容。 组合优化 组合优化的函数f由有限个元素组

16、成的集合和若干子集构成，组合优化可以用列举排序的方法求出最优解，如n个叶片排序问题，20个叶片有20!=2432902008176640000种排列，因此组合优化的问题，就是要寻找一个有效的算法。 图论、网络流 由于许多离散性的问题均可通过图来表示，使得图论的研究越来越受重视。图论中应用最多的是网络流。图论在运筹学、电路网络、计算机科学已成为重要的数学工具。 动态规划 动态规划主要用于求解以时间划分阶段的动态过程的优化问题，用以区别与时间无关的静态规划(如线性规划、非线性规划)，可以把动态规划看作多阶段决策过程。如最短路线、库存管理、资源分配、设备更新、排序、装载等问题。,30,1.7 MATLAB优化工具箱介绍,Optimization Toolbox: 求解线性规划和二次规划 求函数最大值与最小值 非线性函数的最小二乘 多目标优化 约束条件的优化 求解非线性方程,