# Questions tagged [primal-dual]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
77 views

### Primal/Dual of the Lasserre/ SOS SDP hierarchy

Sum of Squares proofs and the Lasserre hierarchy can both be stated as SDPs. It is often claimed without proof that these SDPs are dual to each other, although I do not see that this is obvious. I was ...
389 views

### When is the duality gap of semidefinite programming (SDP) zero?

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
20k views

### Intuitively, why is the complementary slackness condition true?

What's an intuitive proof that shows that the conditions of complementary slackness are indeed true: If $x^*_j > 0$ then the $j$-th constraint in the dual is binding. If the $j$-th constraint in ...
747 views

### Why is complementary slackness important?

Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint. The two ...
671 views

### On the stopping criterion of coordinate descent method

I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion. Consider the optimization problem \min f(\...
2k views

### Applications of duality

We have recently covered linear programming and I am comfortable with the weak and strong duality theorems. However, I don't understand what the applications of duality are that are specific to TCS. ...
531 views

### LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?

Given any Integer Linear Program (ILP) there are 2 ways to approximate it: Write down ILP, convert to LP by relaxing the integer constraints and round the solution Write down the ILP, convert to LP ...
4k views

### An intuitive/informal proof for LP Duality?

What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of ...
424 views

### Is it enough for linear program constraints to be satisfied in expectation?

In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
7k views

### Difference between weak duality and strong duality?

For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different: Weak duality: If $\bar{x}$ ...
953 views

### Primal vs dual decomposition methods

I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
538 views

### Difference between Primal Dual Algorithm for Proper and Uncrossable Functions

Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions: (1) super-modular functions (2) proper functions ...
149 views

### Primal Dual model in the continuous domain

The continuous max flow problem is posed as follows : sup $\int_\Omega p_s(x)dx$ subject to : $|p(x)| \le C(x); \forall x \in \Omega$ $p_s(x) \le C_s(x); \forall x \in \Omega$ \$p_t(x) \le ...
1k views

### Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" ...
326 views

### Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.

Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship ...
2k views

### Generalization of the Hungarian algorithm to general undirected graphs?

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important ...