Optimization Software and Modeling Systems

Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results

  • Loris Cannelli
  • Francisco Facchinei
  • Vyacheslav Kungurtsev
  • Gesualdo Scutari
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , ,

    We present complexity and numerical results for a new asynchronous parallel algorithmic method for the minimization of the sum of a smooth nonconvex function and a convex nonsmooth regularizer, subject to both convex and nonconvex constraints. The proposed method hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of … Read more

    On the Convergence of Asynchronous Parallel Iteration with Arbitrary Delays

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
    • Categories Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call \emph{delay}, is the number of times it has been … Read more

    Unified approach for solving Box-Constrained models with continuous or discrete variables by Non monotonous Derivative Free Optimization techniques.

  • Ubaldo M Garcia Palomares
  • Pedro S Rodríguez Hernández
    • Categories Bound-constrained Optimization, Integer Programming, Problem Solving Environments Tags , ,

    This paper describes a unified approach for solving Box-Constrained Optimization Problems (BCOP) in Euclidian spaces. The variables may be either continuous or discrete; in which case, they range on a grid of isolated points regularly spaced. For the continuous case, convergence is shown under standard assumptions; for the discrete case, slight modifications ensure that the … Read more

    A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems

  • Natashia Boland
  • Brian Dandurand
  • Andrew C. Eberhard
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. The dual solution approach needs … Read more

    trlib: A vector-free implementation of the GLTR method for iterative solution of the trust region problem

  • Christian Kirches
  • Andreas Potschka
  • Felix Lenders
    • Categories Optimization Software and Modeling Systems, Quadratic Programming Tags , , ,

    We describe trlib, a library that implements a Variant of Gould’s Generalized Lanczos method (Gould et al. in SIAM J. Opt. 9(2), 504–525, 1999) for solving the trust region problem. Our implementation has several distinct features that set it apart from preexisting ones. We implement both conjugate gradient (CG) and Lanczos iterations for assembly of … Read more

    Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server

  • Arda Aytekin
  • Hamid Reza Feyzmahdavian
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    This paper presents an asynchronous incremental aggregated gradient algorithm and its implementation in a parameter server framework for solving regularized optimization problems. The algorithm can handle both general convex (possibly non-smooth) regularizers and general convex constraints. When the empirical data loss is strongly convex, we establish linear convergence rate, give explicit expressions for step-size choices … Read more

    Can linear superiorization be useful for linear optimization problems?

  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Linear Programming, Problem Solving Environments Tags , , , , , , , , ,

    Linear superiorization considers linear programming problems but instead of attempting to solve them with linear optimization methods it employs perturbation resilient feasibility-seeking algorithms and steers them toward reduced (not necessarily minimal) target function values. The two questions that we set out to explore experimentally are (i) Does linear superiorization provide a feasible point whose linear … Read more

    An Augmented Lagrangian Filter Method for Real-Time Embedded Optimization

  • Nai-Yuan Chiang
  • Victor M. Zavala
  • Rui Huang
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , , ,

    We present a filter line-search algorithm for nonconvex continuous optimization that combines an augmented Lagrangian function and a constraint violation metric to accept and reject steps. The approach is motivated by real-time optimization applications that need to be executed on embedded computing platforms with limited memory and processor speeds. In particular, the proposed method enables … Read more

    On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms

  • Robert Hannah
  • Wotao Yin
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    The need for scalable numerical solutions has motivated the development of asynchronous parallel algorithms, where a set of nodes run in parallel with little or no synchronization, thus computing with delayed information. This paper studies the convergence of the asynchronous parallel algorithm ARock under potentially unbounded delays. ARock is a general asynchronous algorithm that has … Read more

    A simple preprocessing algorithm for semidefinite programming

  • Preston Faulk
  • Gabor Pataki
  • Quoc Tran-Dinh
    • Categories Convex Optimization, Optimization Software Benchmark, Semi-definite Programming

    We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, … Read more