0
$\begingroup$

Imagine you have e.g. the following optimization objective over a joint $D$-dimensional real-valued space, i.e.

$x^* = \min_{x} f(x), \quad x \in \mathbb{R}^D$

And then you have the following relaxation over the $D$ individual, separate components:

$\hat{x}_i^* = \min_{\hat{x}_i} g(\hat{x}_i), \quad \hat{x}_i \in \mathbb{R}, \; i \in \{1, \dots, D \}$

Obviously, these are not necessarily equivalent since the relaxation doesn't take interactions among components into account. As with all relaxations, it is expected to be easier to solve, since all $\hat{x}_i$ components are treated independently and the respective search spaces are exponentially smaller. And the relaxed optimum $\hat{x}$ might be off from the original one $x$, leading to worse results.

An example would be assuming that a multivariate Random Variable has a diagonal covariance matrix, when fitting said RV to a given dataset. This is usual e.g. in variational approaches.

But independently of the application, and in its most general sense, I'd assume this to be a fairly popular relaxation, does it have a name? Could anyone point me to materials in the general context of optimization theory? (i.e. specific instances of relaxations are fine as long as this joint-to-parts element is treated on the foreground and in a general manner)

$\endgroup$
3
  • $\begingroup$ I think a general framework to describe every instance of an optimization problem being decomposed in such a way (which can take such forms as by a simplifying independence assumption, coordinate descent as mentioned below, etc.) is perhaps slightly ambitious $\endgroup$
    – gfppoy
    Commented May 17, 2021 at 15:57
  • $\begingroup$ Note that I'm not asking for ways to solve this, rather pointers to previous work studying this and ideally giving it a name $\endgroup$
    – fr_andres
    Commented May 17, 2021 at 16:28
  • 1
    $\begingroup$ What I mean is such a decomposition can occur in such varied settings that to classify all such instances under one general class of optimization problems and expecting that classification to be meaningful seems ambitious. $\endgroup$
    – gfppoy
    Commented May 18, 2021 at 9:20

1 Answer 1

1
$\begingroup$

Coordinate descent algorithms might be something along those lines. An interesting application at http://statweb.stanford.edu/~tibs/ftp/lasso-retro.pdf.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .