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
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 ...
user avatar
  • 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 ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 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}$, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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\\ \...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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{...
user avatar
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-...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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&...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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(\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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\\...
user avatar
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 \...
user avatar
  • 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 {\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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, \\ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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} \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $$...
user avatar
  • 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)$. ...
user avatar
  • 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{...
user avatar
  • 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: $$\...
user avatar
  • 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 ...
user avatar
  • 9,215

1
2 3 4 5
23