第2章 优化方法的数学基础

《第2章 优化方法的数学基础》由会员分享，可在线阅读，更多相关《第2章 优化方法的数学基础（66页珍藏版）》请在金锄头文库上搜索。

1、第二章 优化方法的数学基础,2-1 方向导数与梯度 2-2 目标函数的泰勒展开 2-3 无约束优化问题的极值条件 2-4 凸集、凸函数与凸规划 2-5 有约束优化问题的极值条件,2-1 方向导数与梯度,一、方向导数,二元函数在点x0处沿某一方向s的方向导数,图2-1,方向导数与偏导数之间的数量关系是,方向导数是偏导数概念的推广。偏导数是方向导数的特例。,三元函数 在 点处沿s方向的方向导数,n元函数在点x0处沿s方向的方向导数,二、 梯度,二元函数的梯度,为函数F(x1，x2)在x0点处的梯度。,令,梯度的模：,设,梯度方向和s方向重合时，方向导数值最大。,梯度方向是函数值变化最快的方向，而梯

2、度的模就是函数变化率的最大值 。,图2-2 梯度方向与等值线的关系,设：,则有,为单位向量。,多元函数的梯度,函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。,由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。,梯度 模：,梯度两个重要性质： 性质一 函数在某点的梯度不为零，则必与过该点的等值面垂直； 性质二 梯度方向是函数具有最大变化率的方向。,图2-2 梯度方向与等值面的关系,例题 2-1,求函数 在点3,2T 的 梯度。,在点x(1)=3,2T处的梯度为：,解：,例2-2：试求目标函数 在点 处的最速下降方向，并求沿这个

3、方向移动一个单位长度后新点的目标函数值。,则函数在 处的最速下降方向是,解： 由于,新点是,这个方向上的单位向量是：,几个常用的梯度公式：,外，最简单最重要的一类就是二次函数。,在n元函数中，除了线形函数：,2-2 目标函数的泰勒展开,或 f(X)=aX+c,其中 均为常数。,若 ，X0 ，均有 0 ，则称矩阵Q是正定的。,在代数学中将特殊的二次函数 称为二次型。 对于二次函数，我们更关心的是Q为正定矩阵的情形。,若 ，且X0，均有 0，则称Q是负定的。,定义：设Q为nn对称矩阵,其中 Q= b= Q为对称矩阵,其向量矩阵表示形式是：,二次函数的一般形式为：,解：对称矩阵Q的三个主子式依次为：

4、,例：判定矩阵Q= 是否正定,一个nn对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。,一个nn对称矩阵Q是负定矩阵的充要条件是矩阵Q的各阶主子式的值负、正相间。,因此知矩阵Q是正定的。,定理： 若二次函数 中Q正定，则它的等值面是同心椭球面族，且中心为,证明：作变换 ，代入二次函数式中：,根据解析几何知识，Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。由于上式中的 是常数，所以 的等值面也是以 =0为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。,前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次

5、目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。,特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。,另外，这族椭球面的中心 恰是二次目标函数的唯一极小点。,一、 二元函数的泰勒展开,二元函数：,二元函数 在 点处的泰勒展开式为,二元函数：,二元函数：在点X0处,称作海赛矩阵。,由于函数的二次连续性，有,对二次函数：,为二次函数的海赛（Hessian）矩阵，常量矩阵。,二

6、次函数的梯度为：,二、多元函数泰勒展开,为函数 在 点的海赛矩阵 （Hessia）,解：因为,则,又因为：,故Hesse阵为：,例题:,用泰勒展开将函数,简化的线性函数,简化的二次函数,2-3 无约束优化问题的极值条件,图2-3 一元函数的极值点,图2-4 二元函数的极值点,即,图2-5 驻点不是极值点而是鞍点,无约束优化问题的极值必要条件,即F(x)在 处取得极值，其必要条件是:,即在极值点处函数的梯度为n维零向量。,有了必要条件，那么充分条件是什么呢？,根据二元函数的泰勒展开式和极值的必要条件,极值的充分条件，即要求,即,此条件反映了 在 点处的海赛矩阵 的各阶主子式均大于零。,二元函数在

7、某点处取得极值的 充分条件是在该点处的海赛矩阵为正定。必要条件是梯度,例题：求函数 的极值。,解：,根据极值的必要条件求驻点。,得驻点为,再根据极值的充分条件，判断此驻点是否为极值点。,由于,则， 的一阶主子式为,二阶主子式,故 为正定矩阵,为极小点，极值为,对于多元函数 ，若在 点处取得极值，则 极值的必要条件为,极值的充分条件为海赛矩阵,正定,当极值点X*能使f（X*）在整个可行域中为最小值时，即在整个可行域中对任一X都有f（X）f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。最

8、优化设计的目标是全域最优点。为了判断某一极值点是否为全域最优点，研究一下函数的凸性很有必要。 函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。,为了研究函数的凸性，现引入凸集的概念：,2-4 凸集、凸函数与凸规划,一、凸集,设D为n维欧氏空间中的一个集合，若其中任意两点X(1)、X(2)之间的联接直线都属于D，则称这种集合D为n维欧氏空间的一个凸集。图2-3（a）是二维空间的一个凸集，而图2-3（b）不是凸集。,图2-3 二维空间的凸集与非凸集,X（1）、X（2）两点之间的联接直线，可用数学式表达为:,式中 为由0到1（0 1）间的任

