CIAS – CCOR Minicourse about Programming with Prof. YinYu Ye (Stanford, Shanghai Jiao Tong)
Location: Corvinus University of Budapest, Building C
Date:
-
08 September 2025, 9:50-11:20 (Room C108)
08 September 2025, 11:40-13:10 (Room C108)
09 September 2025, 9:50-11:20 (Room C415)
Language of the event: English
Minicourse 1: Online Linear Programming and Extensions
A natural optimization model that formulates many online learning and resource allocation decision-making with uncertainty is online linear programming (OLP), where the noisy constraint column vectors, along with the objective coefficients and decision variables, are revealed and decided sequentially in real time. In this course, we review the near optimal algorithms and theories for solving this surprisingly general class of online (binary) linear programs and convex optimization problems. Then we present few recent developments of model/algorithms and extensions in this area, including fast online-gradient learning and decision making, Bandit with Knapsacks setting, the Fisher Market with online pricing, decoupling strategy of learning and decision-making, Wait-Less algorithms with mixed LP resolving and online gradient methods, and Hyper-gradient methods with online scaling/pre-conditioning for the gradient-based methods.
Minicourse 2: SDP Relaxation for NP-Hard Optimization and SDP Solvers on GPU
First, we describe semidefinite programming (SDP) relaxation on several NP-hard and nonconvex optimization problems, and illustrate necessary-and-sufficient conditions when the relaxation would be exact. Then we present breakthroughs in the SDP Optimization solver development on the GPU computational platform. We show a computational proof of the well-known Quantum ordered search problem via SDP, the computational results of Graph-Realization or Sensor-Localization, and approximation results of the SDP rounding theories/algorithms on solving huge-scale nonconvex and NP-hard combinatorial optimization problems.
Minicourse 3: Recent Algorithmic Developments for the Markov Decision/Game Processes
We present recent developments related to distributed algorithms for the Markov decision and turn-based game process, or linear programming at large.
We show that the classical policy-iteration method (Howard 1960), including the simple policy-iteration (or simplex method, Dantzig 1947) with the most-negative-reduced-cost pivoting rule, is a strongly polynomial-time algorithm for solving discounted Markov decision processes (MDP) with any fixed discount factor. The result is surprising since almost all complexity results on the simplex and policy-iteration methods are negative, while in practice they are widely used for solving MDPs and stochastic games. Then, we prove that the simple policy-iteration method is strongly polynomial for solving deterministic MDP regardless the factor. Finally, we present the results for solving Stochastic /Deterministic Turn-Based Zero-Sum games, where some problems remain open for many years.
For more info on this and upcoming events, please visit https://www.ccor.hu