Convex quartic problems: homogenized gradient method and preconditioning
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914766075723776 |
|---|---|
| author | Dragomir, Radu-Alexandru Nesterov, Yurii |
| author_facet | Dragomir, Radu-Alexandru Nesterov, Yurii |
| contents | We consider a convex minimization problem for which the objective is the sum of a homogeneous polynomial of degree four and a linear term. Such task arises as a subproblem in algorithms for quadratic inverse problems with a difference-of-convex structure. We design a first-order method called Homogenized Gradient, along with an accelerated version, which enjoy fast convergence rates of respectively $\mathcal{O}(κ^2/K^2)$ and $\mathcal{O}(κ^2/K^4)$ in relative accuracy, where $K$ is the iteration counter. The constant $κ$ is the quartic condition number of the problem.
Then, we show that for a certain class of problems, it is possible to compute a preconditioner for which this condition number is $\sqrt{n}$, where $n$ is the problem dimension. To establish this, we study the more general problem of finding the best quadratic approximation of an $\ell_p$ norm composed with a quadratic map. Our construction involves a generalization of the so-called Lewis weights. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_17683 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Convex quartic problems: homogenized gradient method and preconditioning Dragomir, Radu-Alexandru Nesterov, Yurii Optimization and Control 90C25 We consider a convex minimization problem for which the objective is the sum of a homogeneous polynomial of degree four and a linear term. Such task arises as a subproblem in algorithms for quadratic inverse problems with a difference-of-convex structure. We design a first-order method called Homogenized Gradient, along with an accelerated version, which enjoy fast convergence rates of respectively $\mathcal{O}(κ^2/K^2)$ and $\mathcal{O}(κ^2/K^4)$ in relative accuracy, where $K$ is the iteration counter. The constant $κ$ is the quartic condition number of the problem. Then, we show that for a certain class of problems, it is possible to compute a preconditioner for which this condition number is $\sqrt{n}$, where $n$ is the problem dimension. To establish this, we study the more general problem of finding the best quadratic approximation of an $\ell_p$ norm composed with a quadratic map. Our construction involves a generalization of the so-called Lewis weights. |
| title | Convex quartic problems: homogenized gradient method and preconditioning |
| topic | Optimization and Control 90C25 |
| url | https://arxiv.org/abs/2306.17683 |