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.

Subject Categories:

  • Statistics and Probability
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE