Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
1,123
questions
1
vote
0
answers
8
views
Is there a result on the maximum value of the dual variable for a parametric LP in terms of the parameters of the LP?
I am working with a linear program of the following kind:
\begin{array}[t]{l}
\min c^{\top} x\\
s.t.\\
\quad A x = b\\
\quad 0 \le x \le x^{u}
\end{array}
Can I find out the upper limit of the shadow ...
- 11
1
vote
1
answer
23
views
Theorem of Alternatives proof only one of the systems is solvable
Let $ A \in R^{nxm}$, $x \in R^n$, $c,y \in R^m$ show that, either
I) $Ax=c$
II) $A^Ty=0, c^Ty=1$
is solvable
I'm completely new to the theorem of alternatives, so my attempt is:
If I is solvable ...
2
votes
0
answers
14
views
Kosual duality for crossed algebra
There are dualities of Koszul type
$$\mathsf{dgAlg} \longleftrightarrow \mathsf{dgCoalg}$$
$$\mathsf{dgLieAlg} \longleftrightarrow \mathsf{dgSymmCoal}$$
$$\mathsf{dgSymmAlg}\longleftrightarrow \...
- 407
1
vote
0
answers
20
views
Coinvariants of coaction $a\otimes b \mapsto \sum{\sigma_i(a)}\otimes \sigma_i(b)\otimes \sigma_i^*$
I've been studying Hopf-Galois Theory and currently I'm trying to understand some examples by writing all the explanations step by step by myself. The example I'm interested now is the classical ...
- 3,430
2
votes
0
answers
87
views
Confusions about function spectrum in Anderson duality
In appendix B of this paper https://arxiv.org/abs/math/0211216, Hopkins and Singer defined the Anderson dual $\tilde{I}(E)$ of a spectrum $E$ as the function spectrum of maps from $E$ to $\tilde{I}$, ...
- 33
0
votes
2
answers
72
views
Proof that markov chain equilibrium using Farkas' lemma
Given a transition matrix for markov chain $ P \in \mathbb R^{dxd} $ such that $$ P_{i,j} \geq 0,\quad
1 \leq (i,j) \leq d, \quad
\sum_{j=1 \in d }P_{i,j} $$
and $i=1,....,d$.
Let $ x_{0}$ be ...
- 27
1
vote
1
answer
15
views
Why is the size of a minimum vertex cover always greater than or equal to a maximal matching?
The topic I am dealing with right now is a 2-approximation algorithm for the minimum vertex cover. The proof seems fairly simple but I don't understand one assumption that is made.
It is the ...
- 319
0
votes
0
answers
28
views
How to find the dual of the curve fitting
I am given the following curve fitting function:
$b(a_{i1},...,a_{in}) = \Sigma_{i=1}^{n}a_ix_i$
so that for several inputs, the output $b(a_{i1},...,a_{in})$ is approximately equal to a given value $...
- 1
1
vote
1
answer
32
views
Computing the dual of an LP with equality constraints
I am having a linear program in the form :
\begin{cases}
\min_x\ \ -5x_1 + 27.5x_2 + 4.5x_3 + 12x_4\ \ \mathrm{s.t.}\ \\ \ \\
\qquad\qquad 0.25x_1 − 2.75x_2 − 1.25x_3 + 4.5x_4 + 0.5x_5 = 0\\
\...
- 605
4
votes
0
answers
32
views
Is existence of adjunction between $a\otimes{-}$ and $b\otimes{-}$ enough for duality?
Let $(\mathfrak{C},\otimes,1)$ be a monoidal category. An object $a$ is dual to $b$ if there exist evaluation $ev\colon a\otimes b\to 1$ and coevaluation $coev\colon 1\to b\otimes a$ morphisms ...
- 115
-2
votes
1
answer
18
views
Duality optimisation
enter image description here
Questions. what does that symbol mean between Ax and b?
he has moved the b to Ax-b in the subject too section is this because all constraints have to be on one side ? if ...
2
votes
2
answers
96
views
Why is $\phi_\mu(x)= \int_{\widehat{G}} \xi(x)d\mu(\xi)$ a continuous map?
Let $G$ be a locally compact Hausdorff abelian group. Let $\widehat{G}$ be its dual group, consisting of the unitary characters $G \to \mathbb{T}$. If $\mu \in M(\widehat{G})$ (= complex Radon ...
- 985
0
votes
0
answers
19
views
Conjugate functions - general definition and understanding
I am currently studying Stephen Boyd, where the conjugate function is defined to be $f^*(y) = \underset{x \in Dom(f)}{sup} (y^Tx-f(x))$.
I understand the definition, but when I search for more ...
- 1
0
votes
0
answers
21
views
Finding the dual of a problem $\min_{w,b} \sum_{j=1}^{n}{\max(0,w_j)}$
Consider the optimization problem for support vector machine with
$(x_i,y_i),i=1,2,\ldots,m$ is the training data set
$y_i=\{-1,1\}$
$w\in \mathbb R^n$
$\min_{w,b} \sum_{j=1}^{n}{\max(0,w_j)}\\\text{s....
- 33
0
votes
0
answers
39
views
Inequality for Sobolev trace spaces of negative order
Is anyone aware of an explanation or reference on whether or not one may estimate
$$ \|f\|_{H^{-1}(\partial\Omega)} \leq C \|f\|_{L^2(\Omega)}, $$
where $f\colon\Omega \to \mathbb{R}$ is a smooth and ...
- 88
1
vote
1
answer
33
views
Convex and Lipschitz implies "bounded" subgradient in Banach spaces
In this question: Lipschitz implies bounded gradient it is shown that if $f: \mathbb{R}^n \to \mathbb{R}^n$ is convex and L-Lipschitz the gradient is bounded by L. I wonder if this holds in Banach ...
- 747
0
votes
0
answers
17
views
dual of a LP constraint
Consider the minimization problem
minax1+bx2
s.t:
x1(i,j)-sum(i,x1(i,j))<=0 for each j
that both varibales in the constraint is equivalent. so what is the constraint for x in the dual problem? how ...
0
votes
1
answer
16
views
How to find more (maybe: all) natural isomorphisms with vector space and tensor constructions
Background: I am refreshing my knowledge of tensor dualities to catch up with some physical applications.
Example 1: I am aware that $\mbox{Hom}(V, \mbox{Hom}(W,U))$ is naturally isomorphic to
$\mbox{...
3
votes
0
answers
35
views
Star-autonomous categories are linearly distributive categories with negation?
1.Context
On page 28 of Weakly distributive categories Cockett and Seely are trying to prove the following statement:
The notions of symmetric weakly distributive categories with negation and star-...
- 1,939
6
votes
0
answers
158
views
Graphical calculus for star-autonomous categories?
1. Definiton
Let $(C, \otimes, I, a, l,r)$ be a (not necessarily symmetric) monoidal category.
A (planar) star-autonomous structure on the monoidal category $C$ consists of an adjoint equivalence $D \...
- 1,939
0
votes
1
answer
34
views
Lagrange function and strong duality in an optimization problem
Suppose we have an (not necessarily convex) optimization problem :
$$\begin{split}\min_x f_0(x)\\ f_1(x)\leq 0. \end{split}$$
Let $L(x,\lambda)=f_0(x)+\lambda(f_1(x))$. Then the above problem
can be ...
- 788
2
votes
2
answers
54
views
How does the duality functor with respect to $K$ behave on morphisms?
In A duality formalism in the spirit of Grothendieck and Verdier Boyarchenko and Drinfeld give the following definition of the terms dualizing object and duality functor:
An object $K$ in a monoidal ...
- 1,939
2
votes
1
answer
32
views
Projective Geometry and Duality
On duality, what would be the dual of "coplanar points"?
Let's say $p_1, p_2, p_3 \in \mathbb{P}^3$ are coplanar points, i.e. they all belong to a plane $\pi$. If I want to "translate&...
- 440
0
votes
2
answers
67
views
Closed form solution of the following linear programming question
I want to ask whether the following question has a closed form solution:
$$
\begin{cases}
\displaystyle\min_{x} c^T x \\
\mbox{ s.t. } \\
\mathbf{1}^Tx = b \\
\quad x \geq 0
\end{cases}
$$
We can ...
- 77
1
vote
1
answer
34
views
How good is an optimal solution of the Lagrangian relaxation of an integer linear program?
From what I learned, the Lagrangian relaxation of an integer program is used to find a bound. Is the solution to the relaxed problem considered to be a good approximate solution of the original ...
- 45
1
vote
0
answers
45
views
If $x$ is a feasible solution, satisfies complementary slackness, show that $x$ is a basic feasible solution.
Consider the linear programming problem
$$
\begin{aligned}
&\min&& c^{T} x \\
&\operatorname{s.t. } && A x=b \\
&&& x \geq 0,
\end{aligned}
$$
and its dual ...
- 11
1
vote
1
answer
19
views
What is the dual of a variable that is not in the constaint but in the cost function
Suppose you have the following LP where c is a constant.
$$ \min cx_1 + x_2$$
$$x_2 = 1 $$
$$ x_1, x_2 \geq 0$$
What is the dual of this LP problem?
If I pad zeros, I would get something like
$$\max ...
- 91
1
vote
0
answers
43
views
Looking for the IBM report: Beckman, Categorical notions and duality in automata theory
I am desperately looking for an old IBM research report, cited at the end of Chapter 3 in Samuel Eilenberg's book Automata, Languages and Machines (1974):
Beckman, Categorical notions and duality in ...
- 36.2k
0
votes
1
answer
32
views
Serre duality and symmetric product
Let $X$ be a complex surface, $K$ the canonical divisor, $F$ a rank 2 vector bundle on $X$, $n$ a positive integer, $S^nF$ the $n$-th symmetric product of $F$, $P$ a rational divisor, and $a$ a ...
- 2,034
0
votes
0
answers
23
views
Bidual of a space and Legendre-Fenchel transform
Suppose I have a convex and lower semi-continuous functional $\psi:C_c(\mathcal{X})\to\mathbb{R}$ and that I know of a representation of the form:
\begin{equation}
\Lambda(\mu)= \sup_{f\in C_c(\...
- 805
1
vote
0
answers
46
views
Is this duality result true, i.e., $\|f\| := \sqrt{\|f\|_1^2 + \|f\|_2^2} \implies |x|^2 =\inf_{y\in E} \left [ |x-y |_1^2 + |y|_2^2 \right ]$?
Let $(E, |\cdot|_1)$ be a normed vector space (n.v.s) and $(E', \| \cdot \|_1)$ its dual. Let $|\cdot|_2$ be an equivalent norm of $|\cdot|_1$ on $E$, and $\| \cdot \|_2$ its dual norm on $E'$. In a ...
- 1,153
2
votes
0
answers
23
views
Legendre-Fenchel dual on general spaces
I have some questions on duality and Legendre-Fenchel Transform, and I hope some of you can help (perhaps providing some references as well). All the books/references I looked at on functional ...
- 805
0
votes
0
answers
17
views
Proof that the Dual of an LCA Topological Group is LC with the compact-open topology
Let G be a LCA Topological Group, I define it's dual group, $\Gamma$, by the group of continuous characters $$\gamma:G\to\mathbb{T}$$ where $\mathbb{T}$ is the complex unit circle. I want to equip ...
0
votes
1
answer
21
views
Why is there a sign change for variables when going from primal LP problem to dual LP problem?
I have this primal problem:
$$Z = -2x_1+2x_2+10x_3+4x_4+2x_5 \to \min$$
$$\begin{pmatrix}
-1 & 1 & 2 & 0 & -2\\
-1 & -1 & 1 & 1 & 1\\
\end{pmatrix}
\begin{pmatrix}
x_1\\...
3
votes
0
answers
105
views
Closed form solution for a quadratic program in matrix form with inequality constraint
Is there a closed form solution for the following quadratic program with inequality constraint? Let $P \in \mathbb{S}^n_{++}$ be a symmetric positive definite matrix, and $B$, $F \in \mathbb{R}^{k \...
- 710
0
votes
0
answers
39
views
Duality in laplace transform
Is there any intuition behind this ?
I mean something that help you memorize this (I always make mistake ) :
$$e^{-at}f(t) \xrightarrow {\text{laplace transform}} F(s+a) $$
$$f(t-a) \xrightarrow {\...
- 55
0
votes
0
answers
25
views
Convert Dual LP to a Network Flow Problem
Consider the Dual LP:
$$ \min\sum_{e\in E}c_ey_e$$ s.t.: $$\sum_{e:e\in p}y_e\ge 1\ \ \text{for each}\ \ p\in \mathcal P\\ y_e\ge 0$$
$e$: Represents an edge in $E$
$c_e$: Max flow capacity of an ...
- 477
0
votes
0
answers
30
views
Does a $\mathbb P^1$ with four embedded points have the same dualizing sheaf as $\mathbb P^1$?
Suppose $X$ is a $\mathbb P^1$ with four distinct embedded points, looking locally like $\operatorname{Spec} \mathbb C[x,y] / (x^2, xy)$. I think a subresult of some work I'm doing would be that the ...
- 4,432
3
votes
0
answers
38
views
Dual of braiding in symmetric monoidal category
Let $(\mathcal{C},\otimes,1)$ be a symmetric monoidal category with symmetry $\gamma$.
Assume $X,Y\in\mathcal{C}$ are a dual pair in the sense that there exist evaluation and coevaluation morphisms $...
- 115
0
votes
1
answer
62
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, \\
...
- 691
1
vote
0
answers
36
views
Left versus right dualizability in a braided monoidal category
Let's say we have a duality between two objects $X$ and $Y$ in a braided monoidal category given by $c \colon \mathbb 1 \to X \otimes Y$, $e \colon Y \otimes X \to \mathbb 1$. I was wondering whether ...
- 53
0
votes
1
answer
28
views
What is a Dual Of a Line Segment?
According to duality, dual of a line is a point. If there is a point p(x,y) exists in a plane, If i take dual of this I will get $ax + by = 1$ a line.
But what will be the dual of a line segment. Will ...
- 280
1
vote
0
answers
35
views
How to dualize norm-constrained optimization problem?
Consider the following optimization problem:
\begin{equation*}
\begin{aligned}
& \underset{x\in\mathbb{R}^{+}}{\text{min}}
& & c^{T}x \\
& \text{s.t.}
& & ||x-\hat{x}||_{q} \...
- 11
-2
votes
1
answer
38
views
Unbounded Operator not bounded on any ball
I came across a small proof where the following implication was used:
Let $X$ be a normed v.s. and $T \in X'$ an unbounded operator ( $X'$ denotes the dual of $X$ ), i.e.
$$ \| T (x) \| \gt M \| x ...
- 3
3
votes
0
answers
60
views
The Duality of Electricity and Magnetism
$\DeclareMathOperator{\Hom}{Hom}\DeclareMathOperator{\Gal}{Gal}$In pure mathematics, the idea of duality pops up all over the place, and most generally (as far as I know) it can be defined in category ...
- 16.2k
0
votes
0
answers
28
views
Is the dual problem unique?
I am studying duality (in terms of linear programming) right now and I am a bit confused about one thing. I learned duality as a (linear combination of constraints)-concept.
Take the primal problem $$...
- 11
2
votes
1
answer
42
views
$\int_E f_ng \to \int_E fg$ implies $\{\|f_n\|_p\}$ is uniformly bounded
Assume $E$ has finite measure, $\{f_n\}$ is a sequence of functions in $L^p(E)$, and $f$ is in $L^p(E)$, $1<p<\infty$. Suppose $\lim_{n\to\infty}\int_Ef_ng=\int_Efg$ for all $g\in L^q(E)$. ...
- 4,300
1
vote
1
answer
46
views
how to define the dual of a primal assignment-like program with Hadamard product as a cost function?
I need to define the dual of the assignment-like problem where the cost function is defined as the Hadamard product of two matrices $C=[c_{ij}]$ and $X=[x_{ij}]$ as follows:
\begin{align}
\text{...
- 11
1
vote
1
answer
71
views
How to solve a quadratic programming problem with constraint that is also an linear optimization problem?
Let's say we have $n\times 1$ vector $f$ and $h$, $n\times n$ matrix $A$ and $B$, $m\times n$ matrix $R_1$ and $R_2$, $m\times 1$ vector $b_1$ and $b_2$. Now I try to solve the following problem:
$$\...
- 43
12
votes
2
answers
519
views
Are all isomorphisms between the Fano plane and its dual of order two?
Famously from every finite projective plane $P$ we can create a dual projective plane $P'$ by taking the points of $P'$ to be the lines of $P$ and the lines of $P'$ to be the points of $P$.
It is also ...
- 9,215