Session: Modeling, Solvers, and Quantum
Chair: Giacomo Nannicini
Cluster: nan
Talk 1: Making Some Smooth Problems with Derivative Jumps Easier to Express
Speaker: David Gay
Abstract: Some optimization problems involve an objective or constraints with derivative jumps. The jumps may be due to absolute values or the minimum or maximum of two or more expressions or to the piecewise linearization of a nonlinear function. There are multiple ways to deal with such situations. For example, Griewank and Walther propose using regularization supplied by overloading the relevant expressions. Of interest in this talk is using binary variables to decide which pieces are currently relevant. In the AMPL modeling language, this is implicit when one uses the piecewise-linear notation. This talk will present examples and discuss plans to automatically convert abs(...), min(...), and max}(...) to piecewise-linear forms, enabling efficiently solving by various solvers.
Talk 2: The quantum central path method
Speaker: Giacomo Nannicini
Abstract: Abstract: We propose a new quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. Our approach is inspired by the Newton barrier flow studied in the 80s by several authors, and goes beyond those studies by giving a full description of a quantum algorithm that simulates the corresponding dynamical system. The algorithm has a worst case complexity with favorable scaling in the problem dimension compared to state-of-the-art methods, but worse scaling in the precision and the size of the solution. We hope that with further advancements, this method could pave the way for an end-to-end quantum speedup for linear optimization.
Talk 3: Modeling and algorithmic framework for complex optimization problems and equilibrium problems
Speaker: Olivier Huber
Abstract: Algebraic modeling languages (AML) have shaped the problem structure considered in numerical optimization, and indirectly have an impact on the instances coming from applications and the ones considered by solvers. However, problems not fitting the classical AML format are abundantly found in applications. For instance, nonsmoothness commonly arises in (multistage) stochastic programming problems with coherent risk measures. Bilevel or multilevel models feature multiple optimization problems, and so do Nash equilibrium problems. A given application can feature a combination of the above challenge. Consider the decentralized electricity market, where the weather affect the production level of some producers. This leads to a Nash equilibrium problem with multistage risk-averse agents. To capture these challenging but structured models, we propose a modeling framework based on a directed acyclic graph (DAG). The nodes are of two type: the first one subsumes classical optimization problems and variational inequalities, while the second one indicates a Nash behavior among its children nodes. The directed arcs capture the interactions between optimization problems. This modeling approach is implemented via annotation and extends an AML modeling power. Model transformations are defined over the DAG structure to convert part or all of the model into a form amenable to computations by existing solvers. Many instances captured by this modeling paradigm fall outside of the scope for robust solvers, an algorithmic framework to solve these instances, for instance by decomposition or approximation, is presented. An implementation of these ideas is present in ReSHOP, a reformulation solver for hierarchical optimization problems.
