Constrained Nonlinear Optimization

该文章思路是解决有限制条件的优化问题的方法。

这部分是非线性优化（针对任意函数$f(x)$）的有附加限制条件的优化。

有限制条件的非线性优化问题的形式：

$$\min_x f(x) \\ s.t \ g_i(x) \leq 0,\ i=1,...,m \\ h_i(x)=0, \ i=1,...,p$$

其中，$f(x)$是目标函数；$m$个不等式限制方程$g_i$；$p$个等式限制方程$h_i$。

对于限制优化问题，也有$Lagrangian$方程：

$$L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{i=1}^p \mu_i h_i(x)$$

对于每个限制方程，都有一个对应的对偶变量($dual\ variable$)：$\lambda_i$是$g_i(x)$的对偶变量，$\mu_i$是$h_i(x)$的对偶变量。

如何将$Lagrangian$方程$L(x,\lambda,\mu)$和原始优化方程$f(x)$联系起来呢？

$$\max_{\lambda \geq 0,\mu} L(x,\lambda,\mu)=\begin{cases} f(x), & if\ x\ is\ feasible \\ \infty, & otherwise \end{cases}$$

所以，$\min_{x \in \Omega}f(x)=\min_{x}\max_{\lambda \geq 0,\mu} L(x,\lambda,\mu)$

在一些假设下，可以交换最大化和最小化顺序：

$$\min_{x}\max_{\lambda \geq 0,\mu} L(x,\lambda,\mu)=\max_{\lambda \geq 0,\mu}\min_{x} L(x,\lambda,\mu)$$

KKT(Karush-Kuhn-Tucker) Conditions

满足KKT Conditions的$x^$的点的意义：在给定的约束条件下，$x^$是目标函数局部最优解的候选点。

Active Set:

对偶

对偶目标函数：

$$q(\lambda,\mu)=\min_x L(x,\lambda,\mu)$$

所以，对偶问题的形式是：

$$\max_{\lambda \geq 0,\mu} q(\lambda,\mu)$$

弱对偶性：对偶的目标函数的值比原始函数的值小，

$$q(\lambda,\mu) \leq f(x)$$

强对偶性：在一些条件下(Slater’s condition)，有，

$$q(\lambda^*,\mu^*)=f(x^*)$$

优化问题(Optimization Problem)的应用：支持向量机(Support Vector Machine)

Hard-Margin SVM

SVM: primal optimization problem

$$\max_{x,b} 2/ \|x\| \\ s.t. \ y^i(x^\mathrm{T}s^i+b) \geq 1.$$

将最大化转化成最小化：

$$\min_{x,b} \|x\|^2 /2\\ s.t. \ 1-y^i(x^\mathrm{T}s^i+b) \leq 0.$$

SVM: Dual Optimization Problem

Soft-Margin SVM

投影梯度法(Projected Gradient Mathod)

gradient descent + projection

什么是投影projection? 对于一个给定的点$x$，投影操作通常是找到一个点$x’$，使得$x’$在可行域内，并且距离$x$最近。所以，投影是满足限制条件的点中距离最近的。

投影梯度法有两个步骤：

• 执行无限制的梯度下降步骤：$x^{k+ {1\over 2}}=x^k-\eta_k\nabla f(x^k)$
• 计算在可行域$\Omega$上的投影：$x^{k+1}\in arg \min_{x\in \Omega}|x-x^{k+{1\over 2}}|$

PGD法只在投影操作cheap的时候有效。

SVM问题的解决方法：PGD

交替方向乘数法(ADMM, alternating direction method of multipliers)

对偶问题(Dual Problem)

原始问题：

$$\min_{x\in R^n} f(x)\ s.t.\ Ax=b$$

$Lagrangin$方程：

$$L(x,\lambda)=f(x)+\lambda^\mathrm{T}(Ax-b)$$ $$q(\lambda)=\min_{x\in R^n}\ L(x,\lambda)$$

对偶方程：

$$\max_{\lambda}\ q(\lambda)$$

得到对偶问题的解$\lambda^*$：

$$\lambda^*=arg\max_\lambda\ q(\lambda)$$

最终可以求得原始问题的解$x^*$：

$$x^*=arg\min_{x\in R^n}\ L(x,\lambda^*)$$

如何求解$\lambda^*$？使用梯度上升的方法。

