有条件凸优化问题

在这一部分我们讨论有条件约束的凸优化问题。其中，根据凸优化问题的定义，约束必须是仿射的。

KKT Conditions (Lagrange Conditions)

在数学分析中我们得到了对于函数\(f(x)\)和一系列等式约束\(h_i(x)=0,i \in [k]\)，\(x\)取极值的必要条件为存在乘子\(\lambda_1,\cdots,\lambda_k\)使得\(\nabla f(x)+\sum\limits_{i \in [k]}\lambda_i\nabla h_i(x)=0\)。它可以简写为拉格朗日函数\(L(x,\lambda)=f(x)+\sum\limits_{i \in [k]}\lambda_i h_i(x)\)，要求\(\nabla L(x,\lambda)=0\)。它的直观是，\(\nabla f(x)\)与\(x\)处的切空间垂直，每个\(\nabla h_i(x)\)也都与切空间垂直，因此极值点处的梯度向量要落在各个约束函数在该点的梯度向量张成的空间里。（这里我们要求\(h_i(x)\)是线性独立的。）对于凸函数，拉格朗日条件是充分必要的。

对于一般的约束，既存在等式约束\(h_i(x)=0\)，还存在一系列不等式约束\(g_i(x) \leq 0\)。此时我们想要把不等式的约束转化为等式的约束。如果把对于极值点\(x^*\)处所有不紧的约束\(g_i(x)\leq 0\)扔掉会如何？这样只会留下\(h_i(x)=0\)以及一部分\(g_j(x)=0\)，余下的满足\(g_k(x^*)<0\)。由于连续性，在极值点周围的小邻域内依然成立\(g_k(x^*)<0\)，所以在这个邻域内只留下紧的\(g_j(x)=0\)和原先的\(h_i(x)=0\)求约束下的极值，依然会得到\(x^*\)。也就是说，\(x^*\)在新的约束下依然是一个极小值点，因此扔掉不紧的约束后我们\(x^*\)依然会出现在我们的解集中。

现在我们要把上面的过程形式化地写出来，这样就得到了不等号约束下的极小值点的必要条件，称为KKT条件。如果\(x^*\)是极小值点，那么存在\(\lambda_1,\cdots,\lambda_k\)以及\(\mu_1,\cdots,\mu_m\)，满足\(\nabla f(x^*)+\sum\limits_{i\in[k]}\lambda_i\nabla h_i(x^*)+\sum\limits_{j\in [m]}\mu_j\nabla g_j(x^*)=0\)，\(\forall j \in [m],\mu_j \geq 0\)\(,\mu_jg_j(x^*)=0\)。这样，如果\(g_j\)不紧，\(\mu_j\)就会自动取\(0\)，余下的就是拉格朗日条件了。注意到我们必须特别地限制\(\mu_j\geq 0\)，在拉格朗日条件中并没有这一条，因为我们可以证明如果没有这一条性质我们是能够在某些情形下导出矛盾的，\(\mu_j \geq 0\)的要求本身就被蕴含在了\(x^*\)是极小值点里。同样的，在凸函数情形下KKT条件是充要条件。

在用KKT条件求解最小值时，我们一般需要分类讨论每个\(g_j\)是否是紧的（共\(2^m\)种情况），或者等价地讨论每个\(\mu_j\)是否为0。

在无条件的凸优化问题中，我们知道凸函数取到极值的充分必要条件是\(\nabla f(x)=0\)。而正是因为这个条件的闭式解通常难以求解，我们才诉诸数值计算，或是使用梯度下降、牛顿法等算法来逼近最优值。同样地，在有条件的凸优化问题中，我们有了KKT条件（对于凸函数同样是充分必要的），这个条件本质上也要解函数梯度为零的方程，因此我们同样需要诉诸其它手段。

Projected Gradient Descent(投影梯度下降)

对应于无条件凸优化中的梯度下降法， 在有条件约束时我们有“投影梯度下降法”。

如果我们暂时抛开约束不看，直接应用普通的梯度下降法来求解有约束情形的问题，那么唯一产生的问题是我们有可能在某一步迭代中跑到了可行域外面。于是对于跑到外面的情况，我们强行把它拉回可行域内，采用的方法就是找到可行域内里当前点最近（欧氏距离最小）的点——当前点在可行域上的投影。这就是投影梯度下降法。严格地，为了求解\(\min\limits_{x \in X}f(x)\)，我们从\(x_0\)出发做迭代：\(x_{k+1}=\text{project}_X(x_k-t_k\nabla f(x_k))\)。什么时候停止呢？我们可以把迭代写成这样的形式，\(x_k-x_{k+1}=x_k-\text{project}_X(x_k-t_k\nabla f(x_k))\)，令右式等于\(t_kg(x_k)\)，从而配凑出\(x_{k+1}=x_k-t_kg(x_k)\)这个形式——这与一般梯度下降的迭代形式相同，并且我们通过凸函数的简单性质容易证明\(g(x)\)在这里恰好扮演了一个“梯度”的角色。可以证明\(f\)取到有条件极值当且仅当\(g(x)=0\)。于是我们只需当\(g(x)=0\)或充分小时结束算法即可。

一个有意思的事实是，这个算法的本质就是近端梯度下降算法。我们定义一个关于可行域的indicator \(I_X(x)\)，当\(x \in X\)时取0，否则取\(+\infty\)。这样\(\min\limits_{x \in X}f(x)\)等价于\(\min\limits_{x}\{f(x)+I_X(x)\}\)，后者是一个无条件极值问题。应用近端梯度下降，把\(I_X(x)\)看成\(h(x)\)，发现算子\(\text{prox}_{I_X}(y)=\arg\min\limits \{\dfrac{1}{2}\|x-y\|_2^2+I_X(x)\}\)恰好就是投影\(\text{projext}_X(y)\)，就可以把投影梯度下降改写为近端梯度下降：\(x_{k+1}=\text{prox}_{t_kI_X}(x_k-t_k\nabla f(x_k))\)。根据近端梯度下降的收敛分析，直接得到投影梯度下降的收敛分析：对于\(L\)-smooth的凸函数\(f\)，取步长\(t<\dfrac{1}{L}\)时有\(f(x_k)-f(x^*)\leq\dfrac{\|x^*-x_0\|_2^2}{2tk}\)，可见函数值的差值有一个与迭代次数成反比的上界。特别地，当\(f\)是\(m\)-strongly convex时，有\(\|x^*-x_{k+1}\|_2^2 \leq\)$ (1-mt)|x^*-x_k|_22$，可见自变量距离指数递减。

当然，投影梯度下降算法使用的前提是投影是容易计算的。对于复杂的可行域，投影是难以计算的。但是在方形的、球形的（椭球形的）、仿射的等等这些特殊的可行域上，投影是容易计算的。这时候就可以使用投影梯度下降法。