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) : McLaughlin, Matthew F


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a257112.pdf


Report Date : 08 May 1992


Pagination or Media Count : 99


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 EA/464 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 algorithm's 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 algorithm's performance on the Cray X-MP was analyzed and modeled using the timing results for random concave quadratic function problems. algorithms; parallel programming(computer science); stochastic analysis; mathematical optimization; mathematical programming; connection machines.


Descriptors :   *STOCHASTIC PROCESSES , *PARALLEL PROCESSING , TEST AND EVALUATION , ALGORITHMS , FUNCTIONS , COMPUTERS , REGIONS , PROBLEM SOLVING , FORTRAN , SUPERCOMPUTERS , MACHINES , POLYNOMIALS , MATHEMATICAL PROGRAMMING , PHASE , EFFICIENCY , COMPUTER PROGRAMMING , GLOBAL , OPTIMIZATION , COMPUTATIONS


Subject Categories : Statistics and Probability
      Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE