Applications of symmetric derivatives in mathematical programming

In recent times the Kuhn—Tucker optimality conditions and the duality theorems for convex programming have been extended by generalizations of the convexity concept. In this paper the notion of a symmetric derivative for a function of several variables is introduced and used to provide extensions of some fundamental optimality and duality theorems of convex programming. Symmetric derivatives are also used to extend some optimality and duality theorems involving pseudoconvexity and differentiable quasiconvexity.     

Constraint propagation,relational arithmetic in AI systems and mathematical programs

This paper explores the interrelationships between methods developed in mathematical programming to discover the structure of constraint (feasibility) sets and constraint propagation over networks used by some AI systems to perform inferences about quantities. It is shown that some constraint set problems in mathematical programming are equivalent to inferencing problems for constraint networks with interval labels. This makes the inference and query capabilities associated with AI systems that use logic programming, directly accessible to mathematical programming systems. On the other hand, traditional and newer methods which mathematical programming uses to obtain information about its associated feasibility set can be used to determine the propagation of constraints in a network of nodes of an AI system. When viewed from this point of view, AI problems can access additional mathematical programming analytical tools including new ways to incorporate qualitative data into constraint sets via interval and fuzzy arithmetic.This work was partially supported by the Industrial Consortium to Develop an Intelligent Mathematical Programming System — Amoco Oil Company, General Research Corporation, Ketron Management Science, Shell Oil Company, MathPro, and US West Advanced Technologies.     

Translating statements of symbolic logic into zero-one linear programming

Symbolic logic can be used to translate verbal statements of the optimization problem into an exact mathematical form. There are then three stages in the problem formulation—the verbal stage, the logical stage and the mathematical stage. The purpose of this paper is to translate statements of symbolic logic into the language of zero-one linear programming. Concepts of symbolic logic and zero-one linear programming will be described with examples of translating verbal statements into symbolic logic, and of translating logical statements into a mathematically equivalent form.     

A remark on a regularity assumption for the mathematical programming problem in Banach spaces

This paper deals with a recently proposed Slater-like regularity condition for the mathematical programming problem in infinite-dimensional vector spaces (Ref. 1). The attractive feature of this constraint qualification is the fact that it can be considered as a condition only on theactive part of the constraint. We prove that the studied regularity condition is equivalent to the regularity assumption normally used in the study of the mathematical programming problem in infinite-dimensional vector spaces.     

Convex analysis treated by linear programming

The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham).     

A compact formulation of an elastoplastic analysis problem

Two important problems in the area of engineering plasticity are limit load analysis and elastoplastic analysis. It is well known that these two problems can be formulated as linear and quadratic programming problems, respectively (Refs. 1–2). In applications, the number of variables in each of these mathematical programming problems tends to be large. Consequently, it is important to have efficient numerical methods for their solution. The purpose of this paper is to present a method which allows the quadratic programming formulation of the elastoplastic analysis to be reformulated as an equivalent quadratic programming problem which has significantly fewer variables than the original formulation. Indeed, in Section 4, we will present details of an example for which the original quadratic programming formulation required 297 variables and for which the equivalent formulation presented here required only two variables. The method is based on a characterization of the entire family of optimal solutions for a linear programming problem.This research was supported by the Natural Science and Engineering Council of Canada under Grant No. A8189 and by a Leave Fellowship from the Social Sciences and Humanities Research Council of Canada. The author takes pleasure in acknowledging many stimulating discussions with Professor D. E. Grierson.     

A note on convex cones and constraint qualifications in infinite-dimensional vector spaces

In connection with mathematical programming in infinite-dimensional vector spaces, Zowe has studied the relationship between the Slater constraint qualification and a formally weaker qualification used by Kurcyusz. The attractive feature of the latter is that it involves only active constraints. Zowe has proved that, in barreled spaces, the two qualifications are equivalent and has asked whether the assumption of barreledness is superfluous. By studying cores and interiors of convex cones, we show that the two constraint qualifications are equivalent in a given topological vector spaceE iff every barrel inE is a neighborhood of the origin. Thus, whenE is locally convex, the two constraint qualifications are equivalent iffE is barreled. Other questions of Zowe are also answered.This research was supported in part by the Office of Naval Research, and in part by the Sonderforschungsbereich 21, Institut für Operations Research, Bonn, Federal Republic of Germany. The author is indebted to Professor J. Zowe for some helpful comments.     

On spaces in which countably compact sets are closed, and hereditary properties

A space X is called C-closed if every countably compact subset of X is closed in X. We study the properties of C-closed spaces. Among other results, it is shown that countably compact C-closed spaces have countable tightness and under Martin's Axiom or 2^ω0<2^ω1, C-closed is equivalent to sequential for compact Hausdorff spaces. Furthermore, every hereditarily quasi-k Hausdorff space is Fréchet-Urysohn, which generalizes a theorem of Arhangel'sk in [4]. Also every hereditarily q-space is hereditarily of pointwise countable type and contains an open dense first countable subspace.     

K-spaces of maximal rank

We consider a special type of K-space, i.e., almost-Hermitian manifolds whose fundamental form is a Killing form. The K-spaces of this type are characterized by the fact that their dimension is equal to the rank of the covariant derivative of the structure form. A number of the properties of such spaces are established (they are Einstein, compact, have finite fundamental group, etc.). It is proved that every K-space is locally equivalent to a product of a K-space of maximal rank and a Kähler manifold. The K-spaces with zero holomorphic sectional curvature are studied.Translated from Matematicheskie Zametki, Vol. 22, No. 4, pp. 465–476, October, 1977.In conclusion, I thank A. M. Vasil'ev for his constant interest and assistance.     

