Computational behavior of a feasible direction method for linear programming
type: Item
instance of: scholarly article
title: Computational behavior of a feasible direction method for linear programming
zbMATH Open document ID: 0671.90069
DOI: 10.1016/0377-2217(89)90424-4
author: Yahya Fathi
author: Katta G. Murty
published in: European Journal of Operational Research
publication date: 1989-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/2027.42/27884
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.
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C25
zbMATH DE Number: 4099052
zbMATH Keywords: approximation
zbMATH Keywords: Monte Carlo optimization
zbMATH Keywords: pure adaptive search
MaRDI profile type: Publication
OpenAlex ID: W2152532279
cites work: Q4188659
cites work: Q3682229
cites work: Q3730340
cites work: Q5332463
cites work: A feasible direction method for linear programming
cites work: Q5564917
description: scientific article; zbMATH DE number 4099052