优化设计-2

f(x(0)??)?f(x(0))，则称x(0)为函数f(x)在x(0)处的局部极小值点。若函数f(x)是单峰函

数，则该极小值点也是f(x)的全局极小值点。因此，求函数的一阶导数（或一阶偏导数）并令其为0是求无约束优化问题函数极值的基本方法。以一元函数为例，如果函数f(x)在某点处一阶导数为0，则该点有可能是函数的极值点，进一步的判断要用到函数f(x)在驻点处的二阶导数f??(x0)。也就是对单调、连续、可微的一元函数f(x)，x=x0为其极值点的充分必要条件为

f?(x0)?0,??0(极小值)?f??(x0)??? （2.10）

0??（极大值）?对于多元函数来说，由式2.7可以看到，如果x(0)是函数f(x)的极小值点，则必有

f(x)>f(x(0))

其中，x是以x(0)为中心的某领域内的点。利用函数取得极值的必要条件，有

[?f(x(0))]?0

因此，可得出下面的不等式：

T1x1?x1(0)??2f(x(0))x1?x1(0)?0 2f(x)?f(x(0))?或

????f(x)?f(x(0))?T1x1?x1(0)G(x(0))x1?x1(0)?0 (2.11) 2????将式2.11应用到一元函数的情形，可知，这也就是式2.11。 对于对称矩阵G，若存在非零向量x，满足

xTGx?0 （2.12）

则称G为正定矩阵。对于极大值问题，则要求G为负定矩阵（即），因此，n元函数f(x)在点x(0)处取得极值的充分必要条件是

??f?f(x(0))????x1?f...?x2?f?T?[00...0]?0 (2.13) ??xn?T??2f??x2?21??f(0)2(0)G(x)??f(x)???x2?x1???2??f??x?x?n1?2f?x1?x2?2f2?x2??2f?xn?x2?2f???x1?xn??2?f???x2?xn? （2.14）

????2f??2??xn?x(0)（若为正定，则为极小值；若为负定，则为极大值。）

对于二元函数y=f(x1,x2), x(0)为其极值点的充要条件可表示为

??f(0)?f(x)????x1?f??0（必要条件）

?x2?(0)?xT??2f??x2(0)G(x)??21??f??x?x?21?2f??x1?x2??正定或负定（充分条件） ?2f?2??x2?x(0)?2f?2f(0)(0)(0)(0)且2?0时，(x1,x2)为极大值点，2?0时，(x1,x2)为极小值点。 ?x1?x1对称矩阵G的正定性除可按定义式2.10判定外，更实用的方法是利用矩阵的各阶主子式的正负号进行判定。若G的各阶主子式均大于0，则G为正定矩阵；若G的各阶主子式的正负号负、正相间，即奇数阶主子式小于0，偶数阶主子式大于0，则G为负定矩阵。

?1021???例2.2 判断矩阵A?253的正定性。 ????134??解：

因为a11>0，则

即矩阵A的各阶主子式的值均大于0，故矩阵A为正定。 例2.3 判断矩阵

??12?2??

A???35?3????0?1?2??的正定性。 clc;

A=[-1 2 -2;-3 5 -3;0 -1 -2]; for i=1:3

A1(i)=det(A(1:i,1:i)); end -1 1 -5

2x12x2例2.4 试求函数f(x)?的极值。 ?22[0 0]T

G=[1 0

0 1] 正定 极小值

2.5 凸集与凸函数

经典优化算法大多属于沿某一搜索方向的局部优化算法，要求目标函数和约束条件满足一定要求，如要求目标函数及约束条件为单峰函数或单调函数，或者说要求目标函数和约束函数为凸函数，对应的解集为凸集。相对于全局优化算法来说，凸集、凸函数的概念对于局部优化算法更为重要。如果已知目标函数为凸函数且求解域为凸集，则求解出的局部极值点也是全局极值点，否则求出的局部极值点就不一定是全局极值点。对于约束优化问题应验证解是否满足约束条件。