A generalized subgradient method with relaxation step

We study conditions for convergence of a generalized subgradient algorithm in which a relaxation step is taken in a direction, which is a convex combination of possibly all previously generated subgradients. A simple condition for convergence is given and conditions that guarantee a linear convergence rate are also presented. We show that choosing the steplength parameter and convex combination of subgradients in a certain sense optimally is equivalent to solving a minimum norm quadratic programming problem. It is also shown that if the direction is restricted to be a convex combination of the current subgradient and the previous direction, then an optimal choice of stepsize and direction is equivalent to the Camerini—Fratta—Maffioli modification of the subgradient method.Research supported by the Swedish Research Council for Engineering Sciences (TFR).     

On dual locally uniformly rotund norms

We show that the existence of an equivalent dual LUR norm on a dual Banach space can be characterized by a topological property similar to the fragmentability. The compact spaces homeomorphic to weak* compact subsets of a dual LUR Banach space have the same properties as the class of Radon-Nikodym compact spaces. Research supported by the DGICYT PB 95-1025.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

A Regularity Result of Nikolskii Type for an Evolution Equation on Compact Homogeneous Spaces

In the previous paper [2], we proposed a definition of a class of function spaces of Nikolskii type on a special class of riemannian manifolds, namely the manifolds M admitting a transitive compact connected Lie group of isometries. In this paper we continue the subject and we complete the proof that the spaces we have introduced coincide with the classical ones, defined through (finitely many) local charts of M. Moreover, our equivalent definition of these spaces allows us to prove here a regularity result for the solution of a Stefan-like problem on M, in which the initial datum is assumed to be of Nikolskii type.     

On quadratic andO\left( {\sqrt {nL} } \right) convergence of a predictor—corrector algorithm for LCP

Recently several new results have been developed for the asymptotic (local) convergence of polynomial-time interior-point algorithms. It has been shown that the predictor—corrector algorithm for linear programming (LP) exhibits asymptotic quadratic convergence of the primal—dual gap to zero, without any assumptions concerning nondegeneracy, or the convergence of the iteration sequence. In this paper we prove a similar result for the monotone linear complementarity problem (LCP), assuming only that a strictly complementary solution exists. We also show by example that the existence of a strictly complementarity solution appears to be necessary to achieve superlinear convergence for the algorithm.Research supported in part by NSF Grants DDM-8922636 and DDM-9207347, and an Interdisciplinary Research Grant of the University of Iowa, Iowa Center for Advanced Studies.     

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).     

Necessary optimality conditions for a special class of bilevel programming problems with unique lower level solution

We consider a bilevel programming problem in Banach spaces whose lower level solution is unique for any choice of the upper level variable. A condition is presented which ensures that the lower level solution mapping is directionally differentiable, and a formula is constructed which can be used to compute this directional derivative. Afterwards, we apply these results in order to obtain first-order necessary optimality conditions for the bilevel programming problem. It is shown that these optimality conditions imply that a certain mathematical program with complementarity constraints in Banach spaces has the optimal solution zero. We state the weak and strong stationarity conditions of this problem as well as corresponding constraint qualifications in order to derive applicable necessary optimality conditions for the original bilevel programming problem. Finally, we use the theory to state new necessary optimality conditions for certain classes of semidefinite bilevel programming problems and present an example in terms of bilevel optimal control.     

Qualification conditions for multivalued functions in Banach spaces with applications to nonsmooth vector optimization problems

In this paper we introduce qualification conditions for multivalued functions in Banach spaces involving the A-approximate subdifferential, and we show that these conditions guarantee metric regularity of multivalued functions. The results are then applied for deriving Lagrange multipliers of Fritz—John type and Kuhn—Tucker type for infinite non-smooth vector optimization problems.     

Multifunctions on abstract measurable spaces and application to stochastic decision theory

Summary The main results are some very general theorems about measurable multifunctions on abstract measurable spaces with compact values in a separable metric space. It is shown that measurability is equivalent to the existence of a pointwise dense countable family of measurable selectors, and that the intersection of two compact-valued measurable multifunctions is measurable. These results are used to obtain a Filippov type implicit function theorem, and a general theorem concerning the measurability of y(t)=min f({t} × Γ(t)) when f is a real valued function and Γ a compact valued multifunction. An application to stochastic decision theory is given generalizing a result of Benes. The research in this paper was partially supported by University of Kansas General Research Fund Grants 3918-5038 and 3199-5038. Entrata in Redazione il 20 dicembre 1972.     

An ordering (enumerative) algorithm for nonlinear 0-1 programming

In this paper, a new algorithm to solve a general 0–1 programming problem with linear objective function is developed. Computational experiences are carried out on problems where the constraints are inequalities on polynomials. The solution of the original problem is equivalent with the solution of a sequence of set packing problems with special constraint sets. The solution of these set packing problems is equivalent with the ordering of the binary vectors according to their objective function value. An algorithm is developed to generate this order in a dynamic way. The main tool of the algorithm is a tree which represents the desired order of the generated binary vectors. The method can be applied to the multi-knapsack type nonlinear 0–1 programming problem. Large problems of this type up to 500 variables have been solved.     

远达函数的可导性与远达点的存在性

该文考察Banach空间上的远达函数的可导性与远达点的存在性间的关系，指出某些Banach空间上的远达函数(对有界闭集而言)具等于1或-1的单侧方向导数蕴含远达点的存在性，并给出了Banach空间CLUR和LUR的新等价刻划．