On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

求线性二层规划∈-全局最优解的一种方法

本文研究了线性二层规划问题.利用下层问题的KKT最优性条件将其转化为一个具有互补约束的数学规划问题,提出了一种新的求解方法.该方法仅仅需要求解若干个双线性规划问题,便可以获得原问题的∈-全局最优解.最后,通过一个算例说明了所提出方法的可行性.     

Nondegeneracy of Polyhedra and Linear Programs

This paper deals with nondegeneracy of polyhedra andlinear programming (LP) problems. We allow for the possibilitythat the polyhedra and the feasible polyhedra of the LPproblems under consideration be non-pointed.(A polyhedron is pointed if it has a vertex.) With respect to a given polyhedron, we consider two notions ofnondegeneracy and then provide several equivalent characterizationsfor each of them. With respect to LP problems, we study thenotion of constant cost nondegeneracy first introduced byTsuchiya [25] under a different name, namelydual nondegeneracy. (We do not follow this terminology sincethe term dual nondegeneracy is already used to refer to a relatedbut different type of nondegeneracy.) We show two main results about constant cost nondegeneracy of an LP problem.The first one shows that constant cost nondegeneracy of an LPproblem is equivalent to the condition that the union of all minimal faces of the feasible polyhedron be equal to the set of feasible points satisfying a certain generalized strict complementarity condition.When the feasible polyhedron of an LP is nondegenerate,the second result showsthat constant cost nondegeneracy is equivalent to the conditionthat the set of feasible points satisfying the generalizedcondition be equal to the set of feasible points satisfyingthe same complementarity condition strictly.For the purpose of giving a preview of the paper,the above results specialized to the context of polyhedra and LP problems in standard form are described in the introduction.     

On greedy algorithms for series parallel graphs

This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel graph to be found by a greedy algorithm.     

Sources and Sinks in Comparability Graphs

We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained.     

On various duality theorems in nonlinear programming

Recently, Gulati and Craven and Mond and Egudo established strict converse duality theorems for some of Mond-Weir duals for nonlinear programming problems. Here, we establish various duality theorems under weaker convexity conditions that are different from those of Gulati and Craven, Mond and Weir, and Mond and Egudo.The first author is thankful to the Natural Science and Engineering Research Council of Canada for financial support through Grant A-5319.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

Duality in Fuzzy Linear Programming: Some New Concepts and Results

A class of fuzzy linear programming (FLP) problems based on fuzzy relations is introduced, the concepts of feasible and -efficient solutions are defined. The class of crisp (classical) LP problems and interval LP problems can be embedded into the class of FLP ones. Moreover, for FLP problems a new concept of duality is introduced and the weak and strong duality theorems are derived. The previous results are applied to the special case of interval LP and compared to the existing literature.     

Duality in mathematics and linear and integer programming

Linear programming (LP) duality is examined in the context of other dualities in mathematics. The mathematical and economic properties of LP duality are discussed and its uses are considered. These mathematical and economic properties are then examined in relation to possible integer programming (IP) dualities. A number of possible IP duals are considered in this light and shown to capture some but not all desirable properties. It is shown that inherent in IP models are inequality and congruence constraints, both of which give on their own well-defined duals. However, taken together, no totally satisfactory dual emerges. The superadditive dual based on the Gomory and Chvátal functions is then described, and its properties are contrasted with LP duals and other IP duals. Finally, possible practical uses of IP duals are considered.The author is indebted to Professor H. B. Griffiths for many stimulating conversations on this topic.     

Duality theorems and algorithms for linear programming in measure spaces

The purpose of this paper is to present some results on linear programming in measure spaces (LPM). We prove that, under certain conditions, the optimal value of an LPM is equal to the optimal value of the dual problem (DLPM). We also present two algorithms for solving various LPM problems and prove the convergence properties of these algorithms.     

Stability of the primal-dual partition in linear semi-infinite programming

