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.     

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.     

On abstract duality in mathematical programming

It is shown that duality in mathematical programming can be treated as a purely order theoretic concept which leads to some applications in economics. Conditions for strong duality results are given. Furthermore the underlying sets are endowed with (semi-)linear structures, and the perturbation function of arising linear and integer problems, which include bottleneck problems and extremal problems (in the sense of K. Zimmermann), is investigated.

---

Zusammenfassung In dieser Arbeit wird aufgezeigt, daß Dualitätskonzepte der mathematischen Optimierung in ordnungstheoretischem Rahmen beschrieben werden können. Dies führt u.a. auf neue Anwendungen in der Ökonomie. Ferner werden Bedingungen hergeleitet, unter denen starke Dualitätsaussagen gelten. Sodann werden die zugrundeliegenden Mengen mit algebraischen Strukturen versehen und es werden Dualitätssätze für lineare und ganzzahlige Programme über diesen Mengen bewiesen. Darunter fallen nicht nur die klassischen linearen und ganzzahligen Programme, sondern auch Probleme mit Engpaßzielfunktion und extremale Probleme im Sinne von K. Zimmermann.

---

---

This paper was partially supported by the NATO Research Grants Programme under SRG 8.     

Local cone approximations in mathematical programming

We show how to use intensively local cone approximations to obtain results in some fields of optimization theory as optimality conditions, constraint qualifications, mean value theorems and error bound.     

Objective function approximations in mathematical programming

Mathematical programming applications often require an objective function to be approximated by one of simpler form so that an available computational approach can be used. An a priori bound is derived on the amount of error (suitably defined) which such an approximation can induce. This leads to a natural criterion for selecting the best approximation from any given class. We show that this criterion is equivalent for all practical purposes to the familiar Chebyshev approximation criterion. This gains access to the rich legacy on Chebyshev approximation techniques, to which we add some new methods for cases of particular interest in mathematical programming. Some results relating to post-computational bounds are also obtained.This paper was partially supported by the National Science Foundation and by the Office of Naval Research, and was the basis for a plenary lecture delivered at the IX International Symposium on Mathematical Programming in Budapest, Hungary, August 1976.     

Characterizing optimality in mathematical programming models

This paper is a survey of basic results that characterize optimality in single- and multi-objective mathematical programming models. Many people believe, or want to believe, that the underlying behavioural structure of management, economic, and many other systems, generates basically continuous processes. This belief motivates our definition and study of optimality, termed structural optimality. Roughly speaking, we say that a feasible point of a mathematical programming model is structurally optimal if every improvement of the optimal value function, with respect to parameters, results in discontinuity of the corresponding feasible set of decision variables. This definition appears to be more suitable for many applications and it is also more general than the usual one: every optimum is a structural optimum but not necessarily vice versa. By characterizing structural optima, we obtain some new, and recover the familiar, optimality conditions in nonlinear programming.The paper is self-contained. Our approach is geometric and inductive: we develop intiution by studying finite-dimensional models before moving on to abstract situations.Research partly supported by the National Research Council of Canada.     

Average shadow prices in mathematical programming

We develop the concept of average shadow price in mathematical programming. This concept measures the value of resources along a direction in an average sense, in contrast to traditional marginal analysis; it serves as a useful standard price for management decisions about resources, particularly when there are nonconvexities. We give it an economic interpretation. We also develop simple computational schemes for obtaining and improving the bounds of the average shadow prices and illustrate them in two important classes of nonconvex programs: convex maximization problems and mixed integer programs.     

Nondifferentiable mathematical programming and convex-concave functions

For a convex-concave functionL(x, y), we define the functionf(x) which is obtained by maximizingL with respect toy over a specified set. The minimization problem with objective functionf is considered. We derive necessary conditions of optimality for this problem. Based upon these necessary conditions, we define its dual problem. Furthermore, a duality theorem and a converse duality theorem are obtained. It is made clear that these results are extensions of those derived in studies on a class of nondifferentiable mathematical programming problems.This work was supported by the Japan Society for the Promotion of Sciences.     

Shadow prices in nonconvex mathematical programming

In this paper a definition is proposed for the concept of shadow prices in nonconvex programming. For a nonlinear program with equality and inequality constraints, existence of these prices and bounds for their possible values are obtained under the Mangasarian—Fromowitz regularity condition. Their exact values and some continuity properties are obtained under the more restrictive linear independence regularity condition. A definition of equilibrium prices is also proposed. Under convexity assumptions, all definitions and results coincide with those already known on this subject in convex programming.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-9273.     

Three modeling paradigms in mathematical programming

Celebrating the sixtieth anniversary since the zeroth International Symposium on Mathematical Programming was held in 1949, this paper discusses several promising paradigms in mathematical programming that have gained momentum in recent years but have yet to reach the main stream of the field. These are: competition, dynamics, and hierarchy. The discussion emphasizes the interplay between these paradigms and their connections with existing subfields including disjunctive, equilibrium, and nonlinear programming, and variational inequalities. We will describe the modeling approaches, mathematical formulations, and recent results of these paradigms, and sketch some open mathematical and computational challenges arising from the resulting optimization and equilibrium problems. Our goal is to elucidate the need for a systematic study of these problems and to inspire new research in the field.