Implementation of a projection and rescaling algorithm for second-order conic feasibility problems. (2nd January 2023)

• Record Type: Journal Article
• Authors: Peña, Javier; Soheili, Negar
• Is Part Of: Optimization methods and software. Volume 38:Number 1(2023)
• Page Start: 218
• Page End: 241
• Publication Date: 2023-01-02
• Subjects: Projection -- rescaling -- conditioning -- python; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2022.2119234
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : This paper documents a computational implementation of a projection and rescaling algorithm for solving one of the alternative feasibility problems 1 find x ∈ L ∩ Ω or find x ^ ∈ L ⊥ ∩ Ω, where L is a linear subspace in R n, L ⊥ is its orthogonal complement, and Ω ⊆ R n is the interior of a direct product of second order cones. The gist of the projection and rescaling algorithm is to enhance a low-cost first-order method (a basic procedure ) with an adaptive reconditioning transformation (a rescaling step ). We give a full description of a Python 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 Python code is publicly available. Furthermore, the simplicity of the algorithm makes a computational implementation in other environments completely straightforward.