# Questions tagged [duality-theorems]

For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.

1,210 questions
Filter by
Sorted by
Tagged with
20 views

### How to find the reduced cost of a variable in a large data set

I have been given a large data set with a list of starting nodes, their destination nodes, and the length to each destination node from each starting node. Using Dijkstra's algorithm, I coded a ...
1 vote
971 views

### Do lagrangian multipliers converge to dual variables in LPs?

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal ...
3k views

8k views

### Relation between the dual space, transpose matrices and rank-nullity theorem

Summing up, how can one use linear functionals, transpose matrices, row and column rank equality and annihilators to prove the rank-nullity theorem? While studying linear algebra, I'm trying to get ...
42 views

### Are pre-duals dense if the duals are dense?

Assume we have two Banach spaces $X,Y$ over $\mathbb R$ such that $X' \subset Y'$ is a dense subset (with respect to the norm of $Y'$). My question is: Is $Y \subset X$ a dense subset (with respect to ...
1k views

23 views

### What's the dual problem of this quadratic programming problem?

$$\min\left(\sum_{i=0}^n \sum_{j=0}^n ((V_i)_j)x_ix_j\right)$$ subject to $$x_1 + \dots + x_n = 1,$$ $$m_1x_1 + \dots + m_nx_n = m,$$ $$x_i \ge 0$$
36 views

34 views

### Finding a dual plan of a linear plan of nutrition

Trying to solve the following question: A final list of foods is given, and a final list of nutrients (such as protein, carbohydrates, etc.). Also non-negative numbers $r_{k,l}$ are given that ...
34 views

### Providing a certificate for maximum cardinal matching

I have bipartite graph with six nodes on each side. I have found one of the maximum cardinal matches with 4 pairs. How do I provide a certificate (which can be checked with O(|V | + |E|) elementary ...
1 vote
411 views

### Gordan's lemma by using Farkas' lemma

Gordan's lemma states: Let $A \in \mathbb{R}^{m \times n}$. Then exactly one of the following two systems has a solution: \begin{align*} \text{I:}\quad &\exists x \in \mathbb{R}^n: Ax < 0, \\ ...
39 views

### Using minimum cover to find maximum matching in bipartite

I was shown an algorithm in a test for using minimum vertex coverage in bipartite graph to find maximum edge matching. It made a lot of sense to me and I failed to come up with an example that proves ...
48 views

### Maximum matching = Minimum odd vertex cover

Definition: A set $C⊆V$ and a collection of subsets $𝐵_1,…,𝐵_𝑘⊆V$ is an odd vertex cover if for every edge 𝑒 either $𝑒∩𝐶≠∅$ or $𝑒 ⊆ B_i$ for some 𝑖. The cost of the odd vertex cover is ...
35 views

### Exchanging limsup with liminf

I am working on a problem where I think I might be able to complete my argument if I can show the following relation. \begin{align*} \limsup_{k \rightarrow \infty} \liminf_{x' \rightarrow x} \frac{1}{...
22 views

### Strong Duality with quasi convex objective and linear constraints

Take the problem $$\min f(x) \ \ \text{ s.t. } A x - b \leq 0_M$$ where $f:\mathbb{R}^N \to \mathbb{R}$ is a quasi convex function, $A \in \mathbb{R}^{M \times N}$ $b \in \mathbb{R}^M$, and $0_M$ is ...
1k views

### Lagrange dual of a sum of convex functions

Given a set of convex functions $f_i(x)$ and convex sets $X_i$ in $\mathbb R^n$ I need to find the Lagrange dual problem for the problem $\min \sum{f_i(x)} , x \in X_i \forall i$. There is of course ...
46 views

1 vote
58 views

15 views

### Does the value of the lagrangian of all KKT points lie between $[\max\min \mathcal{L} , \min \max \mathcal{L}]$?

Let a constrained optimization problem where $f$ is nonconvex, $g$ is convex: \begin{align} &\mathrm{min}~f(x)\\ &\mathrm{s.t.}~g(x)\leq 0. \end{align} Does the value of the Lagrangian ...
50 views

464 views

### Pontryagin duality of finite groups

I have a question related to this question in stack exchange. By the above question, if $G$ is finite abelian group then its Pontryagin dual $\hat{G}=\operatorname{Hom}(G, \mathbb{Q}/\mathbb{Z})$ is ...
1 vote
216 views

Let $L$ be a lattice (finitely generated free abelian group), and $M\subseteq L$ be a subgroup of finite index (which is again a lattice). Consider the dual lattices L^\vee={\rm Hom}(L,\mathbb Z)\...
152 views

### The image of the canonical map into the double dual of a vector space

If $V$ is a vector space over some field, we have a canonical map $\phi_V:V\to V^{**}$ from $V$ to its double dual. The map $\phi_V$ depends naturally on $V$, and its scalar multiples are the only ...
3k views

### Why can not we use Lagrange multiplier in mathematical (in particular linear) programming?

I am studying linear programming right now. And I can not explain to myself why I can not solve any linear programming task using the Lagrange multiplier method. Could you help me understand that, ...
42 views

### Approximations of BMO functions

I couldn't think of a good title. There was a small detail when I was trying to prove something about the norm of BMO functions. This small detail is not directly related to the problem itself, but ...
### Dual linear Program for $\min c^Tx$ subject to $Ax\leq b$
For $A\in\mathbb R^{n\times n}, b\in \mathbb R^n, c\in \mathbb R^n$ what is the dual linear program of a) $\min c^Tx$ subject to $Ax\leq b$ and b) $\max c^Tx$ subject to $Ax=b$? I thin the dual ...