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

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

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

2 第1节 最优性条件 第2节 二次规划 第3节 可行方向法 第4节 制约函数法
第8章 约束极值问题 第1节 最优性条件 第2节 二次规划 第3节 可行方向法 第4节 制约函数法 清华大学出版社

3 第1节 最优性条件 大多数极值问题其变量的取值都会受到一定限制，这种限制由约束条件来体现。带有约束条件的极值问题称为约束极值问题。非线性规划的一般形式为 (7-1) 或 (7-2) 问题(7-2)也常写成 (7-3) 清华大学出版社

4 第1节 最优性条件 1.1 起作用约束和可行下降方向的概念 现考虑上述一般非线性规划，假定f(X)、hi(X)和 具有一阶连续偏导数。 设
1.1 起作用约束和可行下降方向的概念 现考虑上述一般非线性规划，假定f(X)、hi(X)和 具有一阶连续偏导数。 设 是非线性规划的一个可行解。现考虑某一不等式约束条件 满足它有两种可能：其一为 ，这时，点 不是处于由这一约束条件形成的可行域边界上，因而这一约束对 点的微小摄动不起限制作用，从而称这个约束条件是 点的不起作用约束(或无效约束)；其二是 ，这时 点处于该约束条件形成的可行域边界上，它对 的摄动起到了某种限制作用，故称这个约束是 点的起作用约束(有效约束)。 显而易见，等式约束对所有可行点来说都是起作用约束。 清华大学出版社

5 第1节 最优性条件 假定X(0)是非线性规划(7-3)式的一个可行点，现考虑此点的某一方向D，若存在实数 ，使对任意 均有
就称方向D是X(0)点的一个可行方向。 清华大学出版社

6 第1节 最优性条件 若D是可行点X(0)处的任一可行方向，则对该点的所有起作用约束 （7-5） 均有
其中J为这个点所有起作用约束下标的集合。 另一方面，由泰勒公式 对所有起作用约束，当λ>0足够小时，只要 （7-6） 就有 图7-1 此外，对X(0)点的不起作用约束，由约束函数的连续性，当λ>0足够小时亦有上式成立。从而，只要方向D满足(7-6)式，即可保证它是X(0)点的可行方向。 清华大学出版社

7 第1节 最优性条件 考虑非线性规划的某一可行点X(0) ，对该点的任一方向D来说，若存在实数 ，使对任意 均有
就称方向D为X(0)点的一个下降方向。 将目标函数f(X)在点X(0)处作一阶泰勒展开，可知满足条件 的方向D必为X(0)点的下降方向。 如果方向D既是X(0)点的可行方向，又是这个点的下降方向，就称它是该点的可行下降方向。假如X(0)点不是极小点，继续寻优时的搜索方向就应从该点的可行下降方向中去找。显然，若某点存在可行下降方向，它就不会是极小点。另一方面，若某点为极小点，则在该点不存在可行下降方向。 清华大学出版社

8 第1节 最优性条件 定理1 设X*是非线性规划(7-3)式的一个局部极小点，目标函数 f(X)在X*处可微，而且 在X*处可微，当
则在X*不存在可行下降方向，从而不存在向量D同时满足： 清华大学出版社

9 第1节 最优性条件 1.2 库恩－塔克条件 假定X*是非线性规划(7-3)式的极小点，该点可能位于可行域的内部，也
1.2 库恩－塔克条件 假定X*是非线性规划(7-3)式的极小点，该点可能位于可行域的内部，也 可能处于可行域的边界上。若为前者，这事实上是个无约束问题，X*必 满足条件 若为后者，情况就复杂得多了。 下面讨论当极小点位于可行域边界的情形。 清华大学出版社

10 第1节 最优性条件 不失一般性，设X*位于第一个约束条件形成的可行域边界上，即第一个约束条件是X*点的起作用约束( )。若X*是极小点，则
必与 在一条直线上且方向相反。 否则，在该点就一定存在可行下降方向(图7-2中的X*点为极小点；X点不满足上述要求，它不是极小点，角度β表示了该点可行下降方向的范围)。 上面的论述说明，在上述条件下，存在实数 ，使 清华大学出版社

