optimal diagonal preconditioner

Optimal diagonal preconditioning beyond worst-case conditioning: theory and practice of omega scaling

  • Saeed Ghadimi
  • Woosuk L. Jung
  • Arnesh Sujanani
  • David Torregrosa-BelĂ©n
  • Henry Wolkowicz
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    Preconditioning is essential in many areas of mathematics, and in particular is a fundamental tool for accelerating iterative methods for solving linear systems. In this work, we study optimal diagonal preconditioning under two distinct notions of conditioning: the classical worst-case \(\kappa\)-condition number and the averaging-based \(\omega\)-condition number. We observe that \(\omega\)-optimal preconditioning generally outperforms \(\kappa\)-optimal … Read more

    Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking

  • Frederik Kunstner
  • Mark Schmidt
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate stepsizes. We … Read more

    Simple Efficient Solutions for Semidefinite Programming

  • Henry Wolkowicz
    • Categories Combinatorial Optimization, Nonlinear Systems and Least-Squares, Semi-definite Programming Tags , , , , ,

    This paper provides a simple approach for solving a semidefinite program, SDP\@. As is common with many other approaches, we apply a primal-dual method that uses the perturbed optimality equations for SDP, $F_\mu(X,y,Z)=0$, where $X,Z$ are $n \times n$ symmetric matrices and $y \in \Re^n$. However, we look at this as an overdetermined system of … Read more