Current state of the art of algorithms and computer software for geometric programming

This paper attempts to consolidate over 15 years of attempts at designing algorithms for geometric programming (GP) and its extensions. The pitfalls encountered when solving GP problems and some proposed remedies are discussed in detail. A comprehensive summary of published software for the solution of GP problems is included. Also included is a numerical comparison of some of the more promising recently developed computer codes for geometric programming on a specially chosen set of GP test problems. The relative performance of these codes is measured in terms of their robustness as well as speed of computation. The performance of some general nonlinear programming (NLP) codes on the same set of test problems is also given and compared with the results for the GP codes. The paper concludes with some suggestions for future research.An earlier version of this paper was presented at the ORSA/TIMS Conference, Chicago, 1975.This work was supported in part by the National Research Council of Canada, Grant No. A-3552, Canada Council Grant No. S74-0418, and a research grant from the School of Organization and Management, Yale University. The author wishes to thank D. Himmelblau, T. Jefferson, M. Rijckaert, X. M. Martens, A. Templeman, J. J. Dinkel, G. Kochenberger, M. Ratner, L. Lasdon, and A. Jain for their cooperation in making the comparative study possible.     

Choice of optimal search strategy

The problem of searching the extremum of a scalar function of a vector argument is considered. It is assumed that a finite set of algorithms, each of which is capable of finding the extremum, is specified. Every algorithm is characterized by a given number of operators each of which is identified with the state of the system. Each algorithm is defined by a transition probability matrix over the possible states (operators) and a corresponding matrix of the respective changes in the value of the function toward the extremal point.A procedure is given for selecting an optimal sequence of algorithms which maximizes the total expected change in the value of the function toward the optimum.     

New least-square algorithms

New algorithms are presented for approximating the minimum of the sum of squares ofM real and differentiable functions over anN-dimensional space. These algorithms update estimates for the location of a minimum after each one of the functions and its first derivatives are evaluated, in contrast with other least-square algorithms which evaluate allM functions and their derivatives at one point before using any of this information to make an update. These new algorithms give estimates which fluctuate about a minimum rather than converging to it. For many least-square problems, they give an adequate approximation for the solution more quickly than do other algorithms.It is a pleasure to thank J. Chesick of Haverford College for suggesting and implementing the application of this algorithm to x-ray crystallography.     

A minimization method for the sum of a convex function and a continuously differentiable function

This paper presents a method for finding the minimum for a class of nonconvex and nondifferentiable functions consisting of the sum of a convex function and a continuously differentiable function. The algorithm is a descent method which generates successive search directions by solving successive convex subproblems. The algorithm is shown to converge to a critical point.The authors wish to express their appreciation to the referees for their careful review and helpful comments.     

DETERMINATION OF EFFICIENT RANGE OF TARGET LEVELS IN MULTIPLE OBJECTIVE PLANNING

This paper describes a nonlinear programming model combined with a binary search technique that systematically searches for the minimum value of a given objective within the nondominated solution set. The procedure provides a way of determining the range of efficient target levels for any multiobjective planning problem using information contained in the pay-off table. The method is illustrated using a numerical example.     

Sufficient conditions for duality in homogeneous programming

A symmetric duality theory for programming problems with homogeneous objective functions was published in 1961 by Eisenberg and has been used by a number of authors since in establishing duality theorems for specific problems. In this paper, we study a generalization of Eisenberg's problem from the viewpoint of Rockafellar's very general perturbation theory of duality. The extension of Eisenberg's sufficient conditions appears as a special case of a much more general criterion for the existence of optimal vectors and lack of a duality gap. We give examples where Eisenberg's sufficient condition is not satisfied, yet optimal vectors exist, and primal and dual problems have the same value.     

New results on a class of exact augmented Lagrangians

In this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem.The author wishes to thank Dr. L. Grippo for having suggested the topic of this paper and for helpful discussions.     

Design of a small conversational system

The main features of a time-sharing system for a minicomputer are outlined. An interpretive language LAX plays a central role in the system both as a base for the languages seen by the user and for implementing part of the system. The system is open-ended, new subsystems can be plugged in easily, and a variety of error and interrupt behavior can be obtained.     

An optimal choice problem for a set of checking procedures

An item having a known initial failure probability is to be controlled by some out of a finite set of possible checks. Every check costs a certain amount of money, and budget constraints must be met. A check is characterized by the probabilities of three events: (i) letting a workable item pass, (ii) overlooking a failure if one is present, (iii) introducing a failure into a workable item. We show how any subset of checks to be employed is ordered optimally, and how the optimal subsequence of checks depends on the initial failure probability and oil the budget constraint.     

A dynamic programming algorithm for dynamic lot size models with piecewise linear costs

We propose a new algorithm for dynamic lot size models (LSM) in which production and inventory cost functions are only assumed to be piecewise linear. In particular, there are no assumptions of convexity, concavity or monotonicity. Arbitrary capacities on both production and inventory may occur, and backlogging is allowed. Thus the algorithm addresses most variants of the LSM appearing in the literature. Computational experience shows it to be very effective on NP-hard versions of the problem. For example, 48 period capacitated problems with production costs defined by eight linear segments are solvable in less than 2.5 minutes of Vax 8600 cpu time.