2.2最优性条件在线视频

本单元

主要讲授非线性规划的最优性条件

下面我们讨论一下极值点的概念

若对于定义域D中的任何x

f(X)大于等于f(X*)

即在整个定义域D上

f在X*点的函数值最小

则称X*是f(x)的全局最小值点

类似地有全局最大值点的定义

全局最小值点

全局最大值点统一称为全局最优点

若f在X*点的局部范围内函数值最小

则称X*是f(x)的局部极小值点

图中

D是局部极小值点

B是全局极小值点

A是局部极大值点

C是全局极大值点

若对于定义域D中的任何

不等于X*的X

f(X)大于f(X*)

即则称X*是f(x)的严格全局最小值点

若在X*点的局部范围内

对于任何不等于X*的X

f(X)大于f(X*)

则称X*是f(x)的严格局部极小值点

A是全局最小值点

但不是严格全局最小值点

A是严格局部极小值点

对于二元函数f(x,y)

及点(x0,y0)

若固定y=y0

是关于x的一元函数f(x,y0)

的极小值点若固定x=x0

y=y0是关于y的一元函数

f(x0,y)的极大值点

则称(x0,y0)是f(x,y)的鞍点

鞍点既不是极大值点

也不是极小值点

下面我们讨论一下极值点满足的条件

假设x*是无约束优化问题

（2.1-2）的局部极小值点

f(x)在 处可微

则必有f(x)

在x*处的梯度等于0.

反过来不成立

即

梯度等于0的点

不一定是极值点

例如

鞍点.

若在x*处

f(x)的梯度等于0

且二阶导数矩阵Hesse矩阵正定

则x*为f(x)的严格局部极小值点

对于称矩阵A

若相应的二次型是正定的

即对于任意的非零向量X

XTAX>0则称A为正定的

若相应的二次型是半正定的

即对于任意的向量X

XTAX≥0则称A为半正定的

A是正定矩阵的判别

若A的各阶顺序主子式大于0

则A是正定的

若A的各阶顺序主子式大于等于0

则A是半正定的

f(X)的 Hesse矩阵H是一个3阶对称矩阵

1阶顺序主子式=4>0

2阶顺序主子式=7>0

3阶顺序主子式=14>0

所以H是一个正定矩阵

下面我们讨论一下凸函数的极值点

与凸规划问题的最优解

凸函数的定义如下

对于凸集D上的实函数f(x)

若D中任意两点加权平均的函数值

小于等于这两点函数值的加权平均

如图所示

则称f(x)为D上的凸函数

若-f(x)是凸函数

则称f(x)为凹函数

凸函数有以下2个性质

性质1

凸函数的正线性组合

也是凸函数

凸函数的截集是凸集

如何判断f(x)是否是凸函数呢

我们有以下定理

定理 设D为Rn中的开凸集

f(x)在D上具有二阶连续的偏导数

则f(x)为D上的凸函数的充要条件

是f(x)的Hesse矩阵H(x)

在D上处处半正定

f(x)的Hesse矩阵H(x) 正定

则f(x)在D上是严格凸函数

我们不加证明地给出凸函数的极值定理

设D为Rn中的凸集

f(x)为D上的凸函数

则它的任一极小值点

就是它在D上的最小值点

若f(x)是严格凸函数

则极值点唯一

下面给出凸规划的定义

若可行域 为 中的凸集

为D上的凸函数

则称该非线性规划问题为凸规划

对于非线性规划问题（2.1-1）

若目标函数f(x)是凸函数

所有等式约束hi(x)=0是线性的

不等式约束gj(x)≥0中

-gj(x) 是凸函数

则该非线性规划为凸规划

对于凸规划问题

局部最优解也是全局最优解

当目标函数为严格凸时

最优解必定唯一

下面我们讨论约束非线性规划问题的

最优性条件即Kuhn-Tucer条件

对于标准形式的非线性规划问题

定义广义拉格朗日函数如下

对于约束条件gj(x)≥0

若gj(x*)=0

则称gj(x)≥0约束条件点

在x=x*为起作用的约束

对于非线性规划问题（2.1-1）

若在x=x

所有起作用的约束条件函数的

梯度向量线性无关

则称在x=x*满足约束规范

对于非线性规划问题的标准形式（2.1-1）

若x=x*是非线性规划问题（2.1-1）的

局部最优点

在x=x*满足约束规范

则x=x*满足Kuhn-Tucer条件

（简称K-T条件）

（1）广义拉格朗日函数的梯度等于0

（2）满足非线性规划问题（2.1-1）的约束条件

（3）对于不等式约束而言

（4）对于不等式约束而言

称这组条件为Kuhn-Tucer条件（简称K-T条件）

满足这组条件的点为K-T点.

对于这个例题，

第1步

将它转化为非线性规划的标准形式（2.1-1）

第2步

写出它的广义拉格朗日函数

第3步

对广义拉格朗日函数求偏导数

并令其等于0得K-T条件（1）

第4步

再写出K-T条件（2）-（4）

K-T条件（1）-（4）中

包含不等式方程

联合求解这组方程较困难

需将拉格朗日乘子按

是否等于0组合后求解

也是该凸规划的全局最优点

对于凸规划

K-T条件也是最优解的充分条件

对于该例题

是K-T点

但它不是最优点

相应的最优值为f =-1

这说明K-T条件只是必要条件

只有当非线性规划是凸规时

它才是充要条件

对于该例题

该非线性规划问题的最优解为

但在该点

K-T条件不成立.

原因是在该点不满足约束规范

不能保证K-T条件成立

下面讨论对偶问题

问题（2.2-13）的广义拉格朗日函数

为式（2.2-14）

在式（2.2-15）中

sup为上确界符号

表示右端集合的最小上界

在上确界可达时

等于右端集合的最大值

在式（2.2-16）中

inf为下确界符号

表示右端表示集合的最大下界

在下确界可达时

等于右端集合的最小值

式（2.2-19）被称为原问题

式（2.2-20）被称为该原问题的对偶问题.

我们不加证明地给出对偶定理如下

这一单元课就上到这里

下次再见