1 凸集

设集合S?R，如果对于任意的x1，x2∈Rn，有

n?x1?(1??)x2?S,???[0,1] (2.15)

则称S是一个凸集。该定义用文字描述就是：对于一个点集（或区域），如果连续其中任意两点x1，x2的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。 反过来，如果是一个凸集，点x1,x2,…,xm∈S，则这m个点的组合为凸集：

??x?S

iii?1m其中，

??i?1mi?1,?i?0（i=1，2，…，m）

例2.5 证明超平面H?x?R|px?c是一个凸集。其中p∈Rn是超平面的法向量，且不为0；c是一个标量。

2 凸函数

定义：设f(x)为定义在非空凸集x?R上的实值函数，若对任意x1,x2∈Rn以及数??[0,1]，恒有

n?nT?f[?x1?(1??)x2]?(?)?f(x1)?(1??)f(x2)

则称f(x)为x上的下凸（上凸）函数。 若对任意x1,x2∈Rn以及数??[0,1]，恒有

f[?x1?(1??)x2]?(?)?f(x1)?(1??)f(x2)

则称f(x)为x上的严格下凸（上凸）函数。 性质：

（1）设f(x)为定义在凸集上Rn上的凸函数，则对于任意实数β≥0，函数βf(x)也是定义在Rn上的凸函数。 （2）设f1(x)和f2(x)为定义在凸集Rn上的两个凸函数，α，β为不同时为0的实数，则f(x)= αf1(x)+βf2(x)仍然是定义在Rn上的凸函数。

（3）设f(x)为定义在凸集Rn上的凸函数，则对于任意实数β，集合S?x|x?R,f(x)???n?是凸集。

（4）设f(x)为定义在凸集Rn上的可微凸函数，若存在点x*∈Rn，使得对于所有的x∈Rn有[?f(x)][x?x]?0，则x*是在f(x)上的最小点（全局极小点）。该性质说明，函数f(x)在极值点x*处的梯度与曲线上两点割线构成的矢量的夹角α≤π/2，在极值点处函数的梯度与过极值点的切线垂直。 凸规划

*T*是指目标函数和约束条件均为凸函数的一类优化问题。若x*是凸规划的任何局部最优解，则该点也是凸规划的全局最优解。

2.6 有约束优化问题的极值条件

1 等式约束优化问题的极值条件 等式约束优化设计问题的数学模型为

minf(x),x?Rns.t.hv(x)?0,v?1,2,...,M?n （2.16）

等式约束优化问题一般采用间接法求解，如消元法，拉格朗日乘子法、惩罚函数及增广拉格朗日乘子法等。

2 不等式约束优化问题的极值条件 不等式约束优化设计问题的数学模型为

minf(x),x?Rns.t.gu(x)?0,u?1,2,...,L?n （2.21）

x??xn?1通过引入L个松弛变量~xn?2?xn?L?,xn?u?0，可将不等式约束转化为等

T式约束，再应用拉格朗日乘子法构造无约束优化问题：

~(x)?f(x)??(g(x)?x2) （2.22） minl(x,?)?f(x)??g?uun?uTu?1L根据无约束问题的极值条件，可以得到具有不等式约束的多元函数极值条件：

?f(x*)L?gu(x*)???u?0,i?1,2,...,n?xi?xu?1igu(x*)?0,u?1,2,...,L （2.23）

?ugu(x*)?0,u?1,2,...,L?u?0,u?1,2,...,L这是库恩-塔克条件。式2.23中的第一式称为一阶条件，第二式称为不等式条件，第三式称为松弛约束条件，第四式为乘子非负条件。 例2.10 求凸规划问题

minf(x)??x1?x2,x?Rns.t.223x1?x2?1

x1,x2?0的最优解。

解：

22l(x1,x2,x3,?)??x1?x2??(3x12?x2?1?x3)

库恩-塔克条件