# Tag Info

17

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^*$ ...

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 ...

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