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
0
votes
1
answer
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 ...
- 39.9k
1
vote
1
answer
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 ...
CommunityBot
- 1
6
votes
2
answers
3k
views
Duality in quadratically-constrained quadratic program (QCQP)
I have been given the primal quadratic program with a single quadratic constraint as given below:
$$ \begin{array}{ll} \min\limits_{x \in \mathbb{R}^n} & \frac12 x^{T} Q x \\ \text{subject to} &...
- 19.9k
1
vote
2
answers
642
views
Dual cone's dual cone is the closure of primal cone's convex hull
Assume $K$ is a cone and its dual cone is $K^* = \{y:x^Ty \geq 0,\, \forall x \in K\}$. Then we have $K^{**} = \text{cl}(\text{conv}\ K)$, where cl means closure, conv means convex hull.
How to prove ...
- 49
1
vote
1
answer
56
views
Lagrangian Duality problem
Suppose that $\lambda, N_0 \in \mathbb{R}$, $\boldsymbol{X}_{0} = (X_2',...,X_{m+1}')' \in \mathbb{R}^{m \times n} , X_1 \in \mathbb{R}^n$ is fixed, $\iota \in \mathbb{R}^n$ is the vector of ones, ...
- 367
0
votes
0
answers
32
views
Why dual norm inequality is tight in $\mathbb{R}^{n}$
Let $\lVert \cdot \rVert $ be any norm on $\mathbb{R}^n$
I want to prove that
For any $x$, there is some $z$ such that $z^{T}x = \lVert x \rVert \lVert z \rVert _{*}$
where $\lVert y \rVert _{*} = \...
- 131
0
votes
0
answers
19
views
How to solve minimisation using dual and simplex method
How would I minimise $2y_1 + y_2$ using the simplex method?
subject to:
$ 10y1 + y2 \ge 10 $
$ 2y1 + y2 \ge 8 $
$ y1 + y2 \ge 6 $
$ y1 + 2y_2 \ge 10 $
$ y1 + 12y_2 \ge 12 $
$ y1,y2 \ge 0 $
I have got ...
- 73
2
votes
0
answers
94
views
Constrained Optimization using FFT to find function
I want to find the function $W(x)$ from the following optimization problem:
\begin{equation}
\textrm{min}
\left(I(x) - \int_{-\infty}^{\infty} W(x_0) d(x-x_0) dx_0\right)^2
\end{equation}
\begin{...
2
votes
0
answers
21
views
Dual operator of Markovian operator
I am trying to incorporate the definition of dual operator in a Markovian setting.
Say I have a Markov kernel $K:S\times S\to[0,1]$ i.e., a mapping such that
for every $A\in S$ $x\to K(x,A)$ is a ...
- 889
0
votes
1
answer
13
views
subdifferentiable implies conjugate equality
For function $f(x)=\max_i x_i, x\in\mathbb{R}^n$.
We define the Fenchel conjugate as
$$
f^*(x^*) = \sup_{x} \langle x^*,x\rangle-f(x)
$$
The standard subdifferential for $f(x)$ as
$$
\partial f(x)=\{x^...
- 8,614
5
votes
2
answers
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 ...
- 2,835
0
votes
0
answers
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 ...
- 71
2
votes
1
answer
1k
views
Solving a PL using complementary slackness conditions - dual
I have to find the optimal solution of the dual with the complementary slackness conditions.
This is the primal:
$\max \space\space z= x_1 - 2x_2 $
$\text{s.t.}\space\space\space\space\space x_1-x_2\...
CommunityBot
- 1
0
votes
0
answers
33
views
Operator norm as a dual norm?
Given a space $X$ endowed with a norm $\left\lVert \cdot \right\rVert$ then one can define a norm $\left\lVert \cdot \right\rVert_\star$ on the continuous dual space $X^\star$ considering the ...
- 889
0
votes
0
answers
40
views
Dual polygons: terminology
A question about terminology: is there a specific reason why, given a polygon $P$, the polygon $P^*$ constructed by connecting the midpoints of the edges of $P$ is called the 'dual polygon'? Thanks to ...
- 604
1
vote
1
answer
1k
views
How to find Dual Problem
I have here an example, where I am not able to find the dual problem:
$(P): J_p(x)= \max_{z_1, z_2 } (z_1 + x z_2)$
subj. to:
$z_1 + z_2 = 1$
$z_1\ge 0$
$z_2\ge0$
where $x\in[0,2]$ a ...
CommunityBot
- 1
3
votes
1
answer
131
views
Riesz–Markov–Kakutani representation for symmetric matrix-valued measures
Let
$\Theta$ be a closed $d$-manifold (and hence a metric space with Borel-$\sigma$-algebra $\Sigma \subset 2^\Theta$),
$S^d$ the set of real symmetric $d \times d$ matrices, which we can identify ...
- 4,436
1
vote
1
answer
27
views
If two elements are different there is a functional under where the image is different
I have the following exercise in functional analysis:
Let E be a normed space and $x,y$ different vectors. Prove or disprove finding a counterexample that it exist a function $f \in E^*$ such that $f(...
- 193k
0
votes
0
answers
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$$
- 6,433
0
votes
0
answers
36
views
Kleiman's relative duality: What does the notation $\omega_f \otimes_Y N$ mean, for a sheaf $N$ on $X$?
In Kleiman's paper Relative duality for quasi-coherent sheaves he defines for a proper, finitely presentable morphism $f: X \to Y$ with fibers of dimension $\dim X(y) \leq r$:
An $r$-dualizing sheaf $...
- 6,083
0
votes
0
answers
24
views
Functors and projective covers
I'm looking to understand how a covariant functor that is an equivalences of categories preserves projective covers, and how a contravariant functor that is a dual equivalence of categories maps ...
- 327
0
votes
0
answers
12
views
Total integrality concept
I do not understand the total integrality concept in the integer optimization.
According to the notes I have, a rational system on linear inequalities $Ax \le b$ with $A \in \mathbb{Q}^{m \times n}, b ...
- 457
2
votes
1
answer
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 ...
- 39.9k
0
votes
0
answers
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 ...
- 39.9k
1
vote
2
answers
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, \\
...
- 332
0
votes
1
answer
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 ...
- 39.9k
0
votes
0
answers
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 ...
- 39.9k
0
votes
0
answers
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}{...
- 45.5k
0
votes
0
answers
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 ...
- 71
3
votes
1
answer
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 ...
CommunityBot
- 1
2
votes
0
answers
46
views
Topoi of algebras vs co-algebras, right adjointness compared to left exactness
I am asking about topoi of coalgebras over a comonad and algebras over a monad.
The comonad statement I am aware of is as follows:
Let $\mathcal{E}$ be a topos. Then if a comonad $T \colon \mathcal{E}...
- 15.4k
0
votes
2
answers
110
views
How to apply complementary slackness
Given the primal
$$\max z= 5x_1-4x_2+3x_3$$
subject to
$2x_1+x_2-6x_3=20$
$ 6x_1+5x_2+10x_3\leq 76$
$8x_1-3x_2+6x_3\geq 50$
with $x_1\in \mathbb{R}, x_2\geq 0,x_3\leq 0$.
The question is to construct ...
- 6,433
0
votes
0
answers
19
views
Degeneracy of dual solutions
I'm new to this forum.
I have a question regarding the degeneracy of dual Solution, which I received in my recent exercise and can't seem to get to a proper solution:
"If a primal LP has a ...
2
votes
1
answer
167
views
Dual space of the space of matrix-valued, continuous functions on a locally-compact, Hausdorff space vanishing at infinity.
Let $X$ be a locally-compact, Hausdorff space, and let $\mathcal{A}:=C_{0}(X)$ the $C^{*}$-algebra of complex-valued, continuous functions vanishing at infinity.
Let $\mathcal{B}:=M_{n}(\mathbb{C})$ ...
- 4,436
0
votes
0
answers
40
views
For 3 straights $l_1,l_2,l_3$ in a 2-dimensional projective space $P(V)$ so that they don’t intersect. How can I prove the following statement:
Given 3 straight lines $l_1,l_2,l_3$ in a 2-dimensional projective space $P(V)$ so that for two on two lines: $l_i \cap l_j=\emptyset$
And $\{V_i\vert i=1,2,3\}\subset V $ and $l_i= P(V_i)$
Can ...
- 97
-1
votes
1
answer
50
views
Is there a positive element on the dual of a Banach space [closed]
Let $ X $ be a Banach space (complex or real). Is this possible $$ \sup_{\Vert x^{∗}\Vert \leq 1} x^{∗}(x) ≥0 \quad \forall x\in X.$$
in some Banach spaces, particularly in the Lebesgue space $ X=L^...
- 103k
1
vote
1
answer
58
views
A certain categorical duality exchanges heads and socles?
Let $K$ be a field. Let $\mathsf{C}$ be an essentially small abelian category in which every hom-space is a finite-dimensional $K$-vector space.
For an object $X\in \mathsf C$ denote by $\operatorname{...
- 15.4k
2
votes
2
answers
90
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:
...
- 41
0
votes
0
answers
23
views
Primal constraints satisfaction
Given $\min_x f(x)$ subject to $g(x) = 0$, we write the Lagrangian as $\mathcal{L}(x,\lambda) = f(x) + \lambda g(x)$ and the dual as $g(\lambda) = \min_x \mathcal{L}(x,\lambda)$.
Let $x^* = \arg\min_x ...
- 289
0
votes
0
answers
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 ...
- 185
0
votes
1
answer
50
views
LP Duality. What is the correct dual to this linear program?
Suppose a linear program that is defined as follows with decision variables $ w, x, y, z$ and parameters $a, b, c_j, d_i$.
$\min \sum_{I}^{} a x_{i} + \sum_{I}^{} b y_{i}$
$s.t.$
$x_{i} \geq w + \...
- 39.9k
0
votes
0
answers
32
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 ...
- 15.4k
0
votes
0
answers
37
views
How to prove strong duality in linear programming using minimax theorem?
Let me provide the details of my request step-by-step.
In the further description, I consider finite $n \in \mathbb{N}$ and $m \in \mathbb{N}$ and $\mathbb{R}$ without $\infty$ and $-\infty$. Set $\...
- 477
5
votes
1
answer
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 ...
- 312k
1
vote
1
answer
216
views
Duality for free abelian groups and for finite abelian groups
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)\...
- 312k
2
votes
0
answers
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 ...
- 101
7
votes
2
answers
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, ...
- 39.9k
2
votes
0
answers
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 ...
- 95
0
votes
0
answers
54
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 ...
- 39.9k
0
votes
1
answer
79
views
How is pole-polar duality related to line-point duality.
The above image is my depiction of what I am calling line-point duality. We can either think of the "point" as the equivalence class of arrows parallel to the large silver arrow ($\mathfrak{...
- 3,279