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.     

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.     

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.     

Decision support for the career field selection process at the US Air Force Academy

Each year, the US Air Force Academy graduates nearly 1000 young men and women. To support the decision of which cadets will be classified into which career fields, we describe a linear programming formulation with appealing computational properties that enable it as the core of a decision support tool. We explore methods for measuring and balancing cadets' class standing, Air Force career field requirements, and cadets' career field preferences in the context of this model. Our computational experiments demonstrate the improvement of this method over previous classification approaches, yielding more than 10% increase in the number of cadets assigned to their top career field choice and yielding nearly a 100% reduction in the number of cadets not receiving any of their career field choices. We also explore alternative methods for measuring cadets' career field preferences and demonstrate the positive effect of the new measurement scheme on the overall classification. Because of the short running time of this model, it will serve as a flexible, real-time component of the Academy's classification process.     

A remark on control of partially observed Markov chains

A new state variable is introduced for the problem of controlling a Markov chain under partial observations, which, under a suitably altered probability measure, has a simple evolution.     

Convex duality for finite-fuel problems in singular stochastic control

Upon introducing a finite-fuel constraint in a stochastic control system, the convex duality formulation can be set up to represent the original singular control problem as a minimization problem over the space of vector measures at each level of available fuel. This minimization problem is imbedded tightly into a related weak problem, which is actually a mathematical programming problem over a convex,w*-compact space of vector-valued Radon measures. Then, through the Fenchel duality principle, the dual for the finite-fuel control problems is to seek the maximum of smooth subsolutions to a dynamic programming variational inequality. The approach is basically in the spirit of Fleming and Vermes, and the results of this paper extend those of Vinter and Lewis in deterministic control problems to the finite-fuel problems in singular stochastic control. Meanwhile, we also obtain the characterization of the value function as a solution to the dynamic programming variational inequality in the sense of the Schwartz distribution.The author is much indebted to Professor Wendell H. Fleming for his constant support and many helpful discussions during the preparation of this paper.