Questions tagged [duality-theorems]

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

Filter by
Sorted by
Tagged with
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 ...
user8469759's user avatar
  • 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$ ...
jajaperson's user avatar
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\...
P. Quinton's user avatar
  • 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$
khalid Ahmed's user avatar
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 $\...
evianpring's user avatar
  • 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 $...
jaki's user avatar
  • 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/\...
Fraz's user avatar
  • 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 ...
Zam's user avatar
  • 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)$. ...
evianpring's user avatar
  • 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 ...
Sid N's user avatar
  • 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\...
B.Hueber's user avatar
  • 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 ...
CookieMonster98's user avatar
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 ...
Flavius Aetius's user avatar
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 = \...
Bubaya's user avatar
  • 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 ...
Alice in Wonderland's user avatar
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 ...
Pont's user avatar
  • 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 ...
Pont's user avatar
  • 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 ...
Bubaya's user avatar
  • 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(\...
ugjumb's user avatar
  • 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$, $...
Kenny Ynnek's user avatar
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 \...
Stephen Ge's user avatar
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 ...
Pont's user avatar
  • 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 ...
Small Deviation's user avatar
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 ...
Petra's user avatar
  • 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 ...
numpynp's user avatar
  • 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, $$ ...
HHN's user avatar
  • 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 ...
Christopher Miller's user avatar
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 ...
Zim's user avatar
  • 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,...
Ruihao Wang's user avatar
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 ...
Instanton's user avatar
  • 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 ...
Ronald's user avatar
  • 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, ...
EthanAlvaree's user avatar
  • 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 ...
user829347's user avatar
  • 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: \...
Bryan's user avatar
  • 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 ...
Pedro Lourenço's user avatar
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, ...
GPrathap's user avatar
  • 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 ...
Chang's user avatar
  • 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(...
CrownUpKid's user avatar
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 ...
furious.neutrino's user avatar
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 ...
Sulla's user avatar
  • 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 ...
Pedro Lourenço's user avatar
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$ ...
Isochron 's user avatar
  • 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 \ \...
koromo's user avatar
  • 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)\\ \...
Zifeng Zhang's user avatar
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 ...
Ruben's user avatar
  • 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 ...
containletters's user avatar
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}$, $...
luk767's user avatar
  • 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 ...
Isochron 's user avatar
  • 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 (...
ENTONG HE's user avatar
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 ...
MathStudent101's user avatar

1
2 3 4 5
26