Coffee available

Dongdong Ge Shanghai Jiao Tong University

The Development History of COPT [abstract]
 

This talk will provide a brief introduction to the development of the COPT mathematical optimization software under the leadership of Professor Yinyu Ye. We will explore its journey from inception to becoming the second best software globally in its field. Additionally, I will share recent advancements in leveraging GPU architectures to accelerate mathematical optimization, a new progress made under his guidance.

Anthony Man-Cho So Chinese University of Hong Kong

Distance Geometry through the Lens of Optimization [abstract]
 

A classic problem in distance geometry is that of recovering the positions of a set of objects from an incomplete list of Euclidean distance measurements between pairs of those objects. Although the problem has a simple description, its solution remains challenging and calls for ideas from different branches of mathematics and computer science. In this talk, I share my journey in tackling this problem, which began with my PhD work under Professor Ye's supervision, and discuss how various areas of optimization, including semidefinite optimization, optimization landscape analysis, and manifold optimization, offer powerful tools for understanding both the geometric and algorithmic aspects of the problem.

Erick Delage HEC Montreal

Conditional Robust Optimization [abstract]
 

Conditional Robust Optimization (CRO) is a decision-making framework that blends the flexibility of robust optimization (RO) with the ability to incorporate additional information regarding the structure of uncertainty. This approach solves the RO problem where the uncertainty set structure adapts to account for the most recent information provided by a set of covariates. In this presentation, we will introduce an end-to-end data-driven approach to CRO. We will also show how hypothesis testing can be integrated to the training in order to improve the quality of conditional coverage of the produced uncertainty sets.

Coffee Break

Michael Todd Cornell University

Yinyu Ye's Research on Interior-point Methods [abstract]
 

We survey Yinyu's early work on potential-reduction and path-following methods and the relationship of these methods to the ellipsoid and simplex methods.

Kurt Anstreicher University of Iowa

More New Results on Quadratic Minimization [abstract]
 

In their 2003 paper “New results on quadratic minimization”, Ye and Zhang introduced fundamental theory for SDP relaxations applied to extended trust-region subproblems. This paper stimulated a long line of research that continues to this day. In this talk we will describe some positive results that have been obtained as well as open problems that remain.

Robert Freund MIT

The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization [abstract]
 

In joint work with Zikai Xiong (MIT OR Center), we consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) -- with heuristic enhancements and GPU implementation -- has been very successful in solving huge-scale linear programming (LP) problems. Here we extend the study of rPDHG to encompass Conic Linear Optimization as well. We present a new theoretical analysis of rPDHG for general (convex) conic linear optimization and for LP as a special case thereof. We show a relationship between geometric measures of the primal-dual (sub-)level sets and the convergence rate of rPDHG. We also show how central-path-based linear transformations -- including conic rescaling -- can markedly enhance the convergence rate of rPDHG. Last of all, we present computational results that demonstrate how rescalings can accelerate convergence to high-accuracy solutions, and lead to more efficient methods for huge-scale LP problems in particular. Many of our ideas are aligned with and connected to work by Yinyu Ye, and these connections will be discussed in the talk.

Farid Alizadeh Rutgers University

Using Probabilistic Data in Learning and its Consequences [abstract]
 

We propose a new approach to machine learning where data, instead of a collection of points in the feature space, are presented in the form of probability distributions over the that space. The motivation for this approach is that observations of data are always inexact, ambiguous, or inherently unsuitable to be presented as an exact point. For instance, for many features, there may be errors in the process of measurement or observation (e.g., someone's weight is recorded as 85kg, but the scale showing this value may be somewhat inaccurate.) Another situation is when the feature being measured is not specific (e.g., the "ethnicity" of a person, which is asked in many employment questionnaires, may be a mixture of values.) In another case, a feature may be a time or spatial series (e.g., a person's blood pressure goes up and down during a day or week.) To better capture these ambiguities, we propose presenting each data line as a (joint) probability distribution over all possible values that an observation could attain. We examine the consequences of such an approach to measuring learning algorithms' performance, likelihood functions, and regression problems. In particular, we show that incorporating the ambiguity in the data through probability distributions results in a natural, "baked-in" regularization in the maximum likelihood regression formula.

Lunch Packard Bytes Cafe or Clark Building

Yichuan Daniel Ding McGill University

Efficiency-Fairness Tradeoff in Service Systems [abstract]
 

