机器学习笔记–约束优化

学习笔记

优化问题

我们称在$x$的某些集合$S$中找$f(x)$的最大值和最小值为约束优化问题。集合$S$内的点成为可行点。

约束优化问题的通用形式如下:
$$\{\begin{array}{rl}\min & f(x)\\ s.t.& g_i(x)\le 0,i=1,2,...,q\\ & h_j(x)=0,j=q+1,...,m\\ & x\in D\end{array}$$

其中$f(x)$是优化的目标函数，$g_i(x)\le 0$是不等式约束，$h_j(x)=0$是等式约束，D={x∈Rn∣li≤xi≤ui,li,ui∈R,i=1,2,...,n}D=\{x\in R^n|l_i\le x_i \le u_i, l_i, u_i \in R, i=1, 2,..., n\}D={x∈Rn∣li​≤xi​≤ui​,li​,ui​∈R,i=1,2,...,n}是搜索空间， $D$中所有满足约束条件的解构成可行域$S$，即S={x∣x∈D,gi(x)≤0,i=1,2,...,q,hj(x)=0,j=q+1,...,m}S=\{x| x\in D, g_i(x)\le 0, i=1,2,...,q,h_j(x)=0,j=q+1,...,m\}S={x∣x∈D,gi​(x)≤0,i=1,2,...,q,hj​(x)=0,j=q+1,...,m}。

若在$x^{\ast }\in D$的邻域内的所有点$x$满足：$f(x\ast )<f(x)$，则称$x^{\ast }$为局部最优解；若对$\forall x\in D$，有$f(x^{\ast })<f(x)$，则称其为全局最优解。考虑到算力问题，目前的最优解多为局部最优解。

对于上述优化问题，传统的解决方法是从约束问题形式出发，通过变形，将原本复杂的问题转变为相对简单的问题。传统方法存在以下问题：

1. 传统的基于梯度的优化方法无法获得全局最优解，容易陷入局部最优。并且在实际问题中往往伴随更新过快或过慢的问题。牛顿法在一定程度上解决了更新过慢的问题，添加梯度更新学习率可以防止更新过快而错过最优解。
2. 对于实际问题，往往维数较高，因此在优化曲面中存在多个极小点，因此使得部分基于梯度的优化算法失效。另一方面，梯度优化方法要求目标函数在可行域内连续，并不是每次都能得到满足。
3. 梯度方法无法在非凸或不连通优化问题中奏效。

进化算法是求解优化问题的全局优化方法，其灵感来自于大自然的生物进化，是一种成熟的具有高鲁棒性和广泛适用性的优化算法。目前接触到的有遗传算法、粒子群优化算法、人工蜂群算法。只是接触，并未深入了解。此处留一坑，下图是人工蜂群算法思路图（很大自然）。

拉格朗日乘子法(KKT方法)

KKT方法是针对约束优化问题的一个通用方法。引入新的变量${\lambda }_i$和${\alpha }_i$，引入的变量被称为KKT乘子。通过新的变量，我i们的目标函数可以更改为：$$L(x,\lambda ,\alpha )=f(x)+\sum _i{\lambda }_i{g}^i(x)+\sum _j{\alpha }_j{h}^j(x)$$
该式被称为广义Largrangian函数。

我们的优化问题可以转化为：
$$\underset{x}{\min }\underset{\lambda }{\max }\underset{\alpha ,\alpha >0}{\max }L(x,\lambda ,\alpha )$$
可以这么修改的原因在于，对于可行域$S$之外的点，该约束都有$$\underset{\lambda }{\max }\underset{\alpha ,\alpha >0}{\max }L(x,\lambda ,\alpha )=\infty$$
这些性质确保了不可行点不会只最优解，而可行域范围内的最优点不变。

上述的KKT方法是基于优化问题的标准形式的，对于非标准形可通过以下方法进行转化：

1. 对于${\max }_{i}Z$,通过变换${\min }_i-Z$
2. 对于${\sum }_{j=1}^n{a}_{ij}{x}_j\le b_i$， 加入松弛变量$y_i$，使${\sum }_{j=1}^n{a}_{ij}{x}_j+y_i=b_i,y_i\ge 0$
3. 对于${\sum }_{j=1}^n{a}_{ij}{x}_j\ge b_i$，加入剩余变量$y_i$， 使${\sum }_{j=1}^n{a}_{ij}{x}_j-y_i=b_i,y_i\ge 0$
4. 对于$b_i<0$，考虑$-{\sum }_{j=1}^n{a}_{ij}{x}_j=-b_i$
5. 对于$x_j<0$，考虑$-x_j\ge 0$，若$x_j$任意，则考虑$x_j^{{}^{\prime }}-x_j^{{}^{\prime \prime }},x_j^{{}^{\prime }}\ge 0,x_j^{{}^{\prime \prime }}\ge 0$

我们可以使用一组简单的性质来描述约束优化问题的最优点。这些性质称为$Karush-Kuhn-Tucker$（KKT）条件。这些是确定一个点是最优点的必要条件，但不一定是充分条件。这些条件是：

• 广义Lagrangian的梯度为0
• 所有关于$x$和KKT乘子的约束都满足
• 不等式约束显示的“互补松弛性”：$\alpha \odot h(x)=0$ 。（$\odot$表示同或，当两者符号不同时为0）

对偶问题

对优化问题：
$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}||w|{|}^2\\ s.t.& y_i(w^T{x}_i+b)\ge 1,i=1,2,...,m.\end{array}$$
可以使用拉格朗日乘子法得到其“对偶问题”。对上式篾条约束添加拉格朗日乘子${\alpha }_i\ge 0$，则该问题的拉格朗日函数可写为：
$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b))$$
其中$\alpha =({\alpha }_1,{\alpha }_2,...,{\alpha }_m)$.令$L(w,b,\alpha )$对$w$和$b$的偏导为0（KKT条件的第一个条件）可得：
$$w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$$ $$0=\sum _{i=1}^m{\alpha }_i{y}_i$$
带入原式即可消去$w$和$b$， 并化简可得：
$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ s.t.& \sum _{i=1}^m{\alpha }_i{y}_i=0,\\ & a_i\ge 0,i=1,2,...,m\end{array}$$
上述过程满足的KKT条件为：
$$\{\begin{array}{rl}& {\alpha }_i\ge 0;\\ & y_{i}f(x_i)-1\ge 0(约束);\\ & {\alpha }_i(y_{i}f(x_i)-1)=0(互补松弛性).\end{array}$$
对任意训练样本$(x_i,y_i)$，总有${\alpha }_i=0$或$y_{i}f(x_i)=1$。若${\alpha }_i=0$， 则该样本将不会在求和中出现，也就不会对$f(x)$有任何影响。若${\alpha }_i>0$，则必有$y_{i}f(x_i)=1$， 所对应的样本点位于最大间隔边界上，是一个支持向量。