Linear programming with nonparametric penalty programs and iterated thresholding. (2nd January 2023)

• Record Type: Journal Article
• Authors: Kline, Jeffery; Fung, Glenn Martin
• Is Part Of: Optimization methods and software. Volume 38:Number 1(2023)
• Page Start: 107
• Page End: 127
• Publication Date: 2023-01-02
• Subjects: Linear programming -- duality -- quadratic programming -- penalty method -- fixed point -- nonexpansive map; 90C05 -- 90C20 -- 49M29; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2022.2117356
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : It is known [Mangasarian, A Newton method for linear programming, J. Optim. Theory Appl. 121 (2004), pp. 1–18] that every linear program can be solved exactly by minimizing an unconstrained quadratic penalty program. The penalty program is parameterized by a scalar t >0, and one is able to solve the original linear program in this manner when t is selected larger than a finite, but unknown t 0 > 0 . In this paper, we show that every linear program can be solved using the solution to a parameter-free penalty program. We also characterize the solutions to the quadratic penalty programs using fixed points of certain nonexpansive maps. This leads to an iterative thresholding algorithm that converges to a desired limit point. We show in numerical experiments that this iterative method can outperform a variety of standard quadratic program solvers. Finally, we show that for every t ∈ R, the solution one obtains by solving a parameterized penalty program is guaranteed to lie in the feasible set of the original linear program.