Linear inequalities,mathematical programming and matrix theory

A survey is made of solvability theory for systems of complex linear inequalities.This theory is applied to complex mathematical programming and stability and inertia theorems in matrix theory.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

A system of inequalities and nondifferentiable mathematical programming

A system of inequalities involving nondifferentiable functions, originally introduced by Eisenberg, is extended. This result is then applied to establish optimality criteria and a dual theorem for a nondifferentiable mathematical program involving quasiconvexity in its equality constraints and inequality constraints. These are natural extensions of results recently established by Mond.The author is grateful to Dr. D. J. Fleming, St. Lawrence University, for helpful discussion.     

Implicit function theorems for mathematical programming and for systems of inequalities

Implicit function formulas for differentiating the solutions of mathematical programming problems satisfying the conditions of the Kuhn—Tucker theorem are motivated and rigorously demonstrated. The special case of a convex objective function with linear constraints is also treated with emphasis on computational details. An example, an application to chemical equililibrium problems, is given.Implicit function formulas for differentiating the unique solution of a system of simultaneous inequalities are also derived.     

Enumerative inequalities in integer programming

For a linear integer programming problem, thelocal information contained at an optimal solution of the continuous linear programming extension stems from the theory of L.P. solutions. This paper proposes the use ofenvironmental information (of a global nature but pertaining to the discrete vicinity of ), in order to isolate the set of integer solutions which may be considered as true candidates for the optimum. The concept ofenumerative inequalities is introduced and it is shown how it can be obtained in the context of the convex outer-domain theory of Balas, Young, et al.Generally speaking, enumerative inequalities can be made arbitrarily strong (deep), but at the cost of an increasing amount of work (i.e. enumeration) for their construction. In particular cases, however, very little global information can produce enumerative inequalities stronger than anyvalid cut.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

Convex programming and variational inequalities

We observe that variational inequalities generalize convex programming. We look here for a method of computing solutions of variational inequalities in a finite-dimensional space. The method we propose is quite close to the method of Theil-Van de Panne described in Ref. 1 in the case of quadratic programming.     

Linear interval inequalities

We prove that a system of linear inequalities with interval-valued data is weakly solvable (each system obtained by fixing coefficeints in the intervals prescribed has a solution) if and only if it is strongly solvable (all such systems have a solution in common) and desribe an algorithm for checking strong solvability.     

Linear interval inequalities

We prove that a system of linear inequalities with interval-valued data is weakly solvable (each system obtained by fixing coefficeints in the intervals prescribed has a solution) if and only if it is strongly solvable (all such systems have a solution in common) and desribe an algorithm for checking strong solvability.     

Potential-reduction methods in mathematical programming

We provide a survey of interior-point methods for linear programming and its extensions that are based on reducing a suitable potential function at each iteration. We give a fairly complete overview of potential-reduction methods for linear programming, focusing on the possibility of taking long steps and the properties of the barrier function that are necessary for the analysis. We then describe briefly how the methods and results can be extended to certain convex programming problems, following the approach of Nesterov and Todd. We conclude with some open problems. Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550. Some of this work was done while the author was on a sabbatical leave from Cornell University visiting the Department of Mathematics at the University of Washington.     

Constraint classification in mathematical programming

Consider a set of algebraic inequality constraints defining either an empty or a nonempty feasible region. It is known that each constraint can be classified as either absolutely strongly redundant, relatively strongly redundant, absolutely weakly redundant, relatively weakly redundant, or necessary. We show that is is worth making a distinction between weakly necessary constraints and strongly necessary constraints. We also present afeasible set cover method which can detect both weakly and strongly necessary constraints.The main interest in constraint classification is due to the advantages gained by the removal of redundant constraints. Since classification errors are likely to occur, we examine how the removal of a single constraint can affect the classification of the remaining constraints.     

Hybrid computation in mathematical programming

It is shown that hybrid computation facilitates the solving of problems in the field of mathematical programming. First, the most important features of hybrid computation are discussed. The main part of the paper deals with examples of computational methods in which hybrid computation can be applied succesfully. The main concentration is on constrained static parameter optimization, where for brevity only penalty function techniques are considered. The use of a penalty function having an extra parameter is discussed rather extensively.     

