Generalized complementarity problem

A general complementarity problem with respect to a convex cone and its polar in a locally convex, vector-topological space is defined. It is observed that, in this general setting, the problem is equivalent to a variational inequality over a convex cone. An existence theorem is established for this general case, from which several of the known results for the finite-dimensional cases follow under weaker assumptions than have been required previously. In particular, it is shown that, if the given map under consideration is strongly copositive with respect to the underlying convex cone, then the complementarity problem has a solution.This research was partially supported by the Office of Naval Research, Contract No. N-00014-67-A0112-0011, by the Atomic Energy Commission, Contract No. AT[04-3]-326-PA-18, and by the National Science Foundation, Grant No. GP-9329.     

Optimal switching in coplanar orbit transfer

The set of all controls that satisfy the Weierstrass necessary condition for optimality in the problem of time-open, coplanar orbit transfer via impulses is presented, along with the switching relations that must be satisfied at a corner in an optimal trajectory. This includes detailed data for eccentricities near unity. This study takes advantage of recently discovered closed-form solutions for the switching surfaces of this problem.Portions of this work were supported by NASA Contract No. NASr-54(06) and by NASA Grant No. NGR-06-003-033.     

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.     

On the number of solutions to a class of complementarity problems

In this paper we consider the problem of establishing the number of solutions to the complementarity problem. For the case when the Jacobian of the mapping has all principal minors negative, and satisfies a condition at infinity, we prove that the problem has either 0, 1, 2 or 3 solutions. We also show that when the Jacobian has all principal minors positive, and satisfies a condition at infinity, the problem has a unique solution.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS77-03472 and Grant No. MCS78-09525. This work appeared as an MRC Technical Report No. 1964, University of Wisconsin, Madison, WI, June 1979.     

Distributed computing viewed as a team problem with constraints

The optimal distribution of the workload in a system of interconnected computer units is considered. Formulated as a team decision problem with a singular cost criterion and with equality and inequality constraints, it is shown that the problem admits always a unique piecewise linear strategy which is globally optimal. Some interesting particular cases are studied.The research reported in this paper was made possible through support from the Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-C-0648 and Contract No. N00014-77-C-0531 and by the National Science Foundation, Grant No. ENG-76-11824.     

Exact minimum-time control of a distributed system using a traveling wave formulation

In this paper, the minimum-time control problem for rest-to-rest translation of a one-dimensional second-order distributed parameter system by means of two bounded control inputs at the ends is solved. A traveling wave formulation allows the problem to be solved exactly, i.e., without modal truncation. It is found that the minimum-time control is not bang-bang, as it is for systems with a finite number of degrees of freedom. Rather, it is bang-off-bang, where a period of control inactivity in the middle of the control time interval is required for synchronization with waves propagated through the system.This research was supported in part by AFOSR Grant No. AFOSR-90-0297. The helpful suggestions of the referees are gratefully acknowledged.     

The problem of continuation with least coanalytic deviation

The problem of continuing a function from the unit circle to the unit disk so that the continuation has the least deviation from the Sobolev subspace of analytic functions is considered. A mathematical model of this problem is constructed. It is proved that the problem is well-posed.Translated fromMatematicheskie Zametki, Vol. 64, No. 1, pp. 45–57, July, 1998.This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00621.     

A solution for noncooperative games

In this paper, we study solutions of strict noncooperative games that are played just once. The players are not allowed to communicate with each other. The main ingredient of our theory is the concept of rationalizing a set of strategies for each player of a game. We state an axiom based on this concept that every solution of a noncooperative game is required to satisfy. Strong Nash solvability is shown to be a sufficient condition for the rationalizing set to exist, but it is not necessary. Also, Nash solvability is neither necessary nor sufficient for the existence of the rationalizing set of a game. For a game with no solution (in our sense), a player is assumed to recourse to a standard of behavior. Some standards of behavior are examined and discussed.This work was sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and by the National Science Foundation under Grant No. MCS-75-17385-A01. The author is grateful to J. C. Harsanyi for his comments and to S. M. Robinson for suggesting the problem.     

Second-order and related extremality conditions in nonlinear programming

This paper is concerned with the problem of characterizing a local minimum of a mathematical programming problem with equality and inequality constraints. The main object is to derive second-order conditions, involving the Hessians of the functions, or related results where some other curvature information is used. The necessary conditions are of the Fritz John type and do not require a constraint qualification. Both the necessary conditions and the sufficient conditions are given in equivalent pairs of primal and dual formulations.This research was partly supported by Project No. NR-947-021, ONR Contract No. N00014-75-0569, with the Center for Cybernetic Studies, and by the National Science Foundation, Grant No. NSF-ENG-76-10260.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

Transcendental geometric programs

This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18.     

Nonzero lagrange multipliers

Solutions of constrained minimization problems give rise to Lagrange multiplier rules. In this paper, we show that a simple condition on a specific constraint implies that the associated coefficient in the Lagrange multiplier rule is not zero. We conclude with an example which shows that such knowledge increases the information available about the solution of a problem of minimal curvature.This work supported in part by NSF Grant No. MCS-75-05581-A01.     

