有约束优化概述

有约束优化概述

基本的观点是有约束优化都是类似于盖房子。首先是最基本的砖块，然后才是有各种各样的用砖块建的房子。这个最基本的砖块就是线性约束的二次优化问题。

线性等式约束的二次优化(Equality Constrained Qudratic Programming)

需要优化的目标具有如下的形式：

$$1/2 x ^ T Q x \; + q ^ T x$$
$$s.t. \quad A \cdotp x = b$$
对应的KKT条件表述如下：
$$A \cdotp x = b$$
$$Qx + q + A ^ T \lambda = 0$$
那么解决优化问题就是求解对应的线性方程组的解。可以使用直接解法，比如使用Cholsky分解，或者使用Symmetric Indefinite Decomposition；另外的方法包括使用梯度下降法解决问题。

有等式约束的一般优化问题

有等式约束的一般优化问题如下：

$$argmin_x f(x)$$
$$s.t. A x = b$$
如果使用二阶泰勒展式如下：
$$argmin_x \; f(x_k + p) = f(x_k) + \nabla f(x_k) p + 1/2 p ^ T \nabla ^ 2 f(x) p$$
$$s.t. \quad A(x_k + p) = b$$
可以看到当前的问题已经转化成线性等式约束的二次优化问题。

一般的二次优化问题

优化的问题可以定义如下：

$$argmin_x \; 1/2 x ^ T Q x + \; + q ^ T x$$
$$s.t. \quad c_i(x) \le 0$$
$$\; \quad \quad A \cdotp x = b$$
对这个问题的解决方法有Active-Set和Interior Point两种不同的方法，但是这两种方法对应两种大分类，后面慢慢的介绍。

一般优化问题

优化的目标是可导的即可，解决的问题如下：

$$argmin_x \; f(x)$$
$$s.t. \quad c_i(x) \le 0 \quad (i=1, 2, ..., m)$$
$$\; \quad \quad h_i(x) = 0 (i=1, 2, ..., p)$$
对于问题有三大类不同的方法了。

Penalty or Augmented Lagrangian Method

这类方法的基本想法是将约束条件以某种格式加入到目标函数中，使得有约束的优化问题变成无约束的优化问题。但是这里使用的是逼近的方法，因此某种程度上只是在不停的逼近最正确的解。对于Penalty Method，需要优化如下的目标函数：

$$argmin_x \; f(x) + \mu ^ 2 \sum_{i=1}^{m}{c_i(x) ^ 2} + 1/2 \cdotp \mu ^ 2 \sum_{i=1}^{p}{c_i(x) ^ 2}$$
为了获得较好的近似解，需要不停的增加$\mu$值，但是这样会导致问题很难求解。
对于Augmented Lagrangian Method，需要优化如下的目标函数：
$$argmin_x \; f(x) - \sum_{i=1}^{m}{ \lambda_i c_i(x)} + 1/2 \cdotp \mu \sum_{i=1}^{p}{c_i(x) ^ 2}$$
相比于之前的Penalty Method，在这个方法中显示的加入了拉格朗日项。

Sequential Quadratic Programming

从这个名称可以看出，这个方法对一般优化问题的处理时会将这个问题转化成二次优化问题，通过不停的解决二次优化问题来获得问题的解。这个方法遵循以下的策略：

Equality Quadratic Programming

这个策略选择不等式约束的一个子集，并假定这个集合中的不等式约束全部激活，然后优化对应的二次优化问题，根据求解的结果不停的优化这个子集。

Inequality Quadratic Programming

这个策略直接求解有不等式约束的二次优化问题，然后给出最终问题的Active Set集合。
以只有等式约束的一般优化问题为例：

$$argmin_x \; f(x)$$
$$s.t. \quad \quad \; c_i(x) = 0 (i=1, 2, ..., m)$$
对应的KKT条件如下：
$$\nabla f(x) + A ^ T \lambda = 0$$
$$c_i(x) = 0$$
其中$A ^ T = \left[ \nabla c_1(x), ..., \nabla c_m(x) \right]$可以使用牛顿法解决这个问题。对应的方程组可以转化成一个二次优化问题对应的KKT条件，这样就转化成一个二次优化问题了。

Interior Point Method

内点法和Log Barrier方法可以同等对待。内点法直接将问题做如下的转换：

$$argmin_x \; f(x) + \sum_{i=1} ^ {m} { log(c_i(x))}$$
$$s.t. \quad \quad h_i(x) = 0 \; (i=1, 2, ..., p)$$
可以看到这里强制要求所有的不等式必须严格满足，这就是这类方法称为内点法的原因。相比于一般的KKT条件，内点法解决的问题对应一个互补条件(Complementary Condition)放松的问题，解决对应的KKT等式即可。

这个就是简短的回顾了，稍后会补上对应的code。

Written with StackEdit.