Variational Inequalities, Monotone Operators, and Proximal Methods¶
Job: develop the VI (Stampacchia), the monotone operators (maximal / resolvent), the proximal point / ADMM / Douglas–Rachford, and the mirror descent / Bregman — with the ADMM / Lasso as the worked example.
Core¶
The variational inequality (VI)¶
| VI / complementarity / Stampacchia | Description |
|---|---|
| VI\((F,C)\) | find \(x\in C\) with \(\langle F(x),y-x\rangle\ge0\,\forall y\in C\) (the Stampacchia) |
| Complementarity (CP) | \(C=\mathbb{R}^n_+\): \(x\ge0, F(x)\ge0, \langle F(x),x\rangle=0\) (the CP) |
The monotone operator¶
| Monotone / maximal / resolvent | Description |
|---|---|
| Monotone \(T\) | \(\langle T(x)-T(y),x-y\rangle\ge0\) (the monotone) |
| Maximal monotone | the graph the maximal (the Minty–Rockafellar) |
| Resolvent \(J_T\) | \(J_T=(I+T)^{-1}\) (the proximal, the nonexpansive) |
The proximal point algorithm and the splitting¶
| Proximal point / convergence / ADMM | Description |
|---|---|
| Proximal point | \(x_{k+1}=J_{\lambda T}(x_k)=(I+\lambda T)^{-1}(x_k)\) (the Rockafellar) |
| Convergence | the monotone the convergence (the Rockafellar) |
| Douglas–Rachford / ADMM | the splitting (\(f+g\), the \(x_{k+1}=\mathrm{prox}_{\rho f}, z_{k+1}=\mathrm{prox}_{g/\rho}\), the ADMM) |
The convex-concave and the mirror descent¶
| Convex-concave / mirror descent / Bregman | Description |
|---|---|
| Saddle | \(\min_x\max_y L(x,y)\) (the convex-concave, the game theory) |
| Mirror descent | the Bregman divergence \(D_\phi(x,y)\) (the mirror, the information theory) |
| ODE / SDE | the mirror descent the continuous / the stochastic (the SDE) |
See it¶
Proximal point and the ADMM for the \(\ell_1\) / Lasso. The Lasso \(\min\frac12\|Ax-b\|^2+\lambda\|x\|_1\) (the composite \(f+g\)). The ADMM: \(x=z\), \(f(x)+g(z)\) the splitting, \(x_{k+1}=\mathrm{prox}_{\rho f}(z_k-u_k)\), \(z_{k+1}=\mathrm{prox}_{g/\rho}(x_{k+1}+u_k)\) (the splitting, the \(\mathrm{prox}\)). The \(\ell_1\): \(\mathrm{prox}_{\lambda\|.\|_1}\) the soft-thresholding \(S_\lambda(v)=\mathrm{sign}(v)\max(|v|-\lambda,0)\), the \(z_{k+1}=S_{\lambda/\rho}(x_{k+1}+u_k)\) (the soft-thresholding, the ADMM). The key point: the ADMM the splitting the Lasso, the \(\mathrm{prox}\) the soft-thresholding — the proximal / monotone the composite.
Check¶
Show that the ADMM splitting for the Lasso gives the soft-thresholding, and explain the proximal point.
The Lasso \(\min\frac12\|Ax-b\|^2+\lambda\|x\|_1\) (the \(f=\frac12\|Ax-b\|^2\), \(g=\lambda\|x\|_1\)). The ADMM: \(x=z\), the \(f(x)+g(z)\), the \(x_{k+1}=\mathrm{prox}_{\rho f}(z_k-u_k)=(\rho I+A^TA)^{-1}(A^Tb+z_k-u_k)\) (the ridge), the \(z_{k+1}=\mathrm{prox}_{g/\rho}(x_{k+1}+u_k)=S_{\lambda/\rho}(x_{k+1}+u_k)\) (the soft-thresholding \(S\)). The proximal point: the \(x_{k+1}=J_{\lambda T}(x_k)=(I+\lambda T)^{-1}\) (the Rockafellar, the monotone). The \(\ell_1\) the soft-thresholding, the ADMM the splitting.
Explain the monotone operator and the resolvent, and the maximal monotone.
The monotone: \(\langle T(x)-T(y),x-y\rangle\ge0\) (the monotone). The maximal: the graph the maximal (the Minty–Rockafellar, the no proper monotone extension). The resolvent: \(J_T=(I+T)^{-1}\) (the proximal, the nonexpansive \(\|J_T(x)-J_T(y)\|\le\|x-y\|\)). The proximal point: \(x_{k+1}=J_{\lambda T}(x_k)\) (the Rockafellar, the monotone the convergence). So the monotone the maximal, the resolvent the proximal, the convergence.
Pitfalls¶
- The VI the Stampacchia (the \(\langle F(x),y-x\rangle\ge0\), the complementarity) — the VI the Stampacchia, the CP the \(\mathbb{R}^n_+\).
- The maximal monotone (the graph the maximal, the Minty–Rockafellar) — the maximal the no-extension, the resolvent the nonexpansive.
- The ADMM the splitting (the \(f+g\), the soft-thresholding) — the ADMM the splitting, the \(\mathrm{prox}\) the soft-thresholding.
- The mirror descent (the Bregman, the information theory) — the mirror the Bregman, the ODE / SDE the continuous.
Refs¶
- Rockafellar, "Monotone operators and the proximal point algorithm" (SIAM 1976); the Minty–Rockafellar
- Boyd–Parikh–Chu–Peleato–Eckstein, "Distributed optimization via ADMM" (2011); the ADMM
- Bauschke–Combettes, Convex Analysis and Monotone Operator Theory; the proximal / splitting
- Nemirovski–Yudin, the mirror descent; the Bregman divergence
Next¶
Opt index · Foundations · Conic & SDP · Nonconvex & Landscape · Online & Stochastic · Game theory · Information theory