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

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

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

9 第1节 最优性条件 库恩－塔克(Kuhn－Tucker,简写为K-T)条件。
库恩－塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件。只要是最优点(而且该点起作用约束的梯度线性无关。满足这种要求的点称为正则点)，就必须满足这个条件。但一般说它并不是充分条件，因而满足这个条件的点不一定就是最优点(对于凸规划，它既是最优点存在的必要条件，同时也是充分条件)。

10 第2节 二次规划 若非线性规划的目标函数为自变量X的二次函数，约束条件全是线性的，称这种规划为二次规划。二次规划的数学模型为：
（7-12） （7-13） （7-14） 对于这种问题，库恩-塔克条件不但是极值点存在的必要条件，而且也是充分条件。

11 第2节 二次规划 由库恩-塔克条件可得如下线性规划问题： 解线性规划(7-20)式，若得到最优解： 则，原二次规划问题的最优解为：
（7-20） 解线性规划(7-20)式，若得到最优解： 则，原二次规划问题的最优解为：

12 第2节 二次规划 例2 求解二次规划 解：将上述二次规划改写为 可知目标函数为严格凸函数。此外

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

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

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

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

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

18 第3节 可行方向法 (5) 解下述一维极值问题 此处 (6) 令 转回第(2)步。

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

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

21 第3节 可行方向法 构造在下述线性规划问题： 为便于用单纯形法求解，令 从而得到：

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

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

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

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

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

27 注 记 关于非线性规划的系统研究始于20世纪40年代后期，1951年Kuhn和Tucker提出了著名的Kuhn-Tucker条件。此后，无论在基本理论还是在实用算法的研究方面都发展很快。目前，非线性规划已成为数学规划中内容十分丰富的一个分支。 在求解无约束最优化问题的方法中，变尺度法、共轭梯度法和Powell直接法占有十分重要的地位。 对约束极值问题，可行方向法、梯度投影法、简约梯度法、约束变尺度法、乘子罚函数法、序列二次规划法和起作用约束集法(active set method)等都是很重要的方法。其中简约梯度法和起作用约束集法对处理线性约束非线性规划十分有效。