26

Luca, since a year has passed, you probably have researched your own answer. I'm answering some of your questions here just for the record. I review some Lagrangian-relaxation algorithms for the problems you mention, and sketch the connection to learning (in particular, following expert advice). I don't comment here on SDP algorithms. Note that the ...


19

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution." For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual ...


19

Per OP's wish, here's the math.SE answer I link to in my comment above. Maybe it's worthwhile to talk through where the dual comes from on an example problem. This will take a while, but hopefully the dual won't seem so mysterious when we're done. Suppose with have a primal problem as follows. $$ Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 ...


16

As you have noted, complementary slackness follows immediately from strong duality, i.e., equality of the primal and dual objective functions at an optimum. Complementarity slackness can be thought of as a combinatorial optimality condition, where a zero duality gap (equality of the primal and dual objective functions) can be thought of as a numerical ...


14

Complementary slackness is key in designing primal-dual algorithms. The basic idea is: Start with a feasible dual solution $y$. Attempt to find primal feasible $x$ such that $(x, y)$ satisfy complementary slackness. If step 2. succeeded we are done. Otherwise an obstruction to finding $x$ gives a way to modify $y$ so that the dual objective function value ...


10

Yup. Everything follows from duality. (I am only half joking). A partial list: Boosting The Hard-Core Lemma Online Learning The ability to actually solve LPs efficiently A large fraction of approximation algorithms results. Much more To develop algorithms, you often need a constructive or algorithmic version of the duality theorem (which is ...


10

There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to Ramana. (For another take on this involving SOS, see [KS12].) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me. One notable consequence of this work is ...


9

For the SDP in standard form $$ \min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\}, $$ Slater's condition reduces to the existence of a positive definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the ...


8

I find the geometric interpretation useful. Say we have the primal as $\max c x$ subject to $Ax \le b$ and $x \ge 0$. We know that optimum solutions are vertices of the polytope defined by the constraints. Each such vertex is defined by the intersection of $n$ linearly independent hyperplanes defined by the constraints. When is a vertex solution $x^*$ ...


7

Elaborating on Mike's answer and Vazirani's comment, you get the dual by considering the general form of an optimality proof for the solution to the original problem. Suppose you have a maximization problem given some linear inequalities, and without loss of generality, suppose you're trying to maximize the variable $x$. Given a solution in which $x = B$, ...


7

Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal. Was this helpful enough?


4

Perhaps the most famous application of duality has been the max-flow min-cut theorem (introduced in Ford & Fulkerson's landmark paper "Maximal Flow Through a Network"). The theorem states, formally, that the optimal solution for the (primal) integer linear program for finding the maximum flow is equal to the same optimal solution for the dual program to ...


4

If one uses an ILP formulation and its LP relaxation then clearly it does not hurt to look at the dual. In many cases the dual helps to understand/interpret the lower/upper bound that the relaxations give. This can be exploited algorithmically in a direct fashion, or some times indirectly to provide intuition. Several classical combinatorial optimization ...


2

I don't think one can make a blanket statement on whether primal decomposition methods or dual decomposition methods are more efficient. The efficiency is dictated by the structure of the problem; primal decomposition and dual decomposition are ways of exploiting this structure to develop efficient algorithms. The key aspect in making a choice between these ...


2

Here's one possible solution: $$\nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1} \cdots \frac{\partial f(x)}{\partial x_n}\right]^T$$ The coordinate descent algorithm is exploring all the coordinate axes, so you have an estimate of $\hat{\nabla} f_i(x_k)=\frac{\partial f(x^k)}{\partial x_i}$. In particular, when $\Big| \hat{\nabla} f_i(x_k) \Big| < ...


1

There is a nice (I think....) characterization of when strong duality holds, or fails for {\em all} objective functions. We say that the semidefinite {\em system} $(P_{SD}) \,\, \sum_{i=1}^m x_i A_i \preceq B$ is badly behaved if here is an objective function $c$ for which the SDP $\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$ has a finite ...


Only top voted, non community-wiki answers of a minimum length are eligible