最优化之基本概念.doc

最优化之基本概念第一章1. 最优化问题的数学模型包含有三个要素：即变量（又称设计变量）、目标函数、约束条件。（变量、目标函数、约束条件P4）2. （最优化问题的三种表达形式P5中）3. x称为集约束，通常不作考虑，可认为目标函数的定义域。一般有Rn。可行点（容许点）：满足所有约束的点称为可行点或容许点。可行域（容许集）：全体可行点构成的集合称为可行域，也叫容许集，记为D。 （P5）4. 最优点X*：在可行域内找到的点，使得目标函数值取得最优值 f(X*)。最优值：目标函数值f(X*)最优解：(X*，fX*)，但习惯上把X*本身称为最优解。 （P5底）5. 处理最优化问题的3种方法：解析法、图解法、迭代法6. 迭代算法：选取一个初始可行点，然后根据现有的信息确定本次迭代的一个搜索方向和适当的步长，从而得到一个新点。 搜索方向 迭代步长下降算法：求 minf(x) 有 fxk+1f(xk) (P9)7. 收敛速度：衡量算好好坏的一个标准。 （P9底）具有超线性收敛或者二阶收敛的算法是较快速的算法。 （P10）8. 计算终止的计算终止准则：无约束优化问题的三种计算终止准则：点距准则、函数下降量准则、梯度准则。 （P11）约束优化问题有各自的终止准则。优化算法的基本迭代过程： （P11底）9. 图解法：（P6） 运用求解二位优化问题可行域：即约束集合 （P6）等高线：在三维空间中，不同的c值得到不同的投影曲线。没一条投影曲线对应一个c值，称投影曲线为目标函数的等值线或者等高线。 （P7）10. 组合优化问题举例：背包问题即 0-1问题： P13 例1.9 需要设xi为二进制变量，xi=1 表示装第i个物品。旅行商问题（TSP）： （P14） 组合爆炸 P15聚类问题： （P14） 组合爆炸 P1511. 算法复杂性：算法对时间的复杂性T(n)和对空间的复杂性S(n)。算法的时间复杂性：算法执行基本操作的次数算法的空间复杂性：算法执行期间占用的存储单位 （P15）12. 组合优化问题分类：根据算法的复杂性，可分为P类、NP类、NP完全类。P类问题：具有多项式实践求解算法NP类问题：未找到球最优解的多项式实践算法NP完全类问题：任何一个问题至今未发现有多项式算法；只要其中一个问题找到了多项式算法，那么其他所有问题均有多项式算法。 （P15）第二章1例题2.1 如何判定矩阵是否正定（P19） 充要条件：矩阵的行列式的顺序主子式全部大于零 线代P1642方向导数（P19）（1）方向导数的定义：（P19底）（2）下降方向：（P20） f(x0+tP)f(x)若f(x0)P0，则称P为f在X0处的下降方向。3梯度 （1）定义及常用梯度公式：（P20） （2）梯度与方向导数之间的关系：（P21） 若f(x0)TP0，则P方向是函数f(x)在x0处的上升方向。方向导数的正负决定了函数值的上升或者下降，那么上升或者下降的幅度则由绝对值的大小决定。 （3）关系（P21）梯度方向是函数值的最速上升方向；函数在与其梯度正交的方向上变化率为零；函数在与其梯度成锐角是上升的，而在与其梯度成钝角的方向上是下降的；梯度反方向是函数值的最速下降方向。 例题2.2 对目标函数求某一点的最速下降方向。4Hesse矩阵 （1）Hesse矩阵的定义：（P22）当f(x)在点x0处的所有二阶偏导数连续时有Hesse矩阵对称。 例题2.3、2.4、2.5 计算求解了已知函数的梯度和Hesse矩阵。 线性函数的一阶导数为常向量，二阶导数为零矩阵；二次函数的一阶导数为线性向量函数，二阶导数为常矩阵。（P24）（2）Jacobi矩阵梯度的Jacobi矩阵即为函数的Hesse矩阵。 （P2425）性质见书本P25。（3）泰勒展开式： （P25）证明同见P255二次型与正定矩阵 （1）二次型： （P18第一部分） （2）正定矩阵 （P19文字部分）矩阵A为正定的充要条件是它的行列式A的顺序主子式全部大于零。（P19）判定6极小点的判定条件 （1）局部极小点和严格局部极小点 定义 （P26） 全局极小点和严格全局极小点 定义 （P26） 显然，整体的最优解一定是局部的最优解，而局部的最优解不一定是整体的最优解。 （2）无约束问题的最有性条件几个概念 最优性条件：优化问题最优解所满足的必要条件和充分条件； 必要条件：最优点满足那些条件； 充分条件：满足那些条件的点是最优点。 （3）无约束问题的最优性条件几大定理 （P27）定理2.3 2.5重点 （若x为极值点，则fx=0 导数为0。） （若x为极小值点，则fx=0，一阶导数为0，二阶导数大于0。）6约束问题的最优性条件 （1）约束最优点除了可能落在可行域内的情况外，更是常常在约束边界上或约束曲面上。 （2）约束优化问题的类型：（P37）不等式约束优化问题（IP型）、等式约束优化问题（EP型）、一般约束优化问题（GP型） （3）约束优化问题局部解的一阶必要条件： （P38） 在研究某一点出的可行方向时，只需要考虑在这一点的起作用的约束（P38中）。 （4）IP型约束问题的一阶必要条件：（P39 一般性条件在P40）看书上具有三个不等式约束的二维最优化问题可供理解（P38-39） （5）EP型约束问题的一阶必要条件（P41）（6）GP型约束问题的一阶必要条件（P41）（7）Kuhn-Tucker条件（K-T条件）用于判断某可行迭代点是否可以作为约束优化点输出 步骤 K-T条件检验某迭代点是否为约束最有点的步骤（P42） 例题2.9 利用K-T条件判别某点是否为最优点 （P43）7凸集 （1）凸集的定义与性质：（P28）空集也是凸集 性质1：任意一组凸集的交仍然是凸集。 （2）在凸集中，比较重要的特殊情形有凸锥和多面集。（P29） （3）极点（P29底P30例子） （极点一般为图形的端点和圆的圆周（个人见解） （4）极方向 （P30） （5）表示定理（P31） （6）凸集分离定理（P32） 凸集分离定理是凸分析中最重要的定理之一。8凸函数（1）凸函数定义（P32）（2）其他相关凸函数的定义（P3233）（3）凸函数的性质定理：（P33-34）凸函数的判定（P34）凸函数判定的二阶条件：（P35）9凸规划（不会） （1）定义：（P35）主要看书 （2）极小点的性质：第三章1线性规划数学模型和基本概念 （1）线性规划的数学模型所满足的三个条件（P46） 每一个问题都用一组决策变量x1,x2,xnT表示某一方案；每一组值就代表一个具体方案。 有一个目标函数，可用决心额变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化。 有一组约束条件，可用一组线性等式或不等式来表示。 （2）线性规划的一般形式（P46） （3）线性规划的标准型（P47） 矩阵-向量形式的标准型 略（P47） （4）一般形式转化为标准型（P47-48） 加x 减x例题3.1 如何将一般形式的线性规划问题转化为标准形式 （5）线性规划的基本概念（P48） 如果基解又满足非负条件，则称之为基可行解，此时的基B称为可行基 基可行解中非零分量的个数不会超过m，若基可行解中非零的个数恰为m，称此基可行解为非退化的基可行解，否则称为退化的基可行解。 若一个线性规划的所偶基可行解都是非退化的，称此线性规划是非退化的。2线性规划的基本定理 （1）引理 3.1:：设 X 是标准型线性规划的可行解, X为基可行解的充要条件是, X的正分量对应系数列向量线性无关。 （2）定理3.1：线性规划问题的基可行解 X对应于可行域 D 的顶点。 （3）定理3.2：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。3单纯形法（P50-54好好看吧 ） （1）单纯形法的思路：从可行域中某一个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），直到目标函数到达最优时，基可行解即为最优解。（如书本P51图3.1所示） （2）单纯形法计算步骤：（P51-52） 单纯形法表 P51 （首先要化成标准型） 单纯形法流程图：P52 （3）初始可行基的确定（P53）（表示看不懂） /u55/v_NzY0NTc3ODg.html 单纯形表法的过程，与教材略有差别。 书中的检验数应由书本P51（2）中公式所得，C i的值会影响检验数的值。 看完视频以后可看例题3.2单纯形表法求解线性规划问题。4.大M法（限制条件中含有等式） （1）使用条件：当系数矩阵中不含单位矩阵，没有明显的基可行解时，单纯形法难以使用。 （2）大M法的思想：在约束条件中加入人工变量，构造基矩阵为单位阵的线性规划问题的标准型。同时将人工变量在目标函数中的价值参数为M，M是一个很大的正数。 在迭代过程中，将人工变量从基变量中逐个换出，如果最终所有的检验数均大于零时，基变量中不再含有非零的人工变量，这表明原问题有解，否则无解。 （3）解题步骤：参考P55例题3.35两阶段法（限制条件中含有等式） （1）解题步骤：（P56-57） 第一阶段：给原问题加入人工变量，构造只含价值系数为1的人工变量的目标函数且要求实现最小化，其约束条件与原问题相同，利用单纯行法求解问题。若得到g(X)=0，这说明原问题存在基可行解，可进入第二阶段，否则原问题无可行解，停止计算。 第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换为原问题的目标函数系数，作为第二阶段计算的初始单纯形表进行计算。 例题3.4 两阶段法求解线性规划问题。（P57）6对偶问题的基本原理 （1）原问题与对偶问题的表达形式和关系两者对应关系：见书本P61表3.7所示（2）对偶原理：（P61-62） 弱对偶原理：对偶问题（max）的任何可行解 Y0 ，其目标函数值总是不大于原问题（min）任何可行解 Z0 的目标函数值。 对偶定理：假如原问题货对偶问题之一具有有限的最优解，则另一问题也具有有限的最优解，且两者对应的目标函数值相等。加入一个问题的目标函数值是无界的，则另一问题没有可行解。 互补松弛定理：假如 X0 和 Y0分别是原问题和对偶问题的可行解，U0是原问题剩余变量的值，V0是对偶问题松弛变量的值，则 X0 、Y0分别是原问题和对偶问题最优解的充要条件是 Y0 U0+V0X0=0 （3）对偶问题的迭代算法步骤（P63）例题P64-65 使用对偶单纯形法解线性规划问题7线性规划问题的灵敏度 （会分析当系数变化是，最优解和最优值的变化情况） （1）价值系数 Ck 的变化（P66主要是那个不等式） 例题3.9（P66） （2）资源系数 bk 的变化（P67主要是那个不等式） 例题3.10（P68）第四章1一维搜索法基本概念（P71） （1）迭代算法：选取一个初始可行点，然后根据现有的信息确定本次迭代的一个搜索方向和适当的步长。 （2）一维搜索法：从已知点 Xk出发，沿着某一下降的探索方向Pk来确定步长 tk的问题. 实质是单变量函数(t)关于变量的一维搜索选取问题。 直线搜索有精确直线搜索和非精确直线搜索。 （3）精确直线搜索： 精准一维搜索法可分为两类： 试探法：需要按某种方法找试探点，通过一系列试探点来确定极小点。 函数逼近法（插值法）：用某种较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来估计目标函数的极小点 （4）非精准直线搜索2搜索区间及其确定方法 （1）求解以为最优化问题的步骤：(P72“简言之”) （2）搜索区间的定义：（P72） （3）加步探索法：（P72底-73） 加步探索法的思想：P72底-73 加步探索法的步骤：（P73） 在加步探索法中，一般建议 =2；初始点要尽量取接近于问题的最优解； （4）单谷区间和单谷函数： 定义：（P74） 性质：（P74）若一个区间是某函数的单谷区间，意味着，在该区间中函数只有一个凹谷（极小值）。 某区间上的单谷函数在该区间上不一定是连续函数。 凸函数在所在区间上必然是单谷函数。 经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间。把搜索区间无限缩小，从而求出极小值。（黄金分割法的主要想法来源）3对分法（1）二分法原理：（P75） （2） 对分法迭代步骤（P75）4Newton切线法 （1）原理：（P77） Newton切线迭代公式 （2）Newton切线法迭代步骤：（P77）书本步骤略不同 （3）优点：（P78） 收敛速度很高。如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果。可证明至少是二阶收敛的。 （4）缺点：（P78） 需要求二阶导数。如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出的。 当曲线y=（t）在a,b上有较复杂的弯曲时，这种方法也往往失效。 即使曲线比较正常，在a,b中或者凹或者凸，初始点的选取必须适当。5黄金分割法 （1）原理：（P78）在单谷区间a,b适当的插入两点t1, t2,通过比较这两点函数值的大小来缩短区间的长度，依次迭代。 （2）黄金分割法算法步骤：（P79）6抛物线插值法 （1）原理：（P81）抛物线法就是一个用二次函数来逼近 (t)的方法，这也是我们常说的二次插值法。 （2）抛物线插值法迭代步骤：见书本P82-83 （3）Matlap求解第五章 常用无约束最优化方法1分类：直接搜索法（直接法）：在计算过程中只用到目标函数值，不必计算导数。（坐标轮换法、单纯形法）间接法：在计算过程中要用到目标函数的导数。（最速下降法、Newton法、共轭梯度法、变尺度法）2最速下降法： （1）基本原理：见精准直线搜索法（P87） 若每次迭代的搜索方向Pk取目标函数的负梯度方向，即Pk=-f(Xk)，步长tk取最优步长，由此确定的算法称为最速下降法。 （2）最速下降法迭代步骤：（P87） 最速下降法运用于正定二次函数（P87-88） 例题5.1（P89）（3）特点： 线性收敛，当距最优点较远时，速度快，而接近最优点时，速度下降。 该算法简单，每次迭代计算量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点3Newton法： （1）适用范围：如果目标函数具有连续的二阶偏导数，其Hesse矩阵正定，可用Newton法。此方法收敛速度很快。 （2）原理：（P90-91） 从初始点开始，每一轮从当前迭代点出发，沿着Newton方向并取步长tk=1的算法称为 Newton法。 （具体看书本） （3）Newton法迭代步骤：（P91） 例题5.2 Newton法迭代的运用 （P91-92） 从Newton方向的构造知道，对于正定二次函数，Newton方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解 （4）Newton法缺点 对初始点要求严格。一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的，当初始点远离极小点时，牛顿法不一定收敛。 当Hesse矩阵非正定时， Newton方向不一定是下降方向，经迭代，目标函数值可能上升， Newton法的搜索将会失败. 在进行某次迭代时可能求不出搜索方向。若目标函数在Xk处Hesse矩阵为奇异，则求不出，因而无法构成牛顿方向，从而迭代无法进行。 牛顿方向构造困难，计算相当复杂，占用机器内存相当大。4修正Newton法 （1）原理：（P93）为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法 （2）修正Newton法的迭代步骤：（P93）（3）算法说明： 修正Newton法克服了Newton法的缺点。由于含有一维搜索，每次迭代目标函数值一般有所下降（绝对不会上升）当迭代点接近于最优解时，收敛速度快，对初始点的选择要求不严。 求解的计算量和存储量均很大。5共轭方向法 （1）计算量小，收敛速度没有Newton法快，但比最速下降法快得多。 （2）概念：（P97） 从任意点X0出发，依次沿某组共轭方向进行一 维搜索的求解最优解问题的方法，叫共轭方向法。 （3）原理：书本（P94-97） （4）共轭方向法迭代步骤：（P98）6共轭梯度法： （1）每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，称为共轭梯度法。 （2）基本原理：（P99-100） （3）迭代步骤：（P100-101）例题5.3 共轭梯度法的运用（P102） （4）算法说明：（P103）可将共轭梯度法看作是最速下降法的一种改进。当令k=0时，就变为最速下降法共轭梯度法由于不涉及矩阵，仅仅存向量，因而存储量小，适合于维数较高的优化问题。共轭梯度法不要求精确的直线搜索但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能 7变尺度法（拟牛顿法） （1）基本思想：用不包含二阶导数的矩阵近似 Newton法中的Hesse矩阵的逆矩阵 （2）基本原理：（P103-104） （3）Hk需满足的三个基本条件： （4）变尺度法迭代步骤：（P105） 重点：DFP算法（1）基本原理：（P106-107） DFP算法校正公式： （2）迭代步骤：（P107） 例题5.4 DFP算法的应用（107-108） BFGS算法：（1） 基本原理