Characterization of optimality in convex programming without a constraint qualification

Necessary and sufficient conditions of optimality are given for convex programming problems with no constraint qualification. The optimality conditions are stated in terms of consistency or inconsistency of a family of systems of linear inequalities and cone relations.This research was supported by Project No. NR-047-021, ONR Contract No. N00014-67-A-0126-0009 with the Center for Cybernetics Studies, The University of Texas; by NSF Grant No. ENG-76-10260 at Northwestern University; and by the National Research Council of Canada.     

A second-order method for unconstrained optimization

This paper presents a quadratically converging algorithm for unconstrained minimization. All the accumulation points that it constructs satisfy second-order necessary conditions of optimality. Thus, it avoids second-order saddle andinflection points, an essential feature for a method to be used in minimizing the modified Lagrangians in multiplier methods.The work of the first author was supported by NSF RANN AEN 73-07732-A02 and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by NSF Grant No. GK-37672 and the ARO Contract No. DAHCO4-730C-0025.     

A second-order method for the general nonlinear programming problem

This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025.     

Sample-path analysis of processes with imbedded point processes

The purpose of this paper is to review, unify, and extend previous work on sample-path analysis of queues. Our main interest is in the asymptotic behavior of a discrete-state, continuous-time process with an imbedded point process. We present a sample-path analogue of the renewal-reward theorem, which we callY=X. We then applyY=X to derive several relations involving the transition rates and the asymptotic (long-run) state frequencies at an arbitrary point in time and at the points of the imbedded point process. Included are sample-path versions of the rate-conservation principle, the global-balance conditions, and the insensitivity of the asymptotic frequency distribution to the distribution of processing time in a LCFS-PR service facility. We also provide a natural sample-path characterization of the PASTA property.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University, and by the National Science Foundation, Grant No. ECS-8719825, at the University of North Carolina, Chapel Hill.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University.     

Current inverse iteration software can fail

Inverse iteration is widley used to compute the eigenvectors of a matrix once accurate eigenvalues are known. We discuss various issues involved in any implementation of inverse iteration for real, symmetric matrices. Current implementations resort to reorthogonalization when eigenvalues agree to more than three digits relative to the norm. Such reorthogonalization can have unexpected consequences. Indeed, as we show in this paper, the implementations in EISPACK and LAPACK may fail. We illustrate with both theoretical and empirical failures. This research was supported, while the author was at the University of California, Berkeley, in part by DARPA Contract No. DAAL03-91-C-0047 through a subcontract with the University of Tennessee, DOE Contract No. DOE-W-31-109-Eng-38 through a subcontract with Argonne National Laboratory, by DOE Grant No. DE-FG03-94ER25219, NSF Grant Nos. ASC-9313958 and CDA-9401156, and DOE Contract DE-AC06-76RLO 1830 through the Environmental Molecular Sciences construction project at Pacific Northwest National Laboraotry (PNNL).     

Analysis of decomposition algorithms via nonlinear splitting functions

This paper provides a structural analysis of decomposition algorithms using a generalization of linear splitting methods. This technique is used to identify explicitly the essential similarities and differences between several classical algorithms. Similar concepts can be used to analyze a large class of multilevel hierarchical structures.This research was supported in part by ONR Contract No. N00014-76-C-0346, in part by the US Department of Energy, Division of Electric Energy Systems, Contract No. ERDA-E(49-18)-2087 at the Massachusetts Institute of Technology, and in part by the Joint Services Electronics Program, Contract No. DAAG-29-78-C-0016.The authors would like to thank Dr. P. Varaiya, University of California at Berkeley, and Dr. D. Bertsekas for their comments and suggestions.     

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.     

A dynamic solution concept for abstract games

Several solution concepts have been defined for abstract games. Some of these are the core, due to Gillies and Shapley, the Von Neumann-Morgenstern stable sets, and the subsolutions due to Roth. These solution concepts are rather static in nature. In this paper, we propose a new solution concept for abstract games, called the dynamic solution, that reflects the dynamic aspects of negotiation among the players. Some properties of the dynamic solution are studied. Also, the dynamic solution of abstract games arising fromn-person cooperative games in characteristic function form is investigated.This research was supported by the Office of Naval Research under Contract No. N00014-75-C-0678, by the National Science Foundation under Grants Nos. MPS-75-02024 and MCS-77-03984 at Cornell University, by the United States Army under Contract No. DAAG-29-75-C-0024, and by the National Science Foundation under Grant No. MCS-75-17385-A01 at the University of Wisconsin. The author is grateful to Professor W. F. Lucas under whose guidance the research was conducted.     

