0 凸函数

0.1 定义

函数 是凸的，如果是凸集，且对任意喝任意,有

0.2 一阶条件

假设可微(即其梯度在开集内处处成立), 则函数是凸函数的充要条件是是凸集，且对任意,下式成立:

0.3 二阶条件

假设函数二阶可微，即对于开集内的任意一点，它的Hessian矩阵或者二阶导数存在, 则函数是凸函数的充要条件是, 其Hessian矩阵是半正定阵, 即对于所有的，有:

1 优化问题的标准形式

标准形式的优化问题如下：

2 凸优化问题的标准形式

和一般的标准形式问题相比，凸优化问题有3个附加的要求：

• 目标函数必须是凸的
• 不等式约束函数必须是凸的
• 等式约束函数必须是仿射的

凸优化问题的基本性质：其任意局部最优解也是全局最优解.

凸优化问题的最优解有个很好的判据:
为最优解，当且仅当且

2.1 无约束凸优化问题

对无约束优化问题，为最优解，当且仅当:

2.2 只含等式约束的凸优化问题

为最优解，当且仅当存在, 满足

注: 也可以从KKT条件来看这几个要求.

参考:《Convex Optimization》的4.2.3小节

3 无约束可微问题的最优性理论

无约束可微优化问题通常表示为如下形式:

其中是连续可微函数

3.1 一阶必要条件

假设在全空间可微, 如果是一个局部极小点, 那么
注：这只是个必要条件。局部极小点满足这一条件, 但满足这一条件的不一定是局部极小点, 比如

3.2 二阶最优性条件

必要条件: 若是的一个局部极小点，则, .
充分条件: 若, ，则是的一个局部极小点.

注: 二阶最优性条件给出的仍然是关于局部最优性的判断.对于给定点的全局最优性判断, 我们还需要借助实际问题的性质, 比如目标函数是凸的、非线性最小二乘问题中目标函数值为0等。