📂Optimization

Proximal Minimization Algorithm

Definition¹

When solving the optimization problem for the objective function $f : \mathbb{R}^{n} \to \mathbb{R}^{n}$, the method of updating the optimal solution $\mathbf{x}^{(k)}$ by repeatedly applying the proximal operator is called the proximal minimization algorithm.

$$ \mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda f}(\mathbf{x}^{(k)}) = \argmin\limits_{\mathbf{v}} \left\{ \lambda f(\mathbf{v}) + \dfrac{1}{2}\left\| \mathbf{v} - \mathbf{x}^{(k)} \right\|_{2}^{2} : \mathbf{v} \in \mathbb{R}^{n} \right\} $$

Description

It is also known as the proximal point algorithm or proximal iteration.

In the optimization target, the term $\dfrac{1}{2}\left\| \mathbf{v} - \mathbf{x}^{(k)} \right\|_{2}^{2}$ prevents the updated $\mathbf{x}^{(k+1)}$ from straying too far from $\mathbf{x}^{(k)}$. It means to prevent it from being updated to a very different value suddenly. In other words, looking at the entire objective function, it can be seen that the optimal solution is updated in the direction of minimizing $f$ without straying too far from the previous step.