Month: July 2018

A stochastic Levenberg-Marquardt method using random models with complexity results and application to data assimilation

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Clément W. Royer
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    Globally convergent variants of the Gauss-Newton algorithm are often the methods of choice to tackle nonlinear least-squares problems. Among such frameworks, Levenberg-Marquardt and trust-region methods are two well-established, similar paradigms. Both schemes have been studied when the Gauss-Newton model is replaced by a random model that is only accurate with a given probability. Trust-region schemes … Read more

    A Note on “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs”

  • Austin Buchanan
  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming

    In the paper “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1):53–60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, … Read more

    SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

  • Cong Fang
  • Chris Junchi Li
  • Zhouchen Lin
  • Tong Zhang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order methods. For stochastic first-order method, combining SPIDER with normalized gradient descent, we propose … Read more

    Data-Driven Distributionally Robust Chance-Constrained Optimization with Wasserstein Metric

  • Ran Ji
  • Miguel A. Lejeune
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , ,

    We study distributionally robust chance-constrained programming (DRCCP) optimization problems with data-driven Wasserstein ambiguity sets. The proposed algorithmic and reformulation framework applies to distributionally robust optimization problems subjected to individual as well as joint chance constraints, with random right-hand side and technology vector, and under two types of uncertainties, called uncertain probabilities and continuum of realizations. … Read more

    A Unified Characterization of Nonlinear Scalarizing Functionals in Optimization

  • Gemayqzel Bouza
  • Christiane Tammer
  • Ernest Quintana
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    Over the years, several classes of scalarization techniques in optimization have been introduced and employed in deriving separation theorems, optimality conditions and algorithms. In this paper, we study the relationships between some of those classes in the sense of inclusion. We focus on three types of scalarizing functionals (by Hiriart-Urruty, Drummond and Svaiter, Gerstewitz) and … Read more

    First-order methods for the impatient: support identification in finite time with convergent Frank-Wolfe variants

  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Samuel Rota Bulo
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we focus on the problem of minimizing a non-convex function over the unit simplex. We analyze two well-known and widely used variants of the Frank-Wolfe algorithm and first prove global convergence of the iterates to stationary points both when using exact and Armijo line search. Then we show that the algorithms identify … Read more

    Fast robust shortest path computations

  • Christoph Hansknecht
  • Alexander Richter
  • Sebastian Stiller
    • Categories Network Optimization Tags , ,

    We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an $s$-$t$-graph $D(V,A)$ and for each arc a nominal length $c(a)$ and a maximal increase $d(a)$ of its length. … Read more

    The SCIP Optimization Suite 6.0

  • Michael Bastubbe
  • Leon Eifler
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Matthias Walter
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Franziska Schlösser
  • Christoph Schubert
  • Yuji Shinano
  • Merlin Viernickel
  • Fabian Wegscheider
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more