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
0
answers
57
views
Reformulating a Dual Problem
Let the following dual problem be given:
$$\sup_{p}\inf_{z, w, b}\left\{ J(z) + \frac{\alpha}{2}\vert\vert w\vert\vert^2 - \langle p, A^T w - yb - z\rangle \right\} \qquad (\mathcal D),$$
where $w\in \...
- 602
1
vote
1
answer
39
views
If $uA=0, u\geq0, u1=1$ has not solution then $Ax<0$ yes has solution.
Prove that given a matrix $m \times n$, the system $A x < 0$ has
solution if and only if $u A = 0, u \geqslant 0, u 1 = 1$ has not solution.
My attempt:
I was able to prove the necessary condition ...
- 165
1
vote
1
answer
90
views
proving strong duality from Farkas
I am confused about a step in showing how the Farkas Lemma (really, Gale's theorem) can be used to prove strong duality in linear programming.
Consider the following duality pair of LPs:
By weak ...
- 2,488
1
vote
0
answers
45
views
Dual problem of a Generalized Wahba Problem with additional translation
I have the following optimization problem
$$\min_{M \in SO(3), \mathbf{t} \in \mathbb{R}^3, \mathbf{v} \in \mathbb{R}^3} \sum_i^n \lVert M (\mathbf{p}_i + R_i \mathbf{v}) + \mathbf{t} - \mathbf{q}_i \...
1
vote
1
answer
597
views
What if we found many points satisfying KKT conditions
I have the following convex optimization problem:
\begin{equation}
\begin{aligned}
\max_{x} & \quad f(X)\\
s.t. &\quad \sum\limits_{j=1}^N A_{ij}X_{ij} - \sum\limits_{j=1}^N A_{ji}X_{ji}= 0, \...
- 534
1
vote
1
answer
95
views
Dual of $Cc(X)$ with LB-Topology
I'm currently reading on the Riesz-Markov Representation Theorem which identifies positive linear functionals with certain Radon measures. However, in the project I'm working on, I'm dealing with a ...
0
votes
0
answers
68
views
Problem 5.27 of Boyd & Vandenberghe's Convex Optimization
The following question is question no. 5.27 on p. 282 of Boyd & Vendenberghe's Convex Optimization (Cambridge University Press, 7th Printing, 2009):
Consider the equality contrained least-squres ...
- 11k
2
votes
0
answers
69
views
About the economic interpretation of the dual of a L.P
I am reading the Bazaraa, Linear Programming, and there is something I do not understand about the economic interpretation of the dual
Exactly the part where says
If the right hand side $b_i$ is ...
- 337
0
votes
1
answer
52
views
Trying to derive dual formula for linear programming
I have the following basic linear optimization problem. Let $A \in \mathbb{R}^{n,n},c\in \mathbb{R}^n$, then solve
$$\inf_{x \in \mathbb{R}^n} c^Tx,\ \text{ s.t. }\begin{cases}A^Tx=c \\x_i \geq 0, i=1,...
- 979
2
votes
1
answer
65
views
If $G$ is a subgroup of the circle, then why is $\{(\text{id}\colon G\to\mathbb{T})^{n}:n\in\mathbb{Z}\}$ dense in the dual $\widehat{G}$?
Let $G$ be any subgroup of the circle $\mathbb{T}$ and endow $G$ with the discrete topology. Let $$\text{id}\colon G\to\mathbb{T}$$ be the inclusion map. Why is $$\{\text{id}^{n}:n\in\mathbb{Z}\}$$ ...
- 3,178
1
vote
1
answer
470
views
Dual of Quotient Space of a dual
Let $X$ be a nonreflexive banach space, $X^\ast$ its dual and $U$ some closed subset of $X$. Denote with $U^\perp$ the annihilator of $U$ given by
$$
U^\perp = \{ x^\ast \in X^\ast \;|\; \forall x\in ...
- 482
0
votes
1
answer
79
views
Discreteness of Pontryagin dual of compact abelian group
We have the following theorem:
If $G$ is a compact (Hausdorff) group, then the Pontryagin dual $\widehat{G}$ is discrete.
Does this also imply that $\widehat{G}$ is countable? Or is it possible that,...
- 3,178
1
vote
1
answer
52
views
How does one derive this dual from the primal?
On page 22 in https://tel.archives-ouvertes.fr/tel-02926037/document it states the dual problem to the primal optimal transport problem:
So the primal is $\min_x -\epsilon\langle\exp(\frac{-w}{\...
- 1,300
0
votes
0
answers
21
views
Confusion about signed Radon measures, Continuous functions and duals
I am studying Radon measures and the duals spaces. There are many slightly different versions of the associated spaces and I am trying to wrap my head around which is related to which space of ...
- 482
0
votes
0
answers
136
views
Dual Linear Program for Load Balancing - how to write the dual of an LP with summations?
Load Balancing Problem: The input consists of $n$ jobs $J_1, J_2, \dots J_n$ and an integer $m$ denoting the number of machines. The size of $J_i$ is a non-negative number $s_i$. The goal is to assign ...
- 33
4
votes
0
answers
126
views
Inequality constrained norm minimization
I am trying to understand the solution for the following optimization problem:
$\max_w \mu^Tw - \gamma||w-w_0||_1 \text{ s.t. } \phi^Tw = 0.2$
where $\mu, w, w_0, \phi \in R^{N x1}$ and $\mu, w_0, \...
- 165
0
votes
1
answer
166
views
Dual isogeny of purely inseparable isogeny is not always purely inseparable
Let $φ$ be purely inseparable isogeny of elliptic curves.
Then, dual isogeny of $φ$ is always purely inseparable?
Background
Super singular elliptic curve over a field of characteristic $p$ is defined ...
- 4,305
0
votes
0
answers
113
views
What is the infimum over $x$ of the lagrangian function?
I am learning about duality in convex optimisation. The Lagrangian is defined as $$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^p\nu_ih_i(x)$$ where suppose the optimisation ...
- 157
0
votes
1
answer
88
views
Finding Co-Differential from Differential in Homology
I am trying to use Algebra; Linear and otherwise to find the co-differential ,i.e., the differential
operator d in a Cohomology Theory starting with homology. For now, I just wanted to start with a
...
- 683
2
votes
0
answers
108
views
Abstract symmetric definition of duality in linear algebra?
In his Linear Algebra, 4th ed. from 1975, Greub presents (p. 65) an abstract, symmetric definition of duality, in which two vector spaces $E^*,E$ over a field $\Gamma$ are said to be dual if there is ...
- 2,245
1
vote
1
answer
84
views
Strong Duality in C-SVMs
Consider the C-SVM Dual Problem:
$$ \text{minimize}_{\lambda} \quad \mathbf{q}^{T} \lambda + \frac{1}{2} \lambda \mathbf{P} \lambda $$
$$ \text{subject to} \quad \mathbf{y}^{T} \lambda = 0 $$
$$ \quad ...
- 1,039
0
votes
0
answers
57
views
Representation of Fourier transform
NOTE : This Question is migrated from here : [Electrical Engineering stackexchange Question link][1]
I have a problem interpreting 2 different representations of Fourier transform and proving their ...
- 416
1
vote
0
answers
49
views
Trace morphism in Lipman's "Dualizing sheaves, differentials and residues on algebraic varieties". [duplicate]
Let $f: V \to W$ be a finite surjective morphism of varieties, with $W$ proper and normal. Does there exist a trace map
$$ \operatorname{trace}\colon f_* \mathcal O_V \to \mathcal O_W? $$
I know that ...
- 6,071
1
vote
1
answer
167
views
A single linear feasibility formulation that exactly captures all the optimal solutions of both primal and dual.
Given a linear program, we have the primal as follows:
\begin{array}{lll}
\max: & c^Tx\\
\text{s.t.} & Ax \leq b\\
& x\geq 0\\
\end{array}
And we also have the dual as follows:
\begin{...
- 375
1
vote
0
answers
76
views
Linear Programming: An optimality condition involving the dual
I am stuck at the following exercise:
The primal linear program
\begin{align}
(P): \max \quad &c^Tx \\
\text{ s.t.} &Ax \le b,\\ &x \ge 0
\end{align}
has an optimal solution for all $b$ ...
- 3,564
0
votes
1
answer
107
views
Why does any dual optimal point provide a separating hyperplane between a point and its projection on a convex set?
On page 400, in chapter 8 (Geometric Problems) of Boyd & Vandenberghe's Convex Optimization, there is a discussion on identifying a separating hyperplane between a point and its projection on a ...
- 189
1
vote
1
answer
73
views
Question on dual of a problem
Consider the following primal problem
$$
f=\max_{x}c^{\top}x -{\varepsilon ||x||_2} \quad \text{s.t.} \quad Ax\leq b\\
$$
with $\epsilon>0$.
Could you help me to write down the dual of this ...
- 140
1
vote
0
answers
82
views
Relations between annihilators and preannihilators in reflexive or Hilbert spaces.
Let $X$ be a normed space, denote by $X^*$ the dual space $=$ the space of all continuous linear maps from $X$ to base field $\mathbb{K}$. Annihilator of $Y \subset X$ is
$$ Y^{\bot} = \{f \in X^*:f(y)...
- 815
0
votes
1
answer
77
views
Is it possible to solve SVM via Penalty Method or Augmented Lagrangian Method?
I am going to code from scratch for Soft-margin Kernelised SVM, therefore, I am going to solve the dual form such as to kernelised.
Since most of the Penalty Method and Augmented Lagrangian Method ...
1
vote
0
answers
49
views
Konig's Matrix Proof by Dilworth's Thm [duplicate]
Let M be a (0, 1) matrix; that is, a matrix where each of whose entries is either a 0 or a 1. A line in M is either a row or a column of M. Use Dilworth's theroem to prove that the minimum number of ...
- 135
0
votes
1
answer
24
views
Why we can get more constraints in when converting to dual problem from the primal?
As far as I know,
the dual problem is defined as
$g(\lambda,\nu)=\inf_{x\in\mathbb{R}^n}L(x,\lambda,\nu)$ subject to $\lambda\geq0$
where $\lambda$ is corresponding to the inequality constraints and $\...
0
votes
1
answer
108
views
Does strong duality apply?
Consider the following primal
$$
(1) \quad \max_{y,\nu\geq 0} c^\top x \quad \text{ s.t. } ||By-a+\nu||_2\leq \epsilon
$$
whose dual is
$$
(2) \quad \min_{x\geq 0} a^\top x + \epsilon||x||_2 \quad \...
- 140
0
votes
0
answers
158
views
Show uniqueness of Lagrange multipliers
Consider the following optimisation problem
$$
(1) \quad \min_{x\geq 0} a^\top x+ \epsilon ||x||_2,\\
\quad \quad \quad \text{s.t. }B^\top x=c
$$
with $\epsilon>0$.
Suppose I assume that linear ...
- 140
0
votes
1
answer
83
views
Strictly convex dual problem
Consider the following primal problem:
$$
(1) \quad \max_{y} c^\top y ,\\
\quad \quad \quad \text{s.t. } By \leq a
$$
The dual of (1) is
$$
(2) \quad \min_{x\geq 0} a^\top x,\\
\quad \quad \quad \text{...
- 140
0
votes
1
answer
136
views
Strictly convex linear programming
Consider the following linear programming
$$
(1) \quad \min_{x\geq 0} a^\top x,\\
\quad \quad \quad \text{s.t. }B^\top x=c
$$
Consider the dual of (1)
$$
(2) \quad \max_{y} c^\top y,\\
\quad \quad \...
- 140
1
vote
1
answer
73
views
About primal to dual problem regarding the steps and how to get the dual constraints
Consider the primal objective to be
$\min_{x\in\mathbb{R}^n}x^\top Px$ subject to $Ax\leq b$
where $P$ is symmetric positive definite.
To convert to dual objective, need to first state the Lagrange ...
0
votes
1
answer
100
views
What is the relation between the Lagrange multipliers and the solution of the dual in a linear optimisation problem?
Consider the following linear minimisation problem
$$
(1) \quad \min_{x\geq 0} a^\top x,\\
\quad \quad \quad \text{s.t. }B^\top x=c
$$
where
$x$ is the $p\times 1$ vector of unknowns.
$a$ is a $p\...
- 140
1
vote
0
answers
83
views
Properties of the Lagrangian in a linear programming problem
Consider the following linear minimisation problem
$$
(1) \quad \min_{x\geq 0} a^\top x,\\
\quad \quad \quad \text{s.t. }B^\top x=c
$$
where
$x$ is the $p\times 1$ vector of unknowns.
$a$ is a $p\...
- 140
1
vote
0
answers
30
views
Legendre-Fenchel dual of convex functional
I found in the literature the following transformation. Let $Q$ be a fixed probability measure over the space $X$.
Let $\pi$ be a finite measure absolutely continuous with respect to $Q$. Let $\gamma\...
- 889
0
votes
1
answer
409
views
Complementary slackness and optimal solution for primal
We have primal, minimize $z = 3u_1 + 0.5u_2$
subject to
$$
u_1 - 2u_2 \leq 4 \\
u_1 + u_2 \leq 2 \\
u_1, u_2 \geq 0
$$
I found the dual
$$
\text{max: } z' = 4v_1 + v_2 \\
\text{subject to: } \\
v_1 + ...
- 21
0
votes
0
answers
249
views
proof of duality in projective geometry
I am looking for a proof for duality principle in projective geometry. There is an axiomatic and then a homogeneous coordinates development of projective geometry where dual of lines to points and ...
- 1,191
0
votes
1
answer
55
views
Dot Products and Linear Progamming
Let $v_{1}, \ldots, v_{m}$ and $w$ be vectors in $\mathbb{R}^{n}$. Suppose that whenever $d \in \mathbb{R}^{n}$ satisfies $v_{i} \cdot d \leq 0$ for $i = 1, \ldots, m$, it also satisfies $w \cdot d \...
user842064
7
votes
1
answer
218
views
Yoneda's lemma: group morphisms give Hopf-algebra morphisms
Let $k$ be a commutative ring. Let $\text{Alg}$ be the category of commutative $k$-algebras and $\text{CHopf}$ the category of commutative Hopf-algebras. Let us also write $[\text{Alg}, \text{Grp}]$ ...
user839372
6
votes
1
answer
264
views
Learning roadmap and prerequisites for Isbell duality
I'm looking for a roadmap to learning about Isbell duality. I know a reasonable amount about several of the "specific" dualities (Gelfand duality, AffSch - CRing, frames - locales, etc), ...
- 177
1
vote
0
answers
37
views
Dual of $\{\nabla h, \ h \in W^{1,s}(\Omega)\}$ in $(L^s(\Omega))^3$.
Let $\Omega$ be a bounded regular domain of $\mathbb{R}^d$. Define the following space :
$X:=\{\nabla h, \ h \in W^{1,s}(\Omega)\} \subset (L^s(\Omega))^3$.
Can I say that the dual space of $X$ is the ...
- 2,078
6
votes
0
answers
127
views
Hodge star operator and "Serre duality"
I am familiar with the Hodge star operator or Hodge duality in the theory of finite-dimensional differentiable manifolds, which gives an isomorphism $\star:\Omega^{i}(M)\longrightarrow\Omega^{n-i}(M)$ ...
- 1,482
2
votes
0
answers
53
views
How to formulate principle of duality in projective geometry in terms of category theory?
In projective geometry, the principle of duality states that any theorem that holds for an incidence structure $(P, L, I)$, where $P$ are the points, $L$ are the lines and $I \subseteq P \times L$ is ...
- 446
0
votes
1
answer
529
views
What happens to an equality constraint in the primal when you translate to the dual?
\begin{align}
\text{maximize} &\quad x_1 +3x_2 & & \\
\text{subject to} &\quad x_1 - x_2 = 2 \\
& -2x_1 +3x_2 \ge 5 \\
& \quad\quad\quad ...
- 1,553
1
vote
1
answer
29
views
Rewrite $\min _{z \in \mathbb{R}^{n}}\|z\|_{1}$ s.t. $B z=d$ as an equivalent standard LP problem.
I want to rewrite the following problem
$$ \min _{z \in \mathbb{R}^{n}}\|z\|_{1} s.t. B z=d \ where\ \boldsymbol{B} \in \mathbb{R}^{\boldsymbol{m} \times \boldsymbol{n}} and \ \boldsymbol{d} \in \...
- 373
2
votes
1
answer
138
views
Going from the unit-counit definition of the dual pair to the Hom-adjunction
In "Categories and Sheaves" by Kashiwara and Schapira on the page 101, the definition of the dual pair in tensor category is given and in the next theorem it is shown that if $(X,Y)$ is a ...
- 519