Month: August 2015

Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming

  • Deren Han
  • Defeng Sun
  • Liwei Zhang
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    In this paper, we aim to provide a comprehensive analysis on the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a certain error bound condition, we establish the global linear rate of convergence for a more general semi-proximal ADMM with the dual steplength … Read more

    Robust Dual Response Optimization

  • Dick den Hertog
  • Jack P.C. Kleijnen
  • Ihsan Yanıkoğlu
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Robust Optimization

    This article presents a robust optimization reformulation of the dual response problem developed in response surface methodology. The dual response approach fits separate models for the mean and the variance, and analyzes these two models in a mathematical optimization setting. We use metamodels estimated from experiments with both controllable and environmental inputs. These experiments may … Read more

    Duality in Two-stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds

  • Dimitris Bertsimas
  • Frans J.C.T. de Ruiter
    • Categories Applications - OR and Management Sciences, Robust Optimization

    In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the … Read more

    A priori bounds on the condition numbers in interior-point methods

  • Florian Jarre
    • Categories Linear Programming, Semi-definite Programming Tags , ,

    Interior-point methods are known to be sensitive to ill-conditioning and to scaling of the data. This paper presents new asymptotically sharp bounds on the condition numbers of the linear systems at each iteration of an interior-point method for solving linear or semidefinite programs and discusses a stopping test which leads to a problem-independent “a priori” … Read more

    Thermal Optimization of the Continuous Casting Process using Distributed Parameter Identification Approach — Controlling the Curvature of Solid-Liquid Interface

  • Rouhollah Tavakoli
    • Categories Applications - Science and Engineering, Multidisciplinary Design Optimization, Optimization of Systems modeled by PDEs

    Thermal optimization of vertical continuous casting process is considered in the present study. The goal is to find the optimal distribution of temperature and interfacial heat transfer coefficients corresponding to the primary and secondary cooling systems, in addition to the pulling speed, such that the solidification along the main axis of strand approaches to the … Read more

    Low-rank spectral optimization

  • Michael P. Friedlander
  • Ives Macêdo
    • Categories Convex Optimization

    Various applications in signal processing and machine learning give rise to highly structured spectral optimization problems characterized by low-rank solutions. Two important examples that motivate this work are optimization problems from phase retrieval and from blind deconvolution, which are designed to yield rank-1 solutions. An algorithm is described based solving a certain constrained eigenvalue optimization … Read more

    Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part II: Tight Upper Bounds

  • György Dósa
  • Armin Fügenschuh
  • Zhiyi Tan
  • Zsolt Tuza
  • Krzysztof Wesek
    • Categories Approximation Algorithms Tags , , ,

    We consider a semi-online version of the problem of scheduling a sequence of jobs of different lengths on two uniform machines with given speeds $1$ and $s$. Jobs are revealed one by one (the assignment of a job has to be done before the next job is revealed), and the objective is to minimize the … Read more

    Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part I: Tight Lower Bounds

  • György Dósa
  • Armin Fügenschuh
  • Zhiyi Tan
  • Zsolt Tuza
  • Krzysztof Wesek
    • Categories Approximation Algorithms Tags , , ,

    This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds $1$ and $s \geq 1$, so that the overall completion time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs arrive one … Read more

    New Valid Inequalities and Facets for the Simple Plant Location Problem

  • Laura Galli
  • Adam N. Letchford
  • Sebastian J. Miller
    • Categories Polyhedra, Production and Logistics

    The Simple Plant Location Problem is a well-known (and NP-hard) combinatorial optimisation problem, with applications in logistics. We present a new family of valid inequalities for the associated family of polyhedra, and show that it contains an exponentially large number of new facet-defining members. We also present a new procedure, called facility augmentation, which enables … Read more

    Mixed Integer Second-Order Cone Programming for the Horizontal and Vertical Free-flight Planning Problem

  • Liana Amaya Moreno
  • Armin Fügenschuh
  • Anton Kaier
  • Amina Mollaysa
  • Swen Schlobach
  • Zhi Yuan
    • Categories Airline Optimization, Second-Order Cone Programming Tags , ,

    In the past, travel routes for civil passenger and cargo air traffic were aligned to the air traffic network (ATN). To resolve the network congestion problem, the free-flight system has recently been introduced in more and more regions around the globe, allowing flight operations to make full use of the four space-and-time dimensions. For the … Read more