preconditioning

A note on preconditioning weighted linear least squares, with consequences for weakly-constrained variational data assimilation

  • Serge Gratton
  • Philippe L. Toint
  • Selime Gürol
  • Ehouarn Simon
    • Categories Basic Sciences Applications, Nonlinear Systems and Least-Squares Tags , ,

    The effect of preconditioning linear weighted least-squares using an approximation of the model matrix is analyzed, showing the interplay of the eigenstructures of both the model and weighting matrices. A small example is given illustrating the resulting potential inefficiency of such preconditioners. Consequences of these results in the context of the weakly-constrained 4D-Var data assimilation … Read more

    Preconditioning PDE-constrained optimization with L^1-sparsity and control constraints

  • Margherita Porcelli
  • Valeria Simoncini
  • Martin Stoll
    • Categories Control Applications, Systems governed by Differential Equations Optimization Tags , , , , ,

    PDE-constrained optimization aims at finding optimal setups for partial differential equations so that relevant quantities are minimized. Including sparsity promoting terms in the formulation of such problems results in more practically relevant computed controls but adds more challenges to the numerical solution of these problems. The needed L^1-terms as well as additional inclusion of box … Read more

    A basis-free null space method for solving generalized saddle point problems

  • Maria A. Diniz-Ehrhardt
  • Lucas G. Pedroso
  • Douglas Mendes
    • Categories Constrained Nonlinear Optimization, Optimization of Systems modeled by PDEs Tags , , , , , , ,

    Using an augmented Lagrangian matrix approach, we analytically solve in this paper a broad class of linear systems that includes symmetric and nonsymmetric problems in saddle point form. To this end, some mild assumptions are made and a preconditioning is specially designed to improve the sensitivity of the systems before the calculation of their solutions. … Read more

    A Class of Randomized Primal-Dual Algorithms for Distributed Optimization

  • Jean-Christophe Pesquet
  • Audrey Repetti
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , ,

    Based on a preconditioned version of the randomized block-coordinate forward-backward algorithm recently proposed in [Combettes,Pesquet,2014], several variants of block-coordinate primal-dual algorithms are designed in order to solve a wide array of monotone inclusion problems. These methods rely on a sweep of blocks of variables which are activated at each iteration according to a random rule, … Read more

    Preconditioning issues in the numerical solution of nonlinear equations and nonlinear least squares

  • Stefania Bellavia
  • Margherita Porcelli
    • Categories Nonlinear Optimization Tags , ,

    Second order methods for optimization call for the solution of sequences of linear systems. In this survey we will discuss several issues related to the preconditioning of such sequences. Covered topics include both techniques for building updates of factorized preconditioners and quasi-Newton approaches. Sequences of unsymmetric linear systems arising in Newton- Krylov methods will be … Read more

    Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization

  • Nicolas Gillis
  • Stephen A. Vavasis
    • Categories Data-Mining, Semi-definite Programming Tags , , , ,

    Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exists a cone spanned by a small subset of … Read more

    Inexact Coordinate Descent: Complexity and Preconditioning

  • Jacek Gondzio
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonlinear Systems and Least-Squares, Nonsmooth Optimization Tags , , , , ,

    In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. … Read more

    New updates of incomplete LU factorizations and applications to large nonlinear systems

  • Stefania Bellavia
  • Benedetta Morini
  • Margherita Porcelli
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper, we address the problem of preconditioning sequences of large sparse nonsymmetric systems of linear equations and present two new strategies to construct approximate updates of factorized preconditioners. Both updates are based on the availability of an incomplete LU (ILU) factorization for one matrix of the sequence and differ in the approximation of … Read more

    A preconditioning framework for sequences of diagonally modified linear systems arising in optimization

  • Stefania Bellavia
  • Valentina De Simone
  • Daniela di Serafino
  • Benedetta Morini
    • Categories Nonlinear Optimization Tags , , ,

    We propose a framework for building preconditioners for sequences of linear systems of the form $(A+\Delta_k) x_k=b_k$, where $A$ is symmetric positive semidefinite and $\Delta_k$ is diagonal positive semidefinite. Such sequences arise in several optimization methods, e.g., in affine-scaling methods for bound-constrained convex quadratic programming and bound-constrained linear least squares, as well as in trust-region … Read more

    Preconditioning and Globalizing Conjugate Gradients in Dual Space for Quadratically Penalized Nonlinear-Least Squares Problems

  • Serge Gratton
  • Philippe L. Toint
  • Selime Gürol
    • Categories Nonlinear Systems and Least-Squares, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs Tags , , , , ,

    When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each … Read more