Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming

  • Sun Hongchun
  • Min Sun
    • Categories Convex Optimization

    For a type of multi-block separable convex programming raised in machine learning and statistical inference, we propose a proximal alternating direction method of multiplier (PADMM) with partially parallel splitting, which has the following nice properties: (1) To alleviate the weight of the proximal terms, the restrictions imposed on the proximal parameters are relaxed substantively; (2) … Read more

    Improved Space-State Relaxation for Constrained Two-Dimensional Guillotine Cutting Problems

  • Eduardo Uchoa
  • André Velasco
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , ,

    Christofides and Hadjiconstantinou introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably … Read more

    Iteration complexity on the Generalized Peaceman-Rachford splitting method for separable convex programming

  • Peng Jian-Wen
  • Xue-Qing Zhang
    • Categories Convex Optimization

    Recently, a generalized version of Peaceman-Rachford splitting method (GPRSM) for solving a convex minmization model with a general separable structure has been proposed by \textbf{Sun} et al and its global convergence has been proved. In this paper, we further study theoretical aspects of the generalized Peaceman-Rachford splitting method. We first establish the worst-case $\mathcal{O}(1/t)$ convergence … Read more

    Permuting Spiked Matrices to Triangular Form and its Application to the Forrest-Tomlin Update

  • Jacek Gondzio
  • Lukas Schork
    • Categories Linear Programming Tags ,

    This paper is concerned with the problem of permuting a spiked matrix to triangular form. A spiked matrix results from changing one column or one row in a triangular matrix. In this paper we focus on changing one column in an upper triangular matrix. Spiked matrices arise in updating the LU factors of a matrix … Read more

    An enhanced L-Shaped method for optimizing periodic-review inventory control problems modeled via two-stage stochastic programming

  • Fabricio Oliveira
  • Felipe Placido
    • Categories Production and Logistics, Stochastic Programming

    This paper presents the development of an enhanced L-Shaped method applied to an inventory management problem that considers a replenishment control system based on the periodic review (R,S) policy. We consider single-item one-echelon problems with uncertain demands and partial backorder that are modeled using two-stage stochastic programming. To enable the consideration of large-scale problems, the … Read more

    Invex Optimization Revisited

  • Ksenia Bestuzheva
  • Hassan L. Hijazi
    • Categories Applications - Science and Engineering, Global Optimization Theory, Nonlinear Optimization Tags , , ,

    Given a non-convex optimization problem, we study conditions under which every Karush-Kuhn-Tucker (KKT) point is a global optimizer. This property is known as KT-invexity and allows to identify the subset of problems where an interior point method always converges to a global optimizer. In this work, we provide necessary conditions for KT-invexity in n-dimensions and … Read more

    A simplex method for uncapacitated pure-supply infinite network flow problems

  • Marina A. Epelman
  • Christopher Thomas Ryan
  • Robert L. Smith
    • Categories Infinite Dimensional Optimization, Network Optimization Tags , ,

    We provide a simplex algorithm for a structured class of uncapacitated countably-infinite network flow problems. Previous efforts required explicit capacities on arcs with uniformity properties that facilitate duality arguments. By contrast, this paper takes a “primal” approach by devising a simplex method that provably converges to optimal value using arguments based on convergence of spanning … Read more

    Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems

  • Vincent Guigues
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming

    We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation … Read more

    A rounding procedure for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Semi-definite Programming Tags , , ,

    Recently, Mohammad-Nezhad and Terlaky studied the identification of the optimal partition for semidefinite optimization. An approximation of the optimal partition was obtained from a bounded sequence of solutions on, or in a neighborhood of the central path. Here, we use the approximation of the optimal partition in a rounding procedure to generate an approximate maximally … Read more

    Exploiting Identical Generators in Unit Commitment

  • Bernard Knueven
  • James Ostrowski
  • Jean-Paul Watson
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    We present sufficient conditions under which thermal generators can be aggregated in mixed-integer linear programming (MILP) formulations of the unit commitment (UC) problem, while maintaining feasibility and optimality for the original disaggregated problem. Aggregating thermal generators with identical characteristics (e.g., minimum/maximum power output, minimum up/down-time, and cost curves) into a single unit reduces redundancy in … Read more