Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

New algorithms for constrained minimax optimization

A constrained minimax problem is converted to minimization of a sequence of unconstrained and continuously differentiable functions in a manner similar to Morrison's method for constrained optimization. One can thus apply any efficient gradient minimization technique to do the unconstrained minimization at each step of the sequence. Based on this approach, two algorithms are proposed, where the first one is simpler to program, and the second one is faster in general. To show the efficiency of the algorithms even for unconstrained problems, examples are taken to compare the two algorithms with recent methods in the literature. It is found that the second algorithm converges faster with respect to the other methods. Several constrained examples are also tried and the results are presented.     

On the convergence of a class of derivative-free minimization algorithms

A convergence analysis is presented for a general class of derivative-free algorithms for minimizing a functionf(x) for which the analytic form of the gradient and the Hessian is impractical to obtain. The class of algorithms accepts finite-difference approximation to the gradient, with stepsizes chosen in such a way that the length of the stepsize must meet two conditions involving the previous stepsize and the distance from the last estimate of the solution to the current estimate. The algorithms also maintain an approximation to the second-derivative matrix and require that the change inx made at each iteration be subject to a bound that is also revised automatically. The convergence theorems have the features that the starting pointx ¹ need not be close to the true solution andf(x) need not be convex. Furthermore, despite the fact that the second-derivative approximation may not converge to the true Hessian at the solution, the rate of convergence is still Q-superlinear. The theorry is also shown to be applicable to a modification of Powell's dog-leg algorithm.     

Optimal control of a dam under seasonal electricity prices

This study concerns the optimal control of a hydroelectric dam under seasonal electricity prices: high in winter, low in summer. The goal is to maximize the expected discounted infinite-horizon return through a policy that determines the amount of electricity to be produced in each time period, depending on the water level at the beginning of the period under consideration. The prices are assumed to be deterministic, and the flows into the reservoir are seasonal, stochastic, but independent from one period to another. The electric power generated is proportional to the amount of water flow through the turbines. There exist seepage and evaporation losses.It is shown that in the simplest price structure, the optimal policy is entirely determined by a single critical water level in each period of time, at which one starts producing. An example shows that the discretization of the reservoir levels can destroy this property. A method is proposed to avoid this difficulty. Another way of defining a policy is through goal-levels. This approach is shown to give higher returns than the standard approach.     

Revised simplex algorithm for finite Markov decision processes

We introduce a revised simplex algorithm for solving a typical type of dynamic programming equation arising from a class of finite Markov decision processes. The algorithm also applies to several types of optimal control problems with diffusion models after discretization. It is based on the regular simplex algorithm, the duality concept in linear programming, and certain special features of the dynamic programming equation itself. Convergence is established for the new algorithm. The algorithm has favorable potential applicability when the number of actions is very large or even infinite.     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.     

几类随机线性规划模型及其先验分布的估计

本文研究了随机线发性规划问题的几类基本模型结构．分析了随机线性规划问题对先验分布的依赖关系，给出了解除这种依赖关系的充要条件．最后用“原点距”方法与“信息熵”方法分别对先验分布作出了估计．     

A fuzzy approach to the transportation problem

The transportation problem with fuzzy supply values of the deliverers and with fuzzy demand values of the receivers is analysed. For the solution of the problem the technique of parametric programming is used. This makes it possible to obtain not only the maximizing solution (according to the Bellman-Zadeh criterion) but also other alternatives close to the optimal solution.     

On maximizing the average time at a goal

In a decision process (gambling or dynamic programming problem) with finite state space and arbitrary decision sets (gambles or actions), there is always available a Markov strategy which uniformly (nearly) maximizes the average time spent at a goal. If the decision sets are closed, there is even a stationary strategy with the same property.Examples are given to show that approximations by discounted or finite horizon payoffs are not useful for the general average reward problem.     

Some investigations in a new algorithm for nonlinear optimization based on conic models of the objective function

An appealing approach to the solution of nonlinear optimization problems based on conic models of the objective function has been recently introduced by Davidon. It leads to a broad class of algorithms which, in some sense, can be considered to generalize the existing quasi-Newton algorithms. One particular member of this class has been deeply examined by Sorensen, who has proved some interesting theoretical properties. A new interpretation of this algorithm is suggested in this paper from a more straightforward and somewhat familiar point of view. In addition, numerical experiments have been carried out to compare the Sorensen algorithm with a straightforward BFGS implementation of the classical quasi-Newton method with the final aim to assess the real merits and benefits of the new algorithm. Although some challenging test functions are used in computational experiments, the results are not particularly favorable to the new algorithm. As a matter of fact they do not exhibit any jump of quality, as it might be expected. Lastly, it is pointed out that a difficulty may affect the new method in situations in which it is necessary to exploit the special structure of large-scale problems.This work was supported by the National Research Council of Italy under Grant No. 80-01144.