Month: October 2014

Facets for Continuous Multi-Mixing Set with General Coefficients and Bounded Integer Variables

  • Manish Bansal
  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , , , ,

    Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more

    A Trust Region Algorithm with a Worst-Case Iteration Complexity of ${\cal O}(\epsilon^{-3/2})$ for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Mohammadreza Samadi
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , , , ,

    We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any $\bar\epsilon \in (0,\infty)$, the algorithm requires at most $\mathcal{O}(\epsilon^{-3/2})$ iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any $\epsilon \in (0,\bar\epsilon]$. This improves upon the $\mathcal{O}(\epsilon^{-2})$ bound known to hold for … Read more

    Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

  • Tomonari Kitahara
  • Noriyoshi Sukegawa
    • Categories Linear Programming Tags , ,

    Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the … Read more

    Sequential Bounding Methods for Two-Stage Stochastic Programs

  • Brian T. Denton
  • Alexander Gose
    • Categories Production and Logistics, Stochastic Programming

    CitationAlexander H. Gose Graduate Program of Operations Research, North Carolina State University, Raleigh, NC 27695, ahgose@ncsu.edu Brian T. Denton Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109, btdenton@umich.edu October 17, 2014 (Accepted for publication to INFORMS Journal on Computing)

    Conditional Gradient Sliding for Convex Optimization

  • Guanghui Lan
  • Yi Zhou
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this paper, we present a new conditional gradient type method for convex optimization by utilizing a linear optimization (LO) oracle to minimize a series of linear functions over the feasible set. Different from the classic conditional gradient method, the conditional gradient sliding (CGS) algorithm developed herein can skip the computation of gradients from time … Read more

    Robust constrained shortest path problems under budgeted uncertainty

  • Luigi di Puglia Pugliese
  • Francesca Guerriero
  • Artur Alves Pessoa
  • Michael Poss
    • Categories Combinatorial Optimization, Robust Optimization Tags , , , ,

    We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is \NPhard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the … Read more

    Iteration Bounds for Finding the $\epsilonhBcStationary Points for Structured Nonconvex Optimization

  • Bo Jiang
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we study proximal conditional-gradient (CG) and proximal gradient-projection type algorithms for a block-structured constrained nonconvex optimization model, which arises naturally from tensor data analysis. First, we introduce a new notion of $\epsilon$-stationarity, which is suitable for the structured problem under consideration. %, compared with other similar solution concepts. We then propose two … Read more

    High Detail Stationary Optimization Models for Gas Networks: Validation and Results

  • Martin Schmidt
  • Marc C. Steinbach
  • Bernhard M. Willert
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , ,

    Due to strict regulatory rules in combination with complex nonlinear physics, major gas network operators in Germany and Europe face hard planning problems that call for optimization. In part 1 of this paper we have developed a suitable model hierarchy for that purpose. Here we consider the more practical aspects of modeling. We validate individual … Read more

    Higher Order Maximum Persistency and Comparison Theorems

  • Alexander Shekhovtsov
    • Categories 0-1 Programming, Global Optimization Theory, Polyhedra Tags , , , , ,

    We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in … Read more