1
$\begingroup$

I am curious about the general relation between nested, successive minimization (M1) and asymptotic minimization (M2) as defined in the following. What one wants is to implicitly minimize a sequence of functions where each respective domain is based on the priorly obtained minimizers.

Problem setting. Let $D \subset \mathbb{R}^N$ be some suitable domain and let $$g_k: D \rightarrow \mathbb{R}, \quad k = 0,\ldots,n$$ be continuous functions that have well defined minima. Further, let $$G_\gamma: D \rightarrow \mathbb{R}, \quad G_\gamma(a) := \sum_{k = 0}^n \gamma^{n-k} g_k(a), \quad \gamma > 0.$$

(M1): Let $A_{n+1} := D$ and successively define $$A_k := \{ a \in A_{k+1} \mid g_k(a) = \min_{b \in A_{k+1}} g_k(b) \}, \quad k = n,n-1,\ldots,0.$$ Then set $S_{M1} := A_0$.

(M2): Define $$ S_{M2} := \{ a^\ast \in D \mid \exists (a_\gamma)_{\gamma > 0} \subset D, \ a^\ast = \lim_{\gamma \searrow 0} a_\gamma, \ G_\gamma(a_\gamma) = \min_{a \in D} G_\gamma(a)\}.$$ So this set consists of the limits of minimizers of $G_\gamma$ for $\gamma \searrow 0$.

Question. How little assumptions are required such that $S_{M2} = S_{M1}$ or at least $S_{M2} \subset S_{M1}$?

The interesting situation is of course when the functions $g_k$ are flat around their minimizers.


I am fairly convinced that the sets are commonly equal. In other words, it requires some work to come up with functions for which the sets are not equal, but this is if course a completely informal statement.

Despite some knowledge about the situation (for $n > 1$), I struggle to find literature on this, basically because I do not really know where to start.

  • Can you provide literature about this problems, or suggest under which phrase to search?
  • Can you provide less restrictive assumptions as (A1) laid out below?
  • Can you provide further reaching counter examples as (C1) below?
  • Does the relation always hold if one considers local instead of global minima?

(A1) Let $D = \mathbb{R}^N$ and $s \geq 0$. Assume that for $k = s+1,\ldots,n$ $$\underset{a \in D}{\mathrm{argmin}} \ g_k(a) \subset \underset{a \in D}{\mathrm{argmin}} \ g_{k+1}(a).$$ Then $S_{M2} \subset A_s$. Thus, if additionally $A_s$ contains only one element and $S_{M2}$ is not empty, then $S_{M2} = S_{M1}$.


(C1): For $n = 2$, let $$g_2(x) := \begin{cases} 0 &,\ x < 0 \\ x^2 &,\ x \geq 0 \end{cases}, \quad g_1(x) := \begin{cases} 0 &,\ x < 0 \\ -x &,\ x \in [0,1] \\ -1 &,\ x > 1 \end{cases}, \quad g_0(x) := \begin{cases} \frac{2|x + \frac{1}{2}| - 1}{8} &,\ x < 0 \\ 0 &,\ x \geq 0 \end{cases}. $$ Then $A_2 = (-\infty,0] = A_1$ and thus $S_{M2} = A_0 = \{-\frac{1}{2}\}$. On the other hand, it is $$G_\gamma(x) = \begin{cases} \frac{2|x + \frac{1}{2}| - 1}{8} \gamma^2 &,\ x < 0 \\ x^2 -\gamma x &,\ x \in [0,1] \\ x^2 + \gamma x - 2\gamma &,\ x > 1 \end{cases}$$ Short calculation shows $-\frac{\gamma^2}{8} = G_\gamma(-\frac{1}{2}) = \min_{x < 0} G_\gamma(x)$ and $-\frac{\gamma^2}{4} = G_\gamma(\frac{\gamma}{2}) = \min_{x \geq 0} G_\gamma(x)$. So the minimum within $(-\infty,0]$ is hidden, and we obtain $S_{M2} = \{0\}$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.