发布时间 : 星期一 文章优化设计-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)
库恩-塔克条件