Preconditioning Iterative Methods in Optimization

Wednesday 22 November 2017   Edinburgh

Home       Abstracts       Schedule      

Abstracts

Prof Silvana Bocanegra   (Universidade Federal Rural de Pernambuco, Brazil)

Talk title: Hybrid preconditioners for linear systems arising in interior point methods

Abstract: The most time-consuming part of each interior point method iteration is computing Newton's direction by solving one or more linear systems. As the dimension of the problems increases, iterative methods become interesting because they need low additional memory and preserve sparsity. Preconditioned Gradient Conjugated is a common choice to solve these systems. However, preconditioning is not an easy task since the eigenvalues distributions of the matrices involved in the linear systems for the first interior point method iterations have a very different pattern in comparison with those of the last iterations. Usually, a suitable preconditioner for initial iterations cannot be appropriate for the final iterations and vice versa. Hybrid preconditioners have been applied to solve these systems. We will present two of these hybrid preconditioners and some ideas to improve these approaches. The first hybrid preconditioner was applied to solve general linear programming problems: in the initial interior point iterations a kind of incomplete Cholesky preconditioner is used and for the last iterations, when the systems are ill-conditioned the splitting preconditioner is the choice. The second hybrid preconditioner was developed to solve block-angular problems: in the first iterations, combine Cholesky factorizations for the block constraints and a conjugate gradient based on a power series preconditioner for the linking constraints. In the last iterations, the splitting preconditioner is applied. Determine the moment of switch between these preconditioners is critical for the efficiency of the hybrid approaches. A rule to exchange these preconditioners monitoring a condition number estimative of the preconditioned matrix is presented. This estimative is obtained using the Ritz values, which are approximations of the eigenvalues of the matrix. To improve these hybrid approaches, in some interior point iterations a few Ritz Vectors can be also computed and applied to a Deflated-CG in order to reduce small eigenvalues of the preconditioned matrix and consequently to speed the convergence of the solution.

Dr Alemseged Weldeyesus   (University of Edinburgh, UK)

Talk title: On solving large-scale truss layout optimization problems using iterative methods

Abstract: Truss layout optimization problems, usually modeled as linear programming, are known for being large-scale problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Despite each of these sub-problems is smaller compared to the original one, most of them still remain large-scale, demanding computationally efficient solution techniques. In this presentation, we present a special purpose primal-dual interior point method. The method exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller systems. We use a preconditioned gradient method to solve the already reduced linear systems with a preconditioner designed based on the mathematical properties of the problem. Finally, due to high degree of similarity among the subsequent sub-problems after performing few member adding iterations, we use a warm-start strategy to define a starting point and achieve convergence within fewer interior point iterations. The efficiency and robustness of the method is supported with several numerical experiments.
Joint work with Jacek Gondzio

Dr John Pearson   (University of Edinburgh, UK)

Talk title: Some Perspectives on Preconditioning PDE-Constrained Optimization Problems

Abstract: PDE-constrained optimization problems have a wide range of applications across numerical mathematics and applied science, so it is important to develop fast and feasible methods to solve such problems. We employ preconditioned iterative methods to tackle the large and sparse matrix systems that arise from their discretization, and consider a range of issues related to these solvers. In particular, we discuss applications of reaction-diffusion control problems in mathematical biology, strategies for handling additional box constraints on the PDE variables, approaches for problems involving fractional derivatives, and deferred correction methods for time-dependent problems.

Mr Lukas Schork   (University of Edinburgh, UK)

Talk title: Basis Preconditioners for Normal Equations

Abstract: Solving the normal equation system $AA\text{'}x=b$, where $A$ is an $m\; x\; n$ (m < n) matrix, is a very common and important problem in numerical optimization. Linear systems of that form occur in the least squares method, the linear programming interior point method and in several nonlinear optimization methods.
We consider the case where $A$ is large and sparse and where computing a direct factorization of $AA\text{'}$ is expensive or infeasible. To improve the convergence of an iterative method, we investigate using a preconditioner of the form $BB\text{'}$, where $B$ is an $m\; x\; m$ nonsingular submatrix of $A$. In many applications factorizing $B$ is much less expensive than factorizing $AA\text{'}$, which makes the approach computationally feasible. The talk briefly discusses theoretical properties of basis preconditioners and how to choose a good submatrix. The larger part is devoted to a computational study that evaluates their effectivity and efficiency on real world problems

Dr Margherita Porcelli   (University of Florence, Italy)

Talk title: An inexact dual logarithmic barrier method for solving sparse semidefinite programs

Abstract: A dual logarithmic barrier method for solving large, sparse semidefinite programs will be presented. The method is well-suited to problems with sparse objective and constraint matrices and relies on inexact Newton steps in dual space which are computed by the conjugate gradient method applied to the Schur complement of the reduced KKT system. The method may take advantage of low-rank representations of the constraint matrices o perform implicit matrix-vector products with the Schur complement matrix and to compute only specific parts of this matrix.
This allows the construction of the partial Cholesky factorization of the Schur complement matrix which serves as a good preconditioner for it and permits the method to be run in a matrix-free scheme. Convergence properties of the method and a polynomial complexity result will be given together with preliminary computational results of applying the method to maximum cut and matrix completion problems.
Joint work with Jacek Gondzio and Stefania Bellavia