对偶上升(Dual Ascent)：如何基于$\lambda^k$求$\lambda^{k+1}$

如何计算$\nabla q(\lambda^k)$？

已知$q(\lambda)=\min_{x\in R^n} L(x,\lambda)$，假设$\tilde{x}=arg\min_x L(x,\lambda)$，所以$q(\lambda)$可以改写为：

$$q(\lambda)=L(\tilde{x},\lambda)=f(\tilde{x})+\lambda^\mathrm{T}(A\tilde{x}-b).$$

方程的梯度（$q(\lambda)$对$\lambda$求导）是：

$$\nabla q(\lambda)=A\tilde{x}-b$$

所以，对偶上升法的步骤是：

对偶分解(Dual Decomposition)

假设方程$f(x_1,x_2,…,x_N)$是separable的，说明$f(x)$可以被分解成多个方程的乘积或和：

$$f(x_1,x_2,...,x_N)=g_1(x_1)\times g_2(x_2) \times ... \times g_N(x_N)$$ $$f(x_1,x_2,...,x_N)=g_1(x_1)+g_2(x_2)+...+g_N(x_N)$$

对偶分解指可以通过分解$Lagrangin$方程到各个维度分解对偶问题（假设变量$x$是$N$维向量），分解的原理如下：

$$f(x)=g_1(x_{(1)})+g_2(x_{(2)})+...+g_N(x_{(N)}),\ where\ x=(x_{(1)},x_{(2)},...,x_{(N)})^\mathrm{T}$$

所以，我们可以得到：

$$\lambda^\mathrm{T}Ax=\lambda^\mathrm{T}(A_1,...,A_N)\begin{pmatrix} x_{(1)} \\ ... \\ x_{(N)} \end{pmatrix}=\lambda^\mathrm{T}A_ix_{(i)}$$

$Lagrangin$方程是separable的，我们可以得到：

$$L(x,\lambda)=L_1(x_{(1)},\lambda)+...+L_N(x_{(N)},\lambda),\ L_i(x_{(i)},\lambda)=g_i(x_{(i)})+\lambda^\mathrm{T}(A_ix_{(i)}-b_{(i)})$$

可以将$x=(x_1,x_2,…,x_N)$的最小化分解为$N$个分离的最小化问题，其中第$i$维变量在第$k+1$轮次的最小化问题是：

$$(x^{k+1})_i=arg\min_{x_{(i)}}\ L_i(x_{(i)},\lambda^k)$$

其中，$\lambda^k$是第$k$轮求得的对偶问题的结果。

乘数方法(Methods of Multipliers)

对$Lagangin$方程新增一项$(\rho / 2)| Ax-b |^2$，可以得到$Augmented\ Lagrangin$：

$$L_\rho(x,\lambda)=f(x)+\lambda^\mathrm{T}(Ax-b)+(\rho / 2)\| Ax-b \|^2$$

所以，原始优化问题是：

$$\min_x f(x)+(\rho / 2)\| Ax-b \|^2\ s.t.\ Ax-b=0$$

乘数方法步骤

• 第一步是$x$的最小化操作。
• 第二步是对偶变量上升操作，在对偶上升中将$\etak=\rho$，以及$\nabla L\rho(x,\lambda)=Ax^{k+1}-b$。

$for\ k=0,1,…,K-1\ do \
\qquad Set\ x^{k+1}=arg\minx L{\rho}(x,\lambda^k) \
\qquad Set\ \lambda^{k+1}=\lambda^k+\rho(Ax^{k+1}-b)
$

交替方向乘数方法(ADMM,Alternating Direction Method of Multipliers)

该方法用于处理两个变量$x$和$z$的优化问题。

主要(Primal)优化问题：

$$\min_{x,z} f(x)+g(z)\ s.t.\ Ax+Bz=c$$

The augmented Lagrangin is:

$$L_\rho(x,z,\lambda)=f(x)+g(z)+\lambda^\mathrm{T}(Ax+Bz-c)+(\rho / 2)\| Ax+Bz-b \|^2 \\ \nabla L_\rho(\lambda)=Ax+Bz-c$$

ADMM

ADMM方法的最优解的条件

缩放对偶变量的ADMM方法

将$u^k=\rho^{-1}\lambda^k$操作称为缩放对偶变量。

---

• ← Previous Post
• Next Post →