Month: June 2018

An inexact strategy for the projected gradient algorithm in vector optimization problems on variable ordered spaces

  • Yunier Bello-Cruz
  • Gemayqzel Bouza
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Variable order structures model situations in which the comparison between two points depends on a point-to-cone map. In this paper, an inexact projected gradient method for solving smooth constrained vector optimization problems on variable ordered spaces is presented. It is shown that every accumulation point of the generated sequence satisfies the first order necessary optimality … Read more

    On positive duality gaps in semidefinite programming

  • Gabor Pataki
    • Categories Convex Optimization, Semi-definite Programming

    We study semidefinite programs (SDPs) with positive duality gaps, i.e., different optimal values in the primal and dual problems. the primal and dual problems differ. These SDPs are considered extremely pathological, they are often unsolvable, and they also serve as models of more general pathological convex programs. We first fully characterize two variable SDPs with … Read more

    Tractable approximation of hard uncertain optimization problems

  • Aharon Ben-Tal
  • Frans J.C.T. de Ruiter
  • Dick den Hertog
  • Ernst Roos
  • Jianzhe Zhen
    • Categories Robust Optimization Tags , ,

    In many optimization problems uncertain parameters appear in a convex way, which is problematic as common techniques can only handle concave uncertainty. In this paper, we provide a systematic way to construct conservative approximations to such problems. Specifically, we reformulate the original problem as an adjustable robust optimization problem in which the nonlinearity of the … Read more

    The Supporting Hyperplane Optimization Toolkit

  • Jan Kronqvist
  • Andreas Lundell
  • Tapio Westerlund
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , , ,

    In this paper, an open source solver for mixed-integer nonlinear programming (MINLP) problems is presented. The Supporting Hyperplane Optimization Toolkit (SHOT) combines a dual strategy based on polyhedral outer approximations (POA) with primal heuristics. The outer approximation is achieved by expressing the nonlinear feasible set of the MINLP problem with linearizations obtained with the extended … Read more

    Quasi-Newton approaches to Interior Point Methods for quadratic problems

  • Jacek Gondzio
  • Francisco N. C. Sobral
    • Categories Nonlinear Systems and Least-Squares, Quadratic Programming Tags , , , ,

    Interior Point Methods (IPM) rely on the Newton method for solving systems of nonlinear equations. Solving the linear systems which arise from this approach is the most computationally expensive task of an interior point iteration. If, due to problem’s inner structure, there are special techniques for efficiently solving linear systems, IPMs enjoy fast convergence and … Read more

    New sequential optimality conditions for mathematical problems with complementarity constraints and algorithmic consequences

  • Roberto Andreani
  • Gabriel Haeser
  • Paulo J. S. Silva
  • Leonardo D. Secchin
    • Categories Nonlinear Optimization

    In recent years, the theoretical convergence of iterative methods for solving nonlinear constrained optimization problems has been addressed using sequential optimality conditions, which are satisfied by minimizers independently of constraint qualifications (CQs). Even though there is a considerable literature devoted to sequential conditions for standard nonlinear optimization, the same is not true for Mathematical Problems … Read more

    On the Relation between MPECs and Optimization Problems in Abs-Normal Form

  • Lisa Hegerhorst-Schultchen
  • Christian Kirches
  • Marc C. Steinbach
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We show that the problem of unconstrained minimization of a function in abs-normal form is equivalent to identifying a certain stationary point of a counterpart Mathematical Program with Equilibrium Constraints (MPEC). Hence, concepts introduced for the abs-normal forms turn out to be closely related to established concepts in the theory of MPECs. We give a … Read more

    An Enhanced Branch and Price Algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows

  • Gonzalo Lera-Romero
  • Juan José Miranda-Bront
  • Francisco J. Soulignac
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization

    In this paper we implement a branch and price (BP) algorithm for a time dependent vehicle routing problem with time windows (TDVRPTW) in which the goal is to minimize the total route duration (DM-TDVRPTW). The travel time between two customers depends on the departure time and, thus, it need not remain fixed along the planning … Read more

    New facets for the consecutive ones polytope

  • Laura Brentegani
  • Luigi De Giovanni
  • Mattia Festa
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Polyhedra Tags , ,

    A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear … Read more

    A Dual Approximate Dynamic Programming Approach to Multi-stage Stochastic Unit Commitment

  • James R. Luedtke
  • Jagdish Ramakrishnan
    • Categories Applications - OR and Management Sciences

    We study the multi-stage stochastic unit commitment problem in which commitment and generation decisions can be made and adjusted in each time period. We formulate this problem as a Markov decision process, which is “weakly-coupled” in the sense that if the demand constraint is relaxed, the problem decomposes into a separate, low-dimensional, Markov decision process … Read more