On the multi-attribute stopping problem with general value functions

We examine a sequential selection problem in which a single option must be selected. Each option's value is a function of its attributes, whose precise values can be ascertained at a given cost. We prove the optimality of a threshold stopping rule for a general class of objective functions.     

Solving multiple-objective problems in the objective space

Projection and relaxation techniques are employed to decompose a multiobjective problem into a two-level structure. The basic manipulation consists in projecting the decision variables onto the space of the implicit tradeoffs, allowing the definition of a relaxed multiobjective master problem directly in the objective space. An additional subproblem tests the feasibility of the solution encountered by the relaxed problem. Some properties of the relaxed problem (linearity, small number of variables, etc.) render its solution efficient by a number of methods. Representatives of two different classes of multiobjective methods [the Geoffrion, Dyer, Feinberg (GDF) method and the fuzzy method of Baptistella and Ollero] are implemented and applied within this context to a water resources allocation problem. The results attest the computational viability of the overall procedure and its usefulness for the solution of multiobjective problems.This work was partially sponsored by grants from CNP_q and FAPESP, Brazil. The authors are indebted to the anonymous reviewers for their valuable comments.     

Sample-path optimization of convex stochastic performance functions

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs. Sponsored by the National Science Foundation under grant number CCR-9109345, by the Air Force Systems Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAL03-92-G-0408, and by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Sponsored by a Wisconsin/Hilldale Research Award, by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144, and the Air Force Systems Command, USAF, under grant number F49620-93-1-0068. Sponsored by the National Science Foundation under grant number DDM-9201813.     

Generating well-behaved utility functions for compromise programming

The purpose of this paper is to seek utility functions satisfying a weak condition which guarantees that the utility optimum always belongs to the compromise set. This set is a special subset of the attainable or feasible set, which is generated through the application of the well-known operational research approach called compromise programming. It is shown that there are large families of utility functions satisfying this condition, thus reinforcing the value of compromise programming as a good surrogate of the traditional utility optimum.Thanks are due to the reviewers for their helpful suggestions. The English editing by Ms. Christine Méndez is appreciated. The authors have been supported by the Comisión Interministerial de Ciencia y Tecnología (CICYT), Madrid, Spain.     

On the numerical solution of a class of Stackelberg problems

This study tries to develop two new approaches to the numerical solution of Stackelberg problems. In both of them the tools of nonsmooth analysis are extensively exploited; in particular we utilize some results concerning the differentiability of marginal functions and some stability results concerning the solutions of convex programs. The approaches are illustrated by simple examples and an optimum design problem with an elliptic variational inequality.Prepared while the author was visiting the Department of Mathematics, University of Bayreuth as a guest of the FSP Anwendungsbezogene Optimierung und Steuerung.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Stochastic algorithms with armijo stepsizes for minimization of functions

Stochastic algorithms for optimization problems, where function evaluations are done by Monte Carlo simulations, are presented. At each iteratex _i, they draw a predetermined numbern(i) of sample points from an underlying probability space; based on these sample points, they compute a feasible-descent direction, an Armijo stepsize, and the next iteratex _i+1. For an appropriate optimality function , corresponding to an optimality condition, it is shown that, ifn(i) , then (x _i) 0, whereJ is a set of integers whose upper density is zero. First, convergence is shown for a general algorithm prototype: then, a steepest-descent algorithm for unconstrained problems and a feasible-direction algorithm for problems with inequality constraints are developed. A numerical example is supplied.     

Second-order necessary optimality conditions for domain optimization problems of the Neumann type

In this paper, we treat a domain optimization problem in which the boundary-value problem is a Neumann problem. In the case where the domain is in a three-dimensional Euclidean space, the first-order and the second-order necessary conditions which the optimal domain must satisfy are derived under a constraint which is the generalization of the requisite of constant volume.Portions of this paper were presented at the 13th IFIP Conference on System Modelling and Optimization, Tokyo, Japan, 1987.     

An extended continuous Newton method

This paper describes a numerical realization of an extended continuous Newton method defined by Diener. It traces a connected set of locally one-dimensional trajectories which contains all critical points of a smooth functionf: ⁿ . The results show that the method is effectively applicable.The authors would like to thank L. C. W. Dixon for pointing out some errors in the original version of this paper and for several suggestions of improvements.     

On consistency of bounding operations in deterministic global optimization

This technical comment refers to the discussion of strong consistency of several bounding procedures in Lemma 2.1 and Proposition 2.1 of Ref. 1. A necessary clarification is given of the notion of convergence _q in Lemma 2.1, and a derivation of Proposition 2.1 is presented that includes a new and simple consistency proof of the classical bounding by convex envelopes used in many branch-and-bound procedures.