11 第1节 最优性条件 若X*点有两个起作用约束，例如说有 在这种情况下， 必处于 和 的夹角之内。
如若不然，在X*点必有可行下降方向，它就不会是极小点(图7-3)。由此可见，如果X*是极小点，而且X*点的起作用约束条件的梯度 和 线性无关，则可将 表示成 和 的非负线性组合。也就是说，在这种情况下存在实数 和 ，使 清华大学出版社

12 第1节 最优性条件 图7-3 图7-2 如上类推，可以得到 清华大学出版社

13 第1节 最优性条件 为了把不起作用约束也包括进式(7-9)中，增加条件 当 时， 可不为零；当 时，必有
如此即可得到著名的库恩－塔克(Kuhn－Tucker,简写为K-T)条件。 库恩－塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件。只要是最优点(而且该点起作用约束的梯度线性无关。满足这种要求的点称为正则点)，就必须满足这个条件。但一般说它并不是充分条件，因而满足这个条件的点不一定就是最优点(对于凸规划，它既是最优点存在的必要条件，同时也是充分条件)。 清华大学出版社

14 第1节 最优性条件 库恩-塔克条件： 设X*是非线性规划(7-3)式的极小点，而且在X*点的各起作用约束的梯度线性无关，则存在向量
，使下述条件成立： (7-10) 条件(7-10)式常简称为K-T条件。满足这个条件的点(它当然也满足非线性规划的所有约束条件)称为库恩-塔克点(或K-T点)。 清华大学出版社

15 第1节 最优性条件 现考虑带有等约束非线性规划(7-1)式的库恩－塔克条件，我们用 代替约束条件
即可使用条件(7-10)，得到库恩-塔克条件如下： 设X*是非线性规划(7-1)式的极小点，而且X*点的所有起作用约束的梯度 和 线性无关，则存在向量 (7-11) 使下述条件成立： (7-10)式和(7-11)式中的 以及 称为广义拉格朗日乘子。 清华大学出版社

16 第1节 最优性条件 例1 用库恩－塔克条件解非线性规划 解： 先将该非线性规划问题写成以下形式 写出其目标函数和约束函数的梯度：
例1 用库恩－塔克条件解非线性规划 解： 先将该非线性规划问题写成以下形式 写出其目标函数和约束函数的梯度： 对第一个和第二个约束条件分别引入广义拉格朗日乘子，设K-T点为X*，则可以得到该问题的K-T条件。 清华大学出版社

17 第1节 最优性条件 该问题的K-T条件为： 为解上述方程组，考虑以下几种情形： (1) 令 ，无解。 ，解之，得 (2) 令
(3) 令 ，解之，得 ，不是K-T点。 ，解之，得 ，此为K-T点，其目标函数值 (4) 令 由于该非线性规划问题为凸规划，故 就是其全局极小点。该点是可行域的内点，它也可直接由梯度等于零的条件求出。 清华大学出版社

18 第2节 二次规划 若非线性规划的目标函数为自变量X的二次函数，约束条件全是线 性的，称这种规划为二次规划。二次规划的数学模型为：
（7-12） （7-13） （7-14） (7-12)式右端的第二项为二次型。如果该二次型正定(或半正定)，则目标函数为严格凸函数(或凸函数)；此外，二次规划的可行域为凸集，因而，上述规划属于凸规划。第6章已指出：凸规划的局部极值即为全局极值。对于这种问题，库恩-塔克条件不但是极值点存在的必要条件，而且也是充分条件。 清华大学出版社

19 第2节 二次规划 将库恩－塔克条件(7-10)式中的第一个条件应用于二次规划(7-12)式至(7-14)式，并用y代替库恩-塔克条件中的γ，即可得到 （7-15） 在(7-13)式中引入松弛变量 ，(7-13)式即变为(假定 ) （7-16） 再将库恩－塔克条件中的第二个条件应用于上述二次规划，并考虑到(7-16)式，这就得到 （7-17） 此外还有 （7-18） 清华大学出版社

