Abstract:

The numerical solution of a possible inconsistent system of linear inequalities in the l₁ sense is considered. The non-differentiable l₁ norm minimization problem is approximated by a piecewise quadratic Huber smooth function. A continuation algorithm is designed to find an l₁ solution of the inequality system. In the case where the linear inequality system is consistent, a solution is obtained by solving any smoothed problem. Otherwise, the algorithm is shown to terminate in a finite number of iterations. We also consider an alternative smoothing scheme which shares similar properties with the first one, but results in an improved computational performance of the continuation algorithm on inconsistent systems. Numerical experiments are conducted to test the efficiency of the algorithm.

Document Type: Original article

Affiliations: 1: Department of Industrial Engineering, Bilkent University, 06533 Ankara, Turkey 2: Department of Management and Systems, Washington State University, Pullman, WA 99164-4736, USA