凸优化总结

凸优化总结

所有这些想法基本是来自于书籍convex optimization，主要包括凸优化的基本理论，主要的优化算法。
凸优化的基本理论包括凸优化的基本定义，以及KKT条件。

优化问题的定义

优化问题的基本定义如下：

$$argmin_x \space f_0(x)$$
$$s.t. \space f_i(x) \le 0 \space i=1, ..., m$$
$$h_i(x) = 0$$
在这里$f_0(x)$是目标函数，$f_i(x)$和$h_i(x)$是constraint。

凸函数和凸集

凸函数

所有满足如下定义的函数都称之为凸函数:

$$f(\theta * x + (1 - \theta)*y) \le \theta*f(x) + (1-\theta)*f(y) (s.t. 0 \le \theta \le )1$$
凸函数的一阶特性，这个也是凸函数的充要条件：
$$f(y) \ge f(x) +\nabla { f(x) ^ T } * (y-x)$$
这意味着凸函数的任意一个点都可以作为函数下限的估计。
凸函数的二阶充要条件是：
$$\nabla ^ 2 f(x) \succ 0$$
要求凸函数的二阶倒数必须是半正定的。

凸集(Convex Set)

凸集的定义如下：
如果x和y属于集合S，如何x和y满足如下的性质

$$\theta*x + (1-\theta)*y \subset S ( 0 \le \theta \le 1)$$
那么集合S则是凸集。

锥集(Cone Set)

类似于凸集的定义:
如果x和y属于集合S，切且满足如下的性质

$$\theta_1*x + \theta_2*y \subset S (0 \le \theta_1 \, \, and \, \, 0 \le \theta_2)$$
那么集合S称为锥集。可以看出如果是锥集，那么一定是凸集。

凸优化的定义

有了凸函数和凸集的定义，便可以非常容易的定义凸优化问题如下：

$$argmin_x f_0(x)$$
$$s.t. \quad f_i(x) \le 0 ; \; i = 1, ..., m$$
$$\quad \; a_i ^ T*x = b_i; \; i=1, ..., p$$
其中$f_0(x)$和$f_i(x)$必须是凸函数，而且函数域必须是凸集。与标准的优化问题相比，凸优化有三个新的限制：

• $f_0(x)$和$f_i(x)$都必须是凸函数。
• 函数的定义域必须是凸集。
• 等式约束必须是仿射函数。
  相比于其他类型的优化问题，凸优化的局部最优值是全局最优值，因此存在很大的优势。

KKT条件和Langrian系数

对于凸函数的标准定义，可以直接定义拉格朗日函数如下：

$$L(x,\lambda, \nu)=f_0(x) + \sum_{i=1}^{i=m}{\lambda_i \cdotp f_i(x) + \; + \mu ^ T*(A ^ {T}\cdotp x - b) }$$
在这里要求$\lambda_i$必须是非负数。可以看到$L(x,\lambda,\nu)$在x属于定义域的时候必然小于$f_0(x)$。再定义如下的函数：
$$g(\lambda, \nu) = \inf_{x \subset D} L(x, \lambda, \nu)$$
定义dual问题如下：
$$argmx_x \; g(\lambda, \nu)$$
$$s.t. \lambda \succ= 0$$
这个问题称为原优化问题的对偶问题。假设原问题的最优解为$p^*$，对偶问题的最优解为$d^*$,那么$p^* \ge d^*$必然成立。$p^* - d^*$叫做duality gap，只有在强对偶的情况下才为0。
当优化问题达到最值的时候满足KKT条件，对于凸优化问题来说这是充要条件：
$$f_i(x) \le 0 \; (i=1, .., m)$$
$$a_i ^ T * x = b_i \; (i=1, ..., p)$$
$$\lambda_i \ge 0$$
$$\lambda_i * f_i(x) = 0$$
$$\nabla f(x) + \sum_{i}^{m}{\lambda_i \cdotp \nabla f_i(x)} + A ^ T * \nu = 0$$
其中第四个公式称为互补条件(Complentery condition), $\lambda_i$和 $\nu_i$称为拉格朗日系数。
因为对凸优化问题来说KKT条件是充要条件，所以有时凸优化问题的解决在于解决KKT条件所确立的线性方程或者KKT矩阵的变形。

凸优化算法

给定特定的凸优化问题，存在不同类型的优化算法。凸优化问题来说取决于目标函数的形式，约束是等式约束还是不等式约束等等。

无约束最优化

无约束最优化的基本方法包括梯度下降和牛顿法。牛顿法的核心在于使用目标函数在特定点的二阶近似：

$$f(y) = f(x)\; + \nabla f(x) ^ T \cdotp (y - x ) + 1/2*(y-x)\nabla ^ 2 f(x)(y-x)$$
牛顿法就是对这个近似后的函数求最优解。

有等式约束的二次函数

对于有等式约束的二次优化问题，对应的具体形式：

$$argmin_x \; \;1/2 \cdotp x^TPx + q^Tx + b_0$$
$$s.t. A \cdotp x = b$$
对应的KKT条件可表述成：
$$A \cdotp x = b$$
$$A ^ T \cdotp \nu + Px^* + q = 0$$
对于这样的问题，可以直接当作线性代数问题解决。

有等式约束的凸优化

优化的问题可用下面的形式描述：

