优化设计第三次课课件

第六节约束优化问题的极值条件

一、约束极值问题

约束优化问题,即求一个设计点使目标函数且满足约束条件

这个满足所有约束条件的最优点称为约束最优点。

由于约束化问题的最优解受到约束条件的限制，它不仅与目标函数的性质有关，而且与约束函数的性质也有密切关系。所以，一般来说，目标函数的无约束最优解不一定是它的约束最优解。这一点，可以从下图所示的几种情况来说明。图中带阴影线的曲线为约束曲线，无阴影线是目标函数的等值线。

a)图a)所示的目标函数是凸函数，三个约束曲线围成的可行域是一个凸集。从图中看到，椭圆形等值线族的中点是目标函数的极值点，即无约束最优点。因为这个点落在可行域之内，所以，它也是约束的最优点。当所有的约束条件对最优点都不起作用时，这些约束条件存在或不存在，其最优点都是点，因此，可以不考虑这些约束。

c)

图c)所示，目标函数等值线在约束边界处呈波浪形弯曲，有三条不同的等值线与约束曲线分别相切于、、三点。比较这三点，可以确定目标函数值最小的一点是最优点。由此可知，利用等值线与约束曲线相切点来判断是否为约束最优点，只是一个必要条件，并不是充分条件,也就是说等值线与约束相切点不一定是最优点。

d)

图d)表示由于约束条件形状的原因，使可行域为非凸集，因而产生了多个局部极值点，对于这种情况，通常也只有通过比较，从中挑选一个全局极值点。

经过上面的分析，可以看到，由于目标函数和约束函数的非凸性，使约束极值点的数目增多，从而也使优化过程复杂化了。目前虽然已有一些实用的求解方法，但是寻求更完善有效的求

解方法，至今还是优化技术中的一个研究课题。

二、等式约束优化问题的极值条件

求解等式约束优化问题,即求一个设计点使目标函数且满足约束条件

(1)消去法(降维法)先讨论二元函数只有一个等式约束的简单情况，即且满足约束条件

求解这个问题可以应用代数中的消元法，先把约束函数变成以某一变量表示另一变量的函数关系，例如，，

然后将这个函数关系代入目标函数中，消去，变成一元函数。经过这样代换，把等式约束问题转化为无约束问题，把目标函数由二维降为一维。最后，将函数极小化求，再代入，求出，就可得到此优化问题的最优解。

对于维目标函数带有个等式约束的优化问题，可以把上述方法加以推广。若作为个方程的联立方程组，把个变量中的个变量(例如，)，用其余个变量来表示，可由联立方程组解出

拉格朗日乘子法是求解等式约束优化问题的另一种经典方法。它是通过增加变量将等式约束优化问题变成无约束优化问题，所以又称作升维法。现在仍先研究二元函数只带一个等式约束的简单优化问题。当不考虑约束条件时，根据无约束极值的必要条件为即由全微分原理，有(A)(1)拉格朗日乘子法(升维法)

若把式（C）写成，并令它等于一个非零的常数，则（C）可改写成式中为待定常数，称为拉格朗日乘子，解联立方程组：

三个方程三个未知数，可解。求得极值点和值。上式的无约束极值必要条件为

求解上面的联立方程组，由个方程解出和共个变量。要判断是否极值点，通常还需要利用极值的充分条件。因为原等式约束问题是维的，而方程组增加到维。所以，拉格朗日乘子法又称升维法。利用梯度和矩阵形式，可把方程组简洁的写成

式中，,

是向量的梯度矩阵，其矩阵表示为拉格朗日乘子法的几何意义说明如下：

1.在维设计空间中，各等式约束面和目标函数的等值面都可以想象成超曲面，而梯度和则分别为这些超曲面上的法线。

2.满足所有等式约束条件的几何含义是最优点一定要符合这些约束曲面的交面(或交线、交点)之上。

3.极值必要条件表示目标函数的负梯度(即等值面的法线)与所有约束函数的(即约束曲面的法线)为线性相关。其几何意义就是目标函数的负梯度应落在所有约束曲面的法线所张成的空间中。拉格朗日乘子法几何意义

如右图所示三维空间中有两个等式约束曲面、，最优点应落在这两个约束面的交线上。另一方面，与、线性相关表示为这三个向量必须是共面。因为，这里在三维空间中只有两个约束曲面的梯度、，这两个向量张成一个平面。因此，向量就落在此平面上。

例：求、，使目标函数极小，且满足约束条件(1)一个起作用约束情况式中，——约束函数在点的梯度。(2)二个起作用约束情况

