Month: October 2012

On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

    Distributionally Robust Multi-Item Newsvendor Problems with Multimodal Demand Distributions

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Stein W. Wallace
  • Steve Zymler
    • Categories Robust Optimization

    We present a risk-averse multi-dimensional newsvendor model for a class of products whose demands are strongly correlated and subject to fashion trends that are not fully understood at the time when orders are placed. The demand distribution is known to be multimodal in the sense that there are spatially separated clusters of probability mass but … Read more

    Modified alternating direction methods for the modified multiple-sets split feasibility problems

  • Yuning Yang
  • Qingzhi Yang
  • Su Zhang
    • Categories Complementarity and Variational Inequalities Tags , , , ,

    Inthispaper, weproposetwonewmultiple-setssplitfeasibilityproblem(MSFP)models, where the MSFP requires to find a point closest to the intersection of a family of closed convex sets in one space, such that its image under a linear transformation will be closest to the intersection of another family of closed convex sets in the image space. This problem arises in image restoration, … Read more

    The Spectral Bundle Method with Second-Order Information

  • Christoph Helmberg
  • Michael L. Overton
  • Franz Rendl
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    The spectral bundle method was introduced by Helmberg and Rendl to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the spectral bundle method, building on work of Overton … Read more

    Adaptive Regularized Self-Consistent Field Iteration with Exact Hessian for Electronic Structure Calculation

  • Andre Milzarek
  • Michael Ulbrich
  • Zaiwen Wen
  • Hongchao Zhang
    • Categories Nonlinear Optimization Tags , , , ,

    The self-consistent field (SCF) iteration has been used ubiquitously for solving the Kohn-Sham (KS) equation or the minimization of the KS total energy functional with respect to orthogonality constraints in electronic structure calculations. Although SCF with heuristics such as charge mixing often works remarkably well on many problems, it is well known that its convergence … Read more

    A Generalization of a Theorem of Arrow, Barankin and Blackwell to a Nonconvex Case

  • Refail Kasimbeyli
  • Musa Mammadov
    • Categories Global Optimization, Global Optimization Theory, Multi-Criteria Optimization Tags , , , , , ,

    The paper presents a generalization of a known density theorem of Arrow, Barankin, and Blackwell for properly efficient points defined as support points of sets with respect to monotonically increasing sublinear functions. This result is shown to hold for nonconvex sets of a reflexive Banach space partially ordered by a Bishop–Phelps cone. Citation Department of … Read more

    Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

  • Ion Necoara
  • Valentin Nedelcu
    • Categories Convex Optimization, Distributed Control, Parallel Algorithms Tags , , , , ,

    In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence … Read more

    The robust vehicle routing problem with time windows

  • Agostinho Agra
  • Michael Poss
  • Marielle Christiansen
  • Rosa Figueiredo
  • Lars M. Hvattum
  • Cristina Requejo
    • Categories Robust Optimization, Transportation

    This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a … Read more

    On Perspective Functions and Vanishing Constraints in Mixed-Integer Nonlinear Optimal Control

  • Michael N. Jung
  • Christian Kirches
  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags ,

    Logical implications appear in a number of important mixed-integer nonlinear optimal control problems (MIOCPs). Mathematical optimization offers a variety of different formulations that are equivalent for boolean variables, but result in different relaxations. In this article we give an overview over a variety of different modeling approaches, including outer versus inner convexification, generalized disjunctive programming, … Read more