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

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

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

A subspace minimization method for the trust-region step

We consider methods for large-scale unconstrained minimization based on finding an approximate minimizer of a quadratic function subject to a two-norm trust-region constraint. The Steihaug-Toint method uses the conjugate-gradient (CG) algorithm to minimize the quadratic over a sequence of expanding subspaces until the iterates either converge to an interior point or cross the constraint boundary. … Read more

Regularization and Preconditioning of KKT Systems Arising in Nonnegative Least-Squares Problems

A regularized Newton-like method for solving nonnegative least-squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the … Read more

Iterative Solution of Augmented Systems Arising in Interior Methods

Iterative methods are proposed for certain augmented systems of linear equations that arise in interior methods for general nonlinear optimization. Interior methods define a sequence of KKT equations that represent the symmetrized (but indefinite) equations associated with Newton’s method for a point satisfying the perturbed optimality conditions. These equations involve both the primal and dual … Read more

Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more

Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more

Fast iterative solution of saddle point problems in optimal control based on wavelets

In this paper, wavelet techniques are employed for the fast numerical solution of a control problem governed by an elliptic boundary value problem with boundary control. A quadratic cost functional involving natural norms of the state and the control is to be minimized. Firstly the constraint, the elliptic boundary value problem, is formulated in an … Read more