On A characterization of optimality in convex programming

Necessary and sufficient conditions for optimality are given, for convex programming problems, without constraint qualification, in terms of a single mathematical program, which can be chosen to be bilinear.This research was partly supported by Project No. NR 047-02, ONR Contracts N00014-67-A-0126-0008 and N00014-67-A-0126-0009 with the Center for Cybernetic Studies, The University of Texas.     

Uniformly overtaking and weakly overtaking optimal solutions in infinite-horizon optimal control: When optimal solutions are agreeable

In this paper, we investigate the relationship between two classes of optimality which have arisen in the study of dynamic optimization problems defined on an infinite-time domain. We utilize an optimal control framework to discuss our results. In particular, we establish relationships between limiting objective functional type optimality concepts, commonly known as overtaking optimality and weakly overtaking optimality, and the finite-horizon solution concepts of decision-horizon optimality and agreeable plans. Our results show that both classes of optimality are implied by corresponding uniform limiting objective functional type optimality concepts, referred to here as uniformly overtaking optimality and uniformly weakly overtaking optimality. This observation permits us to extract sufficient conditions for optimality from known sufficient conditions for overtaking and weakly overtaking optimality by strengthening their hypotheses. These results take the form of a strengthened maximum principle. Examples are given to show that the hypotheses of these results can be realized.This research was supported by the National Science Foundation, Grant No. DMS-87-00706, and by the Southern Illinois University at Carbondale, Summer Research Fellowship Program.     

Necessary conditions for optimality of singular controls in systems governed by partial differential equations

In this paper, we present a method to obtain necessary conditions for optimality of singular controls in systems governed by partial differential equations (distributed-parameter systems). The method is based on the one developed earlier by the author for singular control problems described by ordinary differential equations. As applications, we consider conditions for optimality of singular controls in a Darboux-Goursat system and in control systems that describe chemical processes.This research was supported in part by the National Science Foundation under Grant No. NSF-MCS-80-02337 at the University of Michigan.The author wishes to express his deep gratitude to Professor L. Cesari for his valuable guidance and constant encouragement during the preparation of this paper.     

Linear pursuit-evasion games with bounded state spaces

The problem of linear pursuit-evasion games with bounded state spaces is considered. Some sufficient conditions for optimality are established, and an example is given.This research was carried out while the author was a Visiting Associate Research Engineer at the University of California at Berkeley. The research was supported by the Office of Naval Research, Grant No. N00014-69-A-0200-1012. The author would like to express his gratitude to Professor G. Leitmann for discussions and for making possible his visit at Berkeley.     

Necessary conditions for optimality of singular controls

The present paper is concerned with the study of controls which are singular in the sense of the maximum principle. We obtain necessary conditions for optimality of singular controls in systems governed by ordinary differential equations. A useful feature of the method considered here is that it can be applied to optimal control problems with distributed parameters.this research was supported in part by the National Science Foundation under Grant No. NSF-MCS-80-02337 at the University of Michigan.The author wishes to express his deep gratitude to Professor L. Cesari for his valuable guidance and constant encouragement during the preparation of this paper.     

Statistical verification of optimality conditions for stochastic programs with recourse

Statistically motivated algorithms for the solution of stochastic programming problems typically suffer from their inability to recognize optimality of a given solution algorithmically. Thus, the quality of solutions provided by such methods is difficult to ascertain. In this paper, we develop methods for verification of optimality conditions within the framework of Stochastic Decomposition (SD) algorithms for two stage linear programs with recourse. Consistent with the stochastic nature of an SD algorithm, we provide termination criteria that are based on statistical verification of traditional (deterministic) optimality conditions. We propose the use of bootstrap methods to confirm the satisfaction of generalized Kuhn-Tucker conditions and conditions based on Lagrange duality. These methods are illustrated in the context of a power generation planning model, and the results are encouraging.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant No. DDM-89-10046 from the National Science Foundation.     

Optimal control of systems with multiple criteria when disturbances are present

