Global ellipsoidal approximations and homotopy methods for solving convex analytic programs

DOI10.1007/BF01445161zbMath0691.90071OpenAlexW2017068042MaRDI QIDQ583119

Gy. Sonnevend, Josef Stoer

Publication date: 1990

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01445161

zbMATH Keywords

algorithmic complexitylogarithmic barrier functionanalytic functionshomotopy methodsglobal ellipsoidal approximations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25)

Related Items

Optimal ellipsoidal approximations around the analytic center, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, An interior-point method for multifractional programs with convex constraints, A combined homotopy interior point method for general nonlinear programming problems, A combined homotopy interior point method for convex nonlinear programming, An interior-point method for semi-infinite programming problems, Applications of the notion of analytic center in approximation (estimation) problems, Path-following barrier and penalty methods for linearly constrained problems, On some efficient interior point methods for nonlinear convex programming, An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems, On the complexity of following the central path of linear programs by linear extrapolation. II, A barrier function method for minimax problems, An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming, A polynomial path following algorithm for convex programming, Interior-point methods for convex programming, Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals, Computation of the distance to semi-algebraic sets, On the convergence of the method of analytic centers when applied to convex quadratic programs, A continuation method for solving convex programming problemsviafischer reformulation, A globally convergent interior point algorithm for non-convex nonlinear programming, An interior-point method for fractional programs with convex constraints

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Introduction to sensitivity and stability analysis in nonlinear programming
• A multiplicative barrier function method for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Containing and shrinking ellipsoids in the path-following algorithm
• On the convergence of the method of analytic centers when applied to convex quadratic programs
• La méthode des centres dans un espace topologique
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• Restrictions of Normal Operators, Padé Approximation and Autoregressive Time Series