Computational performance of a projection and rescaling algorithm. (3rd September 2021)

• Record Type: Journal Article
• Authors: Peña, Javier; Soheili, Negar
• Is Part Of: Optimization methods and software. Volume 36:Number 5(2021)
• Page Start: 934
• Page End: 951
• Publication Date: 2021-09-03
• Subjects: Projection -- rescaling -- relative interior; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1615910
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: This paper documents a computational implementation of a projection and rescaling algorithm for finding most interior solutions to the pair of feasibility problems 1 f i n d x ∈ L ∩ R + n a n d f i n d x ˆ ∈ L ⊥ ∩ R + n, where L denotes a linear subspace in R n and L ⊥ denotes its orthogonal complement. The projection and rescaling algorithm is a recently developed method that combines a basic procedure involving only low-cost operations with a periodic rescaling step. We give a full description of a MATLAB implementation of this algorithm and present multiple sets of numerical experiments on synthetic problem instances with varied levels of conditioning. Our computational experiments provide promising evidence of the effectiveness of the projection and rescaling algorithm. Our MATLAB code is publicly available. Furthermore, the simplicity of the algorithm makes a computational implementation in other environments completely straightforward.