We consider first-order methods with constant step size for minimizing locally Lipschitz coercive functions that are tame in an o-minimal structure on the real field. We prove that if the method is approximated by subgradient trajectories, then the iterates eventually remain in a neighborhood of a connected component of the set of critical points. Under suitable method-dependent regularity assumptions, this result applies to the subgradient method with momentum, the stochastic subgradient method with random reshuffling and momentum, and the random-permutations cyclic coordinate descent method.

In this talk, we provide global stability guarantees for first-order methods with constant step size for objective functions that are locally Lipschitz, coercive, and tame in an o-minimal structure on the real field. In order to do so, we show that the function values and the iterates of an iterative method eventually stabilize around some critical value and the set of critical points, respectively, given that the method is approximated by subgradient trajectories of the objective function. As it turns out, all of the aforementioned first-order methods are approximated by subgradient trajectories of locally Lipschitz functions under method-dependent regularity assumptions. Therefore, these methods fit into our framework, and their stability is guaranteed. To the best of our knowledge, these methods have not been studied before at such generality as in this paper. In particular, we do not require the objective function to be convex and we do not require it to be differentiable with a locally Lipschitz gradient.

This talk consists of two parts. In the first part, we introduce a framework of certifying the non-negativity of a function on a finite set, which is equivalent to certifying the nonnegativity of tensors. Via the Fourier sum of squares (FSOS), we are able to discuss both the theoretical and algorithmic aspects of this problem. The second part is concerned with applications of our framework to MAX-SAT. We will discuss how to find low degree FSOS certificates and estimate the lower bound for MAX-SAT problems.

We discuss generalized Nash equilibrium problems (GNEPs) that are given by polynomial functions. We consider cases each player's constraints are linear in their own strategy vectors. For this kind of GNEPs, the KKT set can be conveniently represented as a union of simpler sets, by using partial Lagrange multiplier expressions. This representation produces a set of branch polynomial optimization problems, each of which can be conveniently solved by Moment-SOS relaxations. We give a method to compute all generalized Nash equilibria, under some genericity assumptions. Extensive numerical experiments are provided to demonstrate the efficiency of the proposed method.

We consider the robotic control problems with safety constraints, which can represented as the nonnegativity on a semialgebraic set of polynomials parameterized by robotic control variables. We apply sum-of-squares (SOS) relaxations to characterize safe controls, and we use moment relaxations to obtain semidefinite relaxation problems. Under mild conditions, we can get optimal safe control for the robot. Numerical simulation and real-robot experiments are made to show the efficiency of our approach.