Questions tagged [primal-dual]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
105 views

Is there an approximate version of the strong duality theorem for linear programming?

Consider the following dual linear programs: $$ \min \mathbf{c^T x} ~~ \text{s.t.} ~~ A \mathbf{x} \geq \mathbf{b}, \mathbf{x}\geq 0; \\ \max \mathbf{b^T y} ~~ \text{s.t.} ~~ A^T \mathbf{y} \leq \...
user avatar
1 vote
0 answers
106 views

Is this proof of $LP$ being in $coNP$ correct?

I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there ...
user avatar
10 votes
3 answers
671 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 ...
user avatar
  • 1,443
11 votes
2 answers
27k 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 ...
user avatar
  • 5,157
10 votes
1 answer
997 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 ...
user avatar
  • 5,157
2 votes
1 answer
920 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 \begin{equation} \min f(\...
user avatar
  • 241
1 vote
2 answers
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. ...
user avatar
4 votes
1 answer
641 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 ...
user avatar
  • 5,157
19 votes
2 answers
5k 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 ...
user avatar
  • 5,157
14 votes
1 answer
458 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 ...
user avatar
  • 1,571
3 votes
1 answer
11k 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}$ ...
user avatar
  • 147
1 vote
1 answer
1k 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 ...
user avatar
7 votes
0 answers
553 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 ...
user avatar
4 votes
1 answer
163 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 ...
user avatar
  • 153
36 votes
1 answer
2k 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 "...
user avatar
2 votes
2 answers
396 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 ...
user avatar
  • 934
14 votes
2 answers
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 ...
user avatar
  • 3,614
5 votes
2 answers
364 views

Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that ...
user avatar
6 votes
2 answers
396 views

Online learning: Perceptron updates

It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?
user avatar