Optimization Software and Modeling Systems

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

    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

    On Stable Piecewise Linearization and Generalized Algorithmic Differentiation

  • Andreas Griewank
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization Software Design Principles Tags , , , , , , , , , , , , ,

    It is shown how functions that are defined by evaluation programs involving the absolute value function (besides smooth elementals), can be approximated locally by piecewise-linear models in the style of algorithmic, or automatic, differentiation (AD). The model can be generated by a minor modification of standard AD tools and it is Lipschitz continuous with respect … Read more

    Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method

  • Achim Koberstein
  • Christian Wolf
    • Categories Optimization Software and Modeling Systems, Stochastic Programming Tags , , ,

    The Nested L-shaped method is used to solve two- and multi-stage linear stochastic programs with recourse, which can have integer variables on the first stage. In this paper we present and evaluate a cut consolidation technique and a dynamic sequencing protocol to accelerate the solution process. Furthermore, we present a parallelized implementation of the algorithm, … Read more

    An Outer-Inner Approximation for separable MINLPs

  • Pierre Bonami
  • Hassan L. Hijazi
  • Adam Ouorou
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , ,

    A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These … Read more

    A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , , ,

    In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for … Read more

    Convergence and Perturbation Resilience of Dynamic String-Averaging Projection Methods

  • Yair Censor
  • Alexander J. Zaslavski
    • Categories Biomedical Applications, Convex Optimization, Parallel Algorithms Tags , , , , , , , , ,

    We consider the convex feasibility problem (CFP) in Hilbert space and concentrate on the study of string-averaging projection (SAP) methods for the CFP, analyzing their convergence and their perturbation resilience. In the past, SAP methods were formulated with a single predetermined set of strings and a single predetermined set of weights. Here we extend the … Read more

    Tolerances

  • Harvey Greenberg
    • Categories Optimization Software and Modeling Systems Tags , ,

    Many different tolerances are used in mathematical programming systems. They are not used in the same way, and tolerances are related to each other. This Mathematical Programming Glossary Supplement presents the main concepts with specifics for some MPS’s and examples to illustrate caution. CitationAvailable as Mathematical Programming Glossary Supplement, 2003, at http://glossary.computing.society.informs.org/ArticleDownload View PDF

    Evolutionary Dynamic Optimization: A Survey of the State of the Art

  • Juergen Branke
  • Trung Thanh Nguyen
  • Shengxiang Yang
    • Categories Meta Heuristics, Optimization Software and Modeling Systems, Other Topics Tags , , , ,

    Optimization in dynamic environments is a challenging but important task since many real-world optimization problems are changing over time. Evolutionary computation and swarm intelligence are good tools to address optimization problems in dynamic environments due to their inspiration from natural self-organized systems and biological evolution, which have always been subject to changing environments. Evolutionary optimization … Read more

    An efficient matrix splitting method for the second-order cone complementarity problem

  • Zhang Lei-Hong
  • Weihong Yang
    • Categories Complementarity and Variational Inequalities, Optimization Software and Modeling Systems, Second-Order Cone Programming Tags , , , , , , ,

    Given a symmetric and positive (semi)definite $n$-by-$n$ matrix $M$ and a vector, in this paper, we consider the matrix splitting method for solving the second-order cone linear complementarity problem (SOCLCP). The matrix splitting method is among the most widely used approaches for large scale and sparse classical linear complementarity problems (LCP), and its linear convergence … Read more