We analyse the primal-dual states in linear semi-infinite programming (LSIP), where we consider the primal problem and the so called Haar's dual problem. Any linear programming problem and its dual can be classified as bounded, unbounded or inconsistent, giving rise to nine possible primal-dual states, which are reduced to six by the weak duality property. Recently, Goberna and Todorov have studied this partition and its stability in continuous LSIP in a series of papers [M.A. Goberna and M.I. Todorov, Primal, dual and primal-dual partitions in continuous linear semi-infinite programming, Optimization 56 (2007), pp. 617–628; M.A. Goberna and M.I. Todorov, Generic primal-dual solvability in continuous linear semi-infinite programming, Optimization 57 (2008), pp. 239–248]. In this article we consider the general case, with no continuity assumptions, discussing the maintenance of the primal-dual state of the problem by allowing small perturbations of the data. We characterize the stability of all of the six possible primal-dual states through necessary and sufficient conditions which depend on the data, and can be easily checked, showing some differences with the continuous case. These conditions involve the strong Slater constraint qualification, and some distinguished convex sets associated to the data.     

Graphical analysis of duality and the Kuhn-Tucker conditions in linear programming

Careful inspection of the geometry of the primal linear programming problem reveals the Kuhn-Tucker conditions as well as the dual. Many of the well-known special cases in duality are also seen from the geometry, as well as the complementary slackness conditions and shadow prices. The latter at demonstrated to differ from the dual variables in situations involving primal degeneracy. Virtually all the special relationships between linear programming and duality theory can be seen from the geometry of the primal and an elementary application of vector analysis.     

Convergence of duality bound method in partly convex programming

We discuss the convergence of a decomposition branch-and-bound algorithm using Lagrangian duality for partly convex programs in the general form. It is shown that this decomposition algorithm has all convergence properties as any known branch-and-bound algorithm in global optimization under usual assumptions. Thus, some strict assumptions discussed in the literature are avoidable.     

An extension of the könig-egerváry property to node-weighted bidirected graphs

Given a bidirected graphG and a vectorb of positive integral node-weights, an integer linear program IP is defined on (G, b). IP generalizes the node packing problem on a node-weighted (undirected) graph in the sense that it reduces to the latter whenG is undirected. A polynomial time algorithm is given that recognizes whether CP (the linear program obtained by relaxing the integrality constraints of IP) has an integral optimal solution. Also an efficient method for solving the linear programming dual of CP is described.Supported by the Natural Sciences and Engineering Research Council of Canada.     

On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function

We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lovász's theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its induced subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a perfect graph using the theta function. Our algorithm iteratively transforms an approximate solution of the semidefinite formulation of the theta function into an approximate solution of another formulation, which is then used to identify a vertex that belongs to a maximum stable set. The subgraph induced by that vertex and its neighbors is removed and the same procedure is repeated on successively smaller graphs. We establish that solving the theta problem up to an adaptively chosen, fairly rough accuracy suffices in order for the algorithm to work properly. Furthermore, our algorithm successfully employs a warm-start strategy to recompute the theta function on smaller subgraphs. Computational results demonstrate that our algorithm can efficiently extract maximum stable sets in comparable time it takes to solve the theta problem on the original graph to optimality. This work was supported in part by NSF through CAREER Grant DMI-0237415. Part of this work was performed while the first author was at the Department of Applied Mathematics and Statisticsat Stony Brook University, Stony Brook, NY, USA.     

Optimal consumption and arbitrage in incomplete,finite state security markets

We study a consistent treatment for both the multi-period portfolio selection problem and the option attainability problem by a dual approach. We assume that time is discrete, the horizon is finite, the sample space is finite and the number of securities is less than that of the possible securities price transitions, i.e. an incomplete security market. The investor is prohibited from investing stocks more than given linear investment amount constraints at any time and he maximizes an expected additive utility function for the consumption process. First we give a set of budget feasibility conditions so that a consumption process is attainable by an admissible portfolio process. To establish this relation, we used an algorithmic approach which has a close connection with the linear programming duality. Then we prove the unique existence of a primal optimal solution from the budget feasibility conditions. Finally, we formulate a dual control problem and establish the duality between primal and dual control problems.We are grateful to the editor, Hiroshi Konno, and two anonymous referees for their valuable comments and constructive suggestions on this research. We are responsible for the remaining errors. The first author is supported in part by the fund endowed to the Research Association for Financial Engineering by Toyo Trust Bank Co. and Mito Shoken Co.