凸优化第四章凸优化问题 4.2凸优化

4.2凸优化

1. 标准形式的凸优化问题
2. 局部最优解与全局最优解
3. 可微函数

   

   的最优性准则
4. 等价的凸问题
5. 拟凸优化

标准形式的凸优化问题

是凸函数，等式约束是仿射函数。则此优化问题是凸优化问题。

也可以写成

重要性质：凸优化问题的可行集也是凸集。

证明：可行集是满足不等式约束和等式约束的点的集合，首先不等式约束函数

是凸函数，满足不等式约束

的x，相当于是

的0-下水平集，凸函数的下水平集是凸集，所以满足每个不等式约束的x均是凸集，同时满足这些不等式约束的x是这些凸集的交集仍为凸集。对于等式约束，满足每个仿射函数的x是凸集，同时满足多个仿射函数的x是凸集的交集也是凸集。同时考虑不等式约束和等式约束，可知凸优化问题的可行集也是凸集。

例子：

首先判断可行集，由两个约束函数可推出

，可知可行集是凸集。

是凸函数。但是这不是一个凸优化问题，因为其不等式约束函数不是凸函数，等式约束函数也不是仿射函数。

但可以得到其等价的凸优化问题：

局部最优解与全局最优解

凸优化问题的基础性质:局部最优解也是全局最优解。

证明：

假设x是局部最优解，且存在一个可行点y，

。

因为x是局部最优解，故存在一些R，

因为凸优化问题的可行集是凸集，故取

都属于可行集。

因为

，故

，此时令

。可知

此时

而根据凸函数性质：

与上式矛盾。故凸优化问题中局部最优解就是全局最优解。

可微函数

的最优性准则

当

是可微凸函数时，根据凸函数一阶条件，可知

如果x是最优解，对任意的y属于可行集，首先满足

，同时满足

。所以x是最优解的充要条件就是对任意的y属于可行集，

等价于

，故几何上如果

，

在可行集上定义了一个支撑超平面。

1）对于无约束问题：

可行集就是

的定义域，所以x是最优解的充要条件就是

。

证明：因为

可微，所以其定义域是开的，因此与x足够近的点都可行，取

,t为很小正数时，y可行，于是

，要想满足

，只能

。

2)对于只有等式约束的问题:

可行解的最优性条件：对任意的y属于可行集，即

,

，因为x,y都是可行解，令

,N(A)表示矩阵A的零空间，

,

将x,y代入最优条件：

，即线性函数非负，故

又因为

上述最优性条件也可以拉格朗日乘子法得到，令

，令其为0，得到最优性条件。

3)对于非负象限的极小化问题:

当x为最优解时，最优性条件：

。而

是y的线性函数，在

时，如果

时，函数无下界，即最优条件不可能恒成立，故

。

于是最优条件写成：

所以要使上式恒成立要求

，而

且

，所以只能是

即

等价的凸问题

保持问题凸性的转换有：消除等式约束、引入等式约束、引入松弛变量、上境图问题形式、极小化部分变量

消除等式约束

等价于

是Ax=b的特解，F的列可以长成A的零空间。

引入等式约束

等价于

引入松弛变量

等价于

上境图形式

凸优化问题的上境图形式：

极小化部分变量

极小化凸函数的部分变量将保持凸性不变，

等价于

拟凸优化

拟凸优化的标准形式

是凸函数，等式约束是仿射函数，

是拟凸函数。则此优化问题是拟凸优化问题。

拟凸优化问题的局部最优解不一定是全局最优解。

如上图

是局部最优解但是不是全局最优解。

用一族凸函数不等式表示拟凸函数的下水平集

选择一族凸函数

，t是凸函数的编号，这些函数满足：

，即拟凸函数的t下水平集是凸函数

的0下水平集。

并且，对于每个x，

都是t的非增函数。

注意：t固定时，每个

是x的凸函数。

例子：

，其中p是凸函数，q是凹函数，在定义域上，

。

则可取

说明：（1）

是凸的：p是凸的，q是凹的，但-q是凸的，所以

是凸的。

（2）满足：

求解拟凸优化的二分法

思想：有一个区间，包含最优解，取区间的中点，判断最优解在上半区间还是下半区间，然后更新区间，不断将区间缩小为原来的一般直到找到足够小的区间。

算法：

给定

，容忍度

重复一下步骤:

1. 

2. 求解凸可行性问题
3. 如果问题可行，u=t，否则l=t

直到