Combinatorics (Fall 2010)/Duality, Matroid

From EtoneWiki
Jump to: navigation, search

Duality

Consider the following LP:

Let be the value of the optimal solution. We want to estimate the upper and lower bound of .

Since is the minimum over the feasible set, every feasible solution forms an upper bound for . For example is a feasible solution, thus .

For the lower bound, the optimal solution must satisfy the two constraints:

Since the 's are restricted to be nonnegative, term-by-term comparison of coefficients shows that

The idea behind this lower bound process is that we are finding suitable nonnegative multipliers (in the above case the multipliers are all 1s) for the constraints so that when we take their sum, the coefficient of each in the sum is dominated by the coefficient in the objective function. It is important to ensure that the multipliers are nonnegative, so they do not reverse the direction of the constraint inequality.

To find the best lower bound, we need to choose the multipliers in such a way that the sum is as large as possible. Interestingly, the problem of finding the best lower bound can be formulated as another LP:

Here and were chosen to be nonnegative multipliers for the first and the second constraint, respectively. We call the first LP the primal program and the second LP the dual program. By definition, every feasible solution to the dual program gives a lower bound for the primal program.

LP duality

Given an LP in canonical form, called the primal LP:

the dual LP is defined as follows:

We then give some examples.

Surviving problem (diet problem)

Let us consider the surviving problem. Suppose we have types of natural food, each containing up to types of vitamins. The th food has amount of vitamin , and the price of the th food is . We need to consume amount of vitamin for each to keep a good health. We want to minimize the total costs of food while keeping healthy. The problem can be formalized as the following LP:

The dual LP is

The problem can be interpreted as follows: A food company produces types of vitamin pills. The company wants to design a pricing system such that

  • The vitamin has a nonnegative price .
  • The price system should be competitive to any natural food. A costumer cannot replace the vitamins by any natural food and get a cheaper price, that is, for any .
  • The company wants to find the maximal profit, assuming that the customer only buy exactly the necessary amount of vitamins ( for vitamin ).
Maximum flow problem

In the last lecture, we defined the maximum flow problem, whose LP is

where directed graph is the flow network, is the source, is the sink, and is the capacity of directed edge .

We add a new edge from to to , and let the capacity be . Let be the new edge set. The LP for the max-flow problem can be rewritten as:

The second set of inequalities seem weaker than the original conservation constraint of flows, however, if this inequality holds at every node, then in fact it must be satisfied with equality at every node, thereby implying the flow conservation.

To obtain the dual program we introduce variables and corresponding to the two types of inequalities in the primal. The dual LP is:

It is more helpful to consider its integer version:

In the last lecture, we know that the LP for max-flow is totally unimordular, so is this dual LP, therefore the optimal solutions to the integer program are the optimal solutions to the LP.

The variables defines a bipartition of vertex set . Let . The complement .

For 0/1-valued variables, the only way to satisfy is to have and . Therefore, is an - cut.

In an optimal solution, if and only if and . Therefore, the objective function of an optimal solution is the capacity of the minimum - cut .

Duality theorems

Let the primal LP be:

Its dual LP is:

Theorem
The dual of a dual is the primal.
Proof.

The dual program can be written as the following minimization in canonical form:

Its dual is:

which is equivalent to the primal:

We have shown that feasible solutions of a dual program can be used to lower bound the optimum of the primal program. This is formalized by the following important theorem.

Theorem (Weak duality theorem)
If there exists an optimal solution to the primal LP:
then,
Proof.

Let be an arbitrary feasible solution to the primal LP, and be an arbitrary feasible solution to the dual LP.

We estimate in two ways. Recall that and , thus

.

Since this holds for any feasible solutions, it must also hold for the optimal solutions.

A harmonically beautiful result is that the optimums of the primal LP and its dual are equal. This is called the strong duality theorem of linear programming.

Theorem (Strong duality theorem)
If there exists an optimal solution to the primal LP:
then,

Matroid

The matroid is a structure shared by a class of optimization problems for which greedy algorithms work.

Kruskal's greedy algorithm for MST

For the minimum-weight spanning tree (MST) problem. We are given a connected undirected graph with positive edge weights , and want to find a spanning tree of the minimum accumulated weight .

We consider the equivalent maximum problem to find a spanning tree with maximum weight. To see this makes the problem no harder, we can replace the weight for every edge by , where is a sufficient large constant which is greater than all weights. The minimum-weight spanning tree for the modified weight is the maximum-weight spanning tree for the original weight.

The following greedy algorithm solves the maximum-weight spanning tree problem.

Kruskal's Algorithm
;
while that is forest
pick such with maximum ;
;

It is not hard to verify the correctness of this greedy algorithm. But we are more interested in the general framework underlying this algorithm.

Matroids

Let be a finite set and be a family of subsets of . A member set is called maximal if for any .

For , denote . Obviously,.

Definition
A set system is a matroid if it satisfies:
  • (hereditary) if then ;
  • (matroid property) for every , all maximal have the same .

Suppose is a matroid. Some matroid terminologies:

  • Each member set is called an independent set.
  • A maximal independent subset of a set , i.e., a maximal , is called a basis of .
  • The size of the maximal is called the rank of , denoted .

Graph matroids

Let be a graph. Define a set system with ground set as

That is, is the set of all forests in .

We claim that is a matroid.

First, is hereditary since any subgraph of a forest must also be a forest.

We then verify the matroid property of . Let be an arbitrary subgraph of . Suppose has connected components. For any maximal forest in (i.e., is a spanning forest in ), it holds that . In other words, for any , all maximal member of have the same cardinality.

Therefore, is a matroid. Each independent set (of matroid) is a forest in . For any subgraph , the rank of is the size of a spanning forest of .

Linear matroids

Let be an matrix. Define a set system as

is hereditary since every any subset of a set of linearly independent vectors is still linearly independent.

For any subset of columns of . Let be the submatrix composed by these columns. Then contains all sets of linearly independent columns of . Clearly, all maximal such sets have the same size, which is the column-rank of .

Therefore, is a matroid. Each independent set (of matroid) is a linearly independent set of columns of matrix . For any set of columns of matrix , the rank of is the column-rank of the submatrix defined by the columns in .

Weighted matroid maximization

Consider the following weighted matroid maximization problem. Let be a matroid. We define positive weights of elements in . Our goal is to find an independent set with the maximum accumulated weight .

We then introduce the Greedy Algorithm which finds the maximum-weight independent set.

Greedy Algorithm
;
while with
choose such with maximum ;
;

The correctness of the greedy algorithm is due to the next theorem.

Theorem (Rado 1957; Edmonds 1970)
The greedy algorithm finds an independent set with the maximum weight.
Proof.

Suppose the theorem is false. Let be the independent set returned by the greedy algorithm and let be a maximum-weight independent set.

Suppose , where the s are chosen by the algorithm in that order. Then it is easy to see that .

Suppose , where .

Choose the least index such that . If none exists, then we must have ; in this case we can let .

In either case we know that the greedy algorithm did not add any of in step . Since what it did choose has smaller weight, it must be that , for , has the property either that or that . In other words, is a basis of . But this contradicts the matroid property, since , being a subset of , is also an independent subset of and is larger.

Matroid intersections