On the exactness of Lasserre relaxations and pure states over real closed fields (Q2007851)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the exactness of Lasserre relaxations and pure states over real closed fields |
scientific article |
Statements
On the exactness of Lasserre relaxations and pure states over real closed fields (English)
0 references
22 November 2019
0 references
The paper under review is concerned with the following problems. For \(\underline{g} = (g_{1}, \dots, g_{m}) \in \mathbb{R}[\underline{X}]^{m}\), where \(\underline{X} = (X_{1}, \dots, X_{n})\) and \(n, m \in \mathbb{N}_+\), solve in \(\mathbb R^n\) the system \[ g_{1}(x) \geq 0, \dots, g_{m}(x) \geq 0 \] of polynomial inequalities. For \(f \in \mathbb{R}[\underline{X}]\), compute the infimum of \(f\) on the solution set \(S(\underline{g})\) of the preceding system, and if the infimum is a minimum, find the corresponding minimizers. Given \(d \in \mathbb{N}\), let \[ M_{d}(\underline{g}) = \left\{\sum_{i=0}^{m}\sum_{j}p_{ij}^{2}g_{i} \mid p_{ij} \in \mathbb{R}[\underline{X}], \deg(p_{ij}^2g_i) \leq d\right\}, \] \[ S_{d}(\underline{g}) = \bigl\{(L(X_{1}), \dots, L(X_{n})) \mid L : \mathbb{R}[\underline{X}]_{\leq d} \to \mathbb{R} \text{ is linear, } L\bigl(M_{d}(\underline{g})\bigr) \subseteq \mathbb{R}_{\geq 0},\, L(1) = 1\bigr\} \] and \[ \operatorname{Lasserre}_{d}(f,\underline{g})= \inf\bigl\{L(f)\mid L : \mathbb{R}[\underline{X}]_{\leq d} \to \mathbb{R}\text{ is linear, }L\bigl(M_{d}(\underline{g})\bigr) \subseteq \mathbb{R}_{\geq 0},\,L(1) = 1\bigr\}, \] where the infimum is taken in \(\{-\infty\} \cup \mathbb{R} \cup \{+\infty\}\). The main contributions of the authors to the mentioned problems include the following results: Theorem 37. Let \(k, N \in \mathbb{N}_{+}\) and \(\varepsilon \in \mathbb{R}_{> 0}\). If \(M(\underline{g}) := \bigcup_{d \in \mathbb{N}}M_{d}(\underline{g})\) is Archimedean and \(S(\underline{g}) \neq \varnothing\), then there exists \(d \in \mathbb{N}\) such that for all \(f \in \mathbb{R}[\underline{X}]_{\leq N}\) with all coefficients in \([-N,N],\) \[ a := \min\{f(x) \mid x \in S(\underline{g})\} \text{ and }\{x \in S(\underline{g}) \mid f(x) = a\}= \{x_{1}, \dots, x_{k}\}, \] we have: if the balls \(B_{\varepsilon}(x_{1}), \dots, B_{\varepsilon}(x_{k})\) are pairwise disjoint and contained in \(S(\underline{g})\), and if we have \[ f \geq a + \varepsilon u \quad \textup{on } S(\underline{g}), \] where \(u:= u_{x_{1}} \cdots u_{x_{k}} \in \mathbb{R}[\underline{X}]\), then \(f - a \in M(\underline{g})\) and consequently \[ \operatorname{Lasserre}_{d}(f,\underline{g}) = a. \] Corollary 56. Suppose \(M(\underline{g})\) is Archimedean and \(S(\underline{g})\) has nonempty interior near its convex boundary. Suppose \(B\) is a closed ball in \(\mathbb{R}^{n}\), \[S := \{x \in B \mid \forall i \in I : g_{i}(x) \geq 0\}, \text{ and }\operatorname{conv} \operatorname{bd}\, S := S \cap \partial \operatorname{conv} S.\] If \(g_{i}\) is strictly quasiconcave on \(\operatorname{conv}bd\, S \cap \{x \in \mathbb{R}^{n} \mid g_{i}(x) = 0\}\) for each \(i \in \{1, \dots, m\}\), then there exists \(d \in \mathbb{N}\) such that \[ S(\underline{g}) = \operatorname{conv} S_{d}(\underline{g}). \]
0 references
moment relaxation
0 references
pure state
0 references
basic closed semi-algebraic set
0 references
polynomial optimization
0 references
0 references
0 references