Solving the discrete l_p-approximation problem by a method of centers

DOI10.1016/S0377-0427(00)00542-2MaRDI QIDQ5936070zbMATHFDO

Authors Jie Sun

Publication date 2 July 2001

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

interior point methodscomplexitylogarithmic barriercomputational resultsNewton-type methodsmethod of analytic centersconstrained convex programming problemdiscrete \(l_p\)-approximation problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Interior-point methods (90C51) Algorithms for approximation of functions (65D15)

Recommendations

• scientific article; zbMATH DE number 3886501
• The complexity of anl p method for discrete Tchebycheff approximation in exact arithmetic
• scientific article; zbMATH DE number 1086510
• Discrete l₁ Approximation by Rational Functions
• An Improved Algorithm for Discrete $l_1 $ Linear Approximation

Cites work

• scientific article; zbMATH DE number 4041641 (Why is no real title available?)
• scientific article; zbMATH DE number 4102820 (Why is no real title available?)
• scientific article; zbMATH DE number 45207 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 4197759 (Why is no real title available?)
• scientific article; zbMATH DE number 3246195 (Why is no real title available?)
• A Large-Step Analytic Center Method for a Class of Smooth Convex Programming Problems
• A cutting plane algorithm for convex programming that uses analytic centers
• A polynomial cutting surfaces algorithm for the convex feasibility problem defined by self-concordant inequalities
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A sufficient condition for self-concordance, with application to some classes of structured convex programming problems
• An Analytic Center Based Column Generation Algorithm for Convex Quadratic Feasibility Problems
• Complexity estimates of some cutting plane methods based on the analytic barrier
• On Vaidya's Volumetric Cutting Plane Method for Convex Programming

Cited in

(4)

• The center problem via averaging method
• Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
• An improvement and an extension of the Elzinga \& Hearn's algorithm to the 1-center problem in \(\mathbb{R}^ n\) with \(l_{2b}\)-norms
• The complexity of anl p method for discrete Tchebycheff approximation in exact arithmetic

This page was built for publication: Solving the discrete \(l_p\)-approximation problem by a method of centers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936070)