Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
1,252
questions
1
vote
0
answers
17
views
Dual space as analogous of inner products, what does it mean?
Currently reading through Optimization by Vector Space methods, specifically chapter 5 Dual Spaces.
I've read several times about this topic, but there's a specific insight here that I've never ...
- 5,253
2
votes
0
answers
49
views
“Dual object” as set of irreps of a finite group
In Barry Simon's Representations of finite and compact groups he refers to the set of irreps (or rather equivalence classes thereof) of a given finite group $G$ as the “dual object” $\widehat G$
...
- 131
1
vote
0
answers
66
views
Is there a closed form to this quadratic program?
Problem :
I am currently trying to solve some optimization problem to get some information about a matrix. In the following, when we have a matrix $A\in\mathbb R^{m\times n}$, $0\leq A$ means that $0\...
- 5,517
-3
votes
0
answers
13
views
Find the dual problem for the primal LPP and solve it. [closed]
Find the dual problem for the primal LPP and solve it.
Maximize $Z = 50X_1 + 40X_2$
Subject to $3X_1 + 5X_2 \leq 150$
$X_2 \leq 20$
$8X_1 + 5X_2 \leq 300$
and $X_1 \geq 0, X_2 \geq 0$
1
vote
0
answers
28
views
Axler: Describe linear functionals $T'\psi_i$ for the linear map $T(x,y,z)=(4x+5y+6z, 7x+8y+9z)$ when $\psi_i$ denote dual basis of $\mathbb{R}^2$.
The following is problem 13 from chapter 3F of the third edition of Axler's Linear Algebra Done Right
Define $T:\mathbb{R}^3\to\mathbb{R}^2$ by
$$T(x,y,z)=(4x+5y+6z, 7x+8y+9z)\tag{1}$$
Suppose $\...
- 4,579
-1
votes
0
answers
48
views
Proof dual of Pappus' Theorem
I have to proof the dual of Pappus' Theorem just like exercise 4.6.1 in "Modern Geometry with Applications" (Jennings,1997) and don't know what to do. The following hint is given:
(Regard $...
- 83
0
votes
0
answers
24
views
Has the Pontryagin dual of a module the same length of the original module?
Let $M$ be a topological module over a complete noetherian local commutative ring $R$ of finite residue characteristic $p$. Its Pontryagin dual is defined to be $M^\vee:=Hom_{cont}(M,\mathbb{Q}_p/\...
- 407
1
vote
0
answers
54
views
How to determine that the problem is unbounded when using Dual Simplex Method? How to prove infeasibility of problem using dual simplex method?
This is how we got the dual simplex method explained: With this method we solve a primary problem, not a dual one, in the primary simplex method (that is, in the standard method for the minimization ...
- 19
0
votes
0
answers
25
views
Interpreting theorem that dual map $T'$ injective $\iff$ $T$ surjective.
Consider the following theorem (Axler, Linear Algebra Done Right 3rd Ed., Theorem 3.108)
$T$ surjective is equivalent to $T'$ injective.
Suppose $V$ and $W$ are finite-dimensional and $T\in L(V,W)$. ...
- 4,579
0
votes
1
answer
56
views
How to prove projective duality?
I am currently in Chapter 12 of 'Lemmas in Olympiad Geometry' by Titu Andreescu et al. They have stated and given a satisfactory proof Brianchon's Theorem using poles and polars as well as Pascal's ...
- 51
4
votes
1
answer
95
views
Precise statement of Poincaré duality
Let $(M,g)$ be a (not-necessarily compact) oriented, connected Riemannian manifold. Lets consider the pairing
$$\Omega^{k}(M)\times\Omega^{d-k}_{c}(M)\to\mathbb{R}, (\alpha,\beta)\mapsto\int_{M}\alpha\...
- 2,496
0
votes
0
answers
47
views
Constrained Minimum Cut Problem
I am trying to find a polynomial time algorithm or a reduction to an NP-hard problem for the following version of the minimum cut problem:
given: Directed Graph $G=(V,R)$, source node $s \in V$ and ...
3
votes
1
answer
76
views
The inverse map of the Poincare duality map
Let $M$ be an oriented compact smooth manifold of dimension $n$. Let $[M]$ be the fundamental class of $M$, that is, $[M]\in H_n(M, \mathbb Z)$. Then, the Poincare duality map is the isomorphism given ...
- 912
0
votes
0
answers
6
views
Double dual basis for projective modules
It is standard that an $A$-module $P$ is projective iff. there exist elements $p_i \in P$ and $\bar{p}_i \in \hom_A(P, A)$ for $i$ in some indexing set $I$ such that for all $q \in P$, we have
$$q = \...
- 2,184
2
votes
1
answer
63
views
Pontryagin duality and quotient groups
I am studying the Pontryagin duality for LCA groups, and I came across two results in which I am finding some difficulty.
Here I will denote by $G^*$ the dual of the group $G$, i.e. the group of all ...
2
votes
1
answer
128
views
Dual of Model Weil group $E(K)$ over a local field $K$ is $H^1(G_K,E)$
Let $K$ be a local field.
Let $G_K=Gal(\overline{K}/K)$ be an absolute Galois group of $K$.
Let $E/K$ be an elliptic curve over $K$.
Let $E(K)^*=Hom_{\Bbb{Z}}(E(K),\Bbb{Q}/\Bbb{Z})$ be a Pontryagin ...
- 5,509
1
vote
1
answer
80
views
$\#imagef=\#imagef^*$, order of image of dual and image of original homomorphism is the same
Let $M$ be an abelian group
Let $M^*=Hom_{\Bbb{Z}}(M,\Bbb{Q}/\Bbb{Z})$ be pontryagin dual of $M$.
Let $M$ be a finite group.
Let $M'$ be an abelian group. Let $f:M\to M'$ be a homomorphism of abelian ...
- 5,509
2
votes
0
answers
27
views
Is $k[x, x^{-1}]$ a (graded) injective $k[x]$-module
Consider $k[x]$ with the usual grading, and the graded $k[x]$-module $k[x, x^{-1}]$. Is it injective? I suppose yes, because it is torsion free and graded divisible (i.e., divisible by homogeneous ...
- 2,184
0
votes
3
answers
103
views
Is the metric space c0 of sequences of real numbers converging to zero is isometric to the metric space $\ell^1(\mathbb{N})$
Is the metric space c0 of sequences of real numbers converging to zero is isometric to the metric space $\ell^1(\mathbb{N})$
To begin this proof do I need to show that:
c0 is complete in $\ell^1(\...
- 171
0
votes
0
answers
38
views
why is it using max for dual form problem for SVM?
Context
SVM: From Primal to Dual
Primal form:
$$\min_{w, b} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^M \xi_i$$
subject to $y^{(i)}(w^T x^{(i)} + b) \geq 1 - \xi_i$, $i = 1, \ldots, M$, and $\xi_i \geq 0$, $...
- 23
1
vote
0
answers
95
views
Dual of Dual problem of a simple convex Quadratic problem
I am trying to verify the
the dual of the dual is the primal? using a simple convex QP:
\begin{align}
\min_x& \frac{1}{2} x^\top H x + h^\top x\\
\text{s.t.} &~Ax\leq b \\
&~ A_e x = b_e
\...
- 139
1
vote
1
answer
85
views
Pontlyagin dual of direct sum,$ \widehat{\bigoplus_{i\in \Lambda} M_i} = \prod_{i\in \Lambda} \hat{M_i}. $
Let $M_i$ (for $i \in \Lambda$) be a family of abelian groups.
Let $\bigoplus_{i\in \Lambda} M_i$ denote the infinite direct sum of the groups $M_i$.
Let $\hat{M}$ denote the Pontryagin dual of the ...
- 5,509
0
votes
1
answer
66
views
Equivalent Formulations of Variational Problems
This post is supposed to collect some Theorems and techniques which can be used to analyse variational problems by (a) finding a related variational problem s.t. their optimal values are the same or ...
- 1,847
0
votes
1
answer
35
views
What do Kassel, Rosso, and Turaev mean by "duality"?
In their book "Quantum Groups and Knot Invariants", Kassel, Rosso, and Turaev prove that $U_q\mathfrak{sl}(N+1)$ has a PBW basis. I'm having trouble following the last step, though.
In ...
- 303
0
votes
0
answers
14
views
how to solve for wasserstein duality easily in a special case when 2-Wasserstein inequality constraint is binding
I was going through this nice paper ” A Simple and General Duality Proof for
Wasserstein Distributionally Robust Optimization”, and one quick qu on applying Theorem 1 to my poject:
What if in my ...
- 61
6
votes
1
answer
201
views
Riesz representation theorem for functionals acting on Hölder $C^\alpha$ functions
Assume you have a linear functional $F:C^\alpha(\mathbb R^n) \mapsto\mathbb R$ such that
$$
|F(f)| \leq \vert f \vert_{C^\alpha(\mathbb R^n)}
$$
but only depending on the Holder seminorm, that is,
$$
...
- 307
0
votes
2
answers
94
views
Are the dual basis functionals not linear maps?
Sheldon Axler's Linear Algebra Done Right defines the dual basis as follows:
Specifically, the dual basis of a basis $v_1, \ldots, v_n$ is the list $\delta_1 \ldots \delta_n \in V'$. However, I ...
1
vote
2
answers
45
views
When is the (Fenchel-Rockafellar) duality gap strictly positive?
In optimization, there is a notion of the duality gap, $\Delta$ which is always positive $\Delta\geq 0$. The condition $\Delta=0$, called strong duality, is sometimes quite convenient in the analysis ...
- 4,168
0
votes
0
answers
33
views
Could a linear programming problem be solved by dual (subgradient) methods?
Consider a linear programming (LP) with inequality constraints:
$$
\text{min}\quad f(x) = c^Tx \\
\text{s.t.} \mu: Ax \leq b, \\
\quad x\in X.
$$
where $X$ is a convex set. $\mu$ is the dual variable,...
2
votes
0
answers
60
views
Is there some dual view of set theory where sets and elements roles are switched?
In some project, I am comparing some sets on the basis of the elements they contain. My data can be represented as a binary matrix $M$ with sets in rows and elements in colunms. Entry $M_{ij} = 1$ if ...
- 133
3
votes
1
answer
77
views
Intuition behind duality in linear programming
I'm looking for an intuitive explanation of the duality principle in Linear Programming.
About having a solution or not:
Farkas' Lemma: $A x=b ; x \geq 0$ has a solution <=> $A^T y \geq 0 ; b^T ...
- 61
0
votes
1
answer
39
views
Lidded Box Optimization: Solve Unfolded Area Minimization Problem given its Dual Volume Maximization Problem
The above volume maximization problem is simple to solve. What would its dual, the unfolded area minimization problem look like, given fixed volume of $V=\frac{8000}{27} \approx 296.3$? I would hope, ...
- 3,332
1
vote
0
answers
59
views
Definition of finite-dimensional 'self-dual algebra' over a field
In some informal notes that are not publicly available and for which I do not have permission to reproduce here, there is a reference to a 'finite-dimensional self-dual algebra over a field $K$'.
I ...
- 3,304
0
votes
0
answers
21
views
Compare shadow prices of one specific constraint in two similar LPs.
I am working with two similar Linear Programming (LP) problems involving nine decision variables.
Here's a representation of the two problems, with the only difference in the third constraint:
LP1:
\...
- 53
1
vote
1
answer
44
views
Subgroups of self dual groups
Let G be an infinite locally compact abelian group that is isomorphic to its own dual. If H is a closed subgroup of G, is it necessarily true that $H \cong \widehat{G/H}$?
I ask because in the case of ...
- 706
0
votes
0
answers
43
views
Derivation of closed form lasso dual
Want to understand how the dual function is derived https://www.stat.cmu.edu/~ryantibs/convexopt-F18/lectures/dual-corres.pdf (Slide number 13)
Minimizing with respect to $\beta$ is clear, however, ...
- 151
0
votes
0
answers
24
views
How could we calculate this duality pairing?
I'm reading a paper recently and have come across with the concept of duality pairing and test function. In particular, I met a function $Z$ on $\mathbb{R}\times \mathbb{R}^d,$ which is the solution ...
- 175
0
votes
0
answers
16
views
When using primal-dual optimization methods, does s denote the lagrange multiplier, the slacks or both?
I'm currently looking into optimization, specifcally into primal-dual interior point methods to solve nonlinear, convex, and constrained optimization problems.
I face problems of type
$$\mathrm{min} f(...
0
votes
0
answers
20
views
Dual graph relation to star-mesh duality
I'm confused about the realtionship between dual graphs and the so called star-mesh transformation: https://en.wikipedia.org/wiki/Star-mesh_transform.
Take a simple triangle, its dual graph looks like ...
0
votes
0
answers
36
views
Minimal number of edges in G that must be removed to separate two nodes.
This is the question I am trying to answer: Let $G = (V,E)$ be a directed graph and $s,t$ $\epsilon$ $V$ with $s$ $\neq$ $t$, prove that the minimal number of edges in G that must be removed in order ...
- 1
9
votes
1
answer
266
views
Weird duality between integers and p-adic integers
The integers are, up to isomorphism, the unique infinite discrete abelian group that is isomorphic to all its non-trivial subgroups. This can be seen easily by Pontryagin Duality: It's equivalent to ...
- 706
0
votes
0
answers
27
views
An Ideal Correspondence For Twisted C*-Dynamical Sytems?
Back in the 90's, Nilsen proved the following result for normal $C^{*}$-dynamical systems:
Suppose that $A$ is a $C^{*}$-algebra, and $G$ is a locally compact group.
Let $\delta$ be a coaction of $G$ ...
- 1,049
0
votes
0
answers
20
views
Dual simplex computational feasibility when applied to primal problems with many bound variables
Assuming primal simplex problem in form of
$$
\displaylines{
\begin{align}
(P) & \\
\text{min} \ & c^Tx \\
\text{s.t.} \ & Ax = b \\
& -\infty \lt l \le x \le u \lt \infty \\
A \ \...
- 1
2
votes
1
answer
83
views
How to solve the primal problem via Lagrangian directly?
From section 5.5.5 of Convex Optimization by Stephen Boyd and Lieven Vandenberghe https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf, consider the primal problem
$$\begin{cases}
\min:\ f_0(x)\\
\...
- 171
0
votes
0
answers
27
views
Factor of a dual curve
Suppose that for a homogeneous polynomial $f(x,y,z)$ we have $f(x,y,z)=g(x,y,z) \cdot h(x,y,z)$. Assume $f_d$ and $g_d$ are the dual curves of $f$ and $g$ respectively. Is it true that $g_d$ is a ...
- 163
0
votes
0
answers
29
views
dual norm optimization problem, how to dervie the second formula from the first one?
There is a post that someone answered it already, but I think his/her answer is how to validate the formula, not the way to derive the formula.
A dual norm optimization problem
This formula comes from ...
1
vote
0
answers
66
views
Determining bound of LP knowing dual variables
I have a simple LP of the form:
\begin{align*}
\text{maximize } & c^Tx\\
\text{s.t. } &A_1x = b_1 \\
&A_2x \le b_2 \\
&x\ge0
\end{align*}
with $x\in R^n$, $A_1 \in R^{m\times n}$, $...
- 11
0
votes
1
answer
27
views
Imai - Takai duality for reduced crossed products?
I'm currently looking for a citation to a statement of Imai-Takai duality, specifically for reduced $C^{*}$-algebra crossed products, and I can't seem to find one.
It's clear to me that such a result ...
- 1,049
0
votes
0
answers
38
views
Dual of the SDP relaxation in Yinyu Ye's paper
I was stuck in computing the dual problem in a paper by Yinyu Ye which raises an SDP relaxation such that
$$ \min_{Z \in \mathcal{K}} \left\{ h(Z) := \sqrt{\sum_{(i, j) \in \mathcal{E}} \gamma_{ij}^2 (...
1
vote
1
answer
48
views
Let $f:V \times W \to \mathbb F$ and $s:V \to W^*, r:W \to V^*$. Find $[s]^B_{C^*}, [r]^C_{B^*}$.
Let $f:V \times W \to \mathbb F$ bilinear map and $s:V \to W^*, r:W \to V^*$ linear transformations s.t: $s(v)(w) = f(v,w)$ and $r(w)(v) = f(v,w), \forall v \in V$ and $\forall w \in W$. Let $B$ an ...
- 411