New Preconditioners Applied to Linear Programming and the Compressive Sensing Problems
- PDF / 3,664,013 Bytes
- 20 Pages / 439.642 x 666.49 pts Page_size
- 34 Downloads / 169 Views
New Preconditioners Applied to Linear Programming and the Compressive Sensing Problems Paula A. Kikuchi1
· Aurelio R. L. Oliveira2
Received: 4 April 2020 / Accepted: 21 September 2020 / Published online: 16 November 2020 © Springer Nature Switzerland AG 2020
Abstract In this paper, we present new preconditioners based on the incomplete Cholesky factorization and on the splitting preconditioner. In the first approach, we consider the interior point methods that are very efficient for solving linear programming problems. The results of the numerical tests for this problem present satisfactory results in relation to the time and number of iterations. In the second approach, we apply a new preconditioner in compressive sensing (CS) problems, which is an efficient technique to acquire and reconstruct signal. An approach for solving this problem is the primal-dual Newton conjugate gradients. We present a new preconditioner, in the construction of which we exploited the fact that close to a solution we can split the variables into two groups and the matrices satisfy certain properties, as demonstrated in a method known from the literature (Fountoulakis 2015). Once the preconditioner exploiting these features has been computed, we apply an incomplete Cholesky factorization on it, and use the factor found as the true preconditioner. Therefore, the new preconditioner is the result of the combination of two preconditioners. The results obtained are satisfactory in relation to the time and the quality of the reconstructed image. Keywords Preconditioner · Linear programming · Signal processing · Compressive sensing
Paula A. Kikuchi
[email protected] Aurelio R. L. Oliveira [email protected] 1
State University of Mato Grosso do Sul, Mato Grosso do Sul, Brazil
2
University of Campinas, S˜ao Paulo, Brazil
36
Page 2 of 20
SN Operations Research Forum (2020) 1: 36
1 Introduction Linear programming problems can be found in a variety of contexts, such as fleet and route logistics planning, operational strategies in mining, steel, agriculture, and others. Among the approaches in the literature for solving linear programming problems, in the first section of the paper, we use the predictor-corrector interior point method. A linear optimization problem consists of minimizing or maximizing a linear objective function, subject to a finite set of linear constraints. Restrictions can be either equality or inequality. The standard form of a linear optimization problem is called a primal problem and is given by: minimize cT x (1) subject to Ax = b , x≥0 , x is a column vector belonging to where A is a constraint matrix belonging to , whose components are called primal variables, and b and c are column vectors , respectively, with c being the costs associated with the and belonging to elements of x. We know that the matrix of the linear system can be ill-conditioned, so the use of the preconditioners is mandatory when using iterative methods. We present a new preconditioner for linear programming problems, which we will
Data Loading...