20 第2节 二次规划 联立求解(7-15)式和(7-16)式，如果得到的解也满足(7-17)式和(7-18)式，则这样的解就是原二次规划问题的解。但是，在(7-15)式中，cj可能为正，也可能为负。为了便于求解，先引入人工变量zj(zj≥0) ，其前面的符号可取正或负，以便得出可行解)，这样(7-15)式就变成了 （7-19） 其中 为符号函数，当 时， ；当 时， 。这样一来，可立刻得到初始基本可行解如下： 清华大学出版社

21 第2节 二次规划 但是，只有当zj=0时才能得到原来问题的解，故必须对上述问题进行修正，从而得到如下线性规划问题： （7-20）
该线性规划尚应满足(7-17)式。这相当于说，不能使xj和yj(对每一个j )同时为基变量。 清华大学出版社

22 第2节 二次规划 解线性规划(7-20)式，若得到最优解： 则 就是原二次规划问题的最优解。 清华大学出版社

23 第2节 二次规划 例2 求解二次规划 解：将上述二次规划改写为 可知目标函数为严格凸函数。此外 清华大学出版社

24 第2节 二次规划 由于c1和c2小于零，故引入的人工变量z1和z2前面取负号，这样就得到线性规划问题如下： 或 此外尚应满足 清华大学出版社

25 第2节 二次规划 用线性规划的单纯形法解之(注意，在转换过程中应满足条件xjyj=0)，得该线性规划问题的解如下：
由此得到原二次规划问题的解为 可以验证， 以及 满足库恩－塔克条件。 清华大学出版社

26 第3节 可行方向法 现考虑非线性规划(7-3)式，设X(k)是它的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，根据以前所说，应在X(k)点的可行下降方向中选取某一方向D(k) ，并确定步长λk，使 （7-21） 若满足精度要求，迭代停止，X(k+1)就是所要的点。否则，从X(k+1)出发继续进行迭代，直到满足要求为止。 上述方法称为可行方向法，其特点是： 迭代过程中采用的搜索方向为可行方向，所产生的迭代点列｛X(k)｝始终在可行域内，目标函数值单调下降。 清华大学出版社

27 第3节 可行方向法 设X(k)点的起作用约束集非空，为求X(k)点的可行下降方向，可由下述不等式组确定向量D： （7-22）
第3节 可行方向法 设X(k)点的起作用约束集非空，为求X(k)点的可行下降方向，可由下述不等式组确定向量D： （7-22） 这等价于由下面的不等式组求向量D和实数η： （7-23） 若使 和 (对所有 )的最大值极小化， 即可将上述选取搜索方向的工作，转换为求解下述线性规划问题： 式中 （7-24） 为向量D的分量。 清华大学出版社

