# Questions tagged [duality-theorems]

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

1,200 questions
Filter by
Sorted by
Tagged with
23 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 ...
• 2,047
15 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 ...
24 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 ...
34 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 densely imbedded. My question is: Is $Y \subset X$ densely imbedded? Here, $X'$ denotes the dual space of $X$, i.e. ...
38 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 ...
28 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}{...
• 149
17 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 ...
• 71
44 views

1 vote
55 views

80 views

### About Benders decomposition for MILP [closed]

I have been using Benders decomposition for the following MILP: Original problem I put the binary y variables into the residual subproblem, which is as follows: Residual subproblem The dual form is: ...
13 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 ...
• 185
29 views

### What will be the dual of the abelian simply connected Lie group with the trivial Poisson structure?

Let $(\mathfrak{g}, [\cdot, \cdot])$ be a finite-dimensional Lie algebra with trivial cobracket with the corresponding abelian simply connected Lie group $G$ having trivial Poisson structure. Then its ...
• 2,647
44 views

• 487
38 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 ...
• 95
48 views

### 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 ...
• 300
17 views

### Slater's Condition and Primal Optimal Value

I know that Slater's condition implies strong duality and that the dual problem's supremum is attained. Is the infimum for the primal also attained under Slater's condition?
• 1,388
11 views

• 3,034