最优化方法教案--东北大学

1、精选优质文档-倾情为你奉上第一章 最优化问题与数学预备知识最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。应用最优化方法解决问题时一般有以下几个特点：1. 实用性强2. 采用定量分析的科学手段3. 计算量大，必须借助于计算机4. 理论涉及面广应用领域：工业，农业，交通运输，能源开发，经济计划，企业管理，军事作战。§1.1 最优化问题实例最优化问题：追求最优目标的数学问题。经典最优化理论：（1） 无约束极值问题： （或）其中，是定义在n维空间上的可微函数。解法（求极值点）：求驻点，即满足并验证这些驻点是否极值点。（2） 约束极值问题：s.t. 解法：采用La

2、grange乘子法，即将问题转化为求Lagrange函数的无约束极值问题。近代最优化理论的实例：例1 (生产计划问题) 设某工厂有3种资源B1，B2，B3，数量各为b1，b2，b3，要生产10种产品A1，A10 。每生产一个单位的Aj需要消耗Bi的量为aij，根据合同规定，产品Aj的量不少于dj，再设Aj的单价为cj 。问如何安排生产计划，才能既完成合同，又使总收入最多？（线性规划问题）数学模型：设Aj的计划产量为，z为总收入。目标函数：约束条件： 线性规划问题通常采用单纯形法来求解。例2 (工厂设址问题) 要在m个不同地点计划修建m个规模不完全相同的工厂，他们的生产能力分别是（为简便起见，假

3、设生产同一种产品），第i个工厂的建设费用。又有n个零售商店销售这种产品，对这种产品的需求量分别为，从第i个工厂运送一个单位产品到第j个零售商店的运费为cij。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。（混合整数规划问题）数学模型： 设第i个工厂运往第j个零售商店的产品数量为xij（i=1，m；j=1，n），且目标函数：约束条件：整数规划问题通常可用分枝定界法或割平面法来求解。例3 (投资计划问题) 假设某一个生产部门在一段时间内可用于投资的总金额为亿元，可供选择的项目总共有n个，分别记为1，2，n。并且已知对第j个项目的投资总数为亿元，而收益额总数为亿元。

4、问如何使用资金亿元，才能使单位投资获得的收益最大。（非线性规划问题）数学模型：设目标函数：约束条件： 非线性规划问题的求解方法很多，是本课的重点。动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源分配问题，生产与存储问题。例4 (多参数曲线拟合问题)已知热敏电阻依赖于温度的函数关系为 （*）其中，是待定的参数，通过实验测得和的15组数据列表如下，如何确定参数？i12345678505560657075808534.7828.6123.6519.6316.3713.7211.549.744i9101112131415909510010511011

5、51208.2617.036.0055.1474.4273.823.307建立数学模型：测量点与曲线对应的点产生“偏差”，即得如下无约束最优化问题：通常采用最小二乘法。§1.2 最优化问题的数学模型一、 最优化问题的数学模型1. 定义1：设向量.若，则记或；若，则记或。2一般模型： ， （1）s.t. 其中，；，是关于变量的实值连续函数，一般可假定它们具有二阶连续偏导数。3向量模型： ， （1）s.t. 其中，称为目标函数；，称为约束函数；满足约束条件（2），（3）的点称为容许解或容许点（或可行解）；可行解的全体称为容许域（或可行域），记为R；满足（1）的容许点称为最优点或最优解（或

6、极小（大）点），记为；称为最优值；不带约束的问题称为无约束问题，带约束的问题称为约束问题；若目标函数，约束函数，都是线性函数，则称为线性规划；若其中存在非线性函数，则称为非线性规划；若变量只取整数，称为整数规划；若变量只取0，1，称为01规划。注：因，则最优化问题一般可写成二、 最优化问题的分类§1.3 二维问题的图解法例1. 解：1. 由全部约束条件作图，求出可行域R：凸多边形OABC2. 作出一条目标函数的等值线：设，作该直线即为一条目标函数的等值线，并确定在可行域内，这条等值线向哪个方向平移可使值增大。3. 平移目标函数等值线，做图求解最优点，再算出最优值。顶点是最优点，即最优