9、意实数。,凸集的性质：,1）若D为凸集， 是一个实数，则集合 D仍是凸集；,2）若D和F均为凸集，则其和（或并）仍是凸集；,3）任何一组凸集的积（或交）仍是凸集。,二、凸函数,具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：,设 f（X）为定义在 n维欧氏空间中的一个凸集D上的函数，如果对任何实数a（0a1）以及对D中任意两点X(1)、X(2)恒有:,则f（X）为D上的凸函数，若不满足上式，则为凹函数。,凸函数的集合意义如图2-4所示：,图2-4 一元凸函数的几何意义,在凸函数曲线上取任意两点（对应于X轴上的坐标X(1)、X（2）联成一直

10、线线段，则该线段上任一点（对应于X轴上的X(k)点）的纵坐标Y值必大于或等于该点（X(k)）处的原函数值f(X(k)。,凸函数的一些性质：,1）若 f（X）为定义在凸集D上的一个凸函数，且 a是一个正数（a 0），则 af（X）也必是定义在凸集D上的凸函数；,3）若f1(X），f2(X )为定义在凸集D上的两个凸函数，和为两个任意正数，则函数 afl（X）f2(X)仍为D上的凸函数。,2）定义在凸集D上的两个凸函数f1(X），f2(X)，其和 f（X）=f1（X）十f2（X）亦必为该凸集上的一个凸函数；,1）若f（X）为定义在凸集D上且具有连续一阶导数的函数，则f（X）为凸函数的充分必要条件为

11、： 对任意两点X（1），X（2），不等式,三、凸性条件,恒成立,2）设f（X）为定义在凸集R上具有连续二阶导数的函数，则f（X）在R上为凸函数的充分必要条件是海赛矩阵G(X)在R上处处半正定。,四、凸规划,对于约束优化问题,式中若F（X）、 均为凸函数，则称此问题为凸规划。,凸规划的一些性质：,3）凸规划问题中的任何局部最优解都是全局最优解；,2）可行域 为凸集；,1）若给定一点x0，则集合 为凸集，即目标函数等值线族呈现大圈套小圈（大球套小球、大超球套小超球）的形式；,不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻

12、烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。,注意：,在满足约束方程 ：,求一组设计变量,2-5 有约束优化问题的极值条件,的条件下，使目标函数值最小，即使,这样求得的最优点 ，称为约束最优点。,一. 优化设计最优解,无约束优化设计问题最优解：,约束优化设计问题最优解：,不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点 x*=x1*,x2*,x n* 和最优值 f(x*)构成无约束问题最优解。,满足约束条件，使目标函数达到最小值的一组设计

13、变量， 即最优点 x*=x1*,x2*,x n* 和最优值 f(x*)构成约束问题最优解。,二. 有约束问题最优点的几种情况,有适时约束 目标函数是凸函数,可行域是凸集，则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点。,无适时约束 目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的最优点。,x (k) 为最优点x*的条件： 必要条件： 充分条件： Hesse矩阵 H(x(k) 是正定矩阵,X*,f (x), x*,有适时约束 目标函数是非凸函数（图 a），或可行域是非凸集（图 b）：,则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是

14、全局最优点。,二. 有约束问题最优点的几种情况,p,Q,Q,p,F（x）的下降方向,对于约束最优化问题，除了需要解决“判断约束极值点存在条件”这一问题外，还应解决“判断所找到的极值点是全域最优点还是局部极值点”这一更复杂的问题。对于后一问题，虽然多年来有许多人进行大量的研究，但至今还没有一个统一而有效的方法。,对于求目标函数的极小化问题，当沿某个可行方向向量s作出微小移动时，其目标函数的变化为,对于充分小的 ， 若存在s使,成立，则s为目标函数下降可行方向。,成立，则 为局部极小点。,三. K-T ( Kuhn-Tucker 库恩-塔克) 条件 有适时约束时获得最优解的条件,1. 有一个适时约

15、束时：,与x(k)点目标函数的负梯度方向成锐角，即沿 S 方向目标函数值下降； 与x(k)点约束函数的梯度方向成钝角，即保证 S方向上各点在可行域内。 此时，获得最优解 x(k) 为最优点 x*， f(x(k)为最优值 f(x*)。,从数学上定义，当从 x(k)点出发不存在一个 S 方向能同时满足： ;，即 ， 则获得最优解：x(k)为最优点 x*，f(x(k)为最优值 f(x*)。,从几何上看，当从 x (k)点出发不存在一个 S 方向能同时满足：,相反，当从 x(k)点出发，存在一个 S 方向能同时满足： 和 时，则 x(k) 不是最优点。,从几何上看，当从 x(k)点出发存在一个 S 方向能同时满足： 与x(k)点目标函数的负梯度方向成锐角，即沿 S 方向目标函数值下降； 与x(k)点约束函数的梯度方向成钝角，即保证 S方向上各点在可行域内。 此时，x(k)不是最优点 x*。,三. K-T ( Kuhn-Tucker 库恩-塔克) 条件 有适时约束时获得最优解的条件,1. 有一个适时约束时：,2. 有二个适时约束时：,x(k)成为约束最优点 x* 的必要条件为