ICCOPT2025USC

Session: Progress in Nonsmooth Optimization
Chair: Feng Ruan
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Subgradient Convergence Implies Subdifferential Convergence on Weakly Convex Functions: With Uniform Rates Guarantees
Speaker: Feng Ruan
Abstract: In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the population risk. Yet, characterizing this convergence remains a fundamental challenge. This work introduces a novel perspective by connecting the uniform convergence of subdifferential mappings to that of subgradient mappings as empirical risk converges to the population risk. We prove that, for stochastic weakly-convex objectives, and within any open set, a uniform bound on the convergence of subgradients -- chosen arbitrarily from the corresponding subdifferential sets -- translates to a uniform bound on the convergence of the subdifferential sets itself, measured by the Hausdorff metric. Using this technique, we derive uniform convergence rates for subdifferential sets of stochastic convex-composite objectives. Our results do not rely on key distributional assumptions in the literature, which require the population and finite sample subdifferentials to be continuous in the Hausdorff metric, yet still provide tight convergence rates. These guarantees lead to new insights into the nonsmooth landscapes of such objectives within finite samples.

Talk 2: Variational Theory and Algorithms for a Class of Asymptotically Approachable Nonconvex Problems
Speaker: Ying Cui
Abstract: We investigate a class of composite nonconvex functions, where the outer function is the sum of univariate extended-real-valued convex functions and the inner function is the limit of difference-of-convex functions. A notable feature of this class is that the inner function can be merely lower semicontinuous instead of continuously differentiable. It covers a range of important yet challenging applications, including the composite value functions of nonlinear programs and the value-at-risk constraints. We propose an asymptotic decomposition of the composite function that guarantees epi-convergence to the original function, leading to necessary optimality conditions for the corresponding minimization problem. The proposed decomposition also enables us to design a numerical algorithm such that any accumulation point of the generated sequence, if exists, satisfies the newly introduced optimality conditions. These results expand on the study of so-called amenable functions introduced by Poliquin and Rockafellar in 1992, which are compositions of convex functions with smooth maps, and the prox-linear methods for their minimization.

Talk 3: Survey Descent: a Case-Study in Amplifying Optimization Research with Modern ML Workflows
Speaker: X.Y. Han
Abstract: Within the classic optimization, one learns that for strongly convex objectives that are smooth, gradient descent ensures linear convergence of iterates and objective values relative to the number of gradient evaluations. Nonsmooth objective functions are more challenging: existing solutions typically invoke cutting plane methods whose complexities are difficult to bound, leading to convergence guarantees that are sublinear in the cumulative number of gradient evaluations. We instead propose a multipoint generalization of the gradient descent called Survey Descent. In this method, one first leverages a one-time initialization procedure to gather a "survey" of points. Then, during each iteration of the method, the survey points are updated in parallel using a simple, four-line procedure inspired by gradient descent. Under certain regularity conditions, we prove that Survey Descent then achieves a desirable performance by converging linearly to the optimal solution in the nonsmooth setting. Despite being an nominally mathematical endeavor, we discuss how the development of Survey Descent was significantly accelerated by a frictionless computational workflow made possible by tools from modern machine learning (ML); how this model of applying new ML workflows to solve open questions in optimization and applied probability could amplify the researchers' productivity; practical computational bottlenecks that could hinder this integration; and what tools are needed to overcome those obstacles.

Session: Optimization for Neural Network Pruning and Quantization
Chair: Lin Xiao
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Understanding Neural Network Quantization and its Robustness Against Data Poisoning Attacks
Speaker: Yiwei Lu
Abstract: Neural network quantization, exemplified by BinaryConnect (BC) and its variants, has become a standard approach for model compression. These methods typically employ the sign function in the forward pass, with various approximations used for gradient computation during backpropagation. While effective, these techniques often rely on heuristics or "training tricks" that lack theoretical grounding. This talk explores the optimization perspective of these quantization methods, introducing forward-backward quantizers as a principled framework. We present ProxConnect++ (PC++), a generalization that encompasses existing quantization techniques and provides automatic theoretical guarantees. Furthermore, we reveal an unexpected benefit of neural network quantization: enhanced robustness against data poisoning attacks.

Talk 2: Convex Regularizations for Pruning- and Quantization-Aware Training of Neural Networks
Speaker: Lin Xiao
Abstract: We present a convex regularization approach for pruning- and quantization-aware training of deep neural networks. While it is well-known that group Lasso can induce structured pruning, we show that convex, piece-wise affine regularizations (PAR) can effectively induce quantization. Previous work have limited success in practice due to the challenge of integrating structured regularization with stochastic gradient methods. We derive an aggregate proximal stochastic gradient method (AProx) that can successfully produce desired pruning and quantization results. Moreover, we establish last-iterate convergence of the method, which better supports the computational practice than the classical theory of average-iterate convergence.

Talk 3: Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guarantees
Speaker: Jianhao Ma
Abstract: Optimization problems involving discrete or quantized variables can be very challenging due to the combinatorial nature of the design space. We show that (coordinate-wise) piecewise-affine regularization (PAR) can effectively induce quantization in the optimization variables. PAR provides a flexible modeling and computational framework for quantization based on continuous and convex optimization. In addition, for linear regression problems, we can approximate $\ell_1$- and squared $\ell_2$-regularizations using different parameterizations of PAR, and obtain statistical guarantees that are similar to those of Lasso and ridge regression, all with quantized regression variables.

Session: Methods for Large-Scale Nonlinear Optimization IV
Chair: Albert Berahas
Cluster: Nonlinear Optimization

Talk 1: High Probability Analysis for Negative Curvature Methods with Probabilistic Oracles
Speaker: Wanping Dong
Abstract: We consider a negative curvature method for continuous nonlinear nonconstrained optimization problems under a stochastic setting where the function values, gradients, and Hessian (products) are available only through inexact probabilistic oracles. Our goal is to develop algorithms that have high probabilistic second-order convergence and affordable complexity so that they can be used for large-scale problems. We introduce general conditions on the probabilistic oracles and propose a method that dynamically chooses between negative curvature and descent steps. We derive a high probability tail bound on the iteration complexity of the algorithm and show improvements compared to our previous negative curvature method. A practical variant is implemented to illustrate the power of the proposed algorithm.

Talk 2: Retrospective Approximation for Stochastic Constrained Problems Using Sequential Quadratic Programming
Speaker: Shagun Gupta
Abstract: Sequential Quadratic Programming (SQP) is one of the state-of-the-art algorithms used to solve deterministic constrained nonlinear optimization problems. In recent years, the framework has been extended to solve deterministic equality and inequality constrained problems with stochastic objective functions. In response to the challenges posed by stochasticity, various schemes have been incorporated into SQP algorithms to adapt key parameters, such as step size and merit parameter, from the deterministic setting to the stochastic setting. These include stochastic line search, Lipschitz constant estimation, and Hessian averaging. In our work, we leverage SQP algorithms within the innovative framework of Retrospective Approximation. This framework introduces a novel approach to solving stochastic constrained problems by allowing the SQP algorithm to solve a series of subsampled deterministic subproblems. Each deterministic subproblem is solved not to optimality, but to a specified accuracy with an increasing sample size for the subsampled deterministic problems. This strategic decoupling of stochasticity from the SQP algorithm proves instrumental, enabling the utilization of legacy deterministic solvers. Thus, by decoupling stochasticity, the Retrospective Approximation framework facilitates the integration of legacy deterministic solvers, reducing requirements for hyper-parameter tuning in stochastic settings. We provide theoretical convergence requirements for the increase in the subsampling batch size and required solution accuracy for deterministic subproblems. We also conduct numerical experiments to showcase the utilization of legacy deterministic solvers for stochastic constrained problems.

Talk 3: Stochastic Second-order Inexact Augmented Lagrangian Framework for Nonconvex Expectation Constrained Optimization
Speaker: Yash Kumar
Abstract: In this talk, we present methods for solving stochastic nonconvex optimization problems where both the objective function and the constraints are expectations of stochastic functions. We consider an inexact Augmented Lagrangian framework for solving these problems, employing stochastic second-order methods for the subproblems instead of first-order methods. This framework ensures convergence to second-order stationary points instead of approximate first-order stationary points. Furthermore, these methods do not require access to full Hessians but only Hessian-vector products, which are typically twice the computational cost of gradients. We provide convergence guarantees for the stochastic second-order inexact Augmented Lagrangian framework, along with total computational complexity guarantees for various second-order subproblem solvers. Numerical experiments on constrained machine learning classification problems demonstrate the efficiency of the proposed framework.

Session: Recent Advances in Large-scale Optimization II
Chair: Salar Fattahi
Cluster: Nonlinear Optimization

Talk 1: Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Space
Speaker: Yao Xie
Abstract: We consider a minimax problem motivated by distributionally robust optimization (DRO) when the worst-case distribution is continuous, leading to significant computational challenges due to the infinite-dimensional nature of the optimization problem. Recent research has explored learning the worst-case distribution using neural network-based generative models to address these computational challenges but lacks algorithmic convergence guarantees. This paper bridges this theoretical gap by presenting an iterative algorithm to solve such a minimax problem, achieving global convergence under mild assumptions and leveraging technical tools from vector space minimax optimization and convex analysis in the space of continuous probability densities. In particular, leveraging Brenier's theorem, we represent the worst-case distribution as a transport map applied to a continuous reference measure and reformulate the regularized discrepancy-based DRO as a minimax problem in the Wasserstein space. Furthermore, we demonstrate that the worst-case distribution can be efficiently computed using a modified Jordan-Kinderlehrer-Otto (JKO) scheme with sufficiently large regularization parameters for commonly used discrepancy functions linked to the radius of the ambiguity set. Additionally, we derive the global convergence rate and quantify the total number of subgradient and inexact modified JKO iterations required to obtain approximate stationary points. These results are potentially apply to nonconvex and nonsmooth scenarios, with broad relevance to modern machine learning applications.

Talk 2: Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning
Speaker: Yuejie Chi
Abstract: Federated reinforcement learning (RL) enables collaborative decision making of multiple distributed agents without sharing local data trajectories. In this work, we consider a multi-task setting, in which each agent has its own private reward function corresponding to different tasks, while sharing the same transition kernel of the environment. Focusing on infinite-horizon Markov decision processes, the goal is to learn a globally optimal policy that maximizes the sum of the discounted total rewards of all the agents in a decentralized manner, where each agent only communicates with its neighbors over some prescribed graph topology. We develop federated vanilla and entropy-regularized natural policy gradient (NPG) methods in the tabular setting under softmax parameterization, where gradient tracking is applied to estimate the global Q-function to mitigate the impact of imperfect information sharing. We establish non-asymptotic global convergence guarantees under exact policy evaluation, where the rates are nearly independent of the size of the state-action space and illuminate the impacts of network size and connectivity. To the best of our knowledge, this is the first time that near dimension-free global convergence is established for federated multi-task RL using policy optimization. We further go beyond the tabular setting by proposing a federated natural actor critic (NAC) method for multi-task RL with function approximation, and establish its finite-time sample complexity taking the errors of function approximation into account.

Talk 3: Invariant Low-Dimensional Subspaces in Gradient Descent for Learning Deep Networks
Speaker: Qing Qu
Abstract: Over the past few years, an extensively studied phenomenon in training deep networks is the implicit bias of gradient descent towards parsimonious solutions. In this work, we first investigate this phenomenon by narrowing our focus to deep linear networks. Through our analysis, we reveal a surprising "law of parsimony" in the learning dynamics when the data possesses low-dimensional structures. Specifically, we show that the evolution of gradient descent starting from orthogonal initialization only affects a minimal portion of singular vector spaces across all weight matrices. In other words, the learning process happens only within a small invariant subspace of each weight matrix, even though all weight parameters are updated throughout training. This simplicity in learning dynamics could have significant implications for both efficient training and a better understanding of deep networks. First, the analysis enables us to considerably improve training efficiency by taking advantage of the low-dimensional structure in learning dynamics. We can construct smaller, equivalent deep linear networks without sacrificing the benefits associated with the wider counterparts. Moreover, we demonstrate the potential implications for efficient training deep nonlinear networks. Second, it allows us to better understand deep representation learning by elucidating the progressive feature compression and discrimination from shallow to deep layers. The study paves the foundation for understanding hierarchical representations in deep nonlinear networks.

Session: Random subspace algorithms in optimization
Chair: Pierre-Louis Poirion
Cluster: Optimization For Data Science

Talk 1: Zeroth-order Random Subspace AAlgorithm for Non-smooth Convex Optimization
Speaker: Akiko Takeda
Abstract: Zeroth-order optimization, which does not use derivative information, is one of the significant research areas in the field of mathematical optimization and machine learning. Although various studies have explored zeroth-order algorithms, one of the theoretical limitations is that oracle complexity depends on the dimension, i.e., on the number of variables, of the optimization problem. In this talk, we propose a zeroth-order random subspace algorithm by combining a gradient-free algorithm (specifically, Gaussian randomized smoothing with central differences) with random projection to reduce the dependency of the dimension in oracle complexity. The algorithm has a local convergence rate independent of the original dimension under some local assumptions.

Talk 2: Random matrix to solve large linear system
Speaker: Jiaming Yang
Abstract: Large matrices arise in real-world applications in the areas of machine learning, data analysis and optimization: from the representation of massive datasets with high dimensional features, to the first and second-order derivatives of an objective function that needs to be optimized. How can we capture the intrinsic patterns and physics efficiently and accurately? As an interdisciplinary research area that roots in theoretical computer science (TCS), random matrix theory (RMT), and recently thrives in scientific computing and machine learning, Randomized Numerical Linear Algebra (RNLA) offers a promising avenue to alleviate computational challenges by introducing randomness to large-scale problems, with the guarantee of creating efficient approximate solutions that retain high accuracy. Specifically, randomized subspace methods are one of the most popular methods that are well established in theory but only start flourishing in the area of optimization recently. In my recent work [Derezinski,Yang, STOC 2024] and [Derezinski, Musco, Yang, SODA 2025], we focus on the problem of solving a linear system and develope different types of stochastic optimization algorithms. Our algorithms provably achieve better time complexity results, and are linear in the input matrix size when we assume that it has a flat tail. As one of our key techniques, we construct a low- rank Nystrom approximation with sparse random sketching, resulting in an easy-to-construct preconditioner with the effective guarantee from the randomized subspace theory.