Optimal rigid body motions,part 2: Minimum time solutions

The time-optimal control of rigid-body angular rates is investigated in the absence of direct control over one of the angular velocity components. The existence of singular subarcs in the time-optimal trajectories is explored. A numerical survey of the optimality conditions reveals that, over a large range of boundary conditions, there are in general several distinct extremal solutions. A classification of extremal solutions is presented, and domains of existence of the extremal subfamilies are established in a reduced parameter space. A locus of Darboux points is obtained, and global optimality of the extremal solutions is observed in relation to the Darboux points. The continuous dependence of the optimal trajectories with respect to variations in control constraints is noted, and a procedure to obtain the time-optimal bang-bang solutions is presented.This work was supported in part by DARPA under Contract No. ACMP-F49620-87-C-0016, by SDIO/IST under Contract No. F49620-87-C0088, and by Air Force Grant AFOSR-89-0001.     

Confidence structures in decision making

Decision making is defined in terms of four elements: the set of decisions, the set of outcomes for each decision, a set-valued criterion function, and the decision maker's value judgment for each outcome. Various confidence structures are defined, which give the decision maker's confidence of a given decision leading to a particular outcome. The relation of certain confidence structures to Bayesian decision making and to membership functions in fuzzy set theory is established. A number of schemes are discussed for arriving atbest decisions, and some new types of domination structures are introduced.This research was partly supported by Project No. NR-047-021, ONR Contract No. N-00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas, Austin, Texas, and by ONR Contract No. N-00014-69-A-0200-1012 with the University of California, Berkeley, California.     

On generalized means and generalized convex functions

Properties of generalized convex functions, defined in terms of the generalized means introduced by Hardy, Littlewood, and Polya, are easily obtained by showing that generalized means and generalized convex functions are in fact ordinary arithmetic means and ordinary convex functions, respectively, defined on linear spaces with suitably chosen operations of addition and multiplication. The results are applied to some problems in statistical decision theory.This research was supported by Project No. NR-047-021, Contract No. N00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas, Austin, Texas, and by NSF Grant No. ENG-76-10260 at Northwestern University, Evanston, Illinois.     

On functions whose stationary points are global minima

In this paper, a characterization of functions whose stationary points are global minima is studied. By considering the level sets of a real function as a point-to-set mapping, and by examining its semicontinuity properties, we obtain the result that a real function, defined on a subset ofR ⁿ and satisfying some mild regularity conditions, belongs to the above family iff the point-to-set mapping of its level sets is strictly lower semicontinuous. Mathematical programming applications are also mentioned.The authors are thankful to an anonymous referee of an earlier version of this paper for his valuable comments. This research was partially supported by the Office of Naval Research, Contract No. N-00014-75-C-0267, by the National Science Foundation, Grant No. MPS-71-03341-A03, and by the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18. An earlier version of this paper appeared as CORE Discussion Paper No. 7502. Part of this research was carried out while the first author was at CORE, Louvain, Belgium.     

Optimal design of pitched laminated wood beams

The optimal design of a pitched laminated wood beam is considered. An engineering formulation is given in which the volume of the beam is minimized. The problem is then reformulated and solved as a generalized geometric (signomial) program. Sample designs are presented.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865; by the US Energy Research and Development Administration Contract No. E(04-3)-326 PA-18; and by the National Science Foundation, Grant No. DCR75-04544 at Stanford University. This work was carried out during the first author's stay at the Management Science Division of the University of British Columbia and the Systems Optimization Laboratory of Stanford University. The authors are indebted to Mr. S. Liu and Mrs. M. Ratner for their assistance in performing the computations.     

Matrix factorizations in optimization of nonlinear functions subject to linear constraints