$$argmin_x \; f_0(x)$$
$$A \cdotp x = b$$
相比于前一个问题，最大的差别在于优化目标从二次函数更换成一般的可求导的函数，解决问题的方法在于使用泰勒展开。假如当前点x满足等式约束的要求，需要获得优化方向$\nabla x_{nt}$,使得目标函数既能下降，又能满足等式约束。
$$argmin_{\nabla x_{nt} } f_0(x + \nabla x_{nt}) = f_0(x) + \nabla ^ T f_0(x)* \nabla x_{nt} + 1/2 \nabla ^ T x_{nt} \nabla ^ 2 f_0(x) \nabla x_{nt}$$
$$s.t \; A(x + \nabla x_{nt} ) = b$$
对比于之前的有等式约束的二次优化问题，可以看出这个可以被直接解决。

一般的凸优化问题

对于既有不等式约束也有等式约束的，且目标函数不是二次和线性函数的凸优化问题，使用两个类似但不同的方法解决问题。

Barrier Method

方法的核心是将不等式约束转化到目标函数中，将问题转化成有等式约束的凸优化问题。
转化的问题可以下面的形式描述：

$$argmin_x f_0(x) + -1/t*(\sum_{i=1} ^ { i=m } { log(-f_i(x)) })(t > 0)$$
$$s.t. \quad A \cdotp x = b$$
这里使用对数函数将不等式条件纳入到优化目标中，且使用t来控制函数在0附近变化的迅速程度。$t$越大，则整个目标函数越接近理想目标。
也可以看成优化如下的目标函数：
$$argmin_x t \cdotp f_0(x) + \phi (x)$$
$$s.t. A \cdotp x = b$$
其中$\phi (x)$定义成 $-( \sum_{i=1} ^ {i=m} { log(- f_i(x) ) } )$，t值怎样变化，唯一的要求就是$f_i(x) \lt 0$且$A \cdotp x = b$,可以看到不等式约束始终处于激活的状态，因此这个方法称为内点法。
给定t值之后，我们可以写出对应的KKT条件如下：
$$A \cdotp x ^ * = b$$
$$t \cdotp \nabla f_0(x) + \nabla \phi(x) + A ^ T \cdotp \nu = 0$$
如果替换成log函数的倒数，那么对应的KKT条件如下：
$$A \cdotp x ^ * = b$$
$$\cdotp \nabla f_0(x) + \sum_{i=1} ^ {i=m}{- \frac{ \nabla f_i(x) }{t \cdotp f_i(x) } } + A ^ T \cdotp \frac{1}{t} \nu =0$$
如果我们定义$\lambda_i = \frac{-1}{t \cdotp f_i(x) }$, $\mu_i = \frac{1}{\nu_i}$，那么对Barrier Method，我们可以给出一个类似于KKT的条件解释如下：
$$A \cdotp x = b$$
$$f_i(x) \le 0 \quad (i = 1, ..., m)$$
$$\lambda \succ = 0$$
$$\nabla f_0(x) + \sum_{i=1}^{i=m}{ \lambda_i \cdotp \nabla f_i(x) } + A^T \cdotp \mu = 0$$
$$\lambda_i \cdotp f_i(x) = - \frac{1}{t}$$
根据这样的解释我们可以给出另外一种方法Primal-Dual Interior Point Method。

Primal-Dual Interior Point Method

根据Barrier Method的KKT解释，我们可以尝试一步解决问题。即首先选定$t$值，然后通过解如下的等式来解决最优化问题：

$$\nabla f_0(x) + \sum_{i=1}^{i=m}{ \lambda_i \cdotp f_i(x) } + A^T \cdotp \mu = 0$$
$$Diag(f_i(x)) \cdotp \lambda = \frac{-1}{t} \bf 1$$
$$A \cdotp x = b$$
其中第一个等式称为Dual Residual,第二个等式称为Primal Residual，第三个等式称为Centering Residual，使用公式$r(x, \lambda, \mu)$来代替三个等式。达到最优解的条件就是：$r(x, \lambda, \mu) = 0$。
直接使用牛顿法解决问题，假设迭代方向为$\nabla y = (\nabla x, \nabla \lambda, \nabla \mu)$，那么使用一阶近似
$$r(x + \nabla x, \lambda + \nabla \lambda, \mu + \nabla \mu) = r(x, \lambda, \mu) + Dr(x, \lambda, \mu) \cdotp (\nabla x, \nabla \lambda, \nabla, \nabla \mu) = 0$$
其中$Dr(x, \lambda, \mu)$定义如下：
$$\left| \begin{array}{ccc} \nabla ^ 2 f_0(x) + \sum_{i=1} ^ {i=m}{ \lambda_i \cdotp \nabla ^ 2 f_i(x) } & D f(x) ^ T & A ^ T \\ -diag(\lambda) \cdotp Df(x) & -diag(f(x)) & \bf 0 \\ A & \bf 0 & \bf 0 \end{array} \right| \left| \begin{array}{ccc} \nabla x \\ \nabla \lambda \\ \nabla \mu \end{array} \right| = -\left| \begin{array}{ccc} r_{dual} \\ r_{primal} \\ r_{centering} \end{array} \right|$$
基本来说可以使用线性方程组的方法解决这个问题。

总结

解决凸优化问题的方法可以认为是从简单到复杂的过程，每一步的解决依赖于前面一步的方法。所使用的手段就是泰勒展式，一阶或者二阶的近似。

Written with StackEdit.