7、解，最优值。分析： 线性规划问题解的几种情况（1） 有唯一最优解（上例）；（2） 有无穷多组最优解：目标函数改为（3） 无可行解：增加约束，则。（4） 无有限最优解（无界解）：例 结论：（1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。（2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。例2. 解：目标函数等值线：C为最优点，得定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集称为等值面。§1.4 预备知识（一） 线性代数一、 n维向量空间1. 向量的内积：设，则内积为2. 向量的范数（或长度或模）：设，若实数具有以下性质：（1）当且仅当时；（2）；（3）

8、.则称为上的向量的范数，简记为。规定了向量范数的线性空间称为线性赋范空间,记为.3. 常见的向量范数向量的范数：，三个重要的向量范数：，注：若无特殊说明，本书中的指的是。4. 间的距离：5. 与正交：若非零向量组，的向量两两正交，称它们是正交向量组。6. 标准正交基：，是n个正交的单位向量，即二、 特征值和特征向量定义：设为n阶方阵，存在数和非零向量，使，则称为矩阵的特征值，非零向量为矩阵属于特征值的特征向量。三、 正定矩阵定义：设为n阶实对称方阵，若对任意非零向量，均有，则称为正定二次型，为正定矩阵，记；若，半正定二次型，为半正定矩阵，记。类似有负定（半负定）二次型，负定（半负定）矩阵的概念

9、。性质：实对称方阵为正定矩阵（负）的特征值均为正（负）的各阶顺序主子式均为正（奇数阶为负，偶数阶为正）实对称方阵为半正定矩阵的特征值均非负的各阶顺序主子式均为非负（二） 数学分析一、 梯度和海色（Hesse）矩阵1. 多元函数的可微性可微定义：设，若存在维向量，对，总有 （1）则称函数在点处可微。式（1）等价于 （2）其中，是的高阶无穷小。 定理1：（可微的必要条件）若函数在点处可微，则在该点关于各个变量的偏导数存在，且2. 梯度（1）概念梯度：令则称为n元函数在处的梯度（或记为）。又称为关于的一阶导数。注：式（2）等价于 （3）等值面：在三维和三维以上的空间中，使目标函数取同一数值的点集称为

10、等值面（曲面）。方向导数：设在点处可微，向量，是方向上的单位向量，则极限称为函数在点处沿方向的方向导数，记作。方向导数的几何解释：方向导数表示函数在点处沿方向的的变化率。函数的下降（上升）方向：设是连续函数，点，为一方向，若存在，对于，都有（）则称方向是函数在点处的下降（上升）方向；结论1：若方向导数，则方向是在点处的下降方向；若方向导数，则方向是在点处的上升方向；（2）性质【性质1】：梯度为等值面在点处的切平面的法矢（向）量。【性质2】：梯度方向是函数具有最大变化率的方向。定理2：设在点处可微，则方向导数其中，是方向上的单位向量，为梯度与的夹角。结论2：1）与梯度方向成锐角的方向是上升方向；

11、与梯度方向成钝角的方向是下降方向；2）梯度方向是函数值上升最快的方向，称为最速上升方向；负梯度方向是函数值下降最快的方向，称为最速下降方向。（3）几种特殊函数的梯度公式（1），为常数；（2），其中；（3）；（4）若是对称方阵，则.例3. 泰勒（Taylor）公式与Hesse矩阵性质1：设具有一阶连续偏导数，则 （*）其中，即介于与之间。性质2：设具有二阶连续偏导数，则 （* ）其中为函数关于的二阶导数，称为的海色（Hesse）矩阵。结论1：当时，（即海色矩阵对称）。注1：1) 设向量函数时，称为向量函数在点处的导数（梯度）。2) 向量函数在点处可微是指所有分量都在点处可微。关于向量函

12、数常见的梯度：（1），；（2），；（3）（4）设，其中，则，例：（三） 极小点的判定条件（求）一、 基本概念1. 点的邻域：2. 局部极小点：设. 若存在点和数，对 都有，则称为在上的（非严格）局部极小点；若（），则称为在上的严格局部极小点。3. 全局极小点：设. 若存在点，对于 都有，则称为在上的（非严格）全局极小点；若（），则称为在上的严格全局极小点。 性质：全局极小点必是局部极小点；但局部极小点不一定是全局极小点。类似有极大点的概念。因，本书主要给出极小问题。4. 驻点：设可微，若，则称点为的驻点或临界点。 二、 极值的条件定理1（一阶必要条件）设具有一阶连续偏导数，是的内点，若是的局部

