Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization

  • Coralia Cartis
  • Phillipe Sampaio
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth nonconvex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this … Read more

    Solution Methods for the Periodic Petrol Station Replenishment Problem

  • Chefi Triki
    • Categories Supply Chain Management

    In this paper we introduce the Periodic Petrol Station Replenishment Problem (PPSRP) over a T-day planning horizon and we describe four heuristic methods for its solution. Even though all the proposed heuristics belong to the common partitioning-then-routing paradigm, they differ in the way of assigning the stations to each day of the horizon. The resulting … Read more

    An Integrated Scenario-Based Approach for Robust Aircraft Routing, Crew Pairing and Re-timing.

  • Michelle Dunbar
  • Gary Froyland
  • Cheng-Lung Wu
    • Categories Airline Optimization Tags , , ,

    For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (eg. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture the … Read more

    Trace-Penalty Minimization for Large-scale Eigenspace Computation

  • Xin Liu
  • Zaiwen Wen
  • Yin Zhang
  • Chao Yang
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    The Rayleigh-Ritz (RR) procedure, including orthogonalization, constitutes a major bottleneck in computing relatively high dimensional eigenspaces of large sparse matrices. Although operations involved in RR steps can be parallelized to a certain level, their parallel scalability, which is limited by some inherent sequential steps, is lower than dense matrix-matrix multiplications. The primary motivation of this … Read more

    Intersection Cuts for Mixed Integer Conic Quadratic Sets

  • Kent Andersen
  • Anders Jensen
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Balas introduced intersection cuts for mixed integer linear sets. Intersection cuts are given by closed form formulas and form an important class of cuts for solving mixed integer linear programs. In this paper we introduce an extension of intersection cuts to mixed integer conic quadratic sets. We identify the formula for the conic quadratic intersection … Read more

    Embedded Online Optimization for Model Predictive Control at Megahertz Rates

  • George A. Constantinides
  • Paul J. Goulart
  • Eric C. Kerrigan
  • Stefan Richter
  • Juan L. Jerez
  • Manfred Morari
    • Categories Parallel Algorithms, Quadratic Programming Tags , ,

    Faster, cheaper, and more power efficient optimization solvers than those currently offered by general-purpose solutions are required for extending the use of model predictive control (MPC) to resource-constrained embedded platforms. We propose several custom computational architectures for different first-order optimization methods that can handle linear-quadratic MPC problems with input, input-rate, and soft state constraints. We … Read more

    On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

  • Yogesh Awate
  • Gérard Cornuéjols
  • Bertrand Guenin
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more

    A framework for automated PDE-constrained optimisation

  • P. E. Farrell
  • S. W. Funke
    • Categories Problem Solving Environments Tags , , , , ,

    A generic framework for the solution of PDE-constrained optimisation problems based on the FEniCS system is presented. Its main features are an intuitive mathematical interface, a high degree of automation, and an efficient implementation of the generated adjoint model. The framework is based upon the extension of a domain-specific language for variational problems to cleanly … Read more

    An Augmented Lagrangian Method for Conic Convex Programming

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more

    Risk-Averse Stochastic Dual Dynamic Programming

  • Vaclav Kozmik
  • David P. Morton
    • Categories Stochastic Programming Tags , , ,

    We formulate a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new … Read more