<  Back to the Polytechnique Montréal portal

A Regularized Interior-Point Method for Constrained Linear Least Squares

Mohsen Dehghani

Master's thesis (2013)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (406kB)
Show abstract
Hide abstract

Abstract

We propose an infeasible interior-point algorithm for constrained linear least-squares problems based on the primal-dual regularization of convex programs of Friedlander and Orban (2012). At each iteration, the sparse LDLT factorization of a symmetric quasi-definite matrix is computed. This coefficient matrix is shown to be uniformly bounded and nonsingular. We establish conditions under which a solution of the original problem is recovered. The regularization allows us to dispense with the assumption that the active gradients are linearly independent. Although the implementation described here is factorization based, it paves the way for a matrix-free implementation in which a regularized unconstrained linear least-squares problem is solved at each iteration. We report on computational experience and illustrate the potential advantages of our approach.

Résumé

Nous proposons une méthode de points intérieurs non réalisable pour le problème aux moindres carrés linéaire avec contraintes basée sur la régularisation primale-duale de problèmes quadratiques convexes de Friedlander et Orban (2012). À chaque itération, la méthode effectue une factorisation LDLT creuse d'une matrice symétrique et quasi définie. Cette matrice est uniformément bornée et non singulière. Nous établissons des conditions sous lesquelles la méthode produit une solution du problème original. La régularisation nous permet d'éliminer l'hypothèse que les gradients actifs sont linéairement indépendants. Bien que l'implémentation proposée ici repose sur une factorisation, elle ouvre la voie à une implémentation itérative dans laquelle on résout un problème aux moindres carrés régularisé sans contraintes de façon inexacte à chaque itération. Nous illustrons notre approche sur plusieurs applications qui mettent en évidence ses avantages.

Department: Department of Mathematics and Industrial Engineering
Program: Mathématiques appliquées
Academic/Research Directors: Dominique Orban
PolyPublie URL: https://publications.polymtl.ca/1121/
Institution: École Polytechnique de Montréal
Date Deposited: 22 Oct 2013 13:59
Last Modified: 05 Apr 2024 22:11
Cite in APA 7: Dehghani, M. (2013). A Regularized Interior-Point Method for Constrained Linear Least Squares [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1121/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item