Accession Number:
ADA257112
Title:
Implementation of a Parallel Stochastic Solving Method for Linearly Constrained Concave Global Optimization Problems Using Parallel Computing
Descriptive Note:
Final rept. 1991-1992
Corporate Author:
NAVAL ACADEMY ANNAPOLIS MD
Personal Author(s):
Report Date:
1992-05-08
Pagination or Media Count:
99.0
Abstract:
A parallel stochastic algorithm is implemented for solving the linearly constrained concave global optimization problem. The algorithm uses a multistart technique which repeatedly employs two phases, the global phase and the local phase. The global phase creates a random search direction to find a vertex of the linearly constrained feasible region. The local phase begins from that vertex and solves for a local minimum. The algorithm repeats the global and local phases to find all the local minima. The algorithm was in FORTRAN on the Connection Machine CM-2 and Cray X-MP EA464 supercomputers. Computational results are presented for more than 200 test problems in three categories known problems from the literature, randomly generated concave quadratic problems, and randomly generated fixed-charge problems. The test problems from the literature were run on both the Cray X-MP and the CM-2 and resulted in an analysis of the stochastic algorithms efficiency on each machine. Computational results from randomly generated quadratic and fixed-charge functions resulted in an examination of how-particular characteristics affect the difficulty of the problem. Lastly, the ,stochastic algorithms performance on the Cray X-MP was analyzed and modeled using the timing results for random concave quadratic function problems. algorithms parallel programmingcomputer science stochastic analysis mathematical optimization mathematical programming connection machines.
Descriptors:
Subject Categories:
- Statistics and Probability
- Operations Research