Optimal control problems with a vector performance index and uncertainty in the state equations are investigated. Nature chooses the uncertainty, subject to magnitude bounds. For these problems, a definition of optimality is presented. This definition reduces to that of a minimax control in the case of a scalar cost and to Pareto optimality when there is no uncertainty or disturbance present. Sufficient conditions for a control to satisfy this definition of optimality are derived. These conditions are in terms of a related two-player zero-sum differential game and suggest a technique for determining the optimal control. The results are illustrated with an example.This research was supported by AFOSR under Grant No. 76-2923.     

Optimal rigid body motions,part 1: Approximate formulation

Optimal rigid body angular motions are investigated in the absence of direct control over one of the angular velocity components, via an approximate dynamic model. An analysis of first-order necessary conditions for optimality with the proposed model reveals that, over a large range of boundary conditions, there are, in general, several distinct extremal solutions. A classification in terms of subfamilies of extremal solutions is presented. Second-order necessary conditions are investigated to establish local optimality for the candidate minimizers.This work was supported in part by DARPA Contract No. ACMP-F49620-87-C-0116 and by Air Force Grant AFOSR-89-0001.     

Primal-dual target-following algorithms for linear programming

In this paper, we propose a method for linear programming with the property that, starting from an initial non-central point, it generates iterates that simultaneously get closer to optimality and closer to centrality. The iterates follow paths that in the limit are tangential to the central path. Together with the convergence analysis, we provide a general framework which enables us to analyze various primal-dual algorithms in the literature in a short and uniform way.This work was completed with the support of a research grant from SHELL. The first author is supported by the Dutch Organization for Scientific Research (NWO), Grant No. 611-304-028. The third author is on leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116. The fourth author is supported by the Swiss National Foundation for Scientific Research, Grant No. 12-34002.92.     

Geometry of optimality conditions and constraint qualifications

Certain types of necessary optimality conditions for mathematical programming problems are equivalent to corresponding regularity conditions on the constraint set. For any problem, a certain natural optimality condition, dependent upon the particular constraint set, is always satisfied. This condition can be strengthened in numerous ways by invoking appropriate regularity assumptions on the constraint set. Results are presented for Euclidean spaces and some extensions to Banach spaces are given.This work was supported in part by the Office of Naval Research, Contract No. N00014-67-A-0321-0003 (NR-047-095).     

Supplementary optimality properties of gradient-restoration algorithms for optimal control problems

In this paper, sequential gradient-restoration algorithms for optimal control problems are considered, and attention is focused on the gradient phase. It is shown that the Lagrange multipliers associated with the gradient phase not only solve the auxiliary minimization problem of the gradient phase, but are also endowed with a supplementary optimality property: they minimize the error in the optimality conditions, subject to the multiplier differential equations and boundary conditions, for given state, control, and parameter.Dedicated to R. BellmanThis work was supported by the National Science Foundation, Grant No. ENG-79-18667.     

Recent results on conditions for the existence of average optimal stationary policies

This paper concerns countable state space Markov decision processes endowed with a (long-run expected)average reward criterion. For these models we summarize and, in some cases,extend some recent results on sufficient conditions to establish the existence of optimal stationary policies. The topics considered are the following: (i) the new assumptions introduced by Sennott in [20–23], (ii)necessary and sufficient conditions for the existence of a bounded solution to the optimality equation, and (iii) equivalence of average optimality criteria. Some problems are posed.This research was partially supported by the Third World Academy of Sciences (TWAS) under Grant No. TWAS RG MP 898-152.     

On optimal control problems with general boundary conditions

It is shown that the necessary optimality conditions for optimal control problems with terminal constraints and with given initial state allow also to obtain in a straightforward way the necessary optimality conditions for problems involving parameters and general (mixed) boundary conditions. In a similar manner, the corresponding numerical algorithms can be adapted to handle this class of optimal control problems.This research was supported in part by the Commission on International Relations, National Academy of Sciences, under Exchange Visitor Program No. P-1-4174.The author is indebted to the anonymous reviewer bringing to his attention Ref. 9 and making him aware of the possible use of generalized inverse notation when formulating the optimality conditions.     

Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions

