最优化方法期末考试复习.docx

最优化理论与方法知识点总结最优化理论与方法知识点总结 1一、最优化简介： 21.1最优化应用举例 21.2基本概念 21.3向量范数 21.4矩阵范数 21.5极限的定义 21.6方向导数存在性和计算公式 21.7梯度定义 21.8海塞矩阵 21.9泰勒展开式： 21.10凸集定义 31.11凸集性质 31.12凸函数定义 31.13凸函数判断 31.14矩阵正定与半正定判断 31.15例题（判断矩阵是否正定） 31.16凸优化 3二、线性规划 32.1线性规划数学模型的一般形式 32.2解的基本定理 32.3解的分类 32.4图解法 32.5例题（图解法） 42.6标准型的化法 42.7例题（化为标准型） 42.8单纯形法 42.9例题（单纯形法） 4三、对偶线性规划 43.1对偶问题 43.2单纯形法解对偶问题 43.3对偶单纯形法求解线性规划问题过程 4四、无约束优化 44.1无约束优化概述 44.2搜索区间的确定 44.3区间消去法原理 44.4黄金分割法 54.5插值方法 54.6常见的终止准则 54.7最速下降法 54.8牛顿类方法 54.9例题（牛顿类方法） 5一、最优化简介：1.1最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc 等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSI etc.排版1.2基本概念目标函数和约束函数都是线性的，称之为线性规划问题，而有的模型中含有非线性函数，称之为非线性规划。

性与非线性规划中，满足约束条件的点称为可行点，全体可行点组成的集合称为可行集或可行域如果一个问题的可行域是整个空间，则称此问题为无约束问题.最优化问题可写成如下形式：1.3向量范数1-范数：║x║1=│x1│+│x2│+…+│xn│2-范数：║x║2=（│x1│2+│x2│2+…+│xn│2）1/2∞-范数：║x║∞=max（│x1│，│x2│，…，│xn│）1.4矩阵范数1-范数：║A║1= max{ ∑|ai1|，∑|ai2|，……，∑|ain| } （列和范数，A每一列元素绝对值之和的最大值）（其中∑|ai1|第一列元素绝对值的和∑|ai1|=|a11|+|a21|+...+|an1|，其余类似）；2-范数：║A║2= A的最大奇异值 = (max{ λi(AH*A) })1/2（谱范数，即A^H*A特征值λi中最大者λ1的平方根，其中AH为A的转置共轭矩阵）；∞-范数：║A║∞= max{ ∑|a1j|，∑|a2j|,...，∑|amj| } （行和范数，A每一行元素绝对值之和的最大值）1.5极限的定义定义：如果序列{xn}与常数a 有下列关系：对于任意给定的正数ε(不论它多么小)，总存在正整数N ，使得对于n >N 时的一切xn，不等式|xn-a |<ε都成立，则称常数a xtax="">0,其中表示xT的转置，就称A为正定矩阵。

2）A是n阶方阵，如果对任何非零向量x，都有xTAx≥0,其中表示xT的转置，就称A为正定矩阵1.15例题（判断矩阵是否正定）1.16凸优化如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题Minf(x),x∈C，其中x为优化变量；f为凸目标函数；C是优化变量的可行域，是一个凸集二、线性规划2.1线性规划数学模型的一般形式2.2解的基本定理1 线性规划问题的可行域是凸集（凸多边形）2 最优解一定是在凸集的某一顶点实现（顶点数目不超过Cnm个）3 先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止2.3解的分类1. 可行解：满足约束条件的解为可行解所有解的集合为可行解的集或可行域2. 最优解：使目标函数达到最大值的可行解线性规划问题的解.3. 基本解：只满足等式约束条件，但不满足其他条件的所有解，最多为Cnm个4. 基本可行解：满足非负约束条件的基本解，简称基本可行解2.4图解法建立直角坐标(x1，x2)，图中阴影部分及边界上的点均为其解，是由约束条件来反映的2.5例题（图解法）2.6标准型的化法2.7例题（化为标准型）2.8单纯形法2.9例题（单纯形法）三、对偶线性规划3.1对偶问题3.2单纯形法解对偶问题对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。

如果得到的基本解的分量皆非负则该基本解为最优解也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解3.3对偶单纯形法求解线性规划问题过程四、无约束优化4.1无约束优化概述4.2搜索区间的确定4.3区间消去法原理4.4黄金分割法4.5插值方法4.6常见的终止准则4.7最速下降法优点：梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解缺点：靠近极小值时收敛速度减慢，求解需要很多次的迭代；直线搜索时可能会产生一些问题；可能会“之字形”地下降4.8牛顿类方法4.9例题（牛顿类方法）。