东北大学最优化方法全部课件

最初，优化方法(优化课件开发组)，退出，发表：张京，优化方法，和优化方法为了实现最佳目标而提出的各种解决方法被称为优化方法。 第二次世界大战前后，优化方法在军事领域的导弹和雷达控制研究中发展起来。 优化方法解决问题的一般步骤： (1)提出需要优化的问题，开始收集相关资料和数据；(2)建立求解优化问题的相关数学模型，确定变量，列出目标函数和相关约束；(3)分析模型，选择适当的优化方法；(4)求解方程。 一般通过编制程序，在计算机上求出最佳解(5)最佳解的验证和实施。 随着系统科学的发展和各领域的需要，优化方法不断地应用于经济、自然、军事和社会研究各领域。第1章预备知识、1.1古典极值问题1 .例、2 .数学模型、第一、没有制约极值问题，或解法：解方程组、第二、仅包含方程式制约的极值问题，或解法： Lagrange乘法、1.2实例数据拟合问题原料切割问题运输问题营养配餐问题分配问题， 1.3基本概念1 .设定最佳化问题的向量表示法后，用以、(1)、向量为变量的实数函数定义向量间的顺序关系(定义1 )。 由此，以向量为变量的实向量值函数最优化问题的一般形式，2 .最优化问题的分类，试验问题：用于验证和比较最优化方法的优劣的最优化问题。 3 .术语、目标函数、等式约束、不等式约束、容许解(点)、容许集、求解问题求、全局极小点的一个解决方法是首先求所有局部极小点，然后从其中找到全局极小点。 4 .极大值问题和极小值问题的关系，、1.4二维问题可以图解，有明显的几何解释。 例解、图解法的步骤：显然取，画出对应的曲线(称为等值线)，确定极值点的位置，用以往的方法求出。 本问题的极小点很容易理解。 更复杂的地方请参照P13上的示例1.7。 三维以上的问题不容易画在平面上，虽然在图形上起不到作用，但是有相应的等值面的概念，等值面具有以下性质：具有不同函数值的等值面不会相互相交(因为目标函数是单一值函数)。 等值面除了有极值点的等值面外，在区域内部不中断。 这是因为目标函数是连续函数，指令、等等值面密集的地方，目标函数值变化比较快，等值面稀疏的地方，目标函数值的变化比较慢。在极值点附近，等值面(等值线)一般是同心椭圆体面族(椭圆线族在1.5梯度和Hesse矩阵中，本段的讨论都基于对数函数，以下和今后的讨论中，以下向量的知识也经常使用。 微妙的假设。和。 的双曲正切值。 矢量也用希腊字符等表示。 向量内积的性质：I )、(对称性)、ii )、(线性)、iii )、然后，只在此时设定、向量的内积，则被称为向量的内积、实际、向量的长度、单位向量、向量的角度、向量的正交性、1 .可微、定义1(1.10 )，2 .坡度，定理1.1点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，点，坡度也称为函数，对于变量可以写为(1.10 )，该式与一次函数展开为二项的Taylor式相对。 梯度性质：梯度，连续时，第一，如果，请务必选择垂直，过点，处理的等值面。 其次，梯度方向是函数具有最大变化率的方向。 以下，以该性质为例进行说明。 上图是此函数的等值线图。 现在请稍微考虑一下。 请拿坐标。 起点向某个方向移动，并考虑其坐标，目标函数值中发生以下变化量，假定点不移动。 问：可动点向哪个方向移动时，目标函数值下降最多或上升最多？ 从图来看，相当于在以点为中心、以1为半径的圆周上，哪个点具有最大或最小的目标函数值的问题。 为了描述函数，通常，必须在点、点、情况和变化速度上引入上升方向和下降方向和方向导数的概念。 沿着方向的变化，函数，点，点，方向的变化反映了函数，直线上的变化，空间上有点，方向，确定的直线方程式是，上升方向和下降方向被设定的连续函数。 如果存在、的话，的话，方向是点，点的上升方向，如果存在，就全部存在，方向是点，点处的下降方向。 定义1.9设定、点、处理微、是非、方向的单位向量。 如果存在极限、零向量、就把它称为函数，点、点、方向的方向导数、备忘录、思考：的异同。 在、的情况下，方向是点、点处的上升方向，根据极限理论，容易理解，如果，方向是点、点处的下降方向。 因此，方向导数的正负决定函数值的升降。 定理1.2是，在各点，如果处理微小，则在其中不设为零向量，而设为左方向的单位向量。 定理1.2另外，的话，表示方向是点，点处的上升方向，则方向是点，点处的下降方向。、函数值的升降速度取决于方向导数的绝对值的大小。 绝对值越大，上升或下降的速度越快；绝对值越小，上升或下降的速度越慢。 这是因为，据此，I )等号成立是理所当然的，是and，同方向或者是and，同方向的缘故。 然后，在和相同方向的情况下，和同方向的情况下，取最小值，)锐角的话， 如果是钝角的话。 因此，方向导数也称为函数，是点、点、方向、方向的变化率。 把函数值下降最快的方向称为下降最快的方向。 最速降方向是，例1.8P19，几个常用函数的梯度式，如果是(1)，则为(2)、(3)、 (四)、 2 .关于2.Hesse矩阵、q :函数和变量，我们来看看二次导数是什么？矢量值函数是什么。 的双曲馀弦值。的所有成分可以是点，可以是微，称为向量值函数，可以是点，可以是微。、定义表示可以简单地用点、点、点、点、点、点、点、点、被称为点处的雅可比矩阵的向量形式来表现。 具有二次连续偏振函数的矩阵被称为函数，且变量的二次导数简称为。 也称为多变量实数函数的Hesse矩阵。 例1.9P21，几个特殊向量值函数的导数式：(1)， (2)、 (三)、 (4)设置，其中。 那么，利用(4)，得到多元函数展开为三项的Taylor公式。 或者，(1.31 )对应于一元函数展开为三项的Taylor表达式。 多元函数的Taylor展开公式在优化方法中非常重要，许多方法及其收敛性的证明就此开始。、1 .凸集合，1.6凸函数和凸规划，直观上，凸集合是空间中没有“孔”，边界不向内凹陷的点的集合，其基本特征是该集合的任意两点之间的线段还属于该集合。非凸集、凸集和空间中两点之间的线段由点的凸组合定义。 定义1.12设定，是，中，已知点。 如果存在点、满足、非负实数，另外，如果满足，的正实数，则是的严格凸的组合。 两点、的凸的组合，正好是连接两点的线段。 线段、严格的凸的组合不包含端点，定义了1.13集的集合。 如果有其中任意两点的话，集合就称为凸集合。 任意凸的组合还属于，空集规定为凸集。 思考：空间中三个不同点的凸组合集合，空间中四个不同点的凸组合集合，常见的凸集合是超平面，直线，球，定理1.5凸集合的交点是凸集合。2 .凸函数，定义1.16集，其中凸集。 如果，中的任何差异与任何对均得到满足，非负实数，经常存在，则为凸集合，上定义的凸函数。 此外，对于任意的正实数，如果全部满足对，则称为凸集合，上面定义的严格凸函数。凸集，如果是上的(严格)凸函数，则称为凸集，上的(严格)凹函数。 凸函数具有以下重要性质。 定理1.6，(1)如果是凸集合，上面定义的凸函数，则是上面的凸函数。 另外，若是任意的非负实数，则(2)凸集合，若是上面定义的凸函数，则是上述的凸函数。 由定理1.6可见，凸集合中定义的任何有限个凸函数的任何非负组合仍为凸函数。 例1.10，定理1.7，其中，非空凸集，如果是凸函数，则是任意的实数，水平集，是凸集。 证明的情况下，如果是空集的话就是凸集。 以下的设定不是空的。 任取。但是，作为根据的凸性，一定是有的，即。 所以，是凸集。 一般很难判断一个函数是否是凸函数。 但是，在函数微小的情况下，有以下判定定理。 定理1.7集，定理1.8集，可微函数，其中，凸集。 并且I )、凸函数的充分条件对于其中的任意两点，ii )、严格凸函数的充分条件对于其中的任意两点存在两个互异点，定理1.8显然有直观的几何解释。 微函数是凸函数的充分条件是，其定义域的凸集合的任何点的切线面(切线)都不在曲面(曲线)上。 右边的画是一维的样子。定理1.9是二次微函数，是非，开了凸集。 那么，上凸函数的充分条件是Hesse矩阵，上面到处都是正定的。 定理1.10是二次导数，非，空凸集，并且如果下一个Hesse矩阵在上面的任何地方都是正则的，则该定理是上面的精确凸函数。 这个命题的逆命题不真实。 举例来说，在中是严格的凸函数，在中是半正定的。 但是，假设Hesse矩阵是3 .凸规划中非空凸集，上面定义的凸函数，(1.36 )形式的优化问题被称为凸规划问题，简称为凸规划。 换句话说，在凸集合中定义的凸函数的极小化问题是凸规划问题。 如果，都是上凹函数，都是上线性函数，容易验证的集合，凸集合。 在这种情况下，凸计划(1.36 )可以表示为： (1.37 )、以下定理显示了凸规划的重要性质。 定理1.11是凸规划(1.36 )的局部极小点。 并且，I )、是(1.36 )的全局极小点，ii )严格的凸函数的情况下，(1.36 )的唯一的极小点，iii)(1.36 )的极小点的集合是凸集合。 定理1.12为微凸函数，且为非空。 凸集，凸计划(1.36 )的极小点的满足，中的任一点，总是。 条件表示，对于定理1.12，凸计划(1.36 )在最佳点上任何允许方向(定义4.3 )都不是下降方向。 推论1.13是微凸函数，非空、凸集。 这样的话，凸计划(1.36 )的全局极小点。4 .二次函数和二次规划、函数(1.38 )被称为元二次函数，其中是对称矩阵。 如果是正定的话，(1.38 )被称为正定、二次函数。 关注、的话，根据定理1.10可知，正定二次函数是严格的凸函数。 在优化算法的结构中，正定二次函数发挥着特殊的作用，本书的很多章节都与其相关。形式为、(1.39 )，最优化问题称为二次计划问题，简称二次计划。 如果半正定或正定，(1.39 )被称为二次凸计划。 定理1.14，一个，对称矩阵，正定矩阵的充，条件，的各级主人式都大于零。 开始，优化方法(优化课件开发组)，退出，发表：张京，优化方法，1.7极小点的判定条件，函数，局部极小点，满足哪些条件？ 相反，令人满意的是，哪些条件方面是局部最小的？ 定理1.15具有一次连续偏导数，是的内点。 请注意，如果是的局部极小点，条件式(1.40 )是不够的，只需要。 例如，点、上的坡度是、是此双曲抛物面的鞍点，不是极小点。 根据定理1.15和推论1.13，凸规划问题整体的极小点的一阶容易得到充分且必要的条件。 在、推论1.16集，可微凸函数、非空开凸集、和(1.36 )的全局极小点上，满足条件为.定义为1.17设定，可微，则定点。 定在点包括极大值点、极小值点、鞍点。 定理1.17具有二次连续偏导数，如果正定，是，严格的局部极小点。 一般来说，这个定理只具有理论意义。 这是因为对于复杂的目标函数，难以求出Hesse矩阵，也难以判定其准确性。 假设、定理1.18，并且具有二次连续偏导数。 可以利用存在、的、近邻、上节和本节的定理，简单说明以下两个论断。 (I )关于正定二次函数，ii )如果多变量函数的极小点处的Hesse矩阵是正规的，则在该极小点附近，其等价面几乎作为同心椭圆面族出现。 I )首先求二次函数的定点。 因为是令、正定矩阵，所以解唯一的驻扎地是、(1.41 )、所以根据推论1.13可以断定是唯一的极小点。 ii )为多变量函数的极小点且足够，为一个等值面，接近极小点，即足够小。 点，地方用Taylor式展开，得到上式右端的第二项，因为是极小点，所以消失，进一步省略，第四项是二次曲面，(1.42 )、等值面，的近似曲面。 根据假设，正定，因此中心椭圆体面是方程(1.42 )。 这是我们想说明的事情。 1 .下降迭代算法、1.8和相关联的概念、集合上的迭