A globally and quadratically convergent affine scaling method for linear \(l_ 1\) problems

DOI10.1007/BF01580899zbMath0760.90069MaRDI QIDQ1199751

Yuying Li, Thomas F. Coleman

Publication date: 16 January 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

descent algorithmaffine scaling of coordinatesinner point methodspiecewise linear \(\ell_ 1\) approximation

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds, Multiple criteria linear regression, Discontinuous piecewise linear optimization, Searching for a best least absolute deviations solution of an overdetermined system of linear equations motivated by searching for a best least absolute deviations hyperplane on the basis of given data, On the application of iterative methods of nondifferentiable optimization to some problems of approximation theory, Pattern search method for discrete \(L_{1}\)-approximation, Least absolute value regression: recent contributions, Efficient implementation and benchmark of interior point methods for the polynomial \(L_{1}\) fitting problem., Loss and retention of accuracy in affine scaling methods, Applications of convex separable unconstrained nonsmooth optimization to numerical approximation with respect to l₁- and l_∞-norms, A Base-Point Descent Algorithm For Solving The Linear l 1 Problem, Approximation in normed linear spaces

Cites Work

• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• A new LAD curve-fitting algorithm: Slightly overdetermined equation systems in \(L_ 1\)
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• On the Method of Weighting for Equality-Constrained Least-Squares Problems
• The Null Space Problem I. Complexity
• The Null Space Problem II. Algorithms
• Quasi-Newton Methods, Motivation and Theory
• Minimization Techniques for Piecewise Differentiable Functions: The $l_1$ Solution to an Overdetermined Linear System
• An Improved Algorithm for Discrete $l_1 $ Linear Approximation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item