An Enhanced Spatial Branch-and-Bound Method in Global Optimization with Nonconvex Constraints

  • Peter Kirst
  • Oliver Stein
  • Paul Steuermann
    • Categories Global Optimization Tags , , ,

    We discuss some difficulties in determining valid upper bounds in spatial branch-and-bound methods for global minimization in the presence of nonconvex constraints. In fact, two examples illustrate that standard techniques for the construction of upper bounds may fail in this setting. Instead, we propose to perturb infeasible iterates along Mangasarian-Fromovitz directions to feasible points whose … Read more

    Gradient methods for convex minimization: better rates under weaker conditions

  • Wotao Yin
  • Hui Zhang
    • Categories Convex Optimization Tags , , , , , , ,

    The convergence behavior of gradient methods for minimizing convex differentiable functions is one of the core questions in convex optimization. This paper shows that their well-known complexities can be achieved under conditions weaker than the commonly assumed ones. We relax the common gradient Lipschitz-continuity condition and strong convexity condition to ones that hold only over … Read more

    On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems

  • Radu Ioan Bot
  • Ernö Robert Csetnek
  • Andre Heinrich
    • Categories Convex Optimization Tags , , , , , , ,

    We present two modified versions of the primal-dual splitting algorithm relying on forward-backward splitting proposed in [21] for solving monotone inclusion problems. Under strong monotonicity assumptions for some of the operators involved we obtain for the sequences of iterates that approach the solution orders of convergence of ${\cal {O}}(\frac{1}{n})$ and ${\cal {O}}(\omega^n)$, for $\omega \in … Read more

    Smoothness Properties of a Regularized Gap Function for Quasi-Variational Inequalities

  • Nadja Harms
  • Oliver Stein
  • Christian Kanzow
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Game Theory Tags , , , , ,

    This article studies continuity and differentiability properties for a reformulation of a finite-dimensional quasi-variational inequality (QVI) problem using a regularized gap function approach. For a special class of QVIs, this gap function is continuously differentiable everywhere, in general, however, it has nondifferentiability points. We therefore take a closer look at these nondifferentiability points and show, … Read more

    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