Questions tagged [primal-dual]
The primal-dual tag has no usage guidance.
21
questions
3
votes
0
answers
60
views
Verifying LP solutions using primal-dual hybrids
We wish to solve an LP in the standard form
Choose vector $x$ to maximize $c^T x$ subject to $Ax \le b$.
Let $x^*$ be a feasible point. By LP duality, $x^*$ solves the LP iff we can write the ...
- 2,393
1
vote
0
answers
80
views
What is a "strongly complementary pair" of primal/dual solutions to a linear program?
While trying to understand this paper by Hammer, Hansen and Simeone, I came across some terminology I was unfamiliar with: the notion of a "strongly complementary pair".
For a linear program ...
3
votes
1
answer
155
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 \...
- 2,078
1
vote
0
answers
115
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 ...
- 89
10
votes
3
answers
742
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 ...
- 1,443
12
votes
2
answers
30k
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 ...
- 5,255
10
votes
1
answer
1k
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 ...
- 5,255
2
votes
1
answer
1k
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(\...
- 241
1
vote
2
answers
3k
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. ...
user15587
4
votes
1
answer
688
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 ...
- 5,255
21
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 ...
- 5,255
14
votes
1
answer
477
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 ...
- 1,591
3
votes
1
answer
14k
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}$ ...
- 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 ...
8
votes
0
answers
565
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
...
- 725
4
votes
1
answer
165
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 ...
- 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 "...
- 4,902
2
votes
2
answers
421
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 ...
- 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 ...
- 3,664
5
votes
2
answers
371
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 ...
user770
6
votes
2
answers
402
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?
- 69