Abstracts

Mixed-Integer Nonlinear Optimization: Applications, Algorithms, and Computation

Sven Leyffer

Argonne National Laboratory

Abstract

Scientists and engineers are increasingly turning from the simulation of complex processes to the optimization and design of complex systems. Many important design problems involve not only continuous variables with nonlinear relationships but also discrete decisions, giving rise to mixed-integer nonlinear programming problems (MINLPs). MINLPs combine the combinatorial complexity of the discrete decisions with the numerical challenges of the nonlinear functions. We review some applications of MINLP that arise in electrical engineering and the modeling of the power grid, chemical engineering, and communication engineering.

We survey solution methods for MINLPs, and present a new package for solving mixed-integer nonlinear optimization problems, MINOTAUR. The MINOTAUR toolkit is designed to provide a flexible and efficient framework for solving MINLPs. The code is developed in a modular way to enable developers and users to efficiently combine the knowledge of problem structure with algorithmic insights. We will provide examples of how to develop solvers within the MINOTAUR framework, focusing on the integration of nonlinear solvers into the MINOTAUR's branch-and-cut framework, and highlight challenges and opportunities for nonlinear optimization.

Maximizing the min-cost flow via convex optimization

De Dennis Meng

Department of Electrical Engineering, University of Washington

Abstract

Given a continuous field defined with weights at each point, we can find the geodesic or min-cost flow between point pairs. In this talk, we consider the problem choosing optimal weights to maximize the cost of the min-cost flow. This turns out to be a convex infinite dimensional optimization problem with PDE constraints, and arises in a variety of applications including geometric optics, landscape design and etc. We explore efficient ways to solve the maximum min-cost flow problem: instead of the primal formulation which is harder to optimize, we derive the dual problem where the nonlinear PDE Eikonal equation naturally arises as a constraint. We show strong duality hold, which unveils interesting physical properties of optimal flow and potential contours. Finally, we discretize the continuous problem to a second-order cone program, and apply different algorithms, including interior point method and proximal point method, by exploiting problem structures and we compare their performance.

Making flippy floppy

James Burke

Department of Mathematics, University of Washington

Abstract

No, this is not a discussion of the US presidential debates. Nor is it a discussion and analysis of the 1983 tune by the Talking Heads. Rather we discuss an approach to solving certain optimization problems by considering a related problem where the roles of the objective and the constraints have been reversed, or flip-flopped. The particular approach we present was pioneered by Ewout van den Berg and Michael Friedlander in a pair of papers appearing in 2008 and 2011. In this talk we review this work and then study the question of just how far this approach to optimization can go, and to what problems it suitably applies.

is joint work with Aleksandr Aravkin and Michael Friedlander.

SMART Filter and EM Filter and their applications to medical imaging

Joe Qranfal

Department of Mathematics, Simon Fraser University

Abstract

Two new filtering algorithms, the SMART filter (simultaneous multiplicative algebraic reconstruction technique) and the EM filter (expectation maximization), are introduced and validated numerically by applying them to solve the ill-posed inverse problem of reconstructing a time-varying medical image. Both methods are tested for the case of image reconstruction from noisy data in dynamic single photon emission computed tomography (SPECT), where the signal strength changes substantially over the required acquisition time. Numerical results confirm the convergence results and corroborate the effectiveness of the reconstruction methods.

Improved semidefinite bounding procedure for solving max-cut problems to optimality

Nathan Krislock

Department of Computer Science, University of British Columbia

Abstract

An algorithm will be presented for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, by adding a quadratic regularization term to the strengthened semidefinite relaxation, we can use a quasi-Newton method to compute the bounds. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: numerical results show that this algorithm dominates the best existing method.

[Joint work with Jérôme Malick (CNRS) and Frédérick Roupin (Université Paris-Nord).]

A coordinated hedging mechanism in a supply chain with multiple producers and wholesalers

Eissa Nematollahi

Institute for Sustainable Energy, Environment, and Economy (ISEEE) and Department of Electrical Engineering, University of Calgary

Abstract

A coordinated hedging mechanism for mitigating price volatility risk in a supply chain with multiple risk-averse producers and wholesalers is developed. Producers compete in quantity to supply a single product to a set of wholesalers who compete in quantities to meet uncertain demand. To mitigate price volatility risk, producers and wholesalers trade financial derivatives in a coordinated manner. Equilibrium price and quantities of each derivative traded by producers and wholesalers are determined. Using the equilibrium model, we study conditions under which aggregate utility of all producers and wholesalers as well as the performance of the supply chain is maximized. Moreover, we provide distribution-free optimal bounds for equilibrium price of a derivative. These bounds are obtained either in closed forms or algorithmically via semidefinite optimization.

[Joint work with Janne Kettunen, William D. Rosehart, and Yuriy Zinchenko.]

Optimality conditions and finite convergence of Lasserre's hierarchy

Jiawang Nie

Department of Mathematics, University of California at San Diego

Abstract

Lasserre's hierarchy is a sequence of semidefinite relaxations for solving polynomial optimization problems globally. This paper studies the relationship between optimality conditions in nonlinear programming theory and finite convergence of Lasserre's hierarchy. Our main results are: i) Lasserre's hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean assumption; ii) these optimality conditions are all satisfied at every local minimizer if a finite set of polynomials, which are in the coefficients of input polynomials, do not vanish at the input data (i.e., they hold in a Zariski open set). This implies that Lasserre's hierarchy has finite convergence generically.