Nonlinear Optimization

Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part I: Model and Convergence

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

    We propose a novel asynchronous parallel algorithmic framework 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 framework hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous … Read more

    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

    Quasi-Newton methods for constrained nonlinear systems: complexity analysis and application

  • Leopoldo Marini
  • Benedetta Morini
  • Margherita Porcelli
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares

    We address the solution of convex constrained nonlinear systems by new linesearch Quasi-Newton methods. These methods are based on a proper use of the projection map onto the constraint set and on a derivative-free and nonmonotone linesearch strategy. The convergence properties of the proposed methods are presented along with a worst-case iteration complexity bound. Several … Read more

    A Penalty Method for Rank Minimization Problems in Symmetric Matrices

  • John E. Mitchell
  • Xin Shen
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Semi-definite Programming Tags , ,

    The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal … Read more

    Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Mohammadreza Samadi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an $\epsilon$-feasible point and a second phase to seek optimality while maintaining at least $\epsilon$-feasibility. A two-phase approach of this kind based on … Read more

    Optimality conditions for problems over symmetric cones and a simple augmented Lagrangian method

  • Ellen H. Fukuda
  • Bruno F. Lourenço
  • Masao Fukushima
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    In this work we are interested in nonlinear symmetric cone problems (NSCPs), which contain as special cases nonlinear semidefinite programming, nonlinear second order cone programming and the classical nonlinear programming problems. We explore the possibility of reformulating NSCPs as common nonlinear programs (NLPs), with the aid of squared slack variables. Through this connection, we show … Read more

    A Limited-Memory Quasi-Newton Algorithm for Bound-Constrained Nonsmooth Optimization

  • Nitish Shirish Keskar
  • Andreas Wächter
    • Categories Bound-constrained Optimization, Nonsmooth Optimization

    We consider the problem of minimizing a continuous function that may be nonsmooth and nonconvex, subject to bound constraints. We propose an algorithm that uses the L-BFGS quasi-Newton approximation of the problem’s curvature together with a variant of the weak Wolfe line search. The key ingredient of the method is an active-set selection strategy that … 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

    Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points

  • Ernesto G. Birgin
  • Gabriel Haeser
  • Alberto Ramos
    • Categories Constrained Nonlinear Optimization Tags , ,

    Augmented Lagrangian methods with convergence to second-order stationary points in which any constraint can be penalized or carried out to the subproblems are considered in this work. The resolution of each subproblem can be done by any numerical algorithm able to return approximate second-order stationary points. The developed global convergence theory is stronger than the … Read more