Nonlinear Optimization

Convergence Conditions for Newton-type Methods Applied to Complementarity Systems with Nonisolated Solutions

  • Andreas Fischer
  • Alexey F. Izmailov
  • Markus Herrich
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , , , ,

    We consider a class of Newton-type methods for constrained systems of equations that involve complementarity conditions. In particular, at issue are the constrained Levenberg–Marquardt method and the recently introduced Linear Programming-Newton method, designed for the difficult case when solutions need not be isolated, and the equation mapping need not be differentiable at the solutions. We … Read more

    New Ranks for Even-Order Tensors and Their Applications in Low-Rank Tensor Optimization

  • Bo Jiang
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper, we propose three new tensor decompositions for even-order tensors corresponding respectively to the rank-one decompositions of some unfolded matrices. Consequently such new decompositions lead to three new notions of (even-order) tensor ranks, to be called the M-rank, the symmetric M-rank, and the strongly symmetric M-rank in this paper. We discuss the bounds … Read more

    On iteratively reweighted Algorithms for Non-smooth Non-convex Optimization in Computer Vision

  • Thomas Brox
  • Peter Ochs
  • Thomas Pock
  • Alexey Dosovitskiy
    • Categories Nonlinear Optimization Tags , , , , , ,

    Natural image statistics indicate that we should use non-convex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge of optimization. Recently, iteratively reweighed $\ell_1$ minimization (IRL1) has been proposed as a way to tackle a class of non-convex functions by solving a … Read more

    ADMM for Convex Quadratic Programs: Linear Convergence and Infeasibility Detection

  • Stefano Di Cairano
  • Arvind U. Raghunathan
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    In this paper, we analyze the convergence of Alternating Direction Method of Multipliers (ADMM) on convex quadratic programs (QPs) with linear equality and bound constraints. The ADMM formulation alternates between an equality constrained QP and a projection on the bounds. Under the assumptions of: (i) positive definiteness of the Hessian of the objective projected on … Read more

    A Preconditioner for a Primal-Dual Newton Conjugate Gradients Method for Compressed Sensing Problems

  • Ioannis Dassios
  • Kimon Fountoulakis
  • Jacek Gondzio
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , ,

    In this paper we are concerned with the solution of Compressed Sensing (CS) problems where the signals to be recovered are sparse in coherent and redundant dictionaries. We extend a primal-dual Newton Conjugate Gradients (pdNCG) method for CS problems. We provide an inexpensive and provably effective preconditioning technique for linear systems using pdNCG. Numerical results … Read more

    Global convergence of the Heavy-ball method for convex optimization

  • Hamid Reza Feyzmahdavian
  • Euhanna Ghadimi
  • Mikael Johansson
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesa ́ro average of the iterates converges to the optimum at a rate of $O(1/k)$ where k is the number of iterations. When … Read more

    A Filter SQP Method: Local Convergence and Numerical Results

  • Nicholas I. M. Gould
  • Daniel P. Robinson
  • Yueling Loh
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    The work by Gould, Loh, and Robinson [“A filter method with unified step computation for nonlinear optimization”, SIAM J. Optim., 24 (2014), pp. 175–209] established global convergence of a new filter line search method for finding local first-order solutions to nonlinear and nonconvex constrained optimization problems. A key contribution of that work was that the … Read more

    Constrained trace-optimization of polynomials in freely noncommuting variables

  • Igor Klep
  • Janez Povh
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , , , , , ,

    The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation … Read more

    Clustering-Based Preconditioning for Stochastic Programs

  • Yankai Cao
  • Carl D. Laird
  • Victor M. Zavala
    • Categories Linear Programming, Quadratic Programming, Stochastic Programming

    We present a clustering-based preconditioning strategy for KKT systems arising in stochastic programming within an interior-point framework. The key idea is to perform adaptive clustering of scenarios (inside-the-solver) based on their influence on the problem as opposed to cluster scenarios based on problem data alone, as is done in existing (outside-thesolver) approaches. We derive spectral … Read more

    Error estimates for the Euler discretization of an optimal control problem with first-order state constraints

  • Joseph Frédéric Bonnans
  • Adriano Festa
    • Categories Control Applications, Systems governed by Differential Equations Optimization Tags , , , ,

    We study the error introduced in the solution of an optimal control problem with first order state constraints, for which the trajectories are approximated with a classical Euler scheme. We obtain order one approximation results in the $L^\infty$ norm (as opposed to the order 2/3 obtained in the literature). We assume either a strong second … Read more