We develop a novel framework that allows us to tight the bound for the price of fairness that was proposed by Bertsimas et al (2011). I will then talk about how efficiency-fairness tradeoffs are made in practical service systems, including the cadaver kidney allocation, affordable housing allocation, emergency department, and an agri-product retailing platform. To make such decisions, the system manager needs to characterize the behaviour of the queueing system, which calls for cutting-edge stochastic modeling and optimization methods.

Oliver Hinder University of Pittsburgh

The Price of Adaptivity in Stochastic Convex Optimization [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.

Xiaocheng Li Imperial College London

Watermarking LLMs with Online Linear Programming [abstract]
 

The watermarking of large language models (LLMs) refers to the procedure of injecting a hidden pattern to the LLM-generated text that is imperceptible to humans but can be algorithmically detected as generated by AI. We consider a natural trade-off of the watermarking procedure between (probability) model distortion and detection ability, and we formulate the watermarking of LLMs as a constrained optimization problem based on the green-red algorithm of Kirchenbauer et al. (2023). We show that the optimal solution to the optimization problem enjoys a nice analytical property. This analytical structure renders the formulation fall under the framework of online optimization with constraints where the existing online linear programming algorithms in OR/MS literature can be naturally applied. These developments also shed light on the properness of model distortion metrics and establish an interesting connection between the repetition phenomenon for the LLM-generated texts and the dual variable of the online optimization problem.

Coffee Break

Dimitris Bertsimas MIT

Global Optimization for Classes of Non-convex Problems [abstract]
 

Yinyu made substantial contributions in approximating non-convex problems. In this work, we propose a new global optimization approach for solving non-convex optimization problems in which the non-convex components are sums of products of convex functions. A broad class of non-convex problems can be written in this way, such as concave minimization problems, difference of convex problems, and fractional optimization problems. Our approach exploits two techniques: first, we introduce a new technique, called the Reformulation-Perspectification Technique (RPT), to obtain a convex approximation of the considered non-convex continuous optimization problem. Next, we develop a spatial Branch and Bound scheme, leveraging RPT, to obtain a global optimal solution. Numerical experiments on several different convex maximization problems, a quadratic constrained quadratic optimization problem, and a dike height optimization problem demonstrate the effectiveness of the proposed approach. In particular, our approach solves more instances to global optimality for the considered problems than BARON and SCIP. We further discuss extensions to robust and adaptive optimization problems. (Joint work Danique de Moor, Dick den Hertog, Thodoris Koukouvinos, Jianzhe Zhen).

Tom Luo CUHK, Shenzhen

Proximal ADMM for Non-convex Problems [abstract]
 

We propose a proximal alternating direction method of multipliers to solve a linearly constrained nonconvex minimization problem. At each iteration, the algorithm first inexactly minimizes a proximal augmented Lagrangian function and then updates the dual multiplier vector using the residual of the linear constraints. When the primal and dual stepsizes are chosen sufficiently small, we show the iterates of the resulting proximal ADMM algorithm converges to a stationary point of the nonconvex problem, provided some mild regularity conditions are satisfied. When the objective function is quadratic, we further establish the linear convergence of the algorithm.

Stephen Vavasis University of Waterloo

First-order Methods for Linear Programming [abstract]
 

Linear programming has been conventionally solved with either the Simplex method or interior-point methods. In the past 10 years, first-order methods, which use only matrix-vector multiplication, have emerged as a competitor to the conventional methods for very large problems. In this talk, I will survey some of these methods including ADMM and PDHG, in which Yinyu Ye has made important advances.

Renato Monteiro Georgia Institute of Technology

A Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming Based on a Hybrid Convex-Nonconvex Approach [abstract]
 

This talk discusses the theory of a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. It is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a novel hybrid low-rank method. In contrast to the classical low-rank method, the new method finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results (to be presented in the next talk) comparing the new method to state-of-the-art solvers on several large SDP instances show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, it can solve in less than 30 minutes, and \(10^{-5}\) relative error condition, a maximum stable set SDP with a \(10^6\times10^7\) matrix variable. Co-authors: Arnesh Sujanani and Diego Cifuentes

Haihao Lu MIT

GPU-Accelerated Linear Programming [abstract]
 

Linear Programming is a fundamental tool in operations research and computational science that has been widely used in practice. This is a field that Yinyu has made propounding contributions, particular the theory and computation of interior-point method. In this talk, we will discuss a new class of algorithms for linear programming, and how GPU architectures can accelerate the convergence performance. This line of research includes recent collaboration with Yinyu.