On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing … Read more

    Fast approximate solution of large dense linear programs

  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories Linear Programming, Statistics Tags ,

    We show how random projections can be used to solve large-scale dense linear programs approximately. This is a new application of techniques which are now fairly well known in probabilistic algorithms, but have never yet been systematically applied to the fundamental class of Linear Programming. We develop the necessary theoretical framework, and show that this … Read more

    A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems

  • Natashia Boland
  • Brian Dandurand
  • Andrew C. Eberhard
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. The dual solution approach needs … Read more

    Rigorous results in electronic structure calculations

  • Denis Chaykin
  • Christian Jansson
  • Frerich Keil
  • Marko Lange
  • Kai Torben Ohlhus
  • Siegfried M. Rump
    • Categories Chemical Engineering, Semi-definite Programming Tags , , , ,

    Electronic structure calculations, in particular the computation of the ground state energy, lead to challenging problems in optimization. These problems are of enormous importance in quantum chemistry for calculations of properties of solids and molecules. Minimization methods for computing the ground state energy can be developed by employing a variational approach, where the second-order reduced … Read more

    Efficient solution of quadratically constrained quadratic subproblems within the MADS algorithm

  • Nadir Amaioua
  • Charles Audet
  • Andrew R. Conn
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization

    The Mesh Adaptive Direct Search algorithm (MADS) is an iterative method for constrained blackbox optimization problems. One of the optional MADS features is a versatile search step in which quadratic models are built leading to a series of quadratically constrained quadratic subproblems. This work explores different algorithms that exploit the structure of the quadratic models: … Read more

    Fully Polynomial Time (Sigma,Pi)-Approximation Schemes for Continuous Nonlinear Newsvendor and Continuous Stochastic Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , , , , ,

    We study the continuous newsvendor problem (i.e. a newsvendor problem concerning goods of a non-discrete nature, such as fresh fruit juice) and a class of stochastic dynamic programs with several application areas, such as inventory control of a continuous good, economics, and supply chain management. The class is characterized by continuous state and action spaces, … Read more

    The Rate of Convergence of Augmented Lagrange Method for a Composite Optimization Problem

  • Jihong Zhang
  • Liwei Zhang
  • Yule Zhang
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we analyze the rate of local convergence of the augmented Lagrange method for solving optimization problems with equality constraints and the objective function expressed as the sum of a convex function and a twice continuously differentiable function. The presence of the non-smoothness of the convex function in the objective requires extensive tools … Read more

    Statistical inference and hypotheses testing of risk averse stochastic programs

  • Vincent Guigues
  • Alexander Shapiro
  • Volker Krätschmer
    • Categories Stochastic Programming Tags , , , , ,

    We study statistical properties of the optimal value and optimal solutions of the Sample Average Approximation of risk averse stochastic problems. Central Limit Theorem type results are derived for the optimal value when the stochastic program is expressed in terms of a law invariant coherent risk measure having a discrete Kusuoka representation. The obtained results … Read more

    Locally weighted regression models for surrogate-assisted design optimization

  • Charles Audet
  • Michael Kokkolaras
  • Sébastien Le Digabel
  • Bastien Talgorn
    • Categories Mechanical Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Locally weighted regression combines the advantages of polynomial regression and kernel smoothing. We present three ideas for appropriate and effective use of LOcally WEighted Scatterplot Smoothing (LOWESS) models for surrogate optimization. First, a method is proposed to reduce the computational cost of LOWESS models. Second, a local scaling coefficient is introduced to adapt LOWESS models … Read more

    Numerical solution of optimal control problems with explicit and implicit switches

  • Hans Georg Bock
  • Christian Kirches
  • Andreas Meyer
  • Andreas Potschka
    • Categories Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization

    In this article, we present a unified framework for the numerical solution of optimal control problems constrained by ordinary differential equations with both implicit and explicit switches. We present the problem class and qualify different types of implicitly switched systems. This classification significantly affects opportunities for solving such problems numerically. By using techniques from generalized … Read more