A MARKOVIAN ALGORITHM FOR STRICTLY CONCAVE PROGRAMMING WITH LINEAR CONSTRAINTS
CALIFORNIA UNIV LOS ANGELES WESTERN MANAGEMENT SCIENCE INST
Pagination or Media Count:
Theil and van de Panne have shown how to replace the problem of maximizing a strictly concave quadratic function subject to linear inequality constraints by a finite sequence of sub-problems involving only linear equality constraints. In another paper, the author generalized this approach to i cover the case of a differentiable and strictly concave objective function, and ii permit almost complete flexibility in the choice of the initial sub- problem. The last feature seems essential for the approach to be of computational interest, for computational experience suggests that the number of sub-problems that must be solved and the amount of computer storage required to keep track of them have a tendency to grow approximately exponentially with the poorness of the choice of the initial sub-problem. In this paper a modification of the above approach is proposed which generates the sub-problems in Markovian fashion. This all but eliminates the storage problem. Although the resulting sequence of sub-problems is no longer necessarily finite, by means of the theory of Markov chains it is shown that eventual convergence to the optimum is assured with probability one and argued that the expected number of sub-problems that must be solved increases only approximately linearly with the poorness of the initial sub-problem. Computational evidence is given which supports this estimate and suggests the probable efficiency of the Markovian algorithm even for quite bad choices of the initial sub-problem.
- Operations Research