In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least squares with ellipsoidal constraints, and quadratic minimization with binary constraints. We discuss examples which demonstrate that our optimality conditions can effectively be used for identifying global minimizers of certain multi-extremal non-convex quadratic optimization problems. The work of Z. Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

A generalization of a minimax theorem of Fan via a theorem of the alternative

A minimization problem for a functional on a convex subsetC of a normed linear space is considered. Under certain hypotheses, optimality in a certain subset ofC implies the validity of first-order necessary optimality conditions for the problem inC. The result is applied to a problem in optimal periodic control of neutral functional differential equations.This work was partially supported by a grant from Deutsche Forschungsgemeinschaft and by AFOSR under Grant No. AFOSR-84-0398.     

A note on a generalized network flow model for manufacturing process

Manufacturing network flow （MNF） is a generalized network model that overcomes the limitation of an ordinary network flow in modeling more complicated manufacturing scenarios, in particular the synthesis of different materials into one product and/or the distilling of one type of material into many different products. Though a network simplex method for solving a simplified version of MNF has been outlined in the literature, more research work is still needed to give a complete answer whether some classical duality and optimality results of the classical network flow problem can be extended in MNF. In this paper, we propose an algorithmic method for obtaining an initial basic feasible solution to start the existing network simplex algorithm, and present a network-based approach to checking the dual feasibility conditions. These results are an extension of those of the ordinary network flow problem.     

Farkas' theorem of nonconvex type and its application to a min-max problem

This note is concerned with the generalization of Farkas' theorem and its application to derive optimality conditions for a mix-max problem. Farkas' theorem is generalized to a system of inequalities described by sup-min type positively homogeneous functions. This generalization allows us to deal with optimization problems consisting of objective and constraint functions whose directional derivatives are not necessarily convex with respect to the directions. As an example of such problems, we formulate a min-max problem and derive its optimality conditions.The author would like to express his sincere thanks to Professors S. Suzuki and T. Asano of Sophia University and Professor K. Shimizu of Keio University for encouragement and suggestions.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 2

In Part 1 of this paper, implementable and conceptual versions of an algorithm for optimal control problems with control constraints and terminal equality constraints were presented. It was shown that anyL accumulation points of control sequences generated by the algorithms satisfy necessary conditions of optimality. Since such accumulation points need not exist, it is shown in this paper that control sequences generated by the algorithms always have accumulation points in the sense of control measure, and these accumulation points satisfy optimality conditions for the corresponding relaxed control problem.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAA-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

Minimum-weight design of elastic sandwich beams with deflection constraints

In this paper, minimum-weight design of an elastic sandwich beam with a prescribed deflection constraint at a given point is investigated. The analysis is based on geometrical considerations using then-dimensional space of discretized specific bending stiffness. Since the present method of analysis is different from the method based on the calculus of variations, the conditions of piecewise continuity and differentiability on specific bending stiffness can be relaxed. Necessary and sufficient conditions for optimality are derived for both statically determinate and statically indeterminate beams. Beams subject to a single loading and beams subject to multiple loadings are analyzed. The degree to which the optimality condition renders the solution unique is discussed. To illustrate the method of solution, two examples are presented for minimum-weight designs under dual loading of a simply supported beam and a beam built in at both ends. The present analysis is also extended to the following problems: (a) optimal design of a beam built in at both ends with piecewise specific stiffness and a prescribed deflection constraint and (b) minimum-cost design of a sandwich beam with prescribed deflection constraints.The results presented in this paper were obtained in the course of research supported partly by the US Army Research Office, Durham, North Carolina, Research Grant No. DA-ARO-31-G1008, and partly by the Office of Naval Research, Contract No. N00014-67-A-0109-0003, Task No. NR 064-496. The authors wish to express their thanks to Professor H. Halkin for pointing out the applicability of optimal control theory to the present problem and to Professor W. Prager for his valuable suggestions.     

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.