a)不是约束最优点b)是约束最优点式中，。

在实际求解过程中，事先并不知道最优点位于哪一个或那几个约束的交汇处。为此，可把个约束条件全部考虑进去，并取不起作用的约束条件的乘子为零。在这种情况，一个局部最优点的必要条件为上式就是著名的库恩-塔克（Kuhn-Tucker）条件，又称K-T条件。(##)库恩-塔克（Kuhn-Tucker）条件的几何意义K-T条件的几何意义

a)不是约束最优点b)是约束最优点

最后，把前面的等式约束极值必要条件式与这里的不等式约束极值必要条件式合并起来，可得到即有等式约束，又有不等式约束优化问题的K-T条件，即

其中与等式约束相关的乘子可正可负，但不能为零。四、库恩-塔克条件应用举例

若给定优化问题的数学模型为利用K-T条件确定极值点它的K-T条件可表示为因为待求，所以现在还无法知道哪些约束是起作用的，哪些约束是不起作用的，只能先根据各种可能情况进行试验。下面按照八种情况分析如下：

2）若、两个约束在处起作用，则根据K-T条件有下式成立从约束方程中解得，相当于图中的A点。将得到的解代回K-T方程得到

由于K-T条件要求，所以A点不是极值点。

3）若、两个约束在处起作用，则根据K-T条件有下式成立从约束方程中解得，相当于图中的B点。将得到的解代回K-T方程得到

由于K-T条件要求，所以B点不是极值点。

4）若、两个约束在处起作用，则根据K-T条件有下式成立满足K-T条件要求，所以C点是极值点。从约束方程中解得，但不满足第三个不等式约束条件所以取相当于图中的C点。将得到的解代回K-T方程得到

5）若只有一个约束在处起作用，则根据K-T条件有下式成立从前两方程组中解得因为假定只有一个约束在处起作用，那么第二个约束在处不起作用，有

即根据可推出由于K-T条件要求，所以此点不是极值点。

6）若只有一个约束在处起作用，则根据K-T条件有下式成立解上面方程组解得此解不满足的要求，故次点不是极值点

7）若只有一个约束在处起作用，则根据K-T条件有下式成立解上面方程组，解得，此解不满足的非负要求，故次点不是极值点

8）若、、三个约束都在处都不起作用，则根据K-T条件有下式成立解上面方程组，解得，此解不满足的要求，故次点不是极值点

从上述八种情况的分析可以看出，利用K-T条件求极值点（解析法）往往是很繁琐的，需要确定哪些约束在极值点出起作用。因此实际应用中，很少利用K-T条件求极值点，而是主要用他来判断所要求点是否只极值点，以及检验一种搜索方法是否合理。例：已知二维约束问题

受约束于

用K-T条件判断是否为极小点。一维搜索方法第一节一维搜索概述

求一元函数的极值问题是一维优化问题，利用直接法求一元函数极值点的过程叫一维搜索。一维搜索更重要的作用在于它是求解多元函数优化问题的基础。因为求解多元函数优化问题的过程，通常可归结为反复求解一维优化问题。因此，它是优化方法中最基本的方法。一维搜索的方法有：分数法，0.618法（黄金分割法），二次插值法，三次插值法，切线法，割线法等，本章主要介绍0.618法、二次插值和切线法等常用的几种一维搜索法。

现在的问题是，在初始点和搜索方向已确定的情况下，步长应走多大，也就是说步长因子应取多大，才能使得到的新点的函数值最小。

换句话说，要求得一个值，使函数值达到最小，这样，问题就转化为求参数的一元函数的极值问题，即

用数学归纳法求多元函数最优解的过程为：选择初始点，由这点出发，沿着给定的方向走一个步，到达一个新点，而且该点的函数值有所下降。如果要使这一步取得最好的效果，则希望所得到点是方向上函数值最小的一个点。然后，又以为新的初始点，沿着给定的方向走一个步长，到达点，同样，该点是方向函数值最小的点，如此继续，直到满足给定的计算精度为止。其具体的迭代过程可以用下式来表示=显然，上式就是一维优化问题，式中的称为最优步长因子。上述概念可以用图形来形象地表示。一维搜索的几何表示设在第步迭代中，从初始点出发，沿着给定的方向走了一个步长，到达新点从图上可以看出这个点是在方向上函数值最小的一个点，如果步长走小一些,得到点，或步长走大一些，得到点，这两点都不是方向