Several ways of implementing methods for solving nonlinear optimization problems involving linear inequality and equality constraints using numerically stable matrix factorizations are described. The methods considered all follow an active constraint set approach and include quadratic programming, variable metric, and modified Newton methods.Part of this work was performed while the author was a visitor at Stanford University. This research was supported in part by the National Science Foundation under Grant GJ 36472 and in part by the Atomic Energy Commission Contract No. AT(04-3)-326PA30.     

Optimum extrapolation and interpolation designs,I

Summary For regression problems where observations may be taken at points in a set X which does not coincide with the set Y on which the regression function is of interest, we consider the problem of finding a design (allocation of observations) which minimizes the maximum over Y of the variance function (of estimated regression). Specific examples are calculated for one-dimensional polynomial regression when Y is much smaller than or much larger than X. A related problem of optimum estimation of two regression coefficients is studied. This paper contains proofs of results first announced at the 1962 Minneapolis Meeting of the Institute of Mathematical Statistics. No prior knowledge of design theory is needed to read this paper. John Simon Guggenheim Memorial Foundation Fellow. Research supported in part by the office of Naval Research under Contract No. Nonr 266(04) (NR 047-005). The research of this author was supported in part by the U.S. Air Force under Contract No. AF 18(600)-685.     

The inverse gravimetry problem: An application to the northern San Francisco craton granite

From the knowledge of the anomalies of the gravitational field, we reconstruct the mass density distribution in a large region of the state of Bahia (Brazil). This inverse gravimetry problem has been translated into a linear programming problem and solved using the simplex method. Both two-dimensional and three-dimensional models have been considered.This research was supported by the European Research Office of the US Army under Contract No. DAJA 45-86-C-0028 with the University of Rome-La Sapienza and by the Ministero Pubblica Istruzione under Contract (60%)-1987 with the University of Camerino.     

Spline approximations for nonlinear hereditary control systems

A spline-based approximation scheme is discussed for optimal control problems governed by nonlinear nonautonomous delay differential equations. The approximating framework reduces the original control problem to a sequence of optimization problems governed by ordinary differential equations. Convergence proofs, which appeal directly to dissipative-type estimates for the underlying nonlinear operator, are given and numerical findings are summarized.This work was supported in part by the Air Force Office of Scientific Research under Contract No. AFOSR-76-3092D, in part by the National Science Foundation under Grants Nos. NSF-MCS-79-05774-05 and NSF-MCS-82-00883, and in part by the US Army Research Office under Contract No. ARO-DAAG29-79-C-0161. The results reported here are a portion of the author's doctoral dissertation written under the supervision of Professor H. T. Banks, Brown University. The author is indebted to Professor Banks for his many valuable comments and suggestions during the course of this work.Part of this research was completed while the author was a visitor at the Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, Virginia.     

Some singular cauchy problems

Summary Existence and uniqueness theorems for some generalizedEuler-Poisson-Darboux equations are proved and growth and convexity properties of the solutions are studied for multiply subharmonic initial values. This research was supported in part by the United States Air Force through the Air Force Office of Scientific Research of the Air Research and Development Command under Contract No. AF 49 (638)-228, at the University of Maryland, and in part by the National Science Foundation, under a fellowship grant.     

Local convergence of the diagonalized method of multipliers

In this study, we consider a modification of the method of multipliers of Hestenes and Powell in which the iteration is diagonalized, that is, only a fixed finite number of iterations of Newton's method are taken in the primal minimization stage. Conditions are obtained for quadratic convergence of the standard method, and it is shown that a diagonalization where two Newton steps are taken preserves the quadratic convergence for all multipler update formulas satisfying these conditions.This work constitutes part of the author's doctoral dissertation in the Department of Mathematical Sciences, Rice University, under the direction of Professor R. A. Tapia and was supported in part by ERDA Contract No. E-(40-1)-5046.The author would like to thank Professor Richard Tapia for his comments, suggestions, and discussions on this material.     

Completion of linear differential games

The concept of completion of differential games was introduced by Pontryagin in Ref. 1. Here, necessary and sufficient conditions for completion of linear differential games are presented.This work was supported by the Air Force Office of Scientific Research, Contract No. AFOSR 68-1547.