28 第3节 可行方向法 在(7-24)中加入最后一个限制条件，为的是使该线性规划有有限最优解；由于我们的目的在于寻找搜索方向D，只需知道D的各分量的相对大小即可。 将线性规划(7-24)式的最优解记为 ，如果求出的 ， 说明在 点不存在可行下降方向，在 (此处 ） 线性无关的条件下， 为一K-T点。若解出的 ， 则得到可行下降方向 ，这就是我们所要的搜索方向。 清华大学出版社

29 第3节 可行方向法 可行方向法的迭代步骤如下： 确定允许误差 ，选初始近似点 ，并令 (2)确定起作用约束指标集 若 ，而且
第3节 可行方向法 可行方向法的迭代步骤如下： 确定允许误差 ，选初始近似点 ，并令 (2)确定起作用约束指标集 若 ，而且 ，停止迭代，得点 ②若 ，但 ，则取搜索方向 ，然后转向第(5)步。 ③若 ，转下一步。 清华大学出版社

30 第3节 可行方向法 (3) 求解线性规划 设它的最优解是 (4) 检验是否满足
第3节 可行方向法 (3) 求解线性规划 设它的最优解是 (4) 检验是否满足 若满足则停止迭代，得到点X(k) ；否则，以D(k)为搜索方向，并转下一步。 清华大学出版社

31 第3节 可行方向法 (5) 解下述一维极值问题 此处 (6) 令 转回第(2)步。 清华大学出版社

32 第3节 可行方向法 例3 用可行方向法解下述非线性规划问题 解：先将该非线性规划问题写成 取初始可行点 (空集)。由于 从而
第3节 可行方向法 例3 用可行方向法解下述非线性规划问题 解：先将该非线性规划问题写成 取初始可行点 从而 (空集)。由于 所以X(0)不是(近似)极小点。 清华大学出版社

33 第3节 可行方向法 现取搜索方向 从而 将其代入约束条件，并令 ，解得 令 对λ的导数等于零，解得λ=1/2。因λ大于 故取 清华大学出版社

34 第3节 可行方向法 构造在下述线性规划问题： 为便于用单纯形法求解，令 从而得到： 清华大学出版社

35 第3节 可行方向法 引入剩余变量y4，松弛变量y5,y6,y7以及人工变量y8，得线性规划问题如下： 其最优解为： ，搜索方向 从而得到，
第3节 可行方向法 引入剩余变量y4，松弛变量y5,y6,y7以及人工变量y8，得线性规划问题如下： 其最优解为： 从而得到， ，搜索方向 清华大学出版社

36 第3节 可行方向法 由此 。现暂用该步长，算出 令 ，得到 因 ，上面算出的 为可行点，说明选取 正确。 继续迭代下去，可得最优解为
第3节 可行方向法 由此 。现暂用该步长，算出 令 ，得到 因 ，上面算出的 为可行点，说明选取 正确。 继续迭代下去，可得最优解为 原来问题的最优解不变，其目标函数值 清华大学出版社

37 第4节 制约函数法 本节介绍求解非线性规划问题的制约函数法。使用这种方法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束极小化技术，简记为SUMT(sequential unconstrained minimization technique)。 常用的制约函数基本上有两类： 惩罚函数(或称罚函数(penalty function))：外点法 障碍函数(barrier function)：内点法。 清华大学出版社

38 4.1 外点法 考虑非线性规划问题(7-3)式，为求其最优解，构造一个函数 （7-25） 现把 视为t，显然 当 时， 当 时， 再构造函数
（7-26） 现求解无约束问题 （7-27） 清华大学出版社

39 4.1 外点法 若该问题有解，假定其解为 ，则由(7-25)式应有 这就是说点 。因而，
不仅是问题(7-27)式的极小解，它也是原问题(7-3)式的极小解。这样一来，就把有约束问题(7-3)式的求解化成了求解无约束问题(7-27)式。 清华大学出版社

40 4.1 外点法 用上述方法构造的函数Ψ(t)在t=0处不连续，更没有导数。为此，将该函数修改为 （7-28）
修改后的函数Ψ(t) ，当t=0时导数等于零，而且Ψ(t)和Ψ’(t)对任意t都连续。当 时仍有 当 时 清华大学出版社

41 4.1 外点法 取一个充分大的数M>0，将 改为 （7-29） 或等价地 （7-30） 从而可使 的解 为原问题的极小解或近似极小解。
若求得的 ，则它必定是原问题的极小解。事实上，对于所有 即当 时，有 清华大学出版社

42 4.1 外点法 函数P(X,M)称为惩罚函数，其中的第二项 称惩罚项。 ，就加大罚因子的值； 若对于某一个(惩)罚因子M，例如
的解 与约束集R的“距离”就越来越近。当 趋于无穷大时，点列 从可行域R外趋于原问题(7-3)的极小点 图7-4 清华大学出版社

43 4.1 外点法 外点法的经济解释： 将目标函数f(X)看成“价格”，约束条件看成某种“规定”，采购人可在规定范围内购置最便宜的东西。此外对违反规定制定了一种“罚款”政策，若符合规定，罚款为零；否则，要收罚款。此时，采购人付出的总代价应是价格和罚款的总和。采购者的目标是使总代价最小，这就是上述的无约束问题。当罚款规定得很苛刻时，违反规定支付的罚款很高，这就迫使采购人符合规定。在数学上表现为当罚因子Mk足够大时，上述无约束问题的最优解应满足约束条件，而成为约束问题的最优解。 清华大学出版社

44 4.1 外点法 外点法迭代步骤： (1) 取 (例如取 )，允许误差 ，并令 (2) 求无约束极值问题的最优解： 其中 (3) 若对某一个
有 则取 (例如， 或10)，令 并转向第2步。否则，停止迭代，得 清华大学出版社

45 4.1 外点法 例4 求解非线性规划 解：构造罚函数 对于不满足约束条件的点 令 ，有 得 的解为 清华大学出版社

46 4.1 外点法 ，可得出以下结果： 取 可知 从R的外面逐步逼近R的边界，当 时， 趋于原问题的极小解 图7-5 清华大学出版社

47 4.2 内点法 内点法的提出 如果要求每次迭代得到的近似解都在可行域内，以便观察目标函数值的变化情况；或者，如果f(X)在可行域外的性质比较复杂，甚至没有定义，这时就无法使用外点法。 内点法的特点 和外点法不同的是，内点法要求迭代过程始终在可行域内部进行。为此，我们把初始点取在可行域内部(既不在可行域外，也不在可行域边界上，这种可行点称为内点)，并在可行域的边界上设置一道“障碍”，使迭代点靠近可行域边界时，给出的新目标函数值会迅速增大，从而使迭代点始终留在可行域内。 清华大学出版社

48 4.2 内点法 内点法中障碍函数的构造 仿照外点法，通过函数叠加的办法来改造原目标函数，使得改造后的目标函数(称为障碍函数)具有这种性质：在可行域R的内部与其边界面较远的地方，障碍函数与原来的目标函数f(X)尽可能相近；而在接近R的边界面时可以有任意大的值。可以想见，满足这种要求的障碍函数，其极小解自然不会在R的边界上达到。这就是说，用障碍函数来代替(近似)原目标函数，并在可行域R内部使其极小化，虽然R是一个闭集，但因极小点不在闭集的边界上，因而实际上是具有无约束性质的极值问题，可借助于无约束最优化的方法进行计算。 清华大学出版社

49 4.2 内点法 根据上述分析，即可将非线性规划(7-3)式转化为一系列无约束极小化问题 （7-31） 其中 （7-32） 或 （7-33）
4.2 内点法 根据上述分析，即可将非线性规划(7-3)式转化为一系列无约束极小化问题 （7-31） 其中 （7-32） 或 （7-33） （7-34） (7-32)式和(7-33)式右端第二项称为障碍项。易见，在R的边界上(即至少有一个 )， 为正无穷大。 清华大学出版社

50 4.2 内点法 如果从可行域内部的某一点X(0)出发，按无约束极小化方法对(7-31)式进行迭代(在进行一维搜索时要适当控制步长，以免迭代点跑到R0之外)，则随着障碍因子r k的逐步减小，即 障碍项所起的作用也越来越小，因而，求出的 的解 也逐步逼近原问题(7-3)式的极小解 若原来问题的极小解在可行域的边界上，则随着r k的的减小，障碍作用逐步降低，所求出的障碍函数的极小解不断靠近边界，直至满足某一精度要求为止。 清华大学出版社

51 4.2 内点法 内点法的迭代步骤： (1) 取 (例如取 )，允许误差 ，并令 (2) 找出一可行内点
4.2 内点法 内点法的迭代步骤： (1) 取 (例如取 )，允许误差 ，并令 (2) 找出一可行内点 (3) 构造障碍函数，障碍项可采用倒数函数((7-32)式)，也可采用对数 函数(例如(7-33)式)。 (4) 以 为初始点，对障碍函数进行无约束极小化: （7-35） 其中 见(7-32)式或(7-33)式。 清华大学出版社

52 4.2 内点法 (5) 检验是否满足收敛准则 或 如满足上述准则，则以 为原问题的近似极小解 ；否则，取 或 )，令 (例如取
4.2 内点法 (5) 检验是否满足收敛准则 或 如满足上述准则，则以 为原问题的近似极小解 ；否则，取 或 )，令 (例如取 ，转向第（3）步。 根据情况，收敛准则也可采用不同形式，如： 或 清华大学出版社

53 4.2 内点法 例5 试用内点法求解 解：构造障碍函数 联立解上述两个方程，得 如此得最优解： 清华大学出版社

54 4.2 内点法 例6 试用内点法解 解：障碍项采用自然对数函数，得障碍函数如下： 各次迭代结果为： 障碍因子 r x1(r) x2(r)
4.2 内点法 例6 试用内点法解 解：障碍项采用自然对数函数，得障碍函数如下： 各次迭代结果为： 障碍因子 r x1(r) x2(r) r1 1.000 0.500 1.250 r2 0.309 0.595 r3 0.250 0.183 0.283 r4 0.100 0.085 0.107 r5 0.0001 0.000 清华大学出版社

55 4.2 内点法 下面讨论初始内点的求法：求初始内点本身也是一个迭代过程。 先任找一点X(0)为初始点，令
4.2 内点法 下面讨论初始内点的求法：求初始内点本身也是一个迭代过程。 先任找一点X(0)为初始点，令 如果S0为空集，则X(0)为初始内点：若R0非空，则以S0中的约束函数为假拟目标函数，并以T0中的约束函数为障碍项，构成一无约束极值问题，对这一问题进行极小化，可得一个新点X(1) 。然后检验X(1), ，若仍不为内点，如上继续进行，并减小障碍因子r，直到求出一个内点为止。 清华大学出版社

56 4.2 内点法 求初始内点的迭代步骤如下： (1) 任取一点 (例如 )，令 (2) 定出指标集Sk及Tk
4.2 内点法 求初始内点的迭代步骤如下： (1) 任取一点 (例如 )，令 (2) 定出指标集Sk及Tk (3) 检查集合Sk是否为空集，若为空集，则Xk在R0内，初始内点找到，迭代停止。否则转向第（4）步。 清华大学出版社

57 4.2 内点法 (4) 构造函数 以X(k)为初始点，在保持对集合 可行的情况下，极小化 ，即 得 ，转向第（5）步。 (5) 令 )，
4.2 内点法 (4) 构造函数 以X(k)为初始点，在保持对集合 可行的情况下，极小化 ，即 得 ，转向第（5）步。 (5) 令 )， ，转向第（2）步。 (例如 清华大学出版社

58 第5节 fmincon函数 fmincon是MATLAB最主要的内置求解约束最优化的函数，它需要的标准形式为： 中等规模问题：序列二次规划
大规模问题：基于内点反射牛顿法的信赖域算法 大规模线性系统：共轭梯度法 [x, fval] = fmincon(fun, x0, A, b, Aeq, beq, lb, ub, nonlcon, options) nonlcon：非线性约束

59 第5节 fmincon函数 options = optimset('LargeScale', 'off', 'display', 'iter'); A = [ ; ]; b = [0; 72]; x0 = [ ]; [x, fval, exitFlag, output] = x0, A, b, [], [], [], [], [], options) x = fval = e+03