上函数值最小点，因为、两点处的等值线的函数值比点处的等值线的函数值要大。在一维搜索中，由于目标函数可以看做步长因子的一元函数，根据一元函数极值的必要条件，则可以采用解析法求解的极小点。为了直接利用的函数式求解最佳步长因子，可把简写成的形式进行泰勒展开，取到二次项，即令

得到由上面的推导可知，采用解析法求解一维搜索问题需要求解目标函数在点处的梯度和海色矩阵，这对函数关系复杂、求导困难或无法求导的函数，采用解析法将是非常困难的，所以在优化设计中，求解最佳步长因子主要采用数值解法，即利用计算机通过迭代计算求得最佳步长因子的近似解。采用数值解法求解一维优化问题即一维搜索的基本步骤是：（1）先确定所在的搜索区间。（2）根据区间消去法的基本原理不断缩小此区间，从而获得的数值近似解。第二节搜索区间的确定与区间消去法原理

为了求得多元函数的最优解，需要进行多次迭代。而每次迭代都要求解一维优化问题。所以，多元函数优化问题的求解过程就归结为反复求解一维优化过程，即反复进行一维搜索。

区间的单峰性

进行一维搜索时，首先要考虑在给定的方向上应确定一个搜索区间，而且在这个区间内部，函数具有单峰性（即函数在该区间有唯一的极小点），这种区间称为单峰区间。如图所示，区间内函数只有一个峰值，即有唯一的极小点，这就是单峰区间。而区间内函数有两个极小点和一个极大点，即有三个峰值，显然，这个区间就不是单峰区间。单峰区间是函数在该区间内只有一个峰值，其函数按“大－小－大”或“高-低-高”规律变化的区间。在确定了搜索区间为单峰区间之后，就可在该区间作一维搜索，求得极小点。对于多峰函数，只要适当划分区间，也可以使该函数在每一个子区间上都是单峰的。为了确定极小点。所在的单谷区间应使函数在区间里形成“高—低一高”趋势。对于性态比较明显的单变量函数，单峰区间可以根据实际情况人为地选定；但对于性态复杂的单变量函数，一般需要利用数值计算的方法来确定单蜂区间。外推法(也称进退法)就是确定单峰区间的一种数值计算方法。一、确定搜索区间的外推法（进退法）采用外推法确定搜索区间的基本思想是：按照一定规律给出一些试算点，依次比较各试算点的函数值大小，直到满足单峰区间的条件，即函数值呈现“大-小-大”变化形式，则为所确定的搜索区间。外推法的具体实现过程为，从开始，以初始步长向前试探。如果函数值上升，则步长变号，即改变试探方向；如果函数值下降，则维持原来的试探方向，并将步长加倍(),区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点，形成函数值的“高-低-高”趋势。下图表示沿的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。经过三步最后确定搜索区间，并且得到区间始点、中间点和终点，及所对应的函数值。下图中，如果开始的试探方向为函数值上升方向，即开始沿着的正向试探，但由于函数值上升而改变了试探方向，最后得到始点、中间点和终点，及它们所对应的函数值，从而形成单谷区间为一维搜索区间。外推法的程序框图例：试用外推法确定函数的初始一维搜索区间，设初始点，初始步长。解：根据给定的初始点和初始步长，直接按照上面外推法的程序框图进行求解。

(1)取，因为，则

(2)因为，所以向前试探，此时

(3)因为，所以继续向前试探，此时再将步长增加两倍，即，于是

(4)比较和，可知，所以搜索结束，已寻得初始搜索区间，所以继续向前试探，此时此时相邻3点的函数值分别是4,0,16，确实形成了“高-低-高”的一维搜索区间。

二、区间消去法原理

当含有极值点的单谷搜索区间确定之后，应逐步缩短搜索区间，从而找到极小点的数值近似解。这里采用区间消去法来实现搜索区间的逐步缩短。首先，在搜索区间内任取两点且，并计算函数值，比较函数值的大小将有下列3种情况。

(1)。由于函数为单谷，所以极小点不可能在区间内，而应在区间内，这时可以去掉区间，把区间缩小为，如下图(a)所示。

(2)。由于函数为单谷，所以极小点不可能在区间内，而应在区间内，这时可以去掉区间，把区间缩小为，如下图(b)所示。

(3)。这时极小点只能在区间内，可以去掉区间或者，甚至将两段同时去掉，只保留区间，，如下图(c)所示。根据上述分析，在区间内插入两个点，并通过比较其函数值大小，就可以把搜索区间缩短成、