Session: Advances in Nonlinear Optimization Methods and Applications
Chair: Wenqi Zhu
Cluster: Nonlinear Optimization
Talk 1: A simple and reliable adaptive trust-region method
Speaker: Fadi Hamad
Abstract: We present an adaptive trust region method for unconstrained optimization that allows inexact solutions to the trust-region subproblems. Our method is a simple variant of the classical trust-region method of \citet{sorensen1982newton}. The method achieves the best possible convergence bound up to an additive log factor, for finding an $\epsilon$-approximate stationary point, i.e., $O( \Delta_f L^{1/2} \epsilon^{-3/2}) + \tilde{O}(1)$ iterations where $L$ is the Lipschitz constant of the Hessian, $\Delta_f$ is the optimality gap, and $\epsilon$ is the termination tolerance for the gradient norm. This improves over existing trust-region methods in terms of its $L$ dependence. We compare our performance with state-of-the-art trust-region (TRU) and cubic regularization (ARC) methods from the GALHAD library on the CUTEst benchmark set on problems with more than 100 variables. We use fewer function evaluations, gradient evaluations and Hessian evaluations than these methods. For instance, the shifted geometric mean of function evaluations improve over TRU and ARC by $1.4$ and $2$ times respectively. Compared to the conference version of this paper \cite{hamad2022consistently}, our revised method includes practical enhancements and a refined subproblems termination criteria. These modifications dramatically improved performance including an order of magnitude reduction in the shifted geometric mean of wall-clock times.}
Talk 2: Price Updates by Interior-Point Methods
Speaker: Chuwen Zhang
Abstract: We study the computation of equilibria in exchange markets with divisible goods and players endowed with heterogeneous utilities. Although centralized interior-point methods can compute equilibrium prices in polynomial time, they obscure the interplay between prices and individual responses. In this paper, we develop interior-point strategies that update only the price vector p, mirroring the tâtonnement process. These methods exploit the separable structure of a dual potential function 𝜑(p). A key insight is that the utility maximization problem possesses implicit barrier properties in both the price and allocation spaces. Focusing on a broad class of market problems, we show that 𝜑 exhibits scaled Lipschitz continuity and that its Hessian operator 𝜑'' decomposes into a sum of diagonal and rank-one matrices, allowing efficient approximations. In the large-market regime with randomly distributed players, we prove that 𝜑'' converges in high probability to a linear operator with an explicit inverse. Building on these properties, we design several inexact interior-point methods. In certain well-behaved cases, one such method achieves a global rate of superlinear convergence. This is a joint work with Chang He, Bo Jiang, and Yinyu Ye.
Talk 3: Quasi-Newton methods for solving general nonlinear equations
Speaker: Chengchang Liu
Abstract: This talk focuses on quasi-Newton methods for solving general nonlinear equations. Unlike existing theory for quasi-Newton methods, which mostly focuses on the case such that the number of nonlinear equations $n$ and the dimension of the variable $d$ are identical, we provide analysis on the case that they can can be different. For $n\geq d$, we establish a fast local linear rate, which can be independent of the condition number. For $n\leq d$, we establish local superlinear rates, which match the results for strongly convex optimization. We will further show how to boost these results by incorporating the block-type quasi-Newton updates.