60 第5节 fmincon函数 例：ex8_1，ex8_2(使用导函数加快运算速度)
options = optimset('LargeScale', 'off', 'display', 'iter'); A = [ ; ]; b = [0; 72]; x0 = [ ]; [x, fval, exitFlag, output] = x0, A, b, [], [], [], [], [], options) x = fval = e+03

61 注 记 关于非线性规划的系统研究始于20世纪40年代后期，1951年Kuhn和Tucker提出了著名的Kuhn-Tucker条件。此后，无论在基本理论还是在实用算法的研究方面都发展很快。目前，非线性规划已成为数学规划中内容十分丰富的一个分支。限于篇幅，本篇仅叙述了非线性规划中最基本的一些概念和算法，力图便于读者掌握一些重要方法，并为进一步深入学习打好基础。 在求解无约束最优化问题的方法中，变尺度法、共轭梯度法和Powell直接法占有十分重要的地位。如欲进一步研究，除本篇末列出的参考文献外，还可参阅： 邓乃扬等著.无约束最优化计算方法. 北京：科学出版社，1982年。 对约束极值问题，除本篇提到者外，梯度投影法、简约梯度法、约束变尺度法、乘子罚函数法、序列二次规划法和起作用约束集法(active set method)等都是很重要的方法。其中简约梯度法和起作用约束集法对处理线性约束非线性规划十分有效。处理一般非线性约束非线性规划的有效方法，有待进一步研究。 清华大学出版社