Computational behavior of a feasible direction method for linear programming

DOI10.1016/0377-2217(89)90424-4MaRDI QIDQ1119474zbMATH OpenOpenAlexFDO

Authors Yahya Fathi, Katta G. Murty

Publication date 1989

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2027.42/27884

zbMATH Keywords

approximationMonte Carlo optimizationpure adaptive search

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30)

Review text

Monte Carlo optimization is concerned with using randomly generated points to approximate optimal solutions of mathematical programs. The simplest algorithm for Monte Carlo optimization is pure random search, which generates a sequence of independent, uniformly distributed points in the feasible region and returns the best point as the approximation. In this paper the authors give a theoretical analysis of pure adaptive search, which generates a sequence of points uniformly distributed in a sequence of nested areas of the feasible region. They show that for convex programming, the number of iterations required to achieve a given accuracy of the solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.

Recommendations

• Pure adaptive search in Monte Carlo optimization
• Application of the Monte-Carlo method to stochastic linear programming
• Pure adaptive search in global optimization
• Adaptive Search in Quasi-Monte-Carlo Optimization
• scientific article; zbMATH DE number 4216294

Cites work

• A feasible direction method for linear programming
• scientific article; zbMATH DE number 3904322 (Why is no real title available?)
• scientific article; zbMATH DE number 3961338 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 3206575 (Why is no real title available?)
• scientific article; zbMATH DE number 3284927 (Why is no real title available?)

Cited in

(8)

• Pure adaptive search in Monte Carlo optimization
• A computational study of redundancy in randomly generated polytopes
• Computer Codes for the Analysis of Infeasible Linear Programs
• A steepest feasible direction method for linear programming. Derivation and embedding in the simplex method
• A global pricing extension of the simplex method
• Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods
• Experiments with external pivoting
• The complex interior-boundary method for linear and nonlinear programming with linear constraints

This page was built for publication: Computational behavior of a feasible direction method for linear programming

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