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
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 ...

1
2 3 4 5
21