Talk 3: Random Subspace Homogenized Trust Region Method
Speaker: Pierre-Louis Poirion
Abstract: We proposes the Random Subspace Homogenized Trust Region (RSHTR) method with the best theoretical guarantees among random subspace algorithms for nonconvex optimization. Furthermore, under rank-deficient conditions, RSHTR converge to a second-order stationary point quadratically. Experiments on real-world datasets verify the benefits of RSHTR.

Session: Contextual Stochastic Optimization under Streaming Data and Decision Dependency
Chair: Guzin Bayraksan
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Residuals-Based Contextual Distributionally Robust Optimization with Decision-Dependent Uncertainty
Speaker: Xian Yu
Abstract: We consider a residuals-based distributionally robust optimization model, where the underlying uncertainty depends on both covariate information and our decisions. We adopt regression models to learn the latent decision dependency and construct a nominal distribution (thereby ambiguity sets) around the learned model using empirical residuals from the regressions. Ambiguity sets can be formed via the Wasserstein distance, a sample robust approach, or with the same support as the nominal empirical distribution (e.g., phi-divergences), where both the nominal distribution and the radii of the ambiguity sets could be decision- and covariate-dependent. We provide conditions under which desired statistical properties, such as asymptotic optimality, rates of convergence, and finite sample guarantees, are satisfied. Via cross-validation, we devise data-driven approaches to find the best radii for different ambiguity sets, which can be decision-(in)dependent and covariate-(in)dependent. Through numerical experiments, we illustrate the effectiveness of our approach and the benefits of integrating decision dependency into a residuals-based DRO framework.

