Bonn, matroids, and Farkas’ Lemma

Bonn

The Hausdorff Institute in Bonn is hosting an excellent trimester program in combinatorial optimization, and last week was devoted to a workshop on rigidity, submodularity and discrete convexity. The organizers of the workshop, Satoru Iwata, Tibor Jordán, and Jan Vondrák, assembled an impressive lineup of speakers, so we had a great overview on the state of the art in these fields. I am not going into details about the talks here (you can soon watch the videos on the youtube channel of the Hausdorff Institute, just mention some quick impressions.

• Clearly, one of the hot topics of recent years is submodular maximization. There were plenty of interesting talks on questions like parallelization, derandomization, restricted queries, and online problems, each with a different spin on the greedy algorithm.
• Great to see that research on discrete convexity is also going strong. Kazuo Murota's seminal work on these concepts led to several applications, and recently new connections have been discovered to auction theory and to multiflow theory . Another framework that keeps popping up in various graph theoretic applications is the Frank-Jordán theorem; András Frank showed us how it leads to good characterizations for the existence of degree-restricted simple graphs with given properties.
• More and more rigidity concepts turn out to be analyzable using combinatorial methods. Although the main open question of the area, the characterization of 3-dimensional rigidity, is still open, the search for a proof led to several new concepts that turned out to be interesting in their own right.
• A surprising new result by Lee, Sidford, and Wong , that they dubbed the “revenge of the ellipsoid method”, may turn out to be a game-changer in the way we think about efficient algorithms in combinatorial optimization. In particular, their result implies [math]\tilde{O}(n^3)[/math] running time for submodular flows, which is far better than anything we can currently hope to achieve by combinatorial methods.

These workshops are also ideal for conversations about different approaches to understanding and teaching basic concepts in combinatorial optimization. A topic that came up during breakfast is the dilemma we face when teaching Farkas’ lemma. There are essentially three different ways to do it:

• Start with the simplex method, and prove Farkas’ Lemma using the finite termination of the algorithm
• Introduce convex separation, and prove Farkas’ Lemma using a combination of convex separation and the existence of basic solutions
• Give a self-contained combinatorial proof of Farkas’ Lemma using induction.

All three methods have their merits, and the choice should probably depend on the skills and predilections of the students. Instead of discussing my real-world teaching preferences here, I will describe a purely hypothetical situation: how would I teach Farkas’ Lemma to students who already know (and love) matroid theory but who are unaware of linear programming duality? I would of course teach them the oriented matroid version!

Warm-up: oriented matroids

The easiest way to define oriented matroids for our purpose is by the cycle axioms. As we know from matroid theory, the family of cycles of a matroid is a clutter [math]{\mathcal C}[/math] that has the following property (we use the stronger version of the cycle axiom):

If [math]C_1[/math] and [math]C_2[/math] are in [math]{\mathcal C}[/math], [math]e \in C_1 \cap C_2[/math], and [math]f \in C_1 \setminus C_2[/math], then there is a cycle [math]C_3[/math] with [math]f \in C_3 \subseteq C_1 \cup C_2 - e[/math].

The oriented cycle axioms are very similar, the difference being that cycles are not sets but unordered pairs of disjoint sets. The first axiom is that if for each pair we take the union of the two sets, then the set family we obtain is a clutter (in particular, we cannot have two different orientation of the same cycle in the oriented matroid). The second axiom is the following.

If [math](C^+_1,C^-_1)[/math] and [math](C^+_2,C^-_2)[/math] are in [math]{\mathcal C}[/math], [math]e \in C^+_1 \cap C^+_2[/math], and [math]f \in (C^+_1 \setminus C^+_2) \cup (C^-_1 \setminus C^-_2)[/math], then there is a cycle [math](C^+_3,C^-_3)[/math] with [math]C^+_3 \subseteq C^+_1 \cup C^-_2 - e[/math], [math]C^-_3 \subseteq C^-_1 \cup C^+_2 - e[/math], and [math]f \in C^+_3 \cup C^-_3[/math].

To have some intuition about this axiom, consider the case of cycles in a directed graph, with the partitioning corresponding to the two directions of the arcs along the cycle. You can convince yourself easily that the oriented cycle axioms hold.

It is also useful to understand the case of linear oriented matroids represented over [math]{\mathbb R}[/math]. Here cycles represent minimal dependent sets of vectors. Each such minimal dependent set has a unique partition into two subsets corresponding to the positive and negative coefficients in the linear dependency (note that the positive and negative part can be switched, this is why the pair is unordered). Let [math]C_1[/math] and [math]C_2[/math] be cycles and [math]e[/math] a vector in their intersection. The vector [math]e[/math] can be uniquely written as a linear combination [math]\lambda[/math] of the vectors in [math]C_1-e[/math], and also as a linear combination [math]\mu[/math] of the vectors in [math]C_2-e[/math]. Let us choose an arbitrary vector [math]f \in C^+_1 \setminus C^+_2[/math]; by rescaling the coefficients, we can assume that [math]\lambda_f-\mu_f=1[/math]. Now observe that [math]\lambda-\mu[/math] is a linear dependency of [math]C_1 \cup C_2-e[/math], and its sign pattern satisfies the second oriented cycle axiom. This gives [math]f[/math] as a linear combination with a given sign pattern, and we can take such a linear combination with the smallest support to get an oriented cycle.

Minors of an oriented matroid [math]M[/math] can be obtained similarly to matroid minors. Let [math]E[/math] be the ground set of [math]M[/math]. Deletion of a subset [math]F\subseteq E[/math], denoted by [math]M\setminus F[/math], means that only cycles disjoint from [math]F[/math] are preserved. Contraction of [math]F[/math] ([math]M/F[/math]) consists of the members of [math]\{(C^+\setminus F,C^-\setminus F): (C^+,C^-) \in {\mathcal C}\}[/math] with inclusionwise minimal non-empty union. It is a bit tricky to show that this satisfies the first axiom, so let me give a short proof by contradiction. Suppose that [math](C^+_1\setminus F,C^-_1 \setminus F)[/math] and [math](C^+_2\setminus F,C^-_2\setminus F)[/math] are distinct cycles in [math]M/F[/math] such that [math](C^+_1 \cup C^-_1)\setminus F = (C^+_2 \cup C^-_2)\setminus F[/math]. Then there are elements [math]e \in (C^+_1 \cap C^+_2) \cup (C^-_1 \cap C^-_2)\setminus F[/math] and [math]f \in (C^+_1 \setminus C^+_2) \cup (C^-_1 \setminus C^-_2)\setminus F[/math]. By the second axiom, there is a cycle [math](C^+_3,C^-_3)[/math] such that [math]f \in C^+_3 \cup C^-_3 \subseteq (C^+_1 \cup C^-_1 \cup C^+_2 \cup C^-_2)-e[/math], which contradicts the minimality of [math](C^+_1 \cup C^-_1)\setminus F[/math].

Not all matroids can be oriented; however, we have the nice property that an orientation of a matroid gives rise to an orientation of the dual. Take a co-cycle [math]D[/math] of the dual matroid, and consider two elements [math]e,f[/math] of [math]D[/math]. Since [math]D[/math] is a cocycle, there must be a cycle [math]C[/math] such that [math]C \cap D =\{e,f\}[/math]. Furthermore, by the first oriented cylce axiom and the properties of contraction, either every such cycle [math]C[/math] has [math]e[/math] and [math]f[/math] in the same class, or all of them have [math]e[/math] and [math]f[/math] in different classes. Define [math]e[/math] and [math]f[/math] to be equivalent if they are in different classes for any such cycle. It can be seen using the second axiom that this is an equivalence relation and there are at most two equivalence classes. This defines the partitioning of [math]D[/math], and the obtained orientation of the dual matroid satisfies the oriented cycle axioms. It is also easy to see that minor operations are switched for the dual, i.e. deletion in the dual is the same as taking the dual of the contraction. The following important property can also be derived from the axioms.

(*) If [math](C^+,C^-)[/math] is a cycle, [math](D^+,D^-)[/math] is a co-cycle, and [math]f \in C^+ \cap D^+[/math], then [math](C^+ \cap D^-) \cup (C^- \cap D^+)[/math] is non-empty.

Proof. By the definition of the orientation of co-cycles, the statement is true if [math]|(C^+ \cup C^-) \cap (D^+ \cup D^-)|=2[/math]. Suppose we have a counterexample with smallest intersection, and let [math]e[/math] by an element different from [math]f[/math] in the intersection. There is a cycle [math](C^+_2,C^-_2)[/math] such that [math](C^+_2 \cup C^-_2) \cap (D^+ \cup D^-)=\{e,f\}[/math]. The second axiom for this cycle and [math](C^+,C^-)[/math] gives a cycle that is a smaller counterexample, a contradiction.

What does the orientation of the dual mean in the two cases that we examined earlier? In a graphic matroid, the same digraph that defined the orientation of the cycles also defines an orientation of the cuts, and this is precisely the orientation of the dual matroid. The situation is a bit less obvious for matroids represented over [math]{\mathbb R}[/math]. If [math]A[/math] is the matrix of the representation, [math]L[/math] is the subspace spanned by the rows of [math]A[/math], and [math]L^\bot[/math] is its orthogonal complement, then the oriented cycles correspond to the signed minimal supports of vectors in [math]L^\bot[/math], while the oriented co-cycles correspond to signed minimal supports of vectors in [math]L[/math].

Finale: Farkas' Lemma

A directed cycle is an oriented cycle where one class is empty; directed co-cycle is defined analogously. Farkas’ Lemma for oriented matroids is simply the following.

Theorem. Every element of an oriented matroid is either in a directed cycle or in a directed co-cycle.

Proof. The statement that an element cannot be in both is implied by property (*). We prove the other direction for a given element [math]e[/math] by induction on the size of the matroid. The statement is trivial if the size is 1. Otherwise let [math]f[/math] be another element. If [math]e[/math] is in a directed cycle in [math]M\setminus f[/math] or it is in a directed co-cycle in [math]M/f[/math], then we are done. Thus we can assume by induction that [math]e[/math] is in a directed co-cycle [math](\emptyset, D^-)[/math] in [math]M\setminus f[/math] and in a directed cycle [math](\emptyset,C^-)[/math] in [math]M\setminus f[/math]; furthermore, [math](f,D^-)[/math] is a co-cycle and [math](f,C^-)[/math] is a cycle in [math]M[/math]. However, this contradicts property (*).

How does this relate to the original Farkas Lemma for a linear system [math]\{Ax=b, x \geq 0\}[/math]? Let [math]M[/math] be the oriented matroid defined by the columns of [math](A, -b)[/math]. The system [math]\{Ax=b, x \geq 0\}[/math] is solvable if and only if [math]-b[/math] is in a directed cycle. Otherwise [math]-b[/math] is in a directed co-cycle, which means that the rows of [math](A,-b)[/math] span a non-negative vector whose last coordinate is positive. This is equivalent to the existence of a vector [math]y[/math] such that [math]yA \geq 0[/math] and [math]yb\lt0[/math], as required by Farkas’ Lemma.

I think the upshot of all this is that the oriented matroid version of Farkas’ Lemma is a purely combinatorial statement that, to my knowledge, cannot be proved using convex separation or a perturbed version of the simplex method. In fact, Bland invented his famous pivoting rule precisely because he wanted a finite simplex method for oriented matroids, and other known rules, like the lexicographic rule, did not seem to generalize to this setting.

The computational complexity of the problem is also interesting. In the cycle oracle model, there is no polynomial algorithm for Farkas’ Lemma, because an exponential number of oracle calls may be needed . A more powerful oracle might do the trick, but for any oracle that is strongly polynomial time computable in the linear case, a polynomial-time algorithm for the oriented matroid Farkas Lemma would mean a strongly polynomial algorithm for the linear Farkas Lemma, which is one of the great open problems in optimization.

To finish the post after this long detour, here is a link to the wiki of the trimester program, which collects the open questions that were raised by the participants.

— Tamás Király (talk) • 15:35, 16 October 2015 • no comments

[ List view ]Comments

(no items)

Please login to comment.