Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
1,015
questions
0
votes
1answer
32 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 ...
0
votes
0answers
23 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 ...
0
votes
1answer
23 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
...
0
votes
0answers
9 views
Linear programming duality theory general question [closed]
Does duality theory imply that if the primal problem is infeasible, then its dual is either infeasible or unbounded?
How would this be proven?
0
votes
0answers
25 views
Linear Programming BT 4.26 [closed]
Let $\mathbf{A}$ be a given matrix. Show that exactly one of the following alternatives must hold.
$(\textbf{a})$ There exists some $\mathbf{x}\ne 0$ such that $\mathbf{Ax} = 0, \mathbf{x}\ge 0$.
$(\...
0
votes
0answers
33 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 ...
-1
votes
0answers
38 views
I want to find the dual to the problem given below.
minimize z = $c^Tx$
subject to $Ax = b$
$l ≤ x ≤ u$,
where $l$ and $u$ are vectors of lower and upper bounds on $x$.
0
votes
1answer
13 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 ...
0
votes
0answers
29 views
Representation of Fourier transform
NOTE : This Question is migrated from here : Electrical Engineering stackexchange Question link
I have a problem interpreting 2 different representations of Fourier transform and proving their ...
0
votes
1answer
26 views
L1 trend filtering derivation [closed]
I'm working on a school project. I need to implement and understand the l1 trend filter. The paper on the algorithm can be found here :
https://web.stanford.edu/~boyd/papers/l1_trend_filter.html
I don'...
2
votes
0answers
36 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 ...
1
vote
1answer
79 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{...
1
vote
0answers
41 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$ ...
0
votes
1answer
49 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 ...
1
vote
1answer
63 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 ...
0
votes
0answers
39 views
Connection between duality in control theory vs. duality in optimization?
In control & estimation theory, we have Kalman's result (and generalizations to nonlinear, deterministic systems etc.) that the minimum-variance estimator for an LQG system can be used to derive ...
1
vote
0answers
29 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)...
0
votes
1answer
30 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 ...
0
votes
0answers
18 views
Does Strong Duality hold?
Consider the following optimisation problem:
Minimise $f(x) = x^2-1$ subject to $g(x)=(x-3)(x-1) \leq 0$
Now it is quite clear to see that the optimal point is at $x^*=1$ in which case we have $f(x^*)=...
0
votes
0answers
14 views
General primal and dual solutions
We are given primal
$$
\text{max: } z = c_1x_1 + c_2x_2 + ....c_nx_n \\
\text{subject to: } a_1x_1 + a_2x_2 + .... a_nx_n \leq b \\
x_1, x_2, ...,x_n \geq 0
$$
And we have to find the dual and then ...
1
vote
0answers
45 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 ...
0
votes
1answer
16 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
1answer
31 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 \...
0
votes
0answers
28 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 ...
0
votes
1answer
41 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{...
0
votes
1answer
33 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 \...
0
votes
1answer
26 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
1answer
24 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\...
1
vote
0answers
45 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\...
1
vote
0answers
17 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\...
0
votes
1answer
31 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 + ...
0
votes
0answers
79 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 ...
0
votes
1answer
47 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 \...
0
votes
0answers
22 views
An example of bounded Linear Programming
I have a question that intrigues me and I am not sure if what I did is right. Anyone could help me with a better solution if possible.
Consider an LP in bounded-variable form
$$\min c^T x \ \text{ s.t ...
0
votes
0answers
14 views
Optimization of a non-separable function of two vectors
I am studying the solution to the following problem. Let $\boldsymbol{x}$ and $\boldsymbol{y}$ be vectors of $\mathbb{R}^{n}$.
\begin{equation}
\begin{aligned}
&\text{ }\min_{\boldsymbol{x},\...
7
votes
1answer
174 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}]$ ...
1
vote
1answer
57 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), ...
1
vote
0answers
34 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 ...
0
votes
0answers
28 views
dual Lie algebra, dual Lie group, and Langland dual group
Are the following concepts somehow related?
dual Lie algebra
dual Lie group
Langland dual group (say of a Lie group)
We can take examples, for su(N) Lie algebra and SU(N) Lie group; or so(N) Lie ...
6
votes
0answers
64 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)$ ...
2
votes
0answers
25 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 ...
0
votes
0answers
12 views
Legendre transform of Log determinant
The function $log det(C)$ is known to be convex when $C$ is restricted to the cone of symmetric non-negative definite matrices $S_n^+$.
What if anything can be said about the Legendre transform of ...
0
votes
1answer
39 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
vote
1answer
18 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 \...
0
votes
0answers
36 views
How to find Dual Problem of L1 norm
I have here an example, where I am not able to find the dual problem:
$\min ||y||^2 + \alpha ||x||_1)$
subject to $Ax + y = b$
$x, y$ are vectors in $\mathbb R^n$, $A$ is matrix in $\mathbb R^{m\times ...
0
votes
0answers
14 views
Conjugate function depending on parameter
Let $(X,d)$ be a metric space and let $f: X \times \mathbb{R}^d \to [0, + \infty]$ be a proper lower semicontinuous function s.t.
$$f(x,\lambda y) = \lambda f(x,y) \quad \forall \, (x,y) \in X \times \...
1
vote
1answer
41 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 ...
0
votes
0answers
17 views
Is $\mathcal P_1(X)$ a necessary condition for the Kantorovich-Rubinstein Duality?
In many books, such as Villni's Optimal Tranport: Old and New, the Kantorovich-Rubinstein duality is written with the condition that $\mu,\nu \in \mathcal P_1(X)$. That is:
$$
\int_X |x|d\mu < +\...
0
votes
0answers
29 views
Understanding the different versions of Kantorovich-Rubinstein Duality
In lecture notes and the book "Optimal Transport: old and new", the Kantorovich-Rubinstein Duality is presented as:
(K-R) Let $X=Y$ Polish, with $c:X \times X \to \overline{\mathbb R}$ lower-...
1
vote
1answer
29 views
Unscented (dual) quaternion kalman filter for pose estimation
This paper Unscented Dual Quaternion Particle Filter for SE(3) Estimation shows a method to use Unscented Kalman Filter (UKF) on dual quaternions in the pose estimation problem.
It proposes a ...
