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.     

Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

Accelerations for global optimization covering methods using second derivatives

Two improvements for the algorithm of Breiman and Cutler are presented. Better envelopes can be built up using positive quadratic forms. Better utilization of first and second derivative information is attained by combining both global aspects of curvature and local aspects near the global optimum. The basis of the results is the geometric viewpoint developed by the first author and can be applied to a number of covering type methods. Improvements in convergence rates are demonstrated empirically on standard test functions.Partially supported by an University of Canterbury Erskine grant.     

Integral global optimization method for solution of nonlinear complementarity problems

The mapping in a nonlinear complementarity problem may be discontinuous. The integral global optimization algorithm is proposed to solve a nonlinear complementarity problem with a robust piecewise continuous mapping. Numerical examples are given to illustrate the effectiveness of the algorithm.     

Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves

Some powerful algorithms for multi-extremal non-convex-constrained optimization problems are based on reducing these multi-dimensional problems to those of one dimension by applying Peano-type space-filling curves mapping a unit interval on the real axis onto a multi-dimensional hypercube. Here is presented and substantiated a new scheme simultaneously employing several joint Peano-type scannings which conducts the property of nearness of points in many dimensions to a property of nearness of pre-images of these points in one dimension significantly better than in the case of a scheme with a single space-filling curve. Sufficient conditions of global convergence for the new scheme are investigated.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

A constrained min‐max algorithm for rival models of the same economic system

There are well established rival theories about the economy. These have, in turn, led to the development of rival models purporting to represent the economic system. The models are large systems of discrete-time nonlinear dynamic equations. Observed data of the real system does not, in general, provide sufficient information for statistical methods to invalidate all but one of the rival models. In such a circumstance, there is uncertainty about which model to use in the formulation of policy. Prudent policy design would suggest that a model-based policy should take into account all the rival models. This is achieved as a pooling of the models. The pooling that yields the policy which is robust to model choice is formulated as a constrained min-max problem. The minimization is over the decision variables and the maximization is over the rival models. Only equality constraints are considered.A successive quadratic programming algorithm is discussed for the solution of the min-max problem. The algorithm uses a stepsize strategy based on a differentiable penalty function for the constraints. Two alternative quadratic subproblems can be used. One is a quadratic min-max and the other a quadratic programming problem. The objective function of either subproblem includes a linear term which is dependent on the penalty function. The penalty parameter is determined at every iteration, using a strategy that ensures a descent property as well as the boundedness of the penalty term. The boundedness follows since the strategy is always satisfied for finite values of the parameter which needs to be increased a finite number of times.The global and local convergence of the algorithm is established. The conditions, involving projected Hessian approximations, are discussed under which the algorithm achieves unit stepsizes and subsequently Q-superlinear convergence.     

A rapidly convergent five-point algorithm for univariate minimization

This paper presents an algorithm for minimizing a function of one variable which uses function, but not derivative, values at five-points to generate each iterate. It employs quadratic and polyhedral approximations together with a safeguard. The basic method without the safeguard exhibits a type of better than linear convergence for certain piecewise twice continuously differentiable functions. The safeguard guarantees convergence to a stationary point for very general functions and preserves the better than linear convergence of the basic method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research sponsored by the Institut National de Recherche en Informatique et Automatique, Rocquencourt, France, and by the Air Force Office of Scientific Research, Air Force System Command, USAF, under Grant Number AFOSR-83-0210.Research sponsored, in part, by the Institut National de Recherche en Informatique et Automatique, Rocquencourt, France.     

On the control of queueing systems with failures and repairs

Several classes of problems can be modelled as queueing systems with failures where preventative maintenance has to be optimized: relevant examples are computer systems, databases and production lines. This paper studies a simple case of such a situation based on the M/M/1 queue where the state of the server can take two values (on, off); the transition on–off happens either when there is a failure or when one decides to maintain. The characterization and an approximation of an optimal policy are given. Extensions to more general models, including general Markov processes, are examined.     

On a special class of bicriterion path problems

In this paper we are concerned with a special class of bicriterion path problems. For the considered class of bicriterion problems at least one of the objectives is type MAXMIN. For the other one, besides an objective type MAXMIN also a MINSUM and a MINRATIO type objective are considered. Two algorithms are presented for the considered class of bicriterion path problems. The first one only determines the minimal complete set of nondominated paths and the second one determines the entire set of nondominated paths. Both algorithms can be used for any type of bicriterion path problems, since one of the objectives is type MAXMIN and an algorithm exists to determine the best path for the other objective. Computational statistics for the three types of considered bicriterion path problems are also presented.     

A recursive linear programming analysis of the future of the pulp and paper industry in the United States: Changes in supplies and demands,and the effects of recycling

The impacts of increased paper recycling on the U.S. pulp and paper sector are investigated, using the North American Pulp And Paper (NAPAP) model. This dynamic spatial equilibrium model forecasts the amount of pulp, paper and paperboard exchanged in a multi-region market, and the corresponding prices. The core of the model is a recursive price-endogenous linear programming system that simulates the behavior of a competitive industry. The model has been used to make forecasts of key variables describing the sector from 1986 to 2012, demand for paper would have the greatest impact on the amount of wood used. But the minimum recycled content policies envisaged currently would have no more effect than what will come about due to unregulated market forces.