Session: Polynomial Optimization & Tensor Methods
Chair: Yang Liu
Cluster: nan
Talk 1: On the convergence of critical points on real varieties and applications to polynomial optimization
Speaker: Ali Mohammad Nezhad
Abstract: Let $F \in \mathrm{R}[X_1,\ldots,X_n]$ and the zero set $V=\mathrm{zero}(\{P_1,\ldots,P_s\},\mathrm{R}^n)$ be given with the canonical Whitney stratification, where $\{P_1,\ldots,P_s\} \subset \mathrm{R}[X_1,\ldots,X_n]$ and $\mathrm{R}$ is a real closed field. We explore isolated trajectories that result from critical points of $F$ on $V_{\xi}=\mathrm{zero}(\{P_1-\xi_1,\ldots,P_s-\xi_s\},\mathrm{R}^n)$ when $\xi \downarrow 0$, in the sense of stratified Morse theory. Our main motivation is the limiting behavior of log-barrier functions in polynomial optimization which leads to a central path, an underlying notion behind the theory of interior point methods. We prove conditions for the existence, convergence, and smoothness of a central path. We also consider the cases where $F$ and $P_i$ are definable functions in a (polynomially bounded) o-minimal expansion of $\mathbb{R}^n$. Joint work with Saugata Basu, Purdue University
Talk 2: APPROXIMATION OF A MOMENT SEQUENCE BY MOMENT-S.o.S HIERARCHY
Speaker: Hoang Anh Tran
Abstract: The moment-S.o.S hierarchy is a widely applicable framework to address polynomial optimization problems over basic semi-algebraic sets based on positivity certificates of polynomial. Recent works show that the convergence rate of this hierarchy over certain simple sets, namely, the unit ball, hypercube, and standard simplex, is of the order $\mathrm{O}(1/r^2)$, where $r$ denotes the level of the moment-S.o.S hierarchy. This paper aims to provide a comprehensive understanding of the convergence rate of the moment-S.o.S hierarchy by estimating the Hausdorff distance between the set of pseudo truncated moment sequences and the set of truncated moment sequences specified by Tchakaloff’s theorem. Our results provide a connection between the convergence rate of the moment-S.o.S hierarchy and the \L{}ojasiewicz exponent of the domain under the compactness assumption. Consequently, we obtain the convergence rate of $\mathrm{O}(1/r)$ for polytopes, $\mathrm{O}(1/\sqrt{r})$ for domains that either satisfy the Polyak-Łojasiewicz condition or are defined by locally strongly convex polynomials, and extends the convergence rate of $\mathrm{O}(1/r^2)$ for general polynomial over the sphere.
Talk 3: Efficient Adaptive Regularized Tensor Methods
Speaker: Yang Liu
Abstract: High-order tensor methods employing local Taylor approximations have attracted considerable attention for convex and nonconvex optimization. The pth-order adaptive regularization (ARp) approach builds a local model comprising a pth-order Taylor expansion and a (p+1)th-order regularization term, delivering optimal worst-case global and local convergence rates. However, for p≥2, subproblem minimization can yield multiple local minima, and while a global minimizer is recommended for p=2, effectively identifying a suitable local minimum for p≥3 remains elusive. This work extends interpolation-based updating strategies, originally proposed for p=2, to cases where p≥3, allowing the regularization parameter to adapt in response to interpolation models. Additionally, it introduces a new prerejection mechanism to discard unfavorable subproblem minimizers before function evaluations, thus reducing computational costs for p≥3. Numerical experiments, particularly on Chebyshev-Rosenbrock problems with p=3, indicate that the proper use of different minimizers can significantly improve practical performance, offering a promising direction for designing more efficient high-order methods.
