四*、非线性规划 第7章 无约束问题 第8章 约束极值问题 清华大学出版社.

Presentation on theme: "四*、非线性规划 第7章 无约束问题 第8章 约束极值问题 清华大学出版社."— Presentation transcript:

1 四*、非线性规划 第7章 无约束问题 第8章 约束极值问题 清华大学出版社

2 引 言 在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和(或)约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。 解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。 一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都有自己特定的适用范围。 清华大学出版社

3 第1节 基本概念 第2节 一维搜索 第3节 无约束极值问题的解法
第7章 无约束问题 第1节 基本概念 第2节 一维搜索 第3节 无约束极值问题的解法 清华大学出版社

4 第1节 基本概念 1.1 引言 1. 问题的提出 例1 某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均是0.5小时，第二种产品是(2+0.25x2)小时，其中x2是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为800小时，试决定使其营业额最大的营业计划。 设该公司计划经营第一种产品x1件，第二种产品x2件。根据题意，其营业额为 由于服务时间的限制，该计划必须满足 此外，这个问题还应满足 ，得到本问题数学模型为： 清华大学出版社

5 是第i个属性的重要性与第j个属性的重要性之比。
第1节 基本概念 例2 为了进行多属性问题(假设有n个属性)的综合评价，需要确定每个属 性的相对重要性，即求它们的权重。为此将各属性的重要性进行两两比 较，从而得出如下判断矩阵 其中元素 是第i个属性的重要性与第j个属性的重要性之比。 现需从判断矩阵求出各属性的权重 为了使 在最小二乘意义上能最好反映判断矩阵的估计，由 ，可得 清华大学出版社

6 第1节 基本概念 2．非线性规划问题的数学模型 非线性规划的数学模型常表示成以下形式 其中自变量 是n维欧氏空间 中的向量(点)；
第1节 基本概念 2．非线性规划问题的数学模型 非线性规划的数学模型常表示成以下形式 其中自变量 是n维欧氏空间 中的向量(点)； 为目标函数， 和 为约束条件。 清华大学出版社

7 第1节 基本概念 由于 当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标 函数极小化，这无损于一般性。
第1节 基本概念 由于 当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标 函数极小化，这无损于一般性。 若某约束条件是“≤”不等式时，仅需用“-1”乘该约束的两端，即可 将这个约束变为“≥”的形式。 由于等式约束 等价于下述两个不等式约束： 因而，也可将非线性规划的数学模型写成以下形式 清华大学出版社

8 第1节 基本概念 3．非线性规划问题的图示 图示法可以给人以直观概念，当只有两个自变量时，非线性规划问题也可像线性规划那样用图示法来表示(如图6-1所示)。 考虑非线性规划问题 若令其目标函数 其中c为某一常数，则(6-8)式代表目标函数值等于c的点的集合，它一般为一条曲线或一张曲面，通常称其为等值线或等值面。对于这个例子来说，若令目标函数(6-6)式分别等于2和4，就得到相应的两条圆形等值线(图6-1)。由图可见，等值线f(X)=2和约束条件直线AB 相切，切点D即为此问题的最优解：x1*=x2*=3，其目标函数值f(X*)=2。 清华大学出版社

9 第1节 基本概念 在这个例子中，约束条件(6-7)式对最优解是有影响的。现若以 代替约束条件(6-7)式，则非线性规划问题(6-6)
第1节 基本概念 在这个例子中，约束条件(6-7)式对最优解是有影响的。现若以 代替约束条件(6-7)式，则非线性规划问题(6-6) 式、(6-9)式的最优解是x1=x2=2，即图6-1中的 C点(这时f(X)=0)。由于最优点位于可行域的 内部，故对这个问题的最优解来说，约束(6-9) 式事实上是不起作用的。在求这个问题的最 优解时，可不考虑约束条件(6-9)式，就相当 于没有这个约束一样。 由第一章知道，如果线性规划问题的最优解 存在，其最优解只能在其可行域的边界上达 到(特别是在可行域的顶点上达到)；而非线性 规划问题的最优解(如果最优解存在)则可能在 其可行域中的任意一点达到。 图6-1 清华大学出版社