Talk 2: Distribution-Free Algorithms for Predictive Stochastic Programming in the Presence of Streaming Data
Speaker: Suvrajeet Sen
Abstract: This work studies a fusion of concepts from stochastic programming and nonparametric statistical learning in which data is available in the form of covariates interpreted as predictors and responses. Such models are designed to impart greater agility, allowing decisions under uncertainty to adapt to the knowledge of predictors (leading indicators). This work studies two classes of methods: one of the methods may be classified as a first-order method, whereas the other studies piecewise linear approximations. In addition, our study incorporates several non-parametric estimation schemes, including k nearest neighbors (kNN) and other standard kernel estimators. Our computational results demonstrate that the new algorithms outperform traditional approaches which were not designed for streaming data applications requiring simultaneous estimation and optimization. (This work was performed as part of the first author's doctoral dissertation.)

Talk 3: An Alternating Optimization Method for Contextual Distributionally Robust Optimization under Streaming Data
Speaker: Guzin Bayraksan
Abstract: We consider data-driven decision-making that incorporates a prediction model within the 1-Wasserstein distributionally robust optimization (DRO) given joint observations of uncertain parameters and covariates using regression residuals in a streaming-data setting. In this setting, additional data become available and allow decisions to adapt to the growing knowledge of the underlying uncertainty. The ambiguity set shrinks as more data is observed. We propose an efficient online optimization method for this streaming-data contextual DRO setting, which iteratively alternates between optimizing the decision and determining the worst-case distribution. We analyze the asymptotic convergence properties of this algorithm and establish dynamic regret bounds to certify the performance of online solutions. Through numerical experiments, we validate our theoretical findings and demonstrate that our approach significantly enhances computational efficiency while maintaining high solution quality under streaming data.

Session: Analysis and Design of First Order Methods for Convex Optimization
Chair: Bartolomeo Stellato
Cluster: Optimization For Data Science

Talk 1: Toward a grand unified theory of accelerations in optimization and machine learning
Speaker: Ernest Ryu
Abstract: Momentum-based acceleration of first-order optimization methods, first introduced by Nesterov, has been foundational to the theory and practice of large-scale optimization and machine learning. However, finding a fundamental understanding of such acceleration remains a long-standing open problem. In the past few years, several new acceleration mechanisms, distinct from Nesterov’s, have been discovered, and the similarities and dissimilarities among these new acceleration phenomena hint at a promising avenue of attack for the open problem. In this talk, we discuss the envisioned goal of developing a mathematical theory unifying the collection of acceleration mechanisms and the challenges that are to be overcome.

Talk 2: Data-driven performance estimation of first-order methods
Speaker: Jisun Park
Abstract: We introduce a data-driven approach to analyze the probabilistic performance of first-order optimization algorithms. Combining Wasserstein Distributionally Robust Optimization to the performance estimation framework, we derive probabilistic performance guarantees to a wide range first-order methods. We show that our method is able to achieve significant reductions in conservatism compared to classical worst-case performance analysis tools.

Talk 3: Exact Verification of First-Order Methods for Quadratic Optimization via Mixed-Integer Programming
Speaker: Vinit Ranjan
Abstract: We present a mixed-integer programming based framework to exactly verify the convergence of first-order methods for parametric convex quadratic and linear optimization. We formulate the verification problem as a mathematical optimization problem where we maximize the infinity norm of the fixed-point residual at the last iteration subject to constraints on the parameters and initial iterates. Our approach uses affine and piecewise affine steps to exactly represent a wide range of gradient, projection, and proximal steps. We scale the mixed-integer formulation using advanced bound tightening and strong formulations for the piecewise affine steps. Numerical examples show orders of magnitude lower worst-case residuals that more closely match the practical convergence.

Session: Advances in Network Optimization and Cooperative Learning
Chair: Cesar A Uribe
Cluster: Multi-agent Optimization and Games

Talk 1: Optimally Improving Cooperative Learning in a Social Settin
Speaker: Shahrzad Haddadan
Abstract: We consider a cooperative learning scenario where a collection of networked agents with individually owned classifiers update their predictions, for the same classification task, through communication or observations of each other’s predictions. Clearly if highly influential vertices use erroneous classifiers, there will be a negative effect on the accuracy of all the agents in the network. We ask the following question: how can we optimally fix the prediction of a few classifiers so as maximize the overall accuracy in the entire network. To this end we consider an aggregate and an egalitarian objective function. We show a polynomial time algorithm for optimizing the aggregate objective function, and show that optimizing the egalitarian objective function is NP-hard. Furthermore, we develop approximation algorithms for the egalitarian improvement. The performance of all of our algorithms are guaranteed by mathematical analysis and backed by experiments on synthetic and real data.

Talk 2: The engineering potential of fish research: swimming upstream to new solutions
Speaker: Daniel Burbano
Abstract: Millions of years of evolution have endowed animals with refined and elegant mechanisms to orient and navigate in complex environments. Elucidating the underpinnings of these processes is of critical importance not only in biology to understand migration and survival but also for engineered network systems to aid the development of bio-inspired algorithms for estimation and control. Particularly interesting is the study of fish navigation where different cues, such as vision and hydrodynamics are integrated and fed back to generate locomotion. Little is known, however, about the information pathways and the integration process underlying complex navigation problems. This talk will discuss recent advances in data-driven mathematical models based on potential flow theory, stochastic differential equations, and control theory describing fish navigation. In addition, we will discuss how biological insights gained from this research can be applied to robot navigation with zero-order optimization and estimation and control problems in network systems

Talk 3: An Optimal Transport Approach for Network Regression
Speaker: Alex Zalles
Abstract: We study the problem of network regression, where one is interested in how the topology of a network changes as a function of Euclidean covariates. We build upon recent developments in generalized regression models on metric spaces based on Fr\'echet means and propose a network regression method using the Wasserstein metric. We show that when representing graphs as multivariate Gaussian distributions, the network regression problem requires the computation of a Riemannian center of mass (i.e., Fr\'echet means). Fr\'echet means with non-negative weights translates into a barycenter problem and can be efficiently computed using fixed point iterations. Although the convergence guarantees of fixed-point iterations for the computation of Wasserstein affine averages remain an open problem, we provide evidence of convergence in a large number of synthetic and real-data scenarios. Extensive numerical results show that the proposed approach improves existing procedures by accurately accounting for graph size, topology, and sparsity in synthetic experiments. Additionally, real-world experiments using the proposed approach result in higher Coefficient of Determination () values and lower mean squared prediction error (MSPE), cementing improved prediction capabilities in practice.

Session: Optimization for Large Language Models and Kernels
Chair: Ming Yin
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Optimizing for a Proxy Reward in RLHF
Speaker: Banghua Zhu
Abstract: Reinforcement Learning from Human Feedback (RLHF) has become an important technique in post-training of Larger Language Models (LLM). During RLHF, one usually first trains a reward model from human preference data, and then optimizes the LLM for the proxy reward signal predicted by the reward model. In this talk, I'll discuss what makes a good reward model for RLHF from both theoretical and empirical observations.

Talk 2: Self-Play Preference Optimization for Language Model Alignment
Speaker: Yue Wu
Abstract: In this paper, we propose a self-play-based method for language model alignment, which treats the problem as a constant-sum two-player game aimed at optimizing the model to approximate the Nash equilibrium. Our approach, dubbed SPPO, is based on a new alignment objective derived from L2 regression. Interestingly, this new objective has a deep connection with the KL-regularized policy gradient and natural gradient methods, and can guarantee the convergence to the optimal solution. In our experiments, this theoretically motivated objective turns out highly effective. By leveraging a small pre-trained preference model, SPPO can obtain a highly-aligned model without additional external supervision from human or stronger language models.

Talk 3: Learning Counterfactual Distributions via Kernel Nearest Neighbors
Speaker: Kyuseong Choi
Abstract: Consider a setting with multiple units (e.g., individuals, cohorts, geographic locations) and outcomes (e.g., treatments, times, items), where the goal is to learn a multivariate distribution for each unit-outcome entry, such as the distribution of a user's weekly spend and engagement under a specific mobile app version. A common challenge is the prevalence of missing not at random data---observations are available only for certain unit-outcome combinations---where the observed distributions can be correlated with properties of distributions themselves, i.e., there is unobserved confounding. An additional challenge is that for any observed unit-outcome entry, we only have a finite number of samples from the underlying distribution. We tackle these two challenges by casting the problem into a novel distributional matrix completion framework and introduce a kernel-based distributional generalization of nearest neighbors to estimate the underlying distributions. By leveraging maximum mean discrepancies and a suitable factor model on the kernel mean embeddings of the underlying distributions, we establish consistent recovery of the underlying distributions even when data is missing not at random and positivity constraints are violated. Furthermore, we demonstrate that our nearest neighbors approach is robust to heteroscedastic noise, provided we have access to two or more measurements for the observed unit-outcome entries—a robustness not present in prior works on nearest neighbors with single measurements.

Session: Dynamic Optimization: Deterministic and Stochastic Continuous-time Models I
Chair: Cristopher Hermosilla
Cluster: Multi-agent Optimization and Games

Talk 1: A Minimality Property of the Value Function in Optimal Control over the Wasserstein Space
Speaker: Cristopher Hermosilla
Abstract: In this talk we study an optimal control problem with (possibly) unbounded terminal cost in the space of Borel probability measures with finite second moment. We consider the metric geometry associated with the Wasserstein distance, and a suitable weak topology rendering this space locally compact. In this setting, we show that the value function of a control problem is the minimal viscosity supersolution of an appropriate Hamilton-Jacobi-Bellman equation. Additionally, if the terminal cost is bounded and continuous, we show that the value function is the unique viscosity solution of the Hamilton-Jacobi-Bellman equation.

Talk 2: Principal-Multiagents problem in continuous-time
Speaker: Nicolás Hernández
Abstract: We study a general contracting problem between the principal and a finite set of competitive agents, who perform equivalent changes of measure by controlling the drift of the output process and the compensator of its associated jump measure. In this setting, we generalize the dynamic programming approach developed by Cvitanić, Possamaï, and Touzi (2017) and we also relax their assumptions. We prove that the problem of the principal can be reformulated as a standard stochastic control problem in which she controls the continuation utility (or certainty equivalent) processes of the agents. Our assumptions and conditions on the admissible contracts are minimal to make our approach work. We also present a smoothness result for the value function of a risk–neutral principal when the agents have exponential utility functions. This leads, under some additional assumptions, to the existence of an optimal contract.

Talk 3: Unbounded viscosity solutions of Hamilton-Jacobi equations in the 2-Wasserstein space
Speaker: Othmane Jerhaoui
Abstract: In this talk, we study unbounded viscosity solutions of Hamilton-Jacobi equations in the 2-Wasserstein space over the Euclidean space. The notion of viscosity is defined by taking test functions that are locally Lipschitz and can be respresented as a difference of two geodesically semiconvex functions. First, We establish a comparison result for a general Hamiltonian sat- isfying mild hypotheses. Then, we will discuss well-posedness of a class of Hamilton-Jacobi equations with a Hamiltonian arising from classical mechanics.

Session: Convex approaches to SDP
Chair: Richard Zhang
Cluster: Conic and Semidefinite Optimization

Talk 1: Fitting Tractable Convex Sets to Support Function Data
Speaker: Venkat Chandrasekaran
Abstract: The geometric problem of estimating an unknown compact convex set from evaluations of its support function arises in a range of scientific and engineering applications. Traditional approaches typically rely on estimators that minimize the error over all possible compact convex sets; in particular, these methods do not allow for much incorporation of prior structural information about the underlying set and the resulting estimates become increasingly more complicated to describe as the number of measurements available grows.  We address both of these shortcomings by describing a new framework for estimating tractably specified convex sets from support function evaluations.  Along the way, we also present new bounds on how well arbitrary convex bodies can be approximated by elements from structured non-polyhedral families of convex sets.  Our numerical experiments highlight the utility of our framework over previous approaches in settings in which the measurements available are noisy or small in number as well as those in which the underlying set to be reconstructed is non-polyhedral. (Joint work with Yong Sheng Soh and Eliza O'Reilly.)

Talk 2: Iterative methods for primal-dual scalings in conic optimization
Speaker: Lieven Vandenberghe
Abstract: A central element in the design of primal-dual interior-point methods for conic optimization is the definition of a suitable primal-dual scaling or metric. The talk will discuss simple iterative methods for computing primal-dual scalings. We will consider the Nesterov-Todd scaling for symmetric cones and extensions to sparse positive semidefinite matrix cones.

Talk 3: Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
Speaker: Nathan Benedetto Proenca
Abstract: We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete problems including MaxCut, Max2Sat, MaxDicut, and more generally, Max-Boolean Constraint Satisfaction and MaxQ (maximization of a positive semidefinite quadratic form over the hypercube) with new APX-complete problems which are stated as convex optimization problems with exponentially many variables. These new dual counterparts, based on what we call Grothendieck covers, range from fractional cut covering problems (for MaxCut) to tensor sign covering problems (for MaxQ). For each of these problem pairs, our framework transforms the randomized approximation algorithms with the best known approximation factors for the primal problems to randomized approximation algorithms for their dual counterparts with reciprocal approximation factors which are tight with respect to the Unique Games Conjecture. For each APX-complete pair, our algorithms solve a single SDP relaxation and generate feasible solutions for both problems which also provide approximate optimality certificates for each other. Our work utilizes techniques from areas of randomized approximation algorithms, convex optimization, spectral sparsification, as well as Chernoff-type concentration results for random matrices.

Session: First-order methods for nonsmooth optimization
Chair: Digvijay Boob
Cluster: Nonlinear Optimization

Talk 1: Efficient Subgradient Method for Minimizing Nonsmooth Maximal Value Functions
Speaker: Hanyang Li
Abstract: We consider the minimization of a class of nonsmooth maximal value functions that are piecewise-smooth. Recent implementable Goldstein-style subgradient methods for general Lipschitz functions involve computationally intensive inner loops to approximate the descent direction. In this paper, we introduce a novel subgradient method that eliminates the sophisticated inner loops by employing a regularization technique, significantly improving computational efficiency for minimizing nonsmooth maximal value functions.

Talk 2: Dimension dependence in nonconvex optimization
Speaker: Guy Kornowski
Abstract: Optimization problems that arise in modern machine learning are often neither smooth nor convex, and typically high-dimensional. In this talk we will discuss the intricate role of the dimension in such problems, and compare it to smooth optimization. We will see that some approaches lead to significant gaps in dimension dependencies, yet sometimes these can be eliminated altogether. In particular, we will examine fundamental concepts such as stationarity, smoothing, and zero-order optimization, and show they exhibit exponential, polynomial, and no such gaps, respectively.

Talk 3: On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Control
Speaker: Swati Padmanabhan
Abstract: Recent work in imitation learning has shown that having an expert controller that is both suitably smooth and stable enables stronger guarantees on the performance of the learned controller. However, constructing such smoothed expert controllers for arbitrary systems remains challenging, especially in the presence of input and state constraints. As our primary contribution, we show how such a smoothed expert can be designed for a general class of systems using a log-barrier-based relaxation of a standard Model Predictive Control (MPC) optimization problem. At the crux of this theoretical guarantee on smoothness is a new lower bound we prove on the optimality gap of the analytic center associated with a convex Lipschitz function, which we hope could be of independent interest. We validate our theoretical findings via experiments, demonstrating the merits of our smoothing approach over randomized smoothing.

Session: Bilevel Optimization for Inverse Problems Part 2
Chair: Juan Carlos de los Reyes
Cluster: PDE-constrained Optimization

Talk 1: Linesearch-enhanced inexact forward–backward methods for bilevel optimization
Speaker: Marco Prato
Abstract: Bilevel optimization problems arise in various real-world applications, often being characterized by the impossibility of having the exact objective function and its gradient available. Developing mathematically sound optimization methods that effectively handle inexact information is crucial for ensuring reliable and efficient solutions. In this talk we propose a line-search based algorithm for solving a bilevel optimization problem, where the approximate gradient and function evaluation obeys an adaptive tolerance rule. Our method is based on implicit differentiation under some standard assumptions, and its main novelty with respect to similar approaches is the well posed, inexact line-search procedure using only approximate function values and adaptive accuracy control. This work is partially supported by the PRIN project 20225STXSB, under the National Recovery and Resilience Plan (NRRP) funded by the European Union - NextGenerationEU.

Talk 2: Tensor train solution to uncertain optimization problems with shared sparsity penalty
Speaker: Akwum Onwunta
Abstract: We develop first- and second-order numerical optimization methods to solve non-smooth optimization problems featuring a shared sparsity penalty, constrained by differential equations with uncertainty. To alleviate the curse of dimensionality, we use tensor product approximations. To handle the non-smoothness of the objective function, we introduce a smoothed version of the shared sparsity objective. We consider both a benchmark elliptic PDE constraint and a more realistic topology optimization problem. We demonstrate that the error converges linearly in iterations and the smoothing parameter and faster than algebraically in the number of degrees of freedom, consisting of the number of quadrature points in one variable and tensor ranks. Moreover, in the topology optimization problem, the smoothed shared sparsity penalty reduces the tensor ranks compared to the unpenalized solution. This enables us to find a sparse high-resolution design under a high-dimensional uncertainty.

Talk 3: TBD
Speaker: Juan Carlos de los Reyes
Abstract: TBD

Session: Derivative-free stochastic optimization methods I
Chair: Stefan Wild
Cluster: Derivative-free Optimization

Talk 1: Improving the robustness of zeroth-order optimization solvers
Speaker: Stefan Wild
Abstract: Zeroth-order optimization solvers are often deployed in settings where little information regarding a problem's conditioning or noise level is known. An ideal solver will perform well in a variety of challenging settings. We report on our experience developing adaptive algorithms, which leverage information learned online to adapt critical algorithmic features. We illustrate our approach in trust-region-based reduced-space methods and show how trained policies can even be deployed effectively in nonstationary cases, where the noise seen changes over the decision space.

Talk 2: A noise-aware stochastic trust-region algorithm using adaptive random subspaces
Speaker: Kwassi Joseph Dzahini
Abstract: We introduce ANASTAARS, a noise-aware stochastic trust-region algorithm using adaptive random subspace strategies, that is effective not only for low- and moderate-dimensional cases, but also for potentially high-dimensional ones. The proposed method achieves scalability by optimizing random models that approximate the objective within low-dimensional affine subspaces, thereby significantly reducing per-iteration costs in terms of function evaluations. These subspaces and their dimension are defined via Johnson--Lindenstrauss transforms such as those obtained from Haar-distributed orthogonal random matrices. In contrast to previous work involving random subspaces with fixed dimensions, ANASTAARS introduces an adaptive subspace selection strategy. Instead of generating a completely new poised set of interpolation points at each iteration, the proposed method updates the model by generating only a few or even a single new interpolation point, reusing past points (and their corresponding function values) from lower-dimensional subspaces in such a way that the resulting set remains poised. This approach not only introduces a novel way to reduce per-iteration costs in terms of function evaluations, but also avoids constructing random models in fixed-dimension subspaces, resulting in a more efficient and optimization process through the use of adaptive subspace models. Furthermore, to address the observation that model-based trust-region methods perform optimally when the signal-to-noise ratio is high, ANASTAARS incorporates a strategy from noise-aware numerical optimization literature by utilizing an estimate of the noise level in each function evaluation. The effectiveness of the method is demonstrated through numerical experiments conducted on problems within the "quantum approximate optimization algorithm" (QAOA) framework.

Talk 3: A consensus-based global optimization method with noisy objective function
Speaker: Greta Malaspina
Abstract: Consensus based optimization is a derivative-free particles-based method for the solution of global optimization problems. Several versions of the method have been proposed in the literature, and different convergence results have been proved, with varying assumptions on the regularity of the objective function and the initial distribution of the particles. However, all existing results assume the objective function to be evaluated exactly at each iteration of the method. In this work, we extend the convergence analysis of a discrete-time CBO method to the case where only a noisy stochastic estimator of the objective function can be computed at a given point. In particular we prove that under suitable assumptions on the oracle’s noise, the expected value of the mean squared distance of the particles from the solution can be made arbitrarily small in a finite number of iterations. Some numerical results showing the impact of noise are also given.

Session: Feasible and infeasible methods for optimization on manifolds I
Chair: Bin Gao
Cluster: Optimization on Manifolds

Talk 1: A double tracking method for optimization with decentralized generalized orthogonality constraints
Speaker: Xin Liu
Abstract: We consider the decentralized optimization problems with generalized orthogonality constraints, where both the objective function and the constraint exhibit a distributed structure. Such optimization problems, albeit ubiquitous in practical applications, remain unsolvable by existing algorithms in the presence of distributed constraints. To address this issue, we convert the original problem into an unconstrained penalty model by resorting to the recently proposed constraint-dissolving operator. However, this transformation compromises the essential property of separability in the resulting penalty function, rendering it impossible to employ existing algorithms to solve. We overcome this difficulty by introducing a novel algorithm that tracks the gradient of the objective function and the Jacobian of the constraint mapping simultaneously. The global convergence guarantee is rigorously established with an iteration complexity. To substantiate the effectiveness and efficiency of our proposed algorithm, we present numerical results on both synthetic and real-world datasets.

Talk 2: A projected gradient descent algorithm for ab initio fixed-volume crystal structure relaxation
Speaker: Yukuan Hu
Abstract: This paper is concerned with ab initio crystal structure relaxation under a fixed unit cell volume, which is a step in calculating the static equations of state and forms the basis of thermodynamic property calculations for materials. The task can be formulated as an energy minimization with a determinant constraint. Widely used line minimization-based methods (e.g., conjugate gradient method) lack both efficiency and convergence guarantees due to the nonconvex nature of the determinant constraint as well as the significant differences in the curvatures of the potential energy surface with respect to atomic and lattice components. To this end, we propose a projected gradient descent algorithm named PANBB. It is equipped with (i) search direction projections for lattice vectors, (ii) distinct curvature-aware initial trial step sizes for atomic and lattice updates, and (iii) a nonrestrictive line minimization criterion as the stopping rule for the inner loop. It can be proved that PANBB favors theoretical convergence to equilibrium states. Across a benchmark set containing 223 structures from various categories, PANBB achieves average speedup factors of approximately 1.41 and 1.45 over the conjugate gradient method and direct inversion in the iterative subspace implemented in off-the-shelf simulation software, respectively. Moreover, it normally converges on all the systems, manifesting its robustness. As an application, we calculate the static equations of state for the high-entropy alloy AlCoCrFeNi, which remains elusive owing to 160 atoms representing both chemical and magnetic disorder and the strong local lattice distortion. The results are consistent with the previous calculations and are further validated by experimental thermodynamic data.

Talk 3: Efficient optimization with orthogonality constraints via random submanifold approach
Speaker: Andi Han
Abstract: Optimization problems with orthogonality constraints are commonly addressed using Riemannian optimization, which leverages the geometric structure of the constraint set as a Riemannian manifold. This method involves computing a search direction in the tangent space and updating via a retraction. However, the computational cost of the retraction increases with problem size. To improve scalability, we propose a method that restricts updates to random submanifolds, reducing per-iteration complexity. We introduce two submanifold selection strategies and analyze the convergence for nonconvex functions, including those satisfying the Riemannian Polyak–Łojasiewicz condition, as well as for stochastic optimization problems. The approach generalizes to quotient manifolds derived from the orthogonal manifold.

Session: Recent Advances in Conic Optimization and Machine Learning
Chair: Godai Azuma
Cluster: Conic and Semidefinite Optimization

Talk 1: Procrustean Differential Privacy: A Parameter-Scalable Method for Privacy-Preserving Collaborative Learning
Speaker: Keiyu Nosaka
Abstract: Privacy-preserving collaborative learning enables multiple parties to jointly train machine learning models without directly sharing sensitive data. While approaches such as Federated Learning and Homomorphic Encryption offer robust privacy guarantees, they often incur significant computational and communication overhead as model complexity increases. In contrast, multiplicative perturbation techniques promise enhanced efficiency; however, they are typically hampered by increased privacy risks from collusion or by a reliance on extensive deep learning-based training to achieve satisfactory performance. In this work, we introduce a novel framework that bridges these extremes by integrating the analytic Gaussian mechanism of differential privacy with the Generalized Orthogonal Procrustes Problem. Our method delivers adjustable privacy–performance trade-offs through tunable differential privacy parameters, allowing practitioners to balance protection and efficiency according to specific application needs. We substantiate our approach with theoretical guarantees and numerical analyses that evaluate its performance across varying privacy levels, data dimensions, and numbers of collaborating parties.

Talk 2: Facial Structure of Copositive and Completely Positive Cones over a Second-Order Cone
Speaker: Mitsuhiro Nishijima
Abstract: A copositive cone over a second-order cone is the closed convex cone of real symmetric matrices whose associated quadratic forms are nonnegative over the given second-order cone. In this talk, we classify the faces of those copositive cones and their duals (i.e., completely positive cones over a second-order cone), and investigate their dimension and exposedness properties. Then we compute two parameters related to chains of faces of both cones. At the end, we discuss some possible extensions of the results with a view toward analyzing the facial structure of general copositive and completely positive cones.

Talk 3: Exact Semidefinite Relaxations for Safety Verification of Neural Network
Speaker: Godai Azuma
Abstract: We study the accuracy of DeepSDP which is proposed as a semidefinite programming (SDP) based method to measure the safety and the robustness of given neural networks by guaranteeing the bounds of their outputs. The dual problem of the DeepSDP is in fact an SDP relaxation of quadratic constraints representing ReLU activation functions. In this talk, we investigate the exactness of the DeepSDP by using exactness conditions for the general SDP relaxation so that the estimated robustness is improved on. We also discuss our assumptions and some results on the accuracy.

Session: Moment-SOS Hierarchy: From Theory to Computation in the Real World (I)
Chair: Heng Yang
Cluster: Conic and Semidefinite Optimization

Talk 1: Polynomial Matrix Optimization, Matrix-Valued Moments, and Sparsity
Speaker: Jie Wang
Abstract: This talk will introduce the matrix version of the moment-SOS hierarchy for solving polynomial matrix optimization problems. Various types of sparsities will be discussed to improve the scalability of the approach.

Talk 2: Practical non-symmetric cone programming algorithms for sums-of-squares optimization
Speaker: Dávid Papp
Abstract: Sums-of-squares relaxations of polynomial optimization problems are usually solved using off-the-shelf semidefinite programming (SDP) methods, which often leads to at least one of the following two problems when the relaxation order (that is, the degree of the SOS polynomials) is high: (1) the time and space complexity of SDP algorithms grow too fast to be practical; (2) the numerical conditioning of the SDPs is prohibitive to obtain accurate solutions. The talk focuses on how both can be mitigated using polynomial interpolation and replacing all-purpose semidefinite programming algorithms with non-symmetric cone programming methods that can optimize directly over sums-of-squares cones. Generalizations to other nonnegativity certificates (SONC, SAGE) will also be briefly discussed.

Talk 3: A squared smoothing Newton Method for semidefinite programming
Speaker: Ling Liang
Abstract: This paper proposes a squared smoothing Newton method via the Huber smoothing function for solving semidefinite programming problems (SDPs). We first study the fundamental properties of the matrix-valued mapping defined upon the Huber function. Using these results and existing ones in the literature, we then conduct rigorous convergence analysis and establish convergence properties for the proposed algorithm. In particular, we show that the proposed method is well-defined and admits global convergence. Moreover, under suitable regularity conditions, i.e., the primal and dual constraint nondegenerate conditions, the proposed method is shown to have a superlinear convergence rate. To evaluate the practical performance of the algorithm, we conduct extensive numerical experiments for solving various classes of SDPs. Comparison with the state-of-the-art SDP solvers demonstrates that our method is also efficient for computing accurate solutions of SDPs.

Session: Variational Analysis: Theory and Applications II
Chair: Walaa Moursi
Cluster: Nonsmooth Optimization

Talk 1: TBA
Speaker: Stephen Simons
Abstract: TBA

Talk 2: TBA
Speaker: Jon Vanderwerff
Abstract: TBA

Talk 3: TBA
Speaker: Gerald Beer
Abstract: TBA

Session: Recent Advances on PDE-constrained optimization packages and libraries : Part I
Chair: Noemi Petra
Cluster: Computational Software

Talk 1: Empowering Numerical Optimization Across Disciplines with the Rapid Optimization Library (ROL)
Speaker: Denis Ridzal
Abstract: The Rapid Optimization Library (ROL) is a versatile, high-performance C++ library designed to address the complex demands of numerical optimization in various scientific and engineering disciplines. As an open-source effort through the Trilinos Project, ROL provides an extensive collection of state-of-the-art optimization algorithms capable of handling any application, hardware architecture, and problem size. This talk introduces ROL's key features, including its abstract linear algebra interface for universal applicability, modern algorithms for smooth, constrained, stochastic, risk-aware, and nonsmooth optimization, and its unique PDE-OPT application development kit for PDE-constrained optimization. Additionally, ROL offers an easy-to-use Python interface, which enhances its accessibility and usability across a wider range of applications and user communities. We highlight ROL's successful uses in fields ranging from electrodynamics and fluid dynamics to super-resolution imaging and machine learning. ROL's design philosophy, emphasizing vector abstractions, matrix-free interfaces, and a comprehensive suite of optimization algorithms, positions it as an important tool for researchers seeking to push the boundaries of numerical optimization. Authors: Robert Baraldi, Brian Chen, Aurya Javeed, Drew Kouri, Denis Ridzal, Greg von Winckel, Radoslav Vuchkov

Talk 2: CLAIRE: Constrained Large Deformation Diffeomorphic Image Registration
Speaker: Andreas Mang
Abstract: We present numerical methods for optimal control problems governed by geodesic flows of diffeomorphisms. Our work focuses on designing efficient numerical methods and fast computational kernels for high-performance computing platforms. We aim to compute a flow map that establishes spatial correspondences between two images of the same scene, modeled as geodesic flows of diffeomorphisms. The related optimization problem is non-convex and non-linear, leading to high-dimensional, ill-conditioned systems. Our solvers use advanced algorithms for rapid convergence and employ adjoint-based, second-order methods for numerical optimization. We provide results from real and synthetic data to assess convergence rates, time to solution, accuracy, and scalability of our methods. We also discuss strategies for preconditioning the Hessian and showcase results from our GPU-accelerated software package termed CLAIRE, which is optimized for clinically relevant problems and scales to hundreds of GPUs on modern architectures.

Talk 3: PyOED: An Extensible Suite for Data Assimilation and Model-Constrained Optimal Design of Experiments
Speaker: Ahmed Attia
Abstract: This talk gives a high-level overview of PyOED, a highly extensible scientific package that enables rapid development, testing, and benchmarking of model-based optimal experimental design (OED) methods for inverse problems. PyOED brings together variational and Bayesian data assimilation (DA) algorithms for inverse problems, optimal design of experiments, and novel optimization, statistical, and machine learning methods, into an integrated extensible research environment. PyOED is continuously being expanded with a plethora of Bayesian inference, DA, and OED methods as well as new scientific simulation models, observation error models, priors, and observation operators. These pieces are added such that they can be permuted to enable developing and testing OED methods in various settings of varying complexities. Authors: Ahmed Attia (ANL), Abhijit Chowdhary (NCSU), Shady Ahmed (PNNL)

Session: Parametric Optimization Problems
Chair: Xiaoqi Yang
Cluster: Fixed Points and Variational Inequalities

Talk 1: Recent stability results in parametric optimization
Speaker: Xiaoqi Yang
Abstract: Recover bounds/relative calmness for sparse optimization models are important for algorithmic convergence analysis in machine learning and compressed sensing. Some recent results in sparse optimization obtained by restricted isometry property and restricted eigenvalue conditions will be reviewed. Lipschitz-like property and Lipschitz continuity are at the core of stability analysis. A projectional coderivative of set-valued mappings will be discussed and and be applied to obtain a complete characterization for a set-valued mapping to have the Lipschitz-property relative to a closed and convex set.

Talk 2: Lipschitz continuity of solution multifunctions of extended l_1 regularization problems
Speaker: Kaiwen Meng
Abstract: In this paper we obtain a verifiable sufficient condition for a polyhedral multifunction to be Lipschitz continuous on its domain. We apply this sufficient condition to establish the Lipschitz continuity of the solution multifunction for an extended l_1 regularization problem with respect to the regularization parameter and the observation parameter under the assumption that the data matrix is of full row rank.

Talk 3: Existence of a solution for stochastic multistage vector variational inequality problems
Speaker: Shengkun Zhu
Abstract: In this talk, we will discuss basic form and extensive forms of a stochastic vector variational inequality problem. We will apply KKM theorem to prove the existence of a solution under the monotonicity and hemi-continuity assumptions.

Session: Computational Frameworks and Applications: Hybridizing Continuous and Discrete Optimization in Practice
Chair: Jordan Jalving & Marta D'Elia
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: Optimal Conceptual Design using Generalized Disjunctive Programming in IDAES/Pyomo
Speaker: E. Soraya Rawlings
Abstract: The need to design more sustainable and energy-efficient processes requires the ability to efficiently pose and solve optimization problems with both discrete and continuous decisions. Traditionally, design optimization problems have been expressed as mixed-integer nonlinear optimization problems (MINLP) using algebraic modeling languages (AMLs; e.g., AIMMS, AMPL, GAMS, JuMP, Pyomo, etc.). A challenge with AMLs is that, not only they combine the structure of the optimization problem with binary variables, but also lack libraries for fast development of process models. An alternative approach is to use an extended mathematical programming environment that provides supplemental capabilities. Relevant in conceptual design are environments with the ability to construct hierarchical models, similar to what is supported in process simulation environments, and the ability to express logical restrictions explicitly in the model. If the environment incorporates both abilities, it can support the construction of design superstructures or topologies that represent all possible combinations of process configurations that we would like to consider in the design process. In this work, we present the application of one such environment to design separation and integrated energy systems. We leverage the open source IDAES platform, which supports the construction of hierarchical process models in Pyomo. We then leverage Generalized Disjunctive Programming to construct design superstructures and systematically convert them to MINLP models that can be solved with standard MINLP solvers. References [1] M. L. Bynum, G. A. Hackebeil, W. E. Hart, C. D. Laird, B. L. Nicholson, J. D. Siirola, J.-P. Watson and D. L. Woodruff, Pyomo - Optimization Modeling in Python, 3rd ed., vol. 67, Springer International Publishing, 2021. [2] Lee, A., Ghouse, J. H., Eslick, J.C., Laird, C.D., Siirola, J.D., Zamarripa, M.A., Gunter, D., Shinn, J. H., Dowling, A. W., Bhattacharyya, D., Biegler, L. T., Burgard, A. P., & Miller, D.C., “The IDAES process modeling framework and model library—Flexibility for process simulation and optimization,” Journal of Advanced Manufacturing and Processing, vol. 3, no. 3, pp. 1-30, 2021. https://doi.org/10.1002/amp2.10095 Disclaimer Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-NA-0003525. This paper describes objective technical results and analysis. Any subjective views or opinions that might be expressed in the paper do not necessarily represent the views of the U.S. Department of Energy or the United States Government.

Talk 2: Bridging Continuous and Discrete Optimization in Julia
Speaker: Thibaut Cuvelier
Abstract: TBA

Talk 3: Computation Design: Integrating Implicit Modeling, Meshless Simulation, and Machine Learning for Optimization with Real-World Efficiency
Speaker: Todd Mcdevitt
Abstract: Across every industry, engineers face ever-shrinking time-to-market demands, often needing more time to optimize their designs fully. Traditional CAD and simulation tools fall short of enabling practical usage of optimization and generative design due to persistent bottlenecks in geometry regeneration and meshing. These limitations prevent engineers from fully leveraging the design space while meeting project timelines. In this presentation, we introduce a new paradigm in mechanical design optimization that integrates implicit modeling, meshless simulation methods, and machine learning to address these challenges. Through diverse use cases across industries, we demonstrate how these techniques unlock the practical use of optimization while adhering to project timelines. We will also compare the computational costs of surrogate models versus the direct evaluation of objective functions with the original high-fidelity model. Attendees will gain insights into the practical deployment of optimization workflows in industrial, fast-paced, multi-disciplinary settings.

Session: Recent advances in open-source continuous solvers
Chair: Charlie Vanaret
Cluster: Computational Software

Talk 1: A new parallel interior point solver for HiGHS
Speaker: Filippo Zanetti
Abstract: HiGHS is open-source software for linear, mixed-integer and quadratic optimization. It includes an interior point method based on an iterative Krylov solver, that has attracted much attention, in particular from the energy modelling community. In this talk, the latest news on the development of a new interior point solver, based on a direct factorization, are presented. The talk discusses multiple approaches that have been considered and highlights the improvements compared to the existing solver. Issues regarding regularization, accuracy, dealing with dense columns and parallelization are also mentioned.

Talk 2: Uno, a modern Lagrange-Newton solver for nonconvex constrained optimization
Speaker: Charlie Vanaret
Abstract: Derivative-based iterative methods for nonlinearly constrained nonconvex optimization usually share common algorithmic components, such as strategies for computing a descent direction and mechanisms that promote global convergence. Based on this observation, we introduce an abstract framework with eight building blocks that describes most derivative-based iterative methods and unifies their workflows. We then present Uno, a Lagrange-Newton solver that implements our abstract framework and allows the automatic generation of various strategy combinations with no programming effort from the user. Uno is meant to (1) organize mathematical optimization strategies into a coherent hierarchy; (2) offer a wide range of efficient and robust methods that can be compared for a given instance; (3) reduce the cost of development and maintenance of multiple optimization solvers; and (4) enable researchers to experiment with novel optimization strategies while leveraging established subproblem solvers and interfaces to modeling languages. We demonstrate that Uno is highly competitive against state-of-the-art solvers such as filterSQP, IPOPT, SNOPT, MINOS, LANCELOT, LOQO and CONOPT. Uno is available as open-source software under the MIT license at https://github.com/cvanaret/Uno

Talk 3: Solving Direct Optimal Control Problems in Real-Time: A Byrd-Omojokun Funnel Solver for acados
Speaker: David Kiessling
Abstract: We present a nonlinear optimization SQP-type method within the acados software framework for solving direct optimal control in real time. acados is a versatile software framework that implements fast solvers exploiting the specific optimal control problem structure using tailored linear algebra and numerical integration methods. This talk focuses on a novel SQP implementation using a funnel to drive global convergence. We present a novel implementation of a Byrd-Omojokun method avoiding infeasible subproblems. Additionally, we will present numerical results comparing our solver against other state-of-the art optimization solvers.

Session: Nonsmooth Optimization - Theory and Algorithms
Chair: Shaoning Han
Cluster: nan

Talk 1: Analysis of a Class of Heaviside Composite Minimization Problems
Speaker: Shaoning Han
Abstract: The minimization of nonclosed functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance constrained stochastic programs, a Heaviside composite optimization problem is one whose objective and constraints are defined by sums of possibly nonlinear multiples of such composite functions. In this talk, we first present difficulties of tackling such problems using existing optimization techniques. Then we establish stationarity conditions for the problem, and introduce a sufficient condition, termed local convex-like property, under which the proposed stationary point is a local minimizer. Finally, we briefly discuss solution strategies via lifting and reformulation techniques. For details of this work, please refer to "Han S, Cui Y, Pang J-S (2024) Analysis of a class of minimization problems lacking lower semicontinuity. Mathematics of Operations Research."

Talk 2: Non-smooth stochastic gradient descent using smoothing functions
Speaker: Jingfu Tan
Abstract: In this talk, we address stochastic optimization problems involving a composition of a non-smooth outer function and a smooth inner function, a formulation frequently encountered in machine learning and operations research. To deal with the non-differentiability of the outer function, we approximate the original non-smooth function using smoothing functions, which are continuously differentiable and approach the original function as a smoothing parameter goes to zero (at the price of increasingly higher Lipschitz constants). The proposed smoothing stochastic gradient method iteratively drives the smoothing parameter to zero at a designated rate. We establish convergence guarantees under strongly convex, convex, and nonconvex settings, proving convergence rates that match known results for non-smooth stochastic compositional optimization. In particular, for convex objectives, smoothing stochastic gradient achieves a~$1/T^{1/4}$ rate in terms of the number of stochastic gradient evaluations. We further show how the general compositional and finite sum compositional problems (widely used frameworks in large-scale machine learning and risk-averse optimization) fit the assumptions needed for the rates (unbiased gradient estimates, bounded second moments, and accurate smoothing errors). We will present numerical results indicating that smoothing stochastic gradient descent is a competitive method for certain classes of problems.

Talk 3: (Canceled) Convergence analysis of the 9th Chebyshev Method for Nonconvex, Nonsmooth Optimization Problems
Speaker: Jiabao Yang
Abstract: Ushiyama-Sato-Matsuo (2022) (hereafter referred to as [USM]) showed that some optimization methods can be regarded as numerical analysis methods for ordinary differential equations. [USM] proposed the 9th Chebyshev method, an optimization method that allows a larger step width than the steepest descent method, under the assumption that the objective function is convex and differentiable. Observing the left edge of the stability domain, we see the 9th Chebyshev method should allow about 78 times larger steps than the steepest descent method. On the other hand, the 9th Chebyshev method requires 9 evaluations of the gradient per iteration, while the steepest descent method requires only one. Considering most calculation time is spent on the gradient, we expect that the 9th Chebyshev method converges 78/9 = 8.7 times faster. However, there are many cases in the world where differentiable, smooth, convex, etc. cannot be used. For example, problems in image analysis and voice recognition require the use of nondifferentiable, nonsmooth, and nonconvex functions. The steepest descent method or the 9th Chebyshev method proposed by [USM] assumes that the objective function is convex and differentiable, and thus cannot be applied to problems with an objective function that is not necessarily differentiable. For nonconvex optimization problems, finding a good local optimal solution is a realistic goal, and Riis-Ehrhardt-Quispel-Scholieb (2022) (hereafter referred to as [REQS]) introduced an alternative concept of differentiation called “Clarke subdifferential” for functions that are not always differentiable, and proposed an optimization method that can be applied to objective functions that are not necessarily differentiable and convex. Although the objective function is not assumed to be differentiable or convex, such as being locally Lipschitz continuous, [REQS] prove that the optimization method converges to the set of Clarke stationary points defined in the framework of Clarke subdifferential under the condition that some assumptions are satisfied. In this talk, based on the proof method of [REQS], we propose a method that combines the method of [REQS] and the method of [USM] and prove that the proposed method converges to the set of Clarke stationary points under the same objective function assumption as [REQS]. Refernces: 1, Kansei Ushiyama, Shun Sato, Takayasu Matsuo, "Deriving efficient optimization methods based on stable explicit numerical methods", JSIAM Letters Vol.14 (2022) pp.29–32 2, Erlend S.Riis, Matthias J.Ehrhardt, G.R.W.Quispel, Carola-Bibiane Schonlieb, "A Geometric Integration Approach to Nonsmooth, Nonconvex Optimisation", Foundations of Computational Mathematics (2022) 22:1351–1394

Session: Algorithms for Nonconvex Problems
Chair: Yulin Peng
Cluster: nan

Talk 1: NEW ALGORITHMS FOR HARD OPTIMIZATION problems PROBLEMS.
Speaker: Aharonl Ben-Tal
Abstract: NEW ALGORITHMS FOR HARD (NONCONVEX) OPTIMIZATION PROBLEMS. The problems addressed in this talk are: (1) Max of convex function (2) Max of max of convex function (3) Max of Difference of convex functions. Almost all existing algorithms for such problems suffer from might be called “the curse of obtaining a good starting point”. In our algorithms a starting point is computed by employing only tractable methods for convex problems. The core algorithm on which the algorithms for problems (2) and (3) are based, is the COMAX algorithm developed for problem (1), See Ben-Tal, A. and Roos E., "An Algorithm for Maximizing a Convex Function Based on its Minimizer". INFORMS Journal on Computing Volume: 34, Number: 6 (November-December 2022): 3200-

Talk 3: Conditional Infimum, Hidden Convexity and the S-Procedure
Speaker: Michel De Lara

Session: Methods for Large-Scale Nonlinear Optimization V
Chair: Raghu Bollapragada
Cluster: Nonlinear Optimization

Talk 1: The Interior-Point Frank-Wolfe Method for Minimizing Smooth Convex Functionals over Linearly Constrained Probability Spaces
Speaker: Di Yu
Abstract: Several important and large problem classes including optimal experimental design, emergency volunteer response, spectral optimal transport, and certain queuing problems can be posed as that of minimizing a smooth convex functional over the space of compactly supported probability measures subject to a linear constraint map. We introduce the interior-point Frank-Wolfe (IPFW) method for solving such problems, where a sequence of barrier problems is constructed as a way to handle the constraints, each of which is solved to increasing accuracy using a Frank-Wolfe method. Importantly, the Frank-Wolfe sub-problems are shown to have a ``closed-form'' solution expressed in terms of the constraint functionals and the influence function of the objective. The sequence of probability measures resulting from the IPFW framework is shown to converge in a certain sense to the correct solution, along with a complexity calculation. The problem and the proposed solution is illustrated through examples.

Talk 2: Local convergence of adaptively regularized tensor methods
Speaker: Karl Welzel
Abstract: Tensor methods are methods for unconstrained continuous optimization that can incorporate derivative information of up to order p > 2 by computing a step based on the pth-order Taylor expansion at each iteration. The most important among them are regularization-based tensor methods which have been shown to have optimal worst-case iteration complexity of finding an approximate minimizer. Moreover, as one might expect, this worst-case complexity improves as p increases, highlighting the potential advantage of tensor methods. Still, the global complexity results only guarantee pessimistic sublinear rates, so it is natural to ask how local rates depend on the order of the Taylor expansion p. In the case of functions that are uniformly convex of order q (ones that around the minimizer x* grow like the distance to x* to the qth power) and a fixed regularization parameter, the answer is given in a paper by Doikov and Nesterov from 2022: we get (p/(q-1))th-order local convergence of function values and gradient norms, if p > q-1. In particular, when the Hessian is positive definite at the minimizer (q=2) we get pth-order convergence, but also when the Hessian is singular at x* (q > 2) superlinear convergence (compared to Newton's linear convergence) is possible as long as enough derivatives are available. The value of the regularization parameter in their analysis depends on the Lipschitz constant of the pth derivative. Since this constant is not usually known in advance, adaptive regularization methods are more practical. We extend the local convergence results to locally uniformly convex functions and fully adaptive methods. We discuss how for p > 2 it becomes crucial to select the "right" minimizer of the regularized local model in each iteration to ensure all iterations are eventually successful. Counterexamples show that in particular the global minimizer of the subproblem is not suitable in general. If the right minimizer is used, the (p/(q-1))th-order local convergence is preserved, otherwise the rate stays superlinear but with an exponent arbitrarily close to one depending on the algorithm parameters.

Talk 3: Noise-Aware Sequential Quadratic Programming for Equality Constrained Optimization with Rank-Deficient Jacobians
Speaker: Jiahao Shi
Abstract: We propose and analyze a sequential quadratic programming algorithm for minimizing a noisy nonlinear smooth function subject to noisy nonlinear smooth equality constraints. The algorithm uses a step decomposition strategy and, as a result, is robust to potential rank-deficiency in the constraints, allows for two different step size strategies, and has an early stopping mechanism. Under linear independence constraint qualifications, convergence is established to a neighborhood of a first-order stationary point, where the radius of the neighborhood is proportional to the noise level in the objective function and constraints. Moreover, in the rank deficient setting, convergence to a neighborhood of an infeasible stationary point is established. Numerical experiments demonstrate the efficiency and robustness of the proposed method.

Session: Continuous and Discrete Optimization
Chair: Marcia Fampa
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: Stochastic Iterative Methods for Linear Problems with Adversarial Corruption
Speaker: Jamie Haddock
Abstract: Stochastic iterative methods, like stochastic gradient descent or the randomized Kaczmarz method, have gained popularity in recent times due to their amenability to large-scale data and distributed computing environments. This talk will focus on variants of the randomized Kaczmarz methods developed for problems with significant or adversarial corruption present in the problem-defining data. This type of corruption arises frequently in applications like medical imaging, sensor networks, error correction, and classification of mislabeled data. We will focus on recent results for linear feasibility problems and tensor regression problems.

Talk 2: Volume formulae for the convex hull of the graph of a $n$-monomial in some special cases
Speaker: Emily Speakman
Abstract: The spatial branch-and-bound algorithmic framework, used for solving non-convex mixed-integer nonlinear optimization problems, relies on obtaining quality convex approximations of the non-convex substructures in a problem formulation. A common example is a simple monomial, $y=x_1x_2, \dots, x_n$, defined over the box $[a_1, b_1] \times [a_2, b_2] \times \dots \times [a_n, b_n] \subseteq \R^n$. There are many choices of convex set that could be used to approximate this solution set, with the (polyhedral) convex hull giving the “tightest” or best possible outer approximation. By computing the volume of the convex hull, we obtain a measure that can be used to evaluate other convex outer approximations in comparison. In previous work, we have obtained a formula for the volume of the convex hull of the graph of a trilinear monomial (i.e., $n=3$) in terms of the $6 = 2n$ box parameters. Here, we seek to extend our work to the case of general $n$ by making additional assumptions on the box domain. In particular, we assume that only $k$ variables have a non-zero lower bound. In this work, we consider $k=1,2,3$, and conjecture the volume of the convex hull in each case. Moreover, we provide a proof for the case $k=1$.

Talk 3: New hierarchies for disjoint bilinear programs
Speaker: Mohit Tawarmalani
Abstract: Disjoint bilinear programs are mathematical optimization problems involving minimization of a bilinear function over a Cartesian product of polytope. In this paper, we iteratively obtain, in closed-form, rational functions that are barycentric coordinates of successively tighter outer-approximations of a polytope. This procedure converges in m steps, where m is the number of constraints describing the polytope. Using this procedure, we construct a finite hierarchy of relaxations that in m steps describes the convex hull of bilinear functions over the feasible region providing a linear reformulation for disjoint bilinear programming.

Session: AI Meets Optimization (Part 2)
Chair: Wotao Yin
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)

Talk 1: TBD
Speaker: Jan Drgona
Abstract: TBD

Talk 2: TBD
Speaker: Jialin Liu
Abstract: TBD

Talk 3: TBD
Speaker: Junchi Yan
Abstract: TBD

Session: Recent advances in algorithms for large-scale optimization (I)
Chair: Xudong Li
Cluster: Computational Software

Talk 1: Infeasible Model Analysis In the Optverse Solver
Speaker: Zirui Zhou
Abstract: Isolating an Irreducible Infeasible Subset (IIS) of constraints is the best way to analyze an infeasible optimization model. The OptVerse solver incorporates very fast algorithms for this purpose. The LP analyzer takes advantage of the presolver to isolate a small subset of constraints for conventional analysis, whether or not the presolve detects infeasibility. The MIP analyzer uses new techniques to very quickly find an IIS that includes the integrality restrictions. Experimental results are given.

Talk 2: HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems
Speaker: Yancheng Yuan
Abstract: This talk introduces an efficient HOT algorithm for solving the optimal transport (OT) problems with finite supports. We particularly focus on an efficient implementation of the HOT algorithm for the case where the supports are in $\mathbb{R}^2$ with ground distances calculated by $L_2^2$-norm. Specifically, we design a Halpern accelerating algorithm to solve the equivalent reduced model of the discrete OT problem. Moreover, we derive a novel procedure to solve the involved linear systems in the HOT algorithm in linear time complexity. Consequently, we can obtain an $\varepsilon$-approximate solution to the optimal transport problem with $M$ supports in $O(M^{1.5}/\varepsilon)$ flops, which significantly improves the best-known computational complexity. We further propose an efficient procedure to recover an optimal transport plan for the original OT problem based on a solution to the reduced model, thereby overcoming the limitations of the reduced OT model in applications that require the transport map. We implement the HOT algorithm in PyTorch and extensive numerical results show the superior performance of the HOT algorithm compared to existing state-of-the-art algorithms for solving the OT problems.

Talk 3: DNNLasso: Scalable Graph Learning for Matrix-Variate Data
Speaker: Meixia Lin
Abstract: We consider the problem of jointly learning row-wise and column-wise dependencies of matrix-variate observations, which are modelled separately by two precision matrices. Due to the complicated structure of Kronecker-product precision matrices in the commonly used matrix-variate Gaussian graphical models, a sparser Kronecker-sum structure was proposed recently based on the Cartesian product of graphs. However, existing methods for estimating Kronecker-sum structured precision matrices do not scale well to large scale datasets. In this work, we introduce DNNLasso, a diagonally non-negative graphical lasso model for estimating the Kronecker-sum structured precision matrix, which outperforms the state-of-the-art methods by a large margin in both accuracy and computational time.

Session: Advances in Mixed-Integer Optimization
Chair: Alberto Del Pia
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: Convexification Techniques For Logical Implication Constraints Involving Cardinality Requirements
Speaker: Jean-Philippe Richard
Abstract: Cardinality requirements and implications between groups of distinct variables are pervasive in applications and are often modeled through the use of integer programming techniques. We describe a general constructive scheme that allows for the convex hull of sets involving logical implication constraints relating the cardinality of groups of variables to be derived in a higher dimensional space. We also discuss aspects of projecting the formulations. We provide simple illustrative applications of the scheme, which subsume existing results in the literature.

Talk 2: Transfer Theorems in Mixed-Integer Convex Optimization
Speaker: Phillip Kerger
Abstract: In this talk, we will present two lines of work that explore the transferability of results between different settings in optimization. First, we will show how performance guarantees from noise-free convex optimization can be adapted to the stochastic setting, even when mixed-integer variables are present. This is achieved through a black-box transfer approach that applies broadly to first-order methods. Second, we will discuss how complexity results from continuous convex optimization can be extended to the mixed-integer setting, which leads to new lower bounds under various oracles, such as those with partial first-order information. Such black-box approaches are especially appealing to have results in easier-to-analyze cases immediately transfer to more complex ones. Finally, some remaining open questions will be discussed.

Talk 3: Extended formulations for some class of Delta-modular IPs
Speaker: Luze Xu
Abstract: Conforti et al. give a compact extended formulation for a class of bimodular-constrained integer programs, namely those that model the stable set polytope of a graph with no disjoint odd cycles. We extend their techniques to design compact extended formulations for the integer hull of translated polyhedral cones whose constraint matrix is strictly $\Delta$-modular and has rows that represent a cographic matroid. Our work generalizes the important special case from Conforti et al. concerning 4-connected graphs with odd cycle transversal number at least 4. We also discuss the necessity of our assumptions. This is joint work with Joseph Paat and Zach Walsh.

Session: Adaptive Methods
Chair: Ilyas Fatkhullin
Cluster: Optimization For Data Science

Talk 1: The Price of Adaptivity in Stochastic Convex Optimization
Speaker: Oliver Hinder
Abstract: We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a ``price of adaptivity'' (PoA) that, roughly speaking, measures the multiplicative increase in suboptimality due to uncertainty in these parameters. When the initial distance to the optimum is unknown but a gradient norm bound is known, we show that the PoA is at least logarithmic for expected suboptimality, and double-logarithmic for median suboptimality. When there is uncertainty in both distance and gradient norm, we show that the PoA must be polynomial in the level of uncertainty. Our lower bounds nearly match existing upper bounds, and establish that there is no parameter-free lunch. En route, we also establish tight upper and lower bounds for (known-parameter) high-probability stochastic convex optimization with heavy-tailed and bounded noise, respectively.

Talk 2: Adaptive Online Learning and Optimally Scheduled Optimization
Speaker: Ashok Cutkosky
Abstract: In this talk I will describe some recent advances in online learning, and how these advances result in improved algorithms for stochastic optimization. We will first describe new online optimization algorithms that achieve optimal regret with neither prior knowledge of Lipschitz constants nor bounded domain assumptions, which imply stochastic optimization algorithms that perform as well as SGD with an optimally-tuned learning rate. We will then survey new and improved conversions from online to stochastic optimization that shed light on heuristic learning rate schedules popular in practice, and illustrate how this analysis allows us to begin investigation into identifying an optimal schedule of learning rates. This is in contrast to most literature on adaptive stochastic optimization that typically seeks to compete only with a single fixed learning rate. We will conclude by highlighting open problems in both online and stochastic optimization.

Talk 3: Unveiling the Power of Adaptive Methods Over SGD: A Parameter-Agnostic Perspective
Speaker: Junchi Yang
Abstract: Adaptive gradient methods are popular in optimizing modern machine learning models, yet their theoretical benefits over vanilla Stochastic Gradient Descent (SGD) remain unclear. We examines the convergence of SGD and adaptive methods when their hyperparameters are set without knowledge of problem-specific parameters. First, for smooth functions, we compare SGD to well-known adaptive methods like AdaGrad, Normalized SGD with Momentum (NSGD-M), and AMSGrad. While untuned SGD attains the optimal convergence rate, it comes at the expense of an unavoidable exponential dependence on the smoothness constant. In contrast, several adaptive methods reduce this exponential dependence to polynomial. Secondly, for a broader class of functions characterized by (L0, L1) smoothness, SGD fail without proper tuning. We show NSGD-M achieves a near-optimal rate, despite an exponential dependence on the L1 constant, which we show is unavoidable for a family of normalized momentum methods.

Session: Recent Advances in Large-scale Optimization III
Chair: Salar Fattahi
Cluster: Nonlinear Optimization

Talk 1: Convexification of a class of optimization problems with step functions
Speaker: Andres Gomez
Abstract: We study nonlinear optimization problems with discontinuous step functions. This class of problems arises often in statistical problems, modeling correct/incorrect predictions with linear classifiers, fairness and nearly isotonic regression. We discuss special classes of problems where convex hulls can be computed explicitly, and discuss algorithmic implementations of the convexifications. Our computational results indicate a good statistical estimators can be obtained from the optimal solutions of the convex relaxations, and that exact methods can be substantially improved in some cases.

Talk 2: AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems
Speaker: Xuan Zhang
Abstract: We consider double-regularized nonconvex-strongly concave (NCSC) minimax problems of the form (P) : minx maxy g(x) + f (x,y) − h(y), where g, h are closed convex, f is L-smooth in (x, y) and strongly concave in y. We propose a proximal alternating gradient descent ascent method AGDA+ that can adaptively choose nonmonotone primal-dual stepsizes to compute an approximate stationary point for (P) without requiring the knowledge of the global Lipschitz constant L. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out by its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyper-parameters. AGDA+ achieves the optimal iteration complexity of O(ε-2) and it is the first step-size search method for NCSC minimax problems that require only O(1) calls to ∇f per backtracking iteration. We also discuss how AGDA+ can easily be extended to search for μ as well. The numerical experiments demonstrate its robustness and efficiency.

Talk 3: Towards Weaker Variance Assumptions for Stochastic Optimization
Speaker: Ahmet Alacaoglu
Abstract: We revisit a classical assumption for analyzing stochastic gradient algorithms where the squared norm of the stochastic subgradient (or the variance for smooth problems) is allowed to grow as fast as the squared norm of the optimization variable. We contextualize this assumption in view of its inception in the 1960s, its seemingly independent appearance in the recent literature, its relationship to weakest-known variance assumptions for analyzing stochastic gradient algorithms, and its relevance even in deterministic problems for non-Lipschitz nonsmooth convex optimization. We build on and extend a connection recently made between this assumption and the Halpern iteration. For convex nonsmooth, and potentially stochastic, optimization we provide horizon-free algorithms with last-iterate rates. For problems beyond simple constrained optimization, such as convex problems with functional constraints, we obtain rates for optimality measures that do not require boundedness of the feasible set.

Session: Preference Robust Optimization
Chair: Wenjie Huang
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: conformal inverse optimization
Speaker: Erick Delage
Abstract: TBA

Talk 2: Preference robust optimization with quasi-concave choice functions in multi-attribute decision making: characterization and computation
Speaker: Wenjie Huang
Abstract: TBA

Talk 3: Adaptive Preference Elicitation in Preference Robust CPT-Based Shortfall
Speaker: Sainan Zhang
Abstract: TBA

Session: Dynamic Optimization: Deterministic and Stochastic Continuous-time Models II
Chair: Cristopher Hermosilla
Cluster: Multi-agent Optimization and Games

Talk 1: Average Cost Problems Subject to State Constraints
Speaker: Nathalie Khalil
Abstract: Control systems with unknown parameters provide a natural framework for modeling uncer- tainties in various applications. In this work, we focus on pathwise state-constrained optimal control problems where these unknown parameters affect the system’s dynamics, cost function, endpoint constraint, and state constraint. The objective is to minimize a cost criterion expressed in integral form, the so-called “average cost”, with the cost function evaluated relative to a refer- ence probability measure defined over the set of unknown parameters. For this class of problems, we derive necessary optimality conditions. By using an average cost criterion, this approach offers an alternative to traditional minimax or robust optimization methods.

Talk 2: Degeneration in Optimal Control Problems with Non-regular Mixed Constraints
Speaker: Karla Cortez
Abstract: In this talk we will discuss the emergence of the degeneration phenomenon in the necessary conditions derived in recent literature on optimal control problems with non-regular mixed constraints. We will examine how the lack of regularity in these constraints can lead to trivial multipliers, hindering the applicability of classical optimality conditions. To address this issue, we will present non-degeneration conditions that ensure the existence of non-trivial multipliers in these problems and we will illustrate their potential through examples and preliminary results. The talk will conclude with a discussion on future directions for extending and validating these findings.

Talk 3: Uniqueness of Multipliers in Optimal Control Problems
Speaker: Jorge Becerril
Abstract: In this talk, we explore conditions for the uniqueness of multipliers in optimal control problems across different settings. We start with the simplest case involving only isoperimetric constraints, highlighting the connection between uniqueness and key concepts such as regularity and normality. Next, we examine optimal control problems with regular mixed constraints, focusing on piecewise continuous controls. In this context, the continuity assumption allows us to relate uniqueness to the observability of a certain no-input linear system. Under additional assumptions, using results from viability theory, we can establish a one-to-one correspondence between the set of Lagrange multipliers and the initial value of certain set-valued function. Lastly, we discuss ongoing efforts to extend these findings to the case of essentially bounded controls.

Session: Models and Algorithms for Optimization with Rare Events
Chair: Anirudh Subramanyam
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Decision-Making under Extreme Risks: Configuring Optimization Algorithms for Rare-Event Optimization
Speaker: Henry Lam
Abstract: We consider stochastic optimization where the goal is not only to optimize an average-case objective, but also mitigate the occurrence of rare but catastrophic events. This problem, which is motivated from emerging applications such as safe AI, requires an integration of variance reduction methods into sampling-based optimization algorithms in order to attain sufficient solution accuracy. However, we explain how natural variance-reduction-optimization integration, even executed in an adaptive fashion studied by recent works, encounters fundamental challenges. On a high level, the challenge arises from the extreme sensitivity of tail-based objectives with respect to the decision variables, which renders the failure of traditional Lipschitz-based analyses. We offer some potential remedies and supporting numerical results.

Talk 2: Risk-Aware Path Integral Diffusion to Sample Rare Events
Speaker: Michael Chertkov
Abstract: TBD

Talk 3: Scaling Scenario-Based Chance-Constrained Optimization under Rare Events
Speaker: Jaeseok Choi
Abstract: Chance-constrained optimization is a suitable modeling framework for mitigating extreme event risk in many practical settings. The scenario approach is a popular solution method for chance-constrained problems, due to its straightforward implementation and ability to preserve problem structure. However, for safety-critical applications where violating constraints is nearly unacceptable, the scenario approach becomes computationally infeasible due to the excessively large sample sizes it demands. We address this limitation with a new yet straightforward decision-scaling technique. Our method leverages large deviation principles and relies on only mild nonparametric assumptions about the underlying uncertainty distributions. The method achieves an exponential reduction in sample size requirements compared to the classical scenario approach for a wide variety of constraint structures, while also guaranteeing feasibility with respect to the uncertain constraints. Numerical experiments spanning engineering and management applications show that our decision-scaling technique significantly expands the scope of problems that can be solved both efficiently and reliably.

Session: First-order methods for nonsmooth and constrained optimization problems
Chair: Digvijay Boob
Cluster: Nonlinear Optimization

Talk 1: Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces
Speaker: Zhe Zhang
Abstract: Non-smoothness is a major bottleneck to efficient optimization. In the absence of smoothness, the theoretical convergence rates drop from linear to sublinear for convex programs, and become orders of magnitude worse for nonconvex programs. Moreover, this huge is known to be unimprovable in general. We focus on mild, structured non-smooth problems: piecewise smooth (PWS) functions whose domain can be partitioned into subsets such that restricted to each subset the function is smooth. PWS functions cover ReLU functions, L1-penalties, and min-max saddle point problems as special cases. In particular, we study convex PWS functions for which we present globally linear convergent methods under the quadratic growth condition; as a corollary, we improve the iteration complexity for solving weakly convex PWS problems by orders of magnitude. Importantly, our method does not require any knowledge about individual smooth pieces, and is thus applicable even to general non-smooth programs exhibiting local PWS structure.

Talk 2: Primal-Dual Algorithm with Last iterate Convergence Guarantees for Stochastic Convex Optimization Problems
Speaker: Mohammad Khalafi
Abstract: We provide the first method that obtains the best-known convergence rate guarantees on the last iterate for stochastic composite nonsmooth convex function-constrained optimization problems. Our novel and easy-to-implement algorithm is based on the augmented Lagrangian technique and uses a new linearized approximation of constraint functions, leading to its name, the Augmented Constraint Extrapolation (Aug-ConEx) method. We show that Aug-ConEx achieves convergence rate in the nonsmooth stochastic setting without any strong convexity assumption and for the same problem with strongly convex objective function. While optimal for nonsmooth and stochastic problems, the Aug-ConEx method also accelerates convergence in terms of Lipschitz smoothness constants to and in the aforementioned cases, respectively. To our best knowledge, this is the first method to obtain such differentiated convergence rate guarantees on the last iterate for a composite nonsmooth stochastic setting without additional factors. We validate the efficiency of our algorithm by comparing it with a state-of-the-art algorithm through numerical experiments.

Talk 3: An Optimal Method for Minimizing Heterogeneously Smooth and Convex Compositions
Speaker: Aaron Zoll
Abstract: This talk will discuss a universal, optimal algorithm for convex minimization problems of the composite form f(x) + h(g_1(x), ..., g_m(x)). We allow each component function g_i(x) to independently range from being nonsmooth Lipschitz to smooth and from convex to strongly convex, described by notions of Holder continuous gradients and uniform convexity. We note that although the objective is built from a heterogeneous combination of components, it does not necessarily possess any smoothness, Lipschitzness, or any favorable structural properties. Regardless, our proposed sliding accelerated gradient method converges at least as fast as the optimal rate guarantees in terms of oracle access to (sub)gradients of each g_i seperately. Furthermore, given access to an estimate of the initial distance to optimal, we provide a “mostly parameter-free” variant. As a key application, fixing h as a nonpositive indicator function, this model readily captures functionally constrained minimization f(x) subject to g_i(x) \leq 0. Our algorithm and analysis are directly inspired by the Q-analysis technique developed for such smooth constrained minimization by Zhang and Lan. Our theory recovers their accelerated guarantees and extends them to benefit from heterogeneously smooth and convex constraints.

Session: Optimization for Machine Learning and AI
Chair: Tianbao Yang
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Model Developmental Safety: A Constrained Optimization Approach
Speaker: Gang Li
Abstract: In this talk, we introduce introduce model developmental safety as a guarantee of a learning system such that in the model development process the new model should strictly preserve the existing protected capabilities of the old model while improving its performance on target tasks. To ensure the model developmental safety, we present a safety-centric framework by formulating the model developmental safety as data-dependent constraints. Under this framework, we study how to develop a pretrained vision-language model (aka the CLIP model) for acquiring new capabilities or improving existing capabilities of image classification. We propose an efficient constrained optimization algorithm with theoretical guarantee and use its insights to finetune a CLIP model with task-dependent heads for promoting the model developmental safety. Our experiments on improving vision perception capabilities on autonomous driving and scene recognition datasets demonstrate the efficacy of the proposed approach.

Talk 2: Provable Accelerated Convergence of Nesterov’s Momentum for Deep ReLU Neural Networks
Speaker: Jasper Liao
Abstract: Current state-of-the-art analyses on the convergence of gradient descent for training neural networks focus on characterizing properties of the loss landscape, such as the Polyak-Lojaciewicz (PL) condition and the restricted strong convexity. While gradient descent converges linearly under such conditions, it remains an open question whether Nesterov’s momentum enjoys accelerated convergence under similar settings and assumptions. In this work, we consider a new class of objective functions, where only a subset of the parameters satisfies strong convexity, and show Nesterov’s momentum achieves acceleration in theory for this objective class. We provide two realizations of the problem class, one of which is deep ReLU networks, which constitutes this work as the first that proves an accelerated convergence rate for non-trivial neural network architectures.

Talk 3: In-processing Methods for Training Partially Fair Predictive Models Based on Difference-of-Convex Constraints
Speaker: Qihang Lin
Abstract: Fairness in machine learning has become a critical concern, particularly in high-stakes applications. Existing approaches often focus on achieving full fairness across all score ranges generated by predictive models, ensuring fairness in both high and low-scoring populations. However, this stringent requirement can compromise predictive performance and may not align with the practical fairness concerns of stakeholders. In this work, we propose a novel framework for building partially fair machine learning models, which enforce fairness within a specific score range of interest, such as the middle range where decisions are most contested, while maintaining flexibility in other regions. We introduce two statistical metrics to rigorously evaluate partial fairness within a given score range, such as the top 20%–60% of scores. To achieve partial fairness, we propose an in-processing method by formulating the model training problem as constrained optimization with difference-of-convex constraints, which can be solved by an inexact difference-of-convex algorithm (IDCA). We provide the complexity analysis of IDCA for finding a nearly KKT point. Through numerical experiments on real-world datasets, we demonstrate that our framework achieves high predictive performance while enforcing partial fairness where it matters most.

Session: Recent progresses in derivative-free optimization II
Chair: Jeffrey Larson
Cluster: Derivative-free Optimization

Talk 1: Some Available Derivative (SAD) Optimization
Speaker: Jeffrey Larson
Abstract: Many practical optimization problems involve objective functions where gradient information is unavailable or expensive to compute for certain variables but is readily available for other variables. This talk presents an optimization method that effectively incorporates available partial gradient information with state-of-the-art derivative-free optimization methods. We introduce a new algorithm tailored to this setting, demonstrate its effectiveness through numerical experiments, and discuss its application to optimizing fusion stellarator designs, where coil parameter gradients are accessible, but plasma parameter gradients are not.

Talk 2: Barycenter of weight coefficient region of least norm updating quadratic models with vanishing trust-region radius
Speaker: Pengcheng Xie
Abstract: Derivative-free optimization problems, where objective function derivatives are unavailable, can be addressed using local quadratic models within a trust-region algorithm. We propose a model updating approach when high accuracy is demanded, such as when the trust-region radius vanishes. Our approach uses the barycenter of a particular coefficient region and is shown to be advantageous in numerical results.

Session: Optimization on Riemannian manifolds and stratified sets (1/2)
Chair: Guillaume Olikier
Cluster: Optimization on Manifolds

Talk 1: First-order optimization on stratified sets
Speaker: Guillaume Olikier
Abstract: This talk considers the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on a closed subset of a Euclidean vector space that can be partitioned into finitely many smooth submanifolds. The partition is called a stratification and the submanifolds are called the strata. Under suitable assumptions on the stratification, first-order methods are proposed that generate a sequence in the set whose accumulation points are guaranteed to be Bouligand stationary. These methods combine retracted line searches along descent directions selected in the Bouligand tangent cone and projections onto the strata. Examples of a set satisfying the assumptions include the algebraic variety of real matrices of upper-bounded rank and its intersection with the cone of symmetric positive-semidefinite matrices. On these sets, Bouligand stationarity is the strongest necessary condition for local optimality.

Talk 2: The Effect of Smooth Parametrizations on Nonconvex Optimization Landscapes
Speaker: Joe Kileel
Abstract: Given a constrained optimization problem, we often tackle it by choosing a parameterization of the constraint set and then optimizing over the parameters. This lets us to approach optimization problems over manifolds or stratified sets through problems over simpler sets, such as Euclidean space without constraints. For example, if we need to optimize a real-valued cost over bounded-rank matrices, then we can parameterize the domain using a low-rank factorization (e.g., the SVD) and then optimize over the factors which are unconstrained. Alternatively, in deep learning when optimizing over the function space represented by a neural network, we have parameterized the space by the weights and biases in the network. In these situations, a natural question is: does the choice of parameterization affect the nonconvex optimization landscape? And: are some parameterizations “better” than others? In this talk, I'll present a geometric framework to formalize such questions and new analysis tools to help answer them. The theory will be applied to several examples, including the aforementioned ones as well as optimization problems from tensor decomposition and semidefinite programming. Based on joint works with Eitan Levin (Caltech), Nicolas Boumal (EPFL), and Chris Criscitiello (EPFL).

Talk 3: Geodesic convexity of polar decomposition
Speaker: Foivos Alimisis
Abstract: In this talk, we will analyze a hidden convexity-like structure for the polar decomposition problem in the orthogonal group. This turns out to be similar to convexity-like structures that have been discovered for the symmetric eigenvalue problem. We will talk about the theoretical, but as well practical implications of this structure in polar decomposition problems under uncertainty.

Session: Global Optimization Theory and Algorithms
Chair: Sergiy Butenko
Cluster: Global Optimization

Talk 1: Solving bilevel polynomial optimization by disjunctive decomposition
Speaker: Suhan Zhong
Abstract: We consider bilevel polynomial optimization problems whose lower level constraints are linear on lower level variables. We show that such a bilevel program can be reformulated as a disjunctive program using partial Lagrange multiplier expressions. Each branch problem of this disjunctive program can be efficiently solved by polynomial optimization techniques. We give necessary and sufficient conditions for solutions of branch problems to be global optimizer of original bilevel optimization, and sufficient conditions for the local optimality.

Talk 2: Adaptive Bilevel Knapsack Interdiciton 
Speaker: Jourdain Lamperski
Abstract: We consider adaptive bilevel knapsack interdiction. A leader aims to interdict items that a follower aims to fill their knapsack with. The leader does not have full information, as captured by a finite number of possible realizations of the follower. The leader can adapt to uncertainty by executing one of a budgeted number of precomputed interdiction policies.  We propose exact and approximate solution methods. In particular, we present theoretical performance guarantees for the approximate solution methods and evalutate their empirical performance against the exact methods through computational experiments. 

Talk 3: Continuous Approaches to Cluster-Detection Problems in Networks
Speaker: Sergiy Butenko
Abstract: We discuss continuous formulations for several important cluster-detection problems in networks. More specifically, the problems of interested are formulated as quadratic, cubic, or higher-degree polynomial optimization problems subject to linear constraints. The proposed formulations are used to develop analytical bounds as well as effective algorithms for some of the problems. Moreover, a novel hierarchy of nonconvex continuous reformulations of optimization problems on networks is discussed.

Session: Feasible and infeasible methods for optimization on manifolds II
Chair: Bin Gao
Cluster: Optimization on Manifolds

Talk 1: A decentralized proximal gradient tracking algorithm for composite optimization on Riemannian manifolds
Speaker: Lei Wang
Abstract: This talk focuses on minimizing a smooth function combined with a nonsmooth regularization term on a compact Riemannian submanifold embedded in the Euclidean space under a decentralized setting. Typically, there are two types of approaches at present for tackling such composite optimization problems. The first, subgradient-based approaches, rely on subgradient information of the objective function to update variables, achieving an iteration complexity of $O(\epsilon^{-4}\log^2(\epsilon^{-2}))$. The second, smoothing approaches, involve constructing a smooth approximation of the nonsmooth regularization term, resulting in an iteration complexity of $O(\epsilon^{-4})$. This paper proposes a proximal gradient type algorithm that fully exploits the composite structure. The global convergence to a stationary point is established with a significantly improved iteration complexity of $O(\epsilon^{-2})$. To validate the effectiveness and efficiency of our proposed method, we present numerical results from real-world applications, showcasing its superior performance compared to existing approaches.

Talk 2: A low-rank augmented Lagrangian method for SDP-RLT relaxations of mixed-binary quadratic programs
Speaker: Di Hou
Abstract: The mixed-binary quadratic program (MBQP) with both equality and inequality constraints is a well-known NP-hard problem that arises in various applications. In this work, we focus on two relaxations: the doubly nonnegative (DNN) relaxation and the SDP-RLT relaxation, which combines the Shor relaxation with a partial first-order reformulation-linearization technique (RLT). We demonstrate the equivalence of these two relaxations by introducing slack variables. Furthermore, we extend RNNAL—a globally convergent Riemannian augmented Lagrangian method (ALM) originally developed for solving DNN relaxations—to handle SDP-RLT relaxations. RNNAL penalizes the inequality constraints while keeping the equality constraints in the ALM subproblems. By applying a low-rank decomposition in each ALM subproblem, the feasible region is transformed into an algebraic variety with advantageous geometric properties for us to apply a Riemannian gradient descent method. Our algorithm can efficiently solve general semidefinite programming (SDP) problems, including relaxations for quadratically constrained quadratic programming (QCQP). Extensive numerical experiments confirm the efficiency of the proposed method.

Talk 3: An improved unconstrained approach for bilevel optimization
Speaker: Nachuan Xiao
Abstract: In this talk, we focus on the nonconvex-strongly-convex bilevel optimization problem (BLO). In this BLO, the objective function of the upper-level problem is nonconvex and possibly nonsmooth, and the lower-level problem is smooth and strongly convex with respect to the underlying variable. We show that the feasible region of BLO is a Riemannian manifold. Then we transform BLO to its corresponding unconstrained constraint dissolving problem (CDB), whose objective function is explicitly formulated from the objective functions in BLO. We prove that BLO is equivalent to the unconstrained optimization problem CDB. Therefore, various efficient unconstrained approaches, together with their theoretical results, can be directly applied to BLO through CDB. We propose a unified framework for developing subgradient-based methods for CDB. Remarkably, we show that several existing efficient algorithms can fit the unified framework and be interpreted as descent algorithms for CDB. These examples further demonstrate the great potential of our proposed approach.

Session: Moment-SOS Hierarchy: From Theory to Computation in the Real World (II)
Chair: Jie Wang
Cluster: Conic and Semidefinite Optimization

Talk 1: Bregman primal--dual first-order method and application to sparse semidefinite programming
Speaker: Xin Jiang
Abstract: We discuss the centering problem in large-scale semidefinite programming with sparse coefficient matrices. The logarithmic barrier function for the cone of positive semidefinite completable sparse matrices is used as the distance-generating kernel. For this distance, the complexity of evaluating the Bregman proximal operator is shown to be roughly proportional to the cost of a sparse Cholesky factorization. This is much cheaper than the standard proximal operator with Euclidean distances, which requires an eigenvalue decomposition. Then primal-dual proximal algorithm with Bregman distances are applied to solve large-scale sparse semidefinite programs efficiently.

Talk 2: Moment-SOS hierarchies for variational problems and PDE control
Speaker: Giovanni Fantuzzi
Abstract: Moment-SOS hierarchies are an established tool to compute converging sequences of lower bounds on the global minimum of finite-dimensional polynomial optimization problems. In this talk, I will show that they can be combined with finite-element discretizations to give a "discretize-then-relax" framework for solving two classes of infinite-dimensional problems: minimization problems for nonconvex integral functionals over functions from a Sobolev space, and some optimal control problems for nonlinear partial differential equations. For each class of problems, I will discuss conditions ensuring that this "discretize-then-relax" framework produces converging approximations (sometimes, bounds) to the global minimum and to the corresponding optimizer. Gaps between theory and practice will be illustrated by means of examples.

Talk 3: Inexact Augmented Lagrangian Methods for Semidefinite Optimization: Quadratic Growth and Linear Convergence
Speaker: Feng-Yi Liao
Abstract: Augmented Lagrangian Methods (ALMs) are widely employed in solving constrained optimizations, and some efficient solvers are developed based on this framework. Under the quadratic growth assumption, it is known that the dual iterates and the Karush–Kuhn–Tucker (KKT) residuals of ALMs applied to semidefinite programs (SDPs) converge linearly. In contrast, the convergence rate of the primal iterates has remained elusive. In this talk, we resolve this challenge by establishing new quadratic growth and error-bound properties for primal and dual SDPs under the strict complementarity condition. Our main results reveal that both primal and dual iterates of the ALMs converge linearly contingent solely upon the assumption of strict complementarity and a bounded solution set. This finding provides a positive answer to an open question regarding the asymptotically linear convergence of the primal iterates of ALMs applied to semidefinite optimization. 

Session: Variational Analysis: Theory and Applications III
Chair: Walaa Moursi
Cluster: Nonsmooth Optimization

Talk 1: TBA
Speaker: Sedi Bartz
Abstract: TBA

Talk 2: TBA
Speaker: Taeho Yoon
Abstract: TBA

Talk 3: TBA
Speaker: Scott Lindstrom
Abstract: TBA

Session: Semidefinite Relaxations in Inference Problems
Chair: Yong Sheng Soh
Cluster: Conic and Semidefinite Optimization

Talk 1: On the exactness of SDP relaxation for quadratic assignment problem
Speaker: Shuyang Ling
Abstract: Quadratic assignment problem (QAP) is a fundamental problem in combinatorial optimization and finds numerous applications in operation research, computer vision, and pattern recognition. However, it is a very well-known NP-hard problem to find the global minimizer to the QAP. In this work, we study the semidefinite relaxation (SDR) of the QAP and investigate when the SDR recovers the global minimizer. In particular, we consider the two input matrices satisfy a simple signal-plus-noise model, and show that when the noise is sufficiently smaller than the signal, then the SDR is exact, i.e., it recovers the global minimizer to the QAP. It is worth noting that this sufficient condition is purely algebraic and does not depend on any statistical assumption of the input data. We apply our bound to several statistical models such as correlated Gaussian Wigner model. Despite the sub-optimality in theory under those models, empirical studies show the remarkable performance of the SDR. Our work could be the first step towards a deeper understanding of the SDR exactness for the QAP.

Talk 2: Exactness Conditions for Semidefinite Relaxations of the Quadratic Assignment Problem
Speaker: Junyu Chen
Abstract: The Quadratic Assignment Problem (QAP) is an important discrete optimization instance that encompasses many well-known combinatorial optimization problems, and has applications in a wide range of areas such as logistics and computer vision. The QAP, unfortunately, is NP-hard to solve. To address this difficulty, a number of semidefinite relaxations of the QAP have been developed. These techniques are known to be powerful in that they compute globally optimal solutions in many instances, and are often deployed as sub-routines within enumerative procedures for solving QAPs. In this paper, we investigate the strength of these semidefinite relaxations. Our main result is a deterministic set of conditions on the input matrices -- specified via linear inequalities -- under which these semidefinite relaxations are exact. Our result is simple to state, in the hope that it serves as a foundation for subsequent studies on semidefinite relaxations of the QAP as well as other related combinatorial optimization problems. As a corollary, we show that the semidefinite relaxation is exact under a perturbation model whereby the input matrices differ by a suitably small perturbation term. One technical difficulty we encounter is that the set of dual feasible solutions is not closed. To circumvent these difficulties, our analysis constructs a sequence of dual feasible solutions whose objective value approaches the primal objective, but never attains it.

Talk 3: Inference of planted subgraphs in random graphs
Speaker: Cheng Mao
Abstract: Suppose that we are given a graph G obtained from randomly planting a template graph in an Erdős–Rényi graph. Can we detect the presence and recover the location of the planted subgraph in G? This problem is well understood in the case where the template graph is a clique or a dense subgraph but has received less attention otherwise. We consider several settings where the planted subgraph is the power of a Hamiltonian cycle or a random geometric graph which arises in multiple applications. The difficulty of the detention or recovery problem primarily lies in the combinatorial nature of the associated optimization problem. To tackle the problem, we study computationally efficient methods such that subgraph counting and spectral methods which leverage the higher triangle density of the planted subgraph.

Session: Optimization for Approximation, Estimation, and Control
Chair: Martin Andersen
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Fast and Certifiable Nonconvex Optimal Control with Sparse Moment-SOS Relaxations
Speaker: Heng Yang
Abstract: Direct methods for optimal control, also known as trajectory optimization, is a workhorse for optimization-based control in robotics and beyond. Nonlinear programming with engineered initializations has been the de-facto approach for trajectory optimization, which however, can suffer from undesired local optimality. In this talk, I will first show that, using the machinery of sparse moment and sums-of-squares (SOS) relaxations, many nonconvex trajectory optimization problems can be solved to certifiable global optimality. That is, globally optimal solutions of the original nonconvex problems can be computed by solving convex semidefinite programs (SDPs) together with optimality certificates. I will then present a specialized SDP solver implemented in CUDA (C++) and runs in GPUs that exploits the structures of the problems to solve the convex SDPs at a scale far beyond existing solvers.

Talk 2: Optimal diagonal preconditioner and how to find it
Speaker: Zhaonan Qu
Abstract: Preconditioning has long been a staple technique in optimization, often applied to reduce the condition number of a matrix and speed up the convergence of algorithms. Although there are many popular preconditioning techniques in practice, most lack guarantees on reductions in condition number. Moreover, the degree to which we can improve over existing heuristic preconditioners remains an important practical question. In this talk, we discuss the problem of optimal diagonal preconditioning that achieves maximal reduction in the condition number of any full-rank matrix by scaling its rows and/or columns. We reformulate the problem as a quasi-convex optimization problem and design interior point method to solve it with O(log(1/ϵ)) iteration complexity. Next, we specialize to one-sided optimal diagonal preconditioning problems, and demonstrate that they can be formulated as standard dual SDP problems. Based on the SDP formulation, several computational techniques are applicable, and can greatly accelerate finding a good diagonal preconditioner with theoretical guarantees. Our experiments suggest that optimal diagonal preconditioners can significantly improve upon existing heuristic-based diagonal preconditioners at reducing condition numbers and speeding up iterative methods.

Talk 3: Power System State Estimation by Phase Synchronization and Eigenvectors
Speaker: Iven Guzel
Abstract: To estimate accurate voltage phasors from inaccurate voltage magnitude and complex power measurements, the standard approach is to iteratively refine a good initial guess using the Gauss-Newton method. But the nonconvexity of the estimation makes the Gauss-Newton method sensitive to its initial guess, so human intervention is needed to detect convergence to plausible but ultimately spurious estimates. This paper makes a novel connection between the angle estimation subproblem and phase synchronization to yield two key benefits: (1) an exceptionally high quality initial guess over the angles, known as a spectral initialization; (2) a correctness guarantee for the estimated angles, known as a global optimality certificate. These are formulated as sparse eigenvalue-eigenvector problems, which we efficiently compute in time comparable to a few Gauss-Newton iterations. Our experiments on the complete set of Polish, PEGASE, and RTE models show, where voltage magnitudes are already reasonably accurate, that spectral initialization provides an almost-perfect single-shot estimation of angles from moderately noisy bus power measurements (i.e. pairs of PQ measurements), whose correctness becomes guaranteed after a single Gauss--Newton iteration. For less accurate voltage magnitudes, the performance of the method degrades gracefully; even with moderate voltage magnitude errors, the estimated voltage angles remain surprisingly accurate.

Session: Quantum Computing and Optimization
Chair: Reuben Tate
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)

Talk 1: Advances in Warm-Started QAOA
Speaker: Reuben Tate
Abstract: Over a decade ago, the Quantum Approximate Optimization Algorithm (QAOA) was developed by Farhi et al. for solving certain problems in combinatorial optimization; the algorithm is a variational algorithm that involves the tuning of continuous circuit parameters. Five years ago, Tate et al. and Egger et al. independently developed a warm-start variant that involves using classically-obtained information to construct a warm-started initial quantum state. In this talk, we will go over recent developments in regards to Warm-Started QAOA from both a theoretical, empirical, and algorithmic-design perspective.

Talk 2: Investigating Alternative Metrics of Performance for QAOA
Speaker: Sean Feeney
Abstract: In modern optimization tasks, combinatorial optimization problems (COPs) are paramount in fields such as logistics, power systems, and circuit design. Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising quantum-classical variational approach for tackling these challenges, yet it often offers limited worst-case approximation guarantees. This work focuses on a recently introduced variant, Warm-Start QAOA, which leverages classical solutions as biased initial states in hopes of boosting the odds of finding high-quality solutions. We conduct an extensive numerical study of Warm-Start QAOA on 3-regular Max-Cut instances. Compared to theoretical lower bounds established by Tate et al. for single-round QAOA, our empirical results consistently indicate better performance across a range of tilt angles. However, this apparent advantage does not extend beyond the classical warm-start solution itself when the QAOA parameters are optimized solely by maximizing the expected objective value. This outcome highlights a pressing need to look beyond standard expectation-value metrics, as they may not capture the subtle elements required for surpassing strong classical baselines in practical settings. To address this gap, we introduce the Better Solution Probability (BSP) metric, which shifts the optimization target from maximizing expectation value performance to maximizing the probability of exceeding a given classical warm-start cut. Our simulations show that BSP-optimized Warm-Start QAOA frequently locates better solutions at non-trivial tilt angles, positions that outperform both the purely classical approach at zero tilt and standard QAOA at 90°, and does so with a non-vanishing probability. Notably, the BSP objective remains feasible to optimize in real-world conditions because it does not rely on a priori knowledge of the optimal solution. By exploring objective functions beyond expectation value, this study offers new insights into how hybrid quantum-classical methods can be enhanced for complex optimization tasks, paving the way for more robust algorithm design and a clearer path toward quantum advantage.

Talk 3: Quantum Hamiltonian Descent Algorithms for Nonlinear Optimization
Speaker: Yufan Zheng
Abstract: Nonlinear optimization is a vibrant field of research with wide-ranging applications in engineering and science. However, classical algorithms often struggle with local minima, limiting their effectiveness in tackling nonconvex problems. In this talk, we explore how quantum dynamics can be exploited to develop novel quantum optimization algorithms. Specifically, we introduce Quantum Hamiltonian Descent (QHD), a quantum optimization algorithm inspired by the connection between accelerated gradient descent and Hamiltonian mechanics. We will discuss the theoretical properties of QHD, including its global convergence in nonlinear and nonconvex optimization, along with strong empirical and theoretical evidence of its advantage over classical algorithms. Additionally, we will present an open-source implementation of the algorithm (named QHDOPT) and demonstrate its real-world applications.

Session: Newton-ish and Higher-Order Methods
Chair: Nick Tsipinakis
Cluster: nan

Talk 1: Multilevel Regularized Newton Methods with Fast Convergence Rates
Speaker: Nick Tsipinakis
Abstract: We introduce new multilevel methods for solving large-scale unconstrained optimization problems. Specifically, the philosophy of multilevel methods is applied to Newton-type methods that regularize the Newton sub-problem using second-order information from a coarse (low dimensional) sub-problem. The new regularized multilevel methods provably converge from any initialization point and enjoy faster convergence rates than Gradient Descent. In particular, for arbitrary functions with Lipschitz continuous Hessians, we show that their convergence rate interpolates between the rate of Gradient Descent and that of the cubic Newton method. If, additionally, the objective function is assumed to be convex, then the proposed method converges with the fast $\mathcal{O}(k^{-2})$ rate. Hence, since the updates are generated using a coarse model in low dimensions, the theoretical results of this paper significantly speed-up the convergence of Newton-type or preconditioned gradient methods in practical applications. Preliminary numerical results suggest that the proposed multilevel algorithms are significantly faster than current state-of-the-art methods. [1] K. Mishchenko, Regularized Newton method with global convergence, SIAM Journal on Optimization, 33 (2023), pp. 1440–1462. [2] N. Doikov and Y. Nesterov, Gradient regularization of Newton method with Bregman dis-tances, Mathematical programming, 204 (2024), pp. 1–25. [3] N. Tsipinakis and P. Parpas, A multilevel method for self-concordant minimization, Journal of Optimization Theory and Applications, (2024), pp. 1–51.

Talk 2: First-ish Order Methods: Hessian-aware Scalings of Gradient Descent
Speaker: Oscar Smee
Abstract: Gradient descent is the primary workhorse for optimizing large-scale problems in machine learning. However, its performance is highly sensitive to the choice of the learning rate. A key limitation of gradient descent is its lack of natural scaling, which often necessitates expensive line searches or heuristic tuning to determine an appropriate step size. In this paper, we address this limitation by incorporating Hessian information to scale the gradient direction. By accounting for the curvature of the function along the gradient, our adaptive, Hessian-aware scaling method ensures a local unit step size guarantee, even in nonconvex settings. Near a local minimum that satisfies the second-order sufficient conditions, our approach achieves linear convergence with a unit step size. We show that our method converges globally under a significantly weaker version of the standard Lipschitz gradient smoothness assumption. Even when Hessian information is inexact, the local unit step size guarantee and global convergence properties remain valid under mild conditions. Finally, we validate our theoretical results empirically on a range of convex and nonconvex machine learning tasks, showcasing the effectiveness of the approach. Preprint: https://arxiv.org/abs/2502.03701

Session: Systems of Quadratic Equations/Inequalities
Chair: Ruey-Lin Sheu
Cluster: nan

Talk 1: On the implementation issue of the non-homogeneous strict Finsler and the non-homogeneous Calabi theorems
Speaker: Min-Chi Wang
Abstract: Let f(x) and g(x) be two real quadratic functions defined on ℝⁿ. The existence of solutions to the system of (in)equality constraints [f(x) = 0, g(x) = 0] and [f(x) = 0, g(x) ≤ 0] has rarely been studied in the literature. Recently, new results have emerged, called the non-homogeneous strict Finsler Lemma and the non-homogeneous Calabi Theorem, which provide necessary and sufficient conditions for the solvability of the above two systems of (in)equality constraints. This talk aims to simplify the conditions to facilitate easier implementation. Numerical results show that our proposed method is efficient in computation.

Talk 2: A QP1QC approach for deciding whether or not two quadratic surfaces intersect
Speaker: Ting-Tsen Lin
Abstract: Given two $n$-variate quadratic functions $f(x)=x^TAx+2a^Tx+a_0, g(x)=x^TBx+2b^Tx+b_0$, we are interested in knowing whether or not the two hypersurfaces $\{x\in \mathbb{R}^n: f(x)=0\}$ and $\{x\in \mathbb{R}^n: g(x)=0\}$ intersect with each other. There are two aspects to look at this problem. In one respect, the famous Finsler-Calabi theorem (1936-1964) asserts that, if $n\ge3$ and $f,g$ are quadratic forms, $f=g=0$ has no common solution other than the trivial one $x=0$ if and only if there exists a positive definite matrix pencil $\alpha A+\beta B\succ0.$ The result is in general not true for non-homogeneous quadratic functions. On the other hand, Levin (c. late 1970) tried to directly solve the intersection curve of $\{x\in \mathbb{R}^n: f(x)=0\}$ and $\{x\in \mathbb{R}^n: g(x)=0\},$ but it turned out to be way too ambitious. In this paper, we show that, by incorporating with the information about the unboundedness and the un-attainability of several (at most 4) quadratic programming problems with one single quadratic constraint (QP1QC), the answer as to whether or not $f(x)=x^TAx+2a^Tx+a_0=0$ and $g(x)=x^TBx+2b^Tx+b_0=0$ intersect can be successfully determined. References: E. Calabi, Linear systems of real quadratic forms, Proceedings of the American Mathematical Society, 15 (1964), pp. 844–846. P. Finsler, Über das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen, Commentarii Mathematici Helvetici, 9 (1936), pp. 188–192. J. Z. Levin, A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces, Communications of the ACM, 19 (1976), pp. 555–563. J. Z. Levin, Mathematical models for determining the intersections of quadric surfaces, Computer Graphics and Image Processing, 11 (1979), pp. 73–87.

Talk 3: Last two pieces of puzzle for un-solvability of a system of two quadratic (in)equalities
Speaker: Ruey-Lin Sheu
Abstract: Given two quadratic functions f(x) = x^{T}Ax+2a^{T}x+a_0 and g(x) = x^{T}Bx+ 2b^{T }x+b_0, each associated with either the strict inequality (< 0); non-strict inequality (≤ 0); or the equality (= 0), it is a fundamental question to ask whether or not the joint system {x ∈ R^n: f(x) ⋆ 0} and {x ∈ R^n: g(x)#0}, where ⋆ and # can be any of {