Differential games,dynamic optimization,and generalized control theory

In this paper, we examine the problem of control in a generalized framework in which there are more than one criterion, more than one intelligent controller, each of which has access to different information. It is argued that optimal control, differential games, dynamic team theory, etc., can all be viewed as special cases of this generalized control theory. Useful concepts and potential difficulties are discussed.The work reported in this paper is a result of research support extended over a period of years by Joint Services Electronic Contract No. N00014-67-A-0298-0006, NASA Grant No. NGR-22-007-068, and AFOSR Grant No. 69-1768 administered through Harvard University. The author has benefited from discussions with numerous colleagues, in particular, K. C. Chu, A. Starr, W. Willman, H. Witsenhausen, and S. Mitter.     

Pointwise quasi-Newton method for unconstrained optimal control problems,II

In this paper, the necessary optimality conditions for an unconstrained optimal control problem are used to derive a quasi-Newton method where the update involves only second-order derivative terms. A pointwise update which was presented in a previous paper by the authors is changed to allow for more general second-order sufficiency conditions in the control problem. In particular, pointwise versions of the Broyden, PSB, and SR1 update are considered. A convergence rate theorem is given for the Broyden and PSB versions.This research was supported by NSF Grant No. DMS-89-00410, by NSF Grant No. INT-88-00560, by AFOSR Grant No. AFOSR-89-0044, and by the Deutsche Forschungsgemeinschaft.     

On the pricing of American options

The problem of valuation for contingent claims that can be exercised at any time before or at maturity, such as American options, is discussed in the manner of Bensoussan [1]. We offer an approach which both simplifies and extends the results of existing theory on this topic.Research supported in part by the National Science Foundation under Grant No. NSF-DMS-84-16736 and by the Air Force Office of Scientific Research under Grant No. F49620-85-C-0144.     

Application of Jensen's inequality to adaptive suboptimal design

In this paper, it is shown that, if the expected cost-to-go functions generated by a suboptimal design for a partially observed, discrete-time, Markov decision problem with a specific state measurement quality are concave, then the suboptimal design has a desirable adaptivity characteristic relative to that state measurement quality. Optimal strategies are shown to possess this adaptivity characteristic, as does a suboptimal design presented in an example.This research was supported by NSF Grant No. ENG-76-15774 and NSF Grant No. ENG-78-06733.     

A conjugate-point condition for a class of differential games

A conjugate-point necessary condition is derived for a class of differential games. This is done by considering the conjugate-point condition for the minimum problem and maximum problem associated with a differential game. Two definitions of a conjugate point and two conjugate-point necessary conditions result. These two definitions and necessary conditions are shown to be equivalent and are combined into one definition and one necessary condition.This research was primarily supported by the National Science Foundation under Traineeship No. 1721-80-282 and Grant No. GK-3341. Additional support was obtained from NASA Institutional Grant No. NGR-15-005-021.     

On sending one bit of information over an AGWN channel with noiseless feedback

We study the problem described by the title under the real-time constraint that no block coding is allowed. Three separate schemes, including the well known center-of-gravity scheme, and their performance are compared.The research reported in this paper was made possible through support from the Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-C-0648 and Contract No. N00014-77-C-0531, and by the National Science Foundation, Grant No. ENG-76-11824.The formulation of this problem took place when the first author was SRC Senior Fellow at Imperial College during the summer of 1977. He appreciates discussions with M. Davis and D. Mayne of Imperial College.     

A dual differentiable exact penalty function

A new penalty function is associated with an inequality constrained nonlinear programming problem via its dual. This penalty function is globally differentiable if the functions defining the original problem are twice globally differentiable. In addition, the penalty parameter remains finite. This approach reduces the original problem to a simple problem of maximizing a globally differentiable function on the product space of a Euclidean space and the nonnegative orthant of another Euclidean space. Many efficient algorithms exist for solving this problem. For the case of quadratic programming, the penalty function problem can be solved effectively by successive overrelaxation (SOR) methods which can handle huge problems while preserving sparsity features. Sponsored by the United States Army under Contract No. DAAG 29-80-C-0041. This material is based upon work supported by the National Science Foundation under Grants No. MCS-790166 and ENG-7903881.     

A flexible framework for Group Decision Support: WINGDSS version 3.0

A flexible framework for Group Decision Support on PCs in Microsoft Windows environment is presented. WINGDSS does not replace human judgment but highly supports the entire process of decision making, from problem structuring to post-decision analysis. The latest version of WINGDSS is a modular, open system with a dynamical connection to relational databases, an interpreter for defining problem specific evaluation procedures, a lot of interactive features from setting up the tree of criteria until the sensitivity analysis on individual/group ranking. By providing tools for recursively redefining the decision problem, WINGDSS helps the decision makers in achieving a result satisfactory to the whole group.Research supported in part by the Hungarian Foundation for Scientific Research, Grant No. 2568 and by the Hungarian National Committee for Technical Research and Development, Grant No. 93-97-67-0553.