0
$\begingroup$

Fix $a \in \mathbb R^n$, $r \ge 0$, $p \in \{1,2\}$, and a positive-definite matrix $C$ of order $n$. Define $u:\mathbb R^n \to \mathbb R$ by $u(x) := \|x-a\|_C + r\|x\|_p$, where $\|z\|_C := \sqrt{z^\top C z}$.

Question. Is there a simple, direct, efficient, firs-order provably convergent algorithm for computing a minimizer of $u$ ?

A cumbersome solution via primal dual algorithms

Define $K := C^{1/2}$, $b := K^{-1} b$, and functions $f,g :\mathbb R^n \to \mathbb R$ by $f(x) = \|x-b\|_2$ and $g(x) := \|x\|_p$.

$$ \inf_x u(x) = \inf_x f(Kx) + g(x) = \inf_xg(x)+\sup_y \langle y,Kx\rangle - f^\star(y) = \inf_x\sup_y \langle y,Kx\rangle + g(x) - f^\star(y), $$

where $f^\star$ is the Fenchel-Legendre conjugate of $f$. Since the proximal operators for $g$ and $f^\star$ admit closed-form expressions, primal-dual algorithms can be used to compute a stationary-point $(x_0,y_0)$ in (2), including rates of converges. One would then use $x_0$ as an approximate minimizer for $u$.

However, I don't like PD algorithms because, compared to first-order direct methods, they tend to be tricker to fine-tune (not 1, but 2 stepsizes have to be properly set, etc.).

Improve this question
$\endgroup$
4
  • $\begingroup$ There is always the subgradient method for such problems. It satisfies all the properties you mentioned (the term "efficient" is not very informative without specifying the dimensions or the required accuracy). $\endgroup$
    – cheyp
    Commented Sep 4, 2022 at 9:51
  • $\begingroup$ Well, subgradient-methods are possibly one of the worst things to do here. For example, they'll typically have a convergence rate of $O(1/\sqrt{t})$, where as a simple PD scheme can ensure $O(1/t)$ in an ergodic sense... $\endgroup$
    – dohmatob
    Commented Sep 4, 2022 at 16:30
  • $\begingroup$ I know, but again if your dimension is 5 and you need to solve it with $\varepsilon=0.1$, it may be worth of a try. For primal-dual methods, you are right that you need two parameters. But if you know the norm of matrix $K$, then you can always take primal and dual steps equal, like $\alpha = \beta = \frac{1}{\|K\|}$. So it is also not that difficult. $\endgroup$
    – cheyp
    Commented Sep 4, 2022 at 17:38
  • $\begingroup$ This problem is structured. All the implicit gradients (aka prox operators) can be computed in closed-form; etc. Subgradient algorithms are not worth the try even for $d=1$ (my problems will typiclaly have large $d$). As for the stepsizes, yes those "oracle" choices (as proposed in Chambolle and Pock 20XY) are enough to get ergodic convergence, but are likely to be suboptimal for this problem. Another issue with PD algorithms is the sense in which convergence is implied. Very indirect. $\endgroup$
    – dohmatob
    Commented Sep 4, 2022 at 17:58

0

Reset to default

You must log in to answer this question.