Decomposition in general mathematical programming

In this paper a unifying framework is presented for the generalization of the decomposition methods originally developed by Benders (1962) and Dantzig and Wolfe (1960). These generalizations, calledVariable Decomposition andConstraint Decomposition respectively, are based on the general duality theory developed by Tind and Wolsey. The framework presented is of a general nature since there are no restrictive conditions imposed on problem structure; moreover, inaccuracies and duality gaps that are encountered during computations are accounted for. The two decomposition methods are proven not to cycle if certain (fairly general) conditions are met. Furthermore, finite convergence can be ensured under the traditional finiteness conditions and asymptotic convergence can be guaranteed once certain continuity conditions are met. The obvious symmetry between both types of decomposition methods is explained by establishing a duality relation between the two, which extends a similar result in Linear Programming. A remaining asymmetry in the asymptotic convergence results is argued to be a direct consequence of a fundamental asymmetry that resides in the Tind-Wolsey duality theory. It can be shown that in case the latter asymmetry disappears, the former does too. Other decomposition techniques, such as Lagrangean Decomposition and Cross Decomposition, turn out to be captured by the general framework presented here as well.This study was supported by the Netherlands Foundation for Mathematics (SMC) with financial aid from the Netherlands Organization for Scientific Research (NWO).Part of this work was done while on leave at the Wharton School of the University of Pennsylvania.     

Error bounds in mathematical programming

Originated from the practical implementation and numerical considerations of iterative methods for solving mathematical programs, the study of error bounds has grown and proliferated in many interesting areas within mathematical programming. This paper gives a comprehensive, state-of-the-art survey of the extensive theory and rich applications of error bounds for inequality and optimization systems and solution sets of equilibrium problems. This work is based on research supported by the U.S. National Science Foundation under grant CCR-9624018.     

Algorithmic Chernoff-Hoeffding inequalities in integer programming

Proofs of classical Chernoff-Hoeffding bounds has been used to obtain polynomial-time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m events whose complements are large deviations corresponding to weighted sums of n mutually independent Bernoulli trials. Raghavan's lattice approximation algorithm constructs for 0-1 weights, and integer deviation terms in O(mn)-time a point for which all events hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic cosine algorithm are deterministic precedures, but a polynomial-time implementation was not known. We resolve this problem with an O(mn²log $ {{mn}\over{\epsilon}} $)-time algorithm, whenever the probability that all events hold is at least ϵ > 0. Since such algorithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the inequality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial-time approximations algorithms. © 1996 John Wiley & Sons, Inc.     

Cluster analysis and mathematical programming

Given a set of entities, Cluster Analysis aims at finding subsets, called clusters, which are homogeneous and/or well separated. As many types of clustering and criteria for homogeneity or separation are of interest, this is a vast field. A survey is given from a mathematical programming viewpoint. Steps of a clustering study, types of clustering and criteria are discussed. Then algorithms for hierarchical, partitioning, sequential, and additive clustering are studied. Emphasis is on solution methods, i.e., dynamic programming, graph theoretical algorithms, branch-and-bound, cutting planes, column generation and heuristics. Research supported by ONR grant N00014-95-1-0917, FCAR grant 95-ER-1048 and NSERC grants GP0105574 and GP0036426. The authors thank Olivier Gascuel and an anonymous referee for insightful remarks.     

Importance measures in reliability and mathematical programming

The importance measures have been a sensitivity analysis for a probabilistic system and are applied in diverse fields along with other design tools. This paper provides a comprehensive view on modeling the importance measures to solve the reliability problems such as component assignment problems, redundancy allocation, system upgrading, and fault diagnosis and maintenance. It also investigates importance measures in broad applications such as networks, mathematical programming, sensitivity and uncertainty analysis, and probabilistic risk analysis and probabilistic safety assessment. The importance-measure based methods are among the most practical decision tools.