A quantifier for matroid duality

A quantifier is introduced on the elements of a matroid which, given an element e, says “for all elements (except possibly e) of some circuit containing e,…”. The matroid dual of this quantifier is shown to be identical with its logical dual, and this provides an elegant reformulation of Minty's self-dual axiomatization of matroids.This approach also provides a practical, and in a sense optimal, means of taking a statement in terms of circuits and constructing its dual, still in terms of circuits.     

A matroid operation that commutes with duality

In this note, we propose an operation for matroids that commutes with duality having deletions and contractions as extremal cases. Crapo and Schmitt's free product of matroids is one of its consequences. A special case of this operation can be used as an inductive tool because it reduces the number of elements of a matroid by two and it is invariant by duality.     

Fenchel-type duality for matroid valuations

The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroidsM _i = (V, _i , _i ) (i = 1,2) defined on a common ground setV, find a common baseB _{1 2} that maximizes ₁ (B) + ₂ (B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Part of this paper has been presented at fifth SIAM Conference on Optimization, Victoria, May 1996.This work was done while the author was at Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 1994–1995.     

A minor-based characterization of matroid 3-connectivity

It is well known that a matroid is 2-connected if and only if every 2-element set is contained in a circuit, or equivalently, a _U1,2$U_{1,2}$-minor. This paper proves that a matroid is 3-connected if and only if every 4-element set is contained in a minor isomorphic to a wheel of rank 3 or 4; a whirl of rank 2, 3, or 4; or the relaxation of a rank-3 whirl. Some variants of this result are also discussed.     

A characterization of complete matroid base graphs

This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form K_n × K_m for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs.     

A duality theory for bilattices

Recent studies of the algebraic properties of bilattices have provided insight into their internal strucutres, and have led to practical results, especially in reducing the computational complexity of bilattice-based multi-valued logic programs. In this paper the representation theorem for interlaced bilattices without negation found in [19] and extended to arbitrary interlaced bilattices without negation in [2] is presented. A natural equivalence is then established between the category of interlaced bilattices and the cartesian square of the category of bounded lattices. As a consequence a dual natural equivalence is obtained between the category of distributive bilattices and the coproduct of the category of bounded Priestley spaces with itself. Some applications of these equivalences are given. The subdirectly irreducible interlaced bilattices are characterized in terms of subdirectly irreducible lattices. A known characterization of the join-irreducible elements of the "knowledge" lattice of an interlaced bilattice is used to establish a natural equivalence between the category of finite, distributive bilattices and the category of posets of the form . Received February 2, 1998; accepted in final form September 2, 1999.     

A simple approach to some basic results in matroid theory

The bases and the cocircuits of a matroid form a blocking pair of clutters; this fact leads to simple proofs of some basic and well-known facts about matroids, including a variety of axiomatizations.     

A generalization of Fenchel duality theory

This paper deals with an extention of Fenchel duality theory to fractional extremum problems, i.e., problems having a fractional objective function. The main result is obtained by regarding the classic Fenchel theorem as a decomposition property for the extremum of a sum of functions into a sum of extrema of functions, and then by extending it to the case where the addition is replaced by the quotient. This leads to a generalization of the classic concept of conjugate function. Several remarks are made about the conceivable further generalizations to other kinds of decomposition.     

Euclideaness and final polynomials in oriented matroid theory

This paper deals with a geometric construction of algebraic non-realizability proofs for certain oriented matroids. As main result we obtain an algorithm which generates a (bi-quadratic) final polynomial [3], [5] for any non-euclidean oriented matroid. Here we apply the results of Edmonds, Fukuda and Mandel [6], [7] concerning non-degenerate cycling of linear programs in non-euclidean oriented matroids.     

A new duality theory for compact groups

Summary The Tannaka-Krein duality theory characterizes the category (G) of finite-dimensional, continuous, unitary representations of a compact group as a subcategory of the category of Hilbert spaces. We prove a more powerful result characterizing (G) as an abstract category: every strict symmetric monoidalC ^*-category with conjugates which has subobjects and direct sums and for which theC ^*-algebra of endomorphisms of the monoidal unit reduces to the complex numbers is isomorphic to a category (G) for a compact groupG unique up to isomorphism.Research supported by the Ministero della Pubblica Istruzione and CNR-GNAFA     

Contour approximation of data: A duality theory

Given a dataset D partitioned in clusters, the joint distance function (JDF) J(x) at any point x is the harmonic mean of the distances between x and the cluster centers. The JDF is a continuous function, capturing the data points in its lower level sets (a property called contour approximation), and is a useful concept in probabilistic clustering and data analysis. In particular, contour approximation allows a compact representation of the data: for a dataset in Rⁿ with N points organized in K clusters, the JDF requires K centers and covariances (if Mahalanobis distances are used), for a total of Kn(n+3)/2 parameters, and a considerable reduction of storage if N?K,n. The JDF of the whole dataset, J(D)?∑{J(x):x∈D}, is a measure of the classifiability of the data, and can be used to determine the “right” number of clusters for D. A duality theory for the JDF J(D) is given, in analogy with Kuhn’s geometric duality theory for the Fermat-Weber location problem. The JDF J(D) is the optimal value of a primal problem (P), for which a dual problem (D) is given, with a sharp lower bound on J(D).     

Additively separable duality theory

In duality theory, there is a trade-off between generality and tractability. Thus, the generality of the Tind-Wolsey framework comes at the expense of an infinite-dimensional dual solution space, even if the primal solution space is finite dimensional. Therefore, the challenge is to impose additional structure on the dual solution space and to identify conditions on the primal program, such that the properties that are typically associated with duality, like weak and strong duality, are preserved.In this paper, we consider real-valuedness, continuity, and additive separability as such additional structures. The virtue of the latter property is that it restores the one-to-one correspondence between primal constraints and dual variables as it exists in Lagrangian duality. The main result of this paper is that, roughly speaking, the existence of realvalued, continuous, and additively separable dual solutions that preserve strong duality is guaranteed, once the primal program satisfies a certain stability condition. The latter condition is ensured by the well-known regularity conditions that imply constraint qualification in Karush-Kuhn-Tucker points. On the other hand, if instead of additive separability, a mild tractability condition is imposed on the dual solution space, then stability turns out to be a necessary condition for strong duality in a well-defined sense. This result, combined with the observation that applicability of some well-known augmented Lagrangian methods to constrained optimization.This study was supported by the Netherlands Foundation for Mathematics (SMC) with financial aid from the Netherlands Organization for Scientific Research (NWO).     

Capacity theory without duality

Summary The paper develops a theory of capacity for a Borel right process without duality assumptions. The basic tool in this approach is a stationary process ralative to an excessive measure.IfP _t )t0 denotes the semigroup of the process on the state spaceE and ifm is an excessive measure onE, then there exists a processY = (Y _t ) _t onE with random birth and death and a -finite measureQ _m such thatY is stationary underQ _m and Markov with respect to (P _t ).For a setB inE the hitting (resp. last exit) time ofY is denoted by _B (resp. _B ), andB is called transient (resp. cotransient) ifQ _m ( _B =)= 0 (resp.Q _m ( _B = – )=0. The main theorem then states that for a both transient and contransient setB the distributions of _B and _B underQ _m are the same. For suchB the capacity is denfined byC(B):=Q _m ( _B [0, 1] and the cocapacity by (B):=Q _m ( _B [0, 1], and it is shown that these definitions in fact generalize previous definitions under duality assumptions.Without duality assumption there is no representation of the capacitary potential in terms of a capacitary measure, but there exists a cocapacitary entrance law _t ^B which generalizes the notion of a cocapacitary measure such that (B)= _t ^B (1).The paper contains investigations of transience and cotransience, a decomposition of the cocapacitrary entrance law, some remarks on left versions, and furthermore a generalization of Spitzer's asymptotic formula.Research supported in part by NSF Grant DMS 8419377Research carried out while visiting University of California, San Diego, during Spring 1985     

Curved Koszul duality theory

We extend the bar–cobar adjunction to operads and properads, not necessarily augmented. Due to the default of augmentation, the objects of the dual category are endowed with a curvature. As usual, the bar–cobar construction gives a cofibrant resolution for any properad. Applied to the properad encoding unital and counital Frobenius algebras, notion which appears in 2d-TQFT, it defines the associated notion up to homotopy. We further define a curved Koszul duality theory for operads or properads presented with quadratic, linear and constant relations. This provides smaller resolutions. We apply this new theory to study the homotopy theory and the cohomology theory of unital associative algebras.     

Polynomials with the half-plane property and matroid theory

A polynomial f is said to have the half-plane property if there is an open half-plane H⊂C, whose boundary contains the origin, such that f is non-zero whenever all the variables are in H. This paper answers several open questions relating multivariate polynomials with the half-plane property to matroid theory.

(1)

We prove that the support of a multivariate polynomial with the half-plane property is a jump system. This answers an open question posed by Choe, Oxley, Sokal and Wagner and generalizes their recent result claiming that the same is true whenever the polynomial is also homogeneous.

(2)

We prove that a multivariate multi-affine polynomial f∈R[z₁,…,zn] has the half-plane property (with respect to the upper half-plane) if and only if

     

Introduction to duality in optimization theory

A systematic exposition of duality theory is given on what appears to be the optimal level of generality. A condition is offered which implies that the ideal of duality theory is achieved. For the case of linear programming, our approach leads to two novel features. In the first place, primal and dual LP-problems and complementarity conditions are defined canonically, without choosing a matrix form. In the second place, without deriving the explicit form of the dual problem, we show that the following well-known fact implies that the condition mentioned above holds: the polyhedral set property is invariant under linear maps. We give a new quick algorithmic proof of this fact.The author would like to thank Jan Boone for his helpful comments on a preliminary version of this paper.     

On duality theory in multiobjective programming

In this paper, we study different vector-valued Lagrangian functions and we develop a duality theory based upon these functions for nonlinear multiobjective programming problems. The saddle-point theorem and the duality theorem are derived for these problems under appropriate convexity assumptions. We also give some relationships between multiobjective optimizations and scalarized problems. A duality theory obtained by using the concept of vector-valued conjugate functions is discussed.The author is grateful to the reviewer for many valuable comments and helpful suggestions.