Scalable adaptive cubic regularization methods

Adaptive cubic regularization (ARC) methods for unconstrained optimization compute steps from linear systems involving a shifted Hessian in the spirit of the Levenberg-Marquardt and trust-region methods. The standard approach consists in performing an iterative search for the shift akin to solving the secular equation in trust-region methods. Such search requires computing the Cholesky factorization of … Read more

A Proximal Quasi-Newton Trust-Region Method for Nonsmooth Regularized Optimization

We develop a trust-region method for minimizing the sum of a smooth term f and a nonsmooth term h, both of which can be nonconvex. Each iteration of our method minimizes apossibly nonconvex model of f+h in a trust region. The model coincides with f+h in value and subdifferential at the center. We establish global … Read more

Constraint-Preconditioned Krylov Solvers for Regularized Saddle-Point Systems

We consider the iterative solution of regularized saddle-point systems. When the leading block is symmetric and positive semi-definite on an appropriate subspace, Dollar, Gould, Schilders, and Wathen (SIAM J. Matrix Anal. Appl., 28(1), 2006) describe how to apply the conjugate gradient (CG) method coupled with a constraint preconditioner, a choice that has proved to be … Read more

BiLQ: An Iterative Method for Nonsymmetric Linear Systems with a Quasi-Minimum Error Property

We introduce an iterative method named BiLQ for solving general square linear systems Ax = b based on the Lanczos biorthogonalization process defined by least-norm subproblems, and is a natural companion to BiCG and QMR. Whereas the BiCG (Fletcher, 1976), CGS (Sonneveld, 1989) and BiCGSTAB (van der Vorst, 1992) iterates may not exist when the … Read more

CUTEst: a Constrained and Unconstrained Testing Environment with safe threads

We describe the most recent evolution of our constrained and unconstrained testing environment and its accompanying SIF decoder. Code-named SIFDecode and CUTEst, these updated versions feature dynamic memory allocation, a modern thread-safe Fortran modular design, a new Matlab interface and a revised installation procedure integrated with GALAHAD. Citation Technical Report Rutherford Appleton Laboratory Chilton, Oxfordshire, … Read more

A Primal-Dual Regularized Interior-Point Method for Semidefinite Programming

Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of \cite{friedlander-orban-2012} to SDP and show that it is possible to recover an optimal … Read more

Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods

Interior-point methods feature prominently among numerical methods for inequality-constrained optimization problems, and involve the need to solve a sequence of linear systems that typically become increasingly ill-conditioned with the iterations. To solve these systems, whose original form has a nonsymmetric 3×3 block structure, it is common practice to perform block Gaussian elimination and either solve … Read more

Customizing the Solution Process of COIN-OR’s Linear Solvers with Python

Implementations of the Simplex method differ only in very specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ only in the type of cuts and the exploration of the search tree. Implementing instances of those frameworks would therefore be more efficient if linear and mixed-integer programming solvers let users … Read more

Trajectory-following methods for large-scale degenerate convex quadratic programming

We consider a class of infeasible, path-following methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An … Read more

An L1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

We propose an interior-point algorithm based on an elastic formulation of the L1-penalty merit function for mathematical programs with complementarity constraints. The method generalizes that of Gould, Orban and Toint (2003) and naturally converges to a strongly stationary point or delivers a certificate of degeneracy without recourse to second-order intermediate solutions. Remarkably, the method allows … Read more