13、极小点，则定理2（二阶必要条件）设具有二阶连续偏导数，若是的内点且为的局部极小点，则是半正定的，即对恒有例定理3（二阶充分条件）设具有二阶连续偏导数，为的内点，且，若正定，则为的严格局部极小点。（四）凸函数与凸规划一、凸集1. 凸集的定义：一个n维向量空间的点集中任意两点的连线仍属于这个集合，即对，有则称该点集为凸集。2. 凸集的性质：（1）凸集的交集仍是凸集；（2）数乘凸集仍是凸集；（3）凸集的和集仍是凸集特别规定，空集是凸集。3. 超平面：设且，则集合称为中的超平面，称为该超平面的法向量，即；（是凸集）半空间：集合称为中的一个半空间。超球：。4. 凸组合：设为中的个点，若存在且，使得则称为

14、的凸组合。若均为正，则称为严格凸组合。5. 顶点（或极点）：设是凸集，若不能用内不同两点和的凸组合表示，即，则称为的顶点。二、凸函数1. 凸函数：设，是凸集，若对及，都有则称为凸集上的凸函数；若则称为凸集上的严格凸函数。类似有凹函数的定义。2.几何意义：函数图形上连接任意两点的线段处处都在函数图形的上方。3. 性质性质1：为凸集上的凸函数，则也为上的凸函数。性质2：两个凸函数的和仍是凸函数。推论1：凸集上有限个凸函数的非负线性组合仍为上的凸函数。性质3：若为凸集上的凸函数，则对，的水平集是凸集。性质4：为凸集上的凹函数为凸集上的凸函数。4. 凸函数的充分必要条件定理1（一阶条件）设可微，是凸集

15、，则（1）为凸函数对，恒有（2）为严格凸函数对，恒有定理2（二阶条件）设具有二阶连续偏导数，为开凸集，则 （1）在内为凸函数对，是半正定的；（2）若正定，则在内为严格凸函数。特殊地，元二次函数为（为对称矩阵）；若正定，则称为正定二次函数。性质：正定二次函数是严格凸函数。（因为）5. 凸函数的极值定理3 设为凸集上的凸函数，则（1）的任一局部极小点为全局极小点；（2）若具有二阶连续偏导数，且存在，使，则为在上的全局极小点；（3）若为严格凸函数，且全局极小点存在，则必唯一。特殊：对于正定二次函数，有，得唯一驻点为唯一的全局极小点。6. 凸规划问题：非空凸集上的凸函数的极小化问题。考虑凸规划问题：，

16、 (1)s.t. 其中，为上的凹函数，为上的线性函数，为凸集，为上的凸函数。注：线性函数既可视为凸函数，又可视为凹函数。二次规划： s.t. 其中，半正定或正定。 （五）下降迭代算法1. 下降迭代算法的步骤（1）选择一个初始点，令k：=0（2）检验是否最优？若是，则停止迭代；若不是，则（3）确定一个下降方向：存在，对，使得（4）从点出发，沿方向进行直线搜索（一维搜索），即求步长使（5）计算，令k：=k+1，转（2）2. 直线搜索及其性质（1）简记： 表示从点出发，沿方向进行直线搜索，得到极小点。（2）定理：设目标函数具有一阶连续偏导数，若，则证明：（反正法）设，则1），此时是点的下降方向；2）

17、，此时是点的下降方向；与矛盾。3. 收敛速度定义1：设序列是线性赋范空间中的点列，若则称序列收敛于，记为。定义2：设向量函数，若当时，总有，则称在点连续；若在内每一点都连续，则称在内连续。特别地，m=1时，为数量函数，则定义3：设序列收敛于，若存在与无关的数和，使得当从某个开始，都有则称序列收敛的阶为，或为阶收敛。当，且时，称线性收敛或一阶收敛；当时，称二阶收敛；当时，称超线性收敛。4. 计算终止准则计算终止准则根据相继两次迭代的结果a. 根据相继两次迭代的绝对误差（不常用），b. 根据相继两次迭代的相对误差，c. 根据目标函数梯度的模足够小为给定的足够小的正数。以上准则统称为Himmelbl