10 第1节 基本概念 1.2 极值问题 1．局部极值和全局极值
第1节 基本概念 1.2 极值问题 1．局部极值和全局极值 由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是在整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但却并不一定是整个可行域上的全局最优解。 清华大学出版社

11 第1节 基本概念 设f(X)为定义在n维欧式空间En的某一区域R上的n元函数，其中 。对于 ，如果存在某个 ，使所有与 的距离小于 的 (即
第1节 基本概念 设f(X)为定义在n维欧式空间En的某一区域R上的n元函数，其中 。对于 ，如果存在某个 ，使所有与 的距离小于 的 (即 且 )均满足不等式 ，则称 为 在R上的局部极小点(或相对极小点)， 为局部极小值。若对于所有 且与 的距离小于 的 ， ，则称 为 在R上的严格局格极小点， 为严格局部极小值。 若点 ，而对于所有 都有 ，则称 为 在R上的全局极小点， 为全局极小值。若对于所有 且 ，都有 ，则称 为 在R上的严格全局极小点， 为严格全局极小值。 清华大学出版社

12 第1节 基本概念 2．极值点存在的条件 定理1 (一阶必要条件) 设R是n维欧式空间En上的某一开集，f(X)在R上有一阶连续偏导数，且在点
第1节 基本概念 2．极值点存在的条件 定理1 (一阶必要条件) 设R是n维欧式空间En上的某一开集，f(X)在R上有一阶连续偏导数，且在点 取得局部极值，则必有 或 上式中 为函数f(X)在点X*处的梯度。 清华大学出版社

13 第1节 基本概念 2．极值点存在的条件 定理2 (二阶必要条件) 设R是n维欧式空间En上的某一开集，f(X)在R上有二阶连续偏导数，且在点
第1节 基本概念 2．极值点存在的条件 定理2 (二阶必要条件) 设R是n维欧式空间En上的某一开集，f(X)在R上有二阶连续偏导数，且在点 取得局部极小值，则X*为驻点，即梯度 且二阶Hesse阵 半正定 清华大学出版社

14 第1节 基本概念 定理3(二阶充分条件) 设R是n维欧式空间En上的某一开集，f(X)在R上有二阶连续偏导数， 有 ，若 ，且对任何非零向量
第1节 基本概念 定理3(二阶充分条件) 设R是n维欧式空间En上的某一开集，f(X)在R上有二阶连续偏导数， ，若 ，且对任何非零向量 有 则X*为f(X)的严格局部极小点。 此处H(X*)为f(X)在点X*处的海赛(Hesse)矩阵： 清华大学出版社

15 第2节 下降迭代算法 为了求某可微函数(假定无约束)的最优解，根据前面的叙述，可如下进行： 令该函数的梯度等于零，由此求得平稳点；
第2节 下降迭代算法 为了求某可微函数(假定无约束)的最优解，根据前面的叙述，可如下进行： 令该函数的梯度等于零，由此求得平稳点； 然后用充分条件进行判别，求出所要的解。 对某些较简单的函数，这样做有时是可行的； 但对一般n元函数f(X)来说，由条件f(X)=0得到的常是一个非线性方程组，解它相当困难。对于不可微函数，当然谈不上使用这样的方法。为此，常直接使用迭代法。 清华大学出版社

16 第2节 下降迭代算法 迭代法的基本思想：为了求函数f(X)的最优解，首先给定一个初始估计 ，然后按某种规划(即算法)找出比 更好的解
第2节 下降迭代算法 迭代法的基本思想：为了求函数f(X)的最优解，首先给定一个初始估计 ，然后按某种规划(即算法)找出比 更好的解 对极小化问题， 对极大化问题， 再按此种规则找出比 更好的解 ，…。如此即可得到一个解的序列 。若这个解序列有极限 ，即 则称它收敛于X*。 若算法是有效的，则它产生的解的序列将收敛于该问题的最优解。但 由于计算机只能进行有限次迭代，一般很难得到准确解，而只能得到 近似解。当达到满足的精度要求后，即可停止迭代。 清华大学出版社

17 第2节 下降迭代算法 现假定已迭代到点 (见图6-5)，若从 出发沿任何方向移动都不能使目标函数值下降，则 是一局部极小点，迭代停止。若从
第2节 下降迭代算法 现假定已迭代到点 (见图6-5)，若从 出发沿任何方向移动都不能使目标函数值下降，则 是一局部极小点，迭代停止。若从 出发至少存在一个方向可使目标函数值有所下降，则可选定能使目标函数值下降的某方向 ，沿这个方向迈进适当的一步，得到下一个迭代点 ，并使 。这相当于在射线 上选定新点 其中， 称为搜索方向； 称为步长或步长因子。 图6-5 清华大学出版社

18 第2节 下降迭代算法 下降迭代算法的步骤： (1) 选定某一初始点 ，并令 (2) 确定搜索方向 (3) 从 出发，沿方向 求步长
第2节 下降迭代算法 下降迭代算法的步骤： (1) 选定某一初始点 ，并令 (2) 确定搜索方向 (3) 从 出发，沿方向 求步长 ，以产生下一个迭代点 (4) 检查得到的新点 是否为极小点或近似极小点。 若是，则停止迭代。 否则，令 ，转回(2)继续进行迭代。 在以上步骤中，选取搜索方向是最关键的一步，各种算法的区分，主要在于确定搜索方向的方法不同。 清华大学出版社

19 第2节 下降迭代算法 确定步长 的的方法。 (1) 令它等于某一常数(例如令 )，这样做不能保证目标函数值下降。
第2节 下降迭代算法 确定步长 的的方法。 (1) 令它等于某一常数(例如令 )，这样做不能保证目标函数值下降。 (2) 第二种称为可接受点算法，只要能使目标函数值下降，可任意选取步长 (3)第三种方法是基于沿搜索方向使目标函数值下降最多，即沿射线 求目标函数f(X)的极小： 由于这项工作是求以λ为变量的一元函数 的极小点 ，故常称这一过程为一维搜索或线搜索，确定的步长为最佳步长。 清华大学出版社

20 第2节 下降迭代算法 fminunc函数 MATLAB求解无约束优化问题的主要函数 x = fminunc(fun, x0)
第2节 下降迭代算法 fminunc函数 MATLAB求解无约束优化问题的主要函数 x = fminunc(fun, x0) [x, fval] = fminunc(fun, x0) [x, fval, exitFlag, output, grad, hessian] = fminunc(fun, x0, options) fun：目标函数；x0：初始解；options：参数设置 x：最优解；fval：最优点函数值 exitFlag：函数结束信息 output：函数基本信息，包括迭代次数、目标最大计算次数、使用的算法、计算规模等 grad：最优点的导数；hessian：最优点二阶导数

21 第2节 下降迭代算法 例：求Banana function 的极小值点 极小值点为(1,1)，对应的函数值为0

22 第2节 下降迭代算法 function f=BanaFun(x) % 不含导数解析式 f=100*(x(2)-x(1)^2)^2+(1-x(1)^2; function [f,g]=BanaFunWithGrad(x) % 含导数解析式 g=[100*(4*x(1)^3-4*x(1)*x(2))+2*x(1)-2 100*(2*x(2)-2*x(1)^2)]

23 第2节 下降迭代算法 x=[-1.9 2]; [x, x) x = fval= [x, x) x = fval=5.1002

24 第3节 无约束极值问题的解法 本节研究无约束极值问题: min f(X) X∈En (6-40)
第3节 无约束极值问题的解法 本节研究无约束极值问题: min f(X) X∈En (6-40) 前面曾指出，在求解上述问题时常使用迭代法。迭代法可大体分为两类。 一类要用到函数的一阶导数和(或)二阶导数，由于用到了函数的解析性质，故称为解析法； 另一类在迭代过程中仅用到函数值，而不要求函数的解析性质，这类方法称为直接法。一般说来，直接法的收敛速度较慢，只是在变量较少时才适用。但是直接法的迭代步骤简单，特别是当目标函数的解析表达式十分复杂，甚至写不出具体表达式时，它们的导数很难求得，或者根本不存在，这时解析法就无能为力了。 本节仅介绍几种常用的基本方法，其中前三种属解析法，后面一种属直接法。 清华大学出版社

25 3.1 梯度法(最速下降法) 1. 梯度法的基本原理 假定无约束极值问题(6-40)式中的目标函数f(X)有一阶连续偏导数，具有极小点X*。以 表示极小点的第k次近似，为了求其第k+1次近似点 ，我们在 点沿方向 做射线 现将 f(X) 在 点处展成泰勒级数 其中 对于充分小的λ，只要 即可保证 。这时若取 就能使目标函数值得到改善。 清华大学出版社

26 3.1 梯度法(最速下降法) 现考查不同的方向 。假定 的模一定(且不为零)，并设 (否则， 是平稳点)，使式(6-41)成立的
有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使 取最小值的 。由线性代数知道 式中θ为向量 与 的夹角。当 与 反向时， 这时(6-41)式成立，而且其左端取最小值。我们称方向 为负梯度方向，它是使函数值下降最快的方向(在 的某一小范围内)。 清华大学出版社

27 3.1 梯度法(最速下降法) 为了得到下一个近似极小点，在选定了搜索方向之后，还要确定步长λ 。当采用可接受点算法时，就是取某一λ进行试算，看是否满足不等式 若上述不等式成立，就可以迭代下去。否则，缩小λ使满足不等式(6-43)式。由于采用负梯度方向，满足(6-43)式的λ总是存在的。 另一种方法是通过在负梯度方向的一维搜索，来确定使f(X)最小的 λk，这种梯度法就是所谓最速下降法。 清华大学出版社

28 3.1 梯度法(最速下降法) 2. 计算步骤 (1) 给定初始近似点 及精度 ，若 ，则 即为近似极小点。 ，求步长 ，并计算 (2) 若
求步长可用一维搜索法、微分法或试算法。 若求最佳步长，则应使用前两种方法。 (3) 一般地，设已迭代到点 ，若 ，则 即为所求的近似解；若 ，则求步长 ，并确定下一个近似点 如此继续，直至达到要求的精度为止。 清华大学出版社

29 3.1 梯度法(最速下降法) 若 具有二阶连续偏导数，在 作 的泰勒展开： 对λ求导并令其等于零，则得近似最佳步长
可见近似最佳步长不只与梯度有关，而且也与海赛矩阵H有关。 确定步长 也可不用公式(6-45)，而采用任一种一维搜索法。 有时，将搜索方向 的模规格化为1，在这种情况下 同时，式(6-45)变为 清华大学出版社

30 3.2 变尺度法 变尺度法是近30多年来发展起来的，它是求解无约束极值问题的一种有效方法。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性，因而使变尺度法获得了很高的声誉，至今仍被公认为求解无约束极值问题最有效的算法之一。 清华大学出版社

31 3.2 变尺度法 变尺度法的计算步骤： (1) 给定初始点X(0)、初始矩阵H(0) ，计算g(0)，令k=0
(2) 令p(k)=-H(k)g(k) (3) 由一维搜索(如0.618法)确定步长ak (4) 令x(k+1)=x(k)+akp(k) (5) 若||g(k+1)||<误差限e， 则x*=x(k+1)即为最优解，算法终止； 否则令s(k)=x(k+1)-x(k),y(k)=g(k+1)-g(k) (6) 由修正公式得到H(k+1)，令k=k+1转(2) 清华大学出版社

32 3.2 变尺度法 DFP修正公式： BFGS修正公式：
BFGS在理论上已证明具有全局收敛性，而DFP法尚未证明具有此性质。总体上来说，BGFS优于DFP 清华大学出版社

33 3.2 变尺度法 例：利用变尺度法求Banana函数的极小值点
解：使用fminunc函数，将HessUpdate参数设置为dfp或bgfs即可 options=optimset(‘HessUpdate’, ‘dfp’) [x, fval] = x, options) x = fval = e-09 options=optimset(‘HessUpdate’, ‘bgfs’) x = fval = e-08 清华大学出版社

34 第4节 直接算法 直接算法可以归为经验算法，不如迭代法有效 基本原则简明，有一定的技术实用性
单纯形法利用变换单纯形来求出极小点，是最常用的一种直接算法。 在单纯形法基础上，对非线性问题，1964年提出了改进的可变多面体算法 fminsearch函数利用此算法求解无约束优化问题 [x, fval] = fminsearch(fun, x0, options) [x, fval, exitflag, output] = fminsearch(…)

35 第4节 直接算法 例：利用fminsearch求Banana函数的极小值点 x0=[-1.9 2];
[x, fval] = x0) x = fval = e-10