Nonlinear Optimization

A Globally Convergent Stabilized SQP Method: Superlinear Convergence

  • Philip E. Gill
  • Vyacheslav Kungurtsev
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    Regularized and stabilized sequential quadratic programming (SQP) methods are two classes of methods designed to resolve the numerical and theoretical difficulties associated with ill-posed or degenerate nonlinear optimization problems. Recently, a regularized SQP method has been proposed that allows convergence to points satisfying certain second-order KKT conditions (SIAM J. Optim., 23(4):1983–2010, 2013). The method is … Read more

    Local Convergence of an Algorithm for Subspace Identification from Partial Data

  • Laura Balzano
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization, Data-Mining Tags , , ,

    GROUSE (Grassmannian Rank-One Update Subspace Estimation) is an iterative algorithm for identifying a linear subspace of $\R^n$ from data consisting of partial observations of random vectors from that subspace. This paper examines local convergence properties of GROUSE, under assumptions on the randomness of the observed vectors, the randomness of the subset of elements observed at … Read more

    iPiano: Inertial Proximal Algorithm for Nonconvex Optimization

  • Thomas Brox
  • Peter Ochs
  • Thomas Pock
  • Yunjin Chen
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly nonconvex) and a convex (possibly nondifferentiable) function. The algorithm iPiano combines forward-backward splitting with an inertial force. It can be seen as a nonsmooth split version of the Heavy-ball method from Polyak. A rigorous analysis of the algorithm … Read more

    Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation

  • Elhoucine Bergou
  • Serge Gratton
  • Luis Nunes Vicente
    • Categories Applications - Science and Engineering, Nonlinear Systems and Least-Squares, Stochastic Programming Tags , , , , , , ,

    The Levenberg-Marquardt algorithm is one of the most popular algorithms for the solution of nonlinear least squares problems. Motivated by the problem structure in data assimilation, we consider in this paper the extension of the classical Levenberg-Marquardt algorithm to the scenarios where the linearized least squares subproblems are solved inexactly and/or the gradient model is … Read more

    Projection Methods: An Annotated Bibliography of Books and Reviews

  • Andrzej Cegielski
  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , ,

    Projections onto sets are used in a wide variety of methods in optimization theory but not every method that uses projections really belongs to the class of projection methods as we mean it here. Here projection methods are iterative algorithms that use projections onto sets while relying on the general principle that when a family … Read more

    How Difficult is Nonlinear Optimization? A Practical Solver Tuning Approach, with Illustrative Results

  • János Pintér
    • Categories Global Optimization Applications, Nonlinear Optimization, Optimization Software Benchmark

    Nonlinear optimization (NLO) per definitionem covers a vast range of problems, from trivial to practically intractable. For this reason, it is impossible to offer “guaranteed” advice to NLO software users. This fact becomes especially obvious, when facing unusually hard and/or previously unexplored NLO challenges. In the present study we offer some related practical observations, propose … Read more

    On the Minimization Over Sparse Symmetric Sets: Projections, Optimality Conditions and Algorithms

  • Amir Beck
  • Nadav Hallak
    • Categories Global Optimization Theory, Nonlinear Optimization Tags , ,

    We consider the problem of minimizing a general continuously differentiable function over symmetric sets under sparsity constraints. These type of problems are generally hard to solve as the sparsity constraint induces a combinatorial constraint into the problem, rendering the feasible set to be nonconvex. We begin with a study of the properties of the orthogonal … Read more

    On the regularizing behavior of recent gradient methods in the solution of linear ill-posed problems

  • Roberta De Asmundis
  • Daniela di Serafino
  • Germana Landi
    • Categories Nonlinear Optimization Tags , , ,

    We analyze the regularization properties of two recently proposed gradient methods applied to discrete linear inverse problems. By studying their filter factors, we show that the tendency of these methods to eliminate first the eigencomponents of the gradient corresponding to large singular values allows to reconstruct the most significant part of the solution, thus yielding … Read more

    Exact duality in semidefinite programming based on elementary reformulations

  • Minghui Liu
  • Gabor Pataki
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Semi-definite Programming

    In semidefinite programming (SDP), unlike in linear programming, Farkas’ lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP by an elementary approach: we reformulate any equality constrained semidefinite system using only elementary row operations, and rotations. When the system is infeasible, the infeasibility of the reformulated system … Read more

    An Efficient Gauss-Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations

  • Xin Liu
  • Zaiwen Wen
  • Yin Zhang
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , ,

    We derive and study a Gauss-Newton method for computing a symmetric low-rank product that is the closest to a given symmetric matrix in Frobenius norm. Our Gauss-Newton method, which has a particularly simple form, shares the same order of iteration-complexity as a gradient method when the size of desired eigenspace is small, but can be … Read more