18、au计算终止准则，简称H终止准则。第二章 线性规划§2.1 数学模型一、线性规划的标准型1. 繁写形式：s.t. 其中，（否则，等式两端同乘以“-1”）。2. 缩写形式：s.t. 3. 向量形式：s.t. 其中，。4. 矩阵形式：s.t. 其中，：约束条件的系数矩阵，一般地，；：限定向量，一般地，；：价值向量；：决策向量，；通常，为已知，未知。二、任一模型化为标准型1. 极大化目标函数：令，则问题转化为2. 约束条件为不等式若约束为“”型，则“左端+松弛变量=右端”（松弛变量0）如：，引入松弛变量，化为若约束为“”型，则“左端-剩余变量=右端”（剩余变量0）如：，引入剩余变量，化为3

19、. 若存在无非负要求的变量（称为自由变量）令，其中，代入目标函数及约束条件即可。4. 某变量有上、下界若，即，令，有。用代替即可。若，即，令，有。用代替即可。例：§2.2 线性规划解的性质一、基本概念标准型（LP）： s.t. 可行解（容许解）：满足约束（2）、（3）的解。最优解：满足（1）的容许解。基：设的秩为，若是中的阶可逆矩阵，称是线性规划问题（LP）的一个基。基向量：基中的一列（）即为一个基向量。（共个）非基向量：基之外的一列（）即为一个非基向量。（共个）基变量：与基向量相应的变量。（共个）非基变量：与非基向量相应的变量。（共个）基本解：令所有非基变量为0，求出的满足约束（2

20、）的解。基本容许解：满足约束（3）的基本解。最优基本容许解：满足约束（1）的基本容许解。退化的基本解：若基本解中有基变量为0的基本解。退化的基本容许解：退化的最优基本容许解：二、线性规划问题的基本定理定理1 若线性规划问题存在容许域，则其容许域是凸集。定理2 线性规划问题的基本容许解对应于容许域的顶点。定理3 若线性规划问题存在有限最优解，则其目标函数最优值一定可以在容许域的顶点达到。§2.3 单纯形法一、单纯形法原理单纯形法的基本思路：根据问题的标准型，从容许域的一个基本容许解（一个顶点）开始，转移到另一个基本容许解（顶点），并且使目标函数值逐步下降；当目标函数达到最小值时，问题就

21、得到了最优解。二、单纯形法的步骤（以“大M法”为例）数学描述例（大M法）：s.t. 1. 构造初始容许基初始容许基是一个单位矩阵，它相应的基本解是容许的。1º引入附加变量，把数学模型化为标准型。2º若约束条件中附加变量系数为“-1”，或原约束即为等式，则一般须引入人工变量。3º目标函数中，附加变量系数为0，而人工变量系数为M（很大的正数）。人工变量系数为大M：只要人工变量>0，使前后约束条件不等价，但由于目标函数的修改，同时也使所求的目标函数最小值是一个很大的数，也是对“篡改”约束条件的一种惩罚，因此，M叫做罚因子，大M法也叫做罚函数法。若对极大化问题，目标

22、函数中人工变量系数为（-M）。得到如下标准型：s.t. 其中，表示基变量；表示非基变量。2. 求出一个基本容许解1º用非基变量表示基变量和目标函数。用非基变量表示基变量，即有用非基变量表示目标函数，即其中，而称为非基变量的检验数。上式中，规定各基变量的检验数为0。其中，是基变量的价值系数，随基的改变而改变。2º求出一个基本容许解及相应的目标函数值。令非基变量=0即得初始基本容许解：，初始目标函数值：3. 最优性检验1º检验数：目标函数式中，各非基变量的系数，即称为各非基变量的检验数。2º最优解判别定理：若在极小化问题中，对于某个基本容许解，所有检验数，且人工变量为0，则该基本容许解是最优解。3º无穷多最优解判别定理：若在极小化问题中，对于某个基本容许解，所有检验数，又存在某个非基变量的检验数为0，且人工变量为0，则该线性规划问题有无穷多最优解。4º无容许解判别定理：若在极小化问题中，对于某个基本容许解，所有检验数，但人工变