A second-order sequential optimality condition associated to the convergence of optimization algorithms

  • Roberto Andreani
  • Gabriel Haeser
  • Alberto Ramos
  • Paulo J. S. Silva
    • Categories Constrained Nonlinear Optimization Tags , ,

    Sequential optimality conditions have recently played an important role on the analysis of the global convergence of optimization algorithms towards first-order stationary points and justifying their stopping criteria. In this paper we introduce the first sequential optimality condition that takes into account second-order information. We also present a companion constraint qualification that is less stringent … Read more

    First order optimality conditions for mathematical programs with second-order cone complementarity constraints

  • Jane J. Ye
  • Jinchuan Zhou
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Second-Order Cone Programming Tags , , , , ,

    In this paper we consider a mathematical program with second-order cone complementarity constraints (SOCMPCC). The SOCMPCC generalizes the mathematical program with complementarity constraints (MPCC) in replacing the set of nonnegative reals by a second-order cone. We show that if the SOCMPCC is considered as an optimization problem with convex cone constraints, then Robinson’s constraint qualification … Read more

    A Lex-BFS-based recognition algorithm for Robinsonian matrices

  • Monique Laurent
  • Matteo Seminaroti
    • Categories Combinatorial Optimization

    Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm … Read more

    Relaxations and discretizations for the pooling problem

  • Shabbir Ahmed
  • Myun-Seok Cheon
  • Santanu S. Dey
  • Akshay Gupte
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment, and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives unifying arguments and new insights on prevalent techniques. We also present new ideas for computing … Read more

    A mean-risk MINLP for transportation network protection

  • Akshay Gupte
  • Yongxi Huang
  • Jie Lu
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Approaches, Transportation Tags , , , ,

    This paper focuses on transportation network protection to hedge against extreme events such as earthquakes. Traditional two-stage stochastic programming has been widely adopted to obtain solutions under a risk-neutral preference through the use of expectations in the recourse function. In reality, decision makers hold different risk preferences. We develop a mean-risk two-stage stochastic programming model … Read more

    Computational investigation of simple memetic approaches for continuous global optimization

  • Federico Cabassi
  • Marco Locatelli
    • Categories Stochastic Approaches Tags , ,

    In [Locatelli et al., 2014] a memetic approach, called MDE, for the solution of continuous global optimization problems, has been introduced and proved to be quite efficient in spite of its simplicity. In this paper we computationally investigate some variants of MDE. The investigation reveals that the best variant of MDE usually outperforms MDE itself, … Read more

    K-Adaptability in Two-Stage Distributionally Robust Binary Programming

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Integer Programming, Robust Optimization

    We propose to approximate two-stage distributionally robust programs with binary recourse decisions by their associated K-adaptability problems, which pre-select K candidate second-stage policies here-and-now and implement the best of these policies once the uncertain parameters have been observed. We analyze the approximation quality and the computational complexity of the K-adaptability problem, and we derive explicit … Read more

    Beam Search for integer multi-objective optimization

  • Thibaut Barthelemy
  • Sophie N. Parragh
  • Richard F. Hartl
  • Fabien Tricoire
    • Categories Meta Heuristics, Multi-Criteria Optimization

    Beam search is a tree search procedure where, at each level of the tree, at most W nodes are kept. This results in a metaheuristic whose solving time is polynomial in W. Popular for single-objective problems, beam search has only received little attention in the context of multi-objective optimization. By introducing the concepts of oracle … Read more

    Strong SOCP Relaxations for the Optimal Power Flow Problem

  • Santanu S. Dey
  • Burak Kocuk
  • Xu Andy Sun
    • Categories Applications - Science and Engineering, Global Optimization, Nonlinear Optimization Tags , , ,

    This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in … Read more