Skip to main content

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
1 answer
50 views

The vector space duality functor from Erdman's Elements of Linear and Multilinear Algebra

In Example 3.2.9 of Elements of Linear and Multilinear Algebra by John Erdman , given a linear map $T \in {\cal L}(V,W)$ where $V, W$ are vector spaces over a field $\mathbb{F}$, the pair of maps $V \...
Ted Black's user avatar
  • 896
0 votes
0 answers
32 views

Understanding Feasibility, Constraints in the Lagrange Dual Function: A Query on Boyd's Least-Squares Example

I am confused by a basic problem with the Lagrange dual function. As Boyd states, $g(\lambda, \mu) = \underset{\scriptsize \text{$x \in D$}}{inf}L(x, \lambda, \mu) = \underset{\scriptsize \text{$x \in ...
LoveDance's user avatar
0 votes
0 answers
20 views

Concave maximization over $d$-dimensional simplex.

Can either an analytic solution or the dual be characterized for the following concave maximization: $v:= \underset{w \in \Delta_d}{\max} \sum^{d}_{i=1}\frac{1}{\sqrt{1+b_i/w_i}}$ where $\Delta_d$ ...
Sushant Vijayan's user avatar
1 vote
1 answer
29 views

Isomorphism as $\Bbb{F}_p$ vector space and Proof of local Tate--Duality $H^1(G_K,E)[p]\cong (E(K)/pE(K))^*$

This is a question regarding Theorem $1.4$ of https://kskedlaya.org/kolyvagin-seminar/duality.pdf. Let $E/K$ be an elliptic curve over number field $K$. Let $p$ be a prime number. The goal of Theorem $...
Poitou-Tate's user avatar
  • 6,351
1 vote
0 answers
31 views

Slack Variables and Duality in Convex Optimization

In context of convex optimization the slack variable $\vec{s} \ge 0$ can be used to convert inequality $A \vec{x} \le \vec{b}$ to the equality $A \vec{x} + \vec{s}= \vec{b}$. Now in wikipedia is ...
user267839's user avatar
  • 7,499
1 vote
0 answers
18 views

What is the value of dual/lagrangian variable of an infeasible problem?

I found some materials saying that: if the primal is unbounded, then the dual is infeasible; If the dual is unbounded, then the primal is infeasible; but it's possible for both the dual and the primal ...
Ruihao Wang's user avatar
1 vote
1 answer
52 views

Lattice with supermodular height function is lower semimodular

Question Let $(L,\leq)$ be a lattice of finite length and let its height function $h$ be supermodular, meaning that $$h(x \wedge y) + h(x \vee y) \geq h(x) + h(y) \quad \forall x,y\in L.$$ Does it ...
azimut's user avatar
  • 23.1k
1 vote
1 answer
44 views

finding dual problem of the function below

I am trying to solve a question from Amir Beck's book "Introduction to nonlinear optimization" the problem is to find the dual problem with one decision variable of the next minimization ...
Chen's user avatar
  • 49
1 vote
0 answers
12 views

Is the solution of the dual problem feasible?

Thank you for reading my question. Assume we have a problem, $$ \begin{align} &\min_x f_0(x)\\ s.t.\quad &h_i(x)=0, i= 1,\dots, p\\ &f_i(x)\leq 0, i =1,\dots,m \end{align} $$ which is ...
Xiangyu Cui's user avatar
1 vote
0 answers
45 views

Duality Results for Convex SDP Programming

Suppose we have an SDP program with a convex (but nonlinear) objective $f(X)$, where $X$ is a positive semidefinite matrix. All other constraints are linear. Does there exist a dual program for such a ...
GoemanWilliamson's user avatar
0 votes
1 answer
62 views

Determine the condition of $\lambda$ so that the given linear programing problem has infinitely many optimal solutions [closed]

I'm having the following linear programming problem: $f = 2x_1 + 4x_2 + \lambda x_3 \text{( to max )} \text{ with constraints } x_i \ge 0\, \forall i = 1,2,3,4$ and $\left\{\begin{aligned}{} ...
Viking A's user avatar
1 vote
0 answers
55 views

Cohomology of number fields, Theorem (8.7.9), $Ш^1(G_S,A)\to H^1(G_S,A)\to \prod_{p\in S} H^1(k_p,A)\to \hat{H^1(G_S,A')}$

I'm reading a book 'Cohomology of number fields' Second edition by J.Neukirhi A.Schmidt, K.Winberg. In the page 511, theorem (8.7.9), there appears suddenly. $Ш^1(G_S,A)\to H^1(G_S,A)\to \prod_{p\in S}...
Poitou-Tate's user avatar
  • 6,351
0 votes
0 answers
84 views

Dual of Quadratic Programming with inequality constraints

I am new to duality concepts and I was reading a document that dualizes the following problem: \begin{equation} \min_{x,y} \ ||x-y||^2 \\s.t. \ A_x x \leq b_x, \ A_y y \leq b_y \end{equation} into: \...
Taiwaninja's user avatar
0 votes
0 answers
24 views

Getting arbitrarily close to $L^1$ norm using $L^\infty$ functions and duality

Let $f\in L^1(\mathbb{R}^d)$ be complex-valued with norm $$\| f\|_{L^1} >\varepsilon$$ for some $\varepsilon >0$. We know that we can write this using duality as $$\sup_{\| g\|_{L^\infty=1}}\...
Diffusion's user avatar
  • 5,611
0 votes
1 answer
41 views

Proof of Modified Farkas lemma: $y\ge0,A^Ty=0,y^Tb<0$ or $Ax\le b$ has a solution

The proof of Farka's lemma is known. An important corollary of Farkas lemma is stated as Modified Farkas Lemma. Let $A$ be an $m\times n$ matrix with values in $R$ and $b\in R^m$. Then exactly one of ...
reyna's user avatar
  • 2,224
2 votes
1 answer
63 views

Help understanding analytic proof of Farkas' lemma

I'm trying to understand the analytic proof of Farkas lemma (presented in a lecture) but I may have noted some steps wrong. Farkas Lemma. Let $A$ be an $m\times n$ matrix with values in $R$ and $b\in ...
reyna's user avatar
  • 2,224
0 votes
1 answer
39 views

Does a convex quadratic program have a unique dual solution?

As shown in Does a convex quadratic program have a unique solution?, a convex quadratic program has a unique primal solution $x$ if $Q$ is PD. $$\min \; x^T Q x \\ s.t. \ Ax= b : \lambda \\ \ \ \ \ \ \...
Sean W's user avatar
  • 1
0 votes
1 answer
37 views

Proving concavity of the Lagrange dual function

The Lagrange dual function for an optimization problem of form $$\min f_0(\boldsymbol x)\quad\text{subject to}\quad f_i(\boldsymbol x)\le0,h_j(\boldsymbol x)=0\quad i=1,2\dots m,j=1,2,\dots p$$ with ...
reyna's user avatar
  • 2,224
1 vote
1 answer
132 views

Exercise 3.F.29(a) in "Linear Algebra Done Right 4th Edition" by Sheldon Axler.

Exercise 3.F.29(a) Suppose $V$ and $W$ are finite-dimensional and $T \in \mathcal{L}(V,W)$. (a) Prove that if $\varphi \in W'$ and $\text{null} \ T' = \text{span} \ (\varphi)$, then $\text{range} \ T =...
Paul Ash's user avatar
  • 1,454
0 votes
1 answer
55 views

When performing the "opposite" operation in a category, can you reverse arrows that are part of an object's definition?

I'm reading Emily Riehl's Category Theory in Context and pondering Exercise 1.2.i, where the author writes "Defining $\mathcal{C}/c$ to be $(c/\mathcal{C}^{op})^{op}$," in an effort to ...
RicLouRiv's user avatar
  • 117
0 votes
1 answer
26 views

Given the primal, turn it into the dual (LP)

Given the primal resource allocation: $$ \min_{x} \text{ costs} = \sum_{i} c_i x_i $$ $$ \sum_{i} x_i = D \\ (p) $$ $$ x_i \leq \text{CAP}_i \quad \forall i \text{ (}\lambda_i\text{)} \\ $$ $$ x_i ...
Marlon Brando's user avatar
1 vote
1 answer
19 views

Is the multiplier of the primal problem equal to the solution of the dual problem if strong duality holds and the solution of primal is unique?

Assume we meet this problem: $$ \min_x f(x)\\ s.t. g(x)=0, h(x)\leq 0 $$ Let's assume the solution is $(x^*,\nu^*,\lambda^*)$ Its dual problem is $$ \max_{\nu,\lambda} l(\nu,\lambda)\\ s.t. \lambda\...
Xiangyu Cui's user avatar
0 votes
0 answers
22 views

Why is the Cartesian product of second-order cones self-dual?

I came upon a paper regarding conic programming (CP) where a constraint is an inequality defined on Cartesian product of second-order cones, named $K$. And he derived the dual problem of this CP with ...
akio cu's user avatar
2 votes
1 answer
47 views

Cannot find the dual function

The picture shows an example of solving the integer problem with a decomposition method. However, what I am trying to ask is about the dual function part instead of the integer part. As you can see, ...
Ruihao Wang's user avatar
1 vote
0 answers
61 views

$\text{Im}(f)=\text{ker}(\widehat{f})$, written in 'Galois cohomology of elliptic curves' by Coates and Sujata

Let $K$ be a number field and $K_v$ be the completion of $K$ at the place $v$. Consider an elliptic curve $E/K$ over $K$. Let $f: H^1(G_K,E[2])\to \bigoplus_v H^1(G_{K_v},E[2])$ be a natural map. For $...
Poitou-Tate's user avatar
  • 6,351
0 votes
1 answer
82 views

Does $\text{Im}(f)\cong \text{Ker}(f^*)$ hold? Pontryagin dual

Let $M, M'$ be a profinite group. Let $M^*=\text{Hom}_{conti}(M,\Bbb{Q}/\Bbb{Z})$ be a Pontryagin dual of $M$. Let $f:M\to M'$ be a homomorphism of abelian group. Let $f^*: M'^*\to M^*$ be a map ...
Poitou-Tate's user avatar
  • 6,351
2 votes
1 answer
123 views

$H^1(G_{K_v}, M^D) \cong \widehat{H^1(G_{K_v}, M)}$, Tate dual and Pontryagin dual

Let $K$ be a number field and $G_K$ the absolute Galois group of $K$. Let $M$ be a finite $G_K$-module. The Tate dual of $M$ is defined as follows: $M^D = \text{Hom}(M, \mu(K))$, where $\mu(K)$ is the ...
Poitou-Tate's user avatar
  • 6,351
2 votes
0 answers
33 views

$0 \to E(K)/2E(K) \to H^1(G_K,E[2])\stackrel{\delta}{\to}H^1(G_{K_v},E)[2]\to 0$ and Pontryagin dual

Let $K$ be a number field and $K_v$ be the completion of $K$ at the place $v$. Consider an elliptic curve $E/K$ over $K$. The short exact sequence $0 \to E[2] \to E \to E \to 0$ induces a famous exact ...
Poitou-Tate's user avatar
  • 6,351
0 votes
1 answer
46 views

Restatement of complementary slackness

Complementary slackness states that if $x$ and $y$ are solutions to primal and dual respectively, then they satisfy: $x$ and $y$ are optimal solutions to primal and dual respectively if and only if ...
John Davies's user avatar
1 vote
0 answers
58 views

proof variant of Farkas’ Lemma - Homogeneous Inequalities with Positive Solutions

need help to prove the following: (already prove that both can't holds, but I need to show that if (a) doesn't hold then (b) hold) Let A ∈ Mm×d(R). Prove that exactly one the following holds: (a) ...
dani johns's user avatar
0 votes
0 answers
23 views

Dual map-injectivity implies surjection

Let $k_n=\mathbb{Q}_p(\zeta_{p^n})$ and $T$ be the $p$-adic Tate module of an elliptic curve $E$. Assume $E$ has good supersingular reduction at $p$. Let $V=T\otimes \mathbb{Q}_p$. Now, by Local Tate ...
user631874's user avatar
0 votes
0 answers
31 views

Minimax theorem for convex quadratic programming

I have a simple and stupid question if I have a convex quadratic optimization problem with polyhedral constraints as follows: $$ \begin{aligned} \inf_{x \in \mathbb{R}^{n}} & x^{\top} Ax + b^{\top}...
zzgsam's user avatar
  • 139
0 votes
0 answers
30 views

Deriving the dual problem from the complex primal problem

I faced the following problem recently. When I was working on an electricity market clearing problem, it is hard for me to derive the dual problem of it, which is necessary to obtain the optimal price....
Smith Sam's user avatar
0 votes
0 answers
27 views

Local Tate pairing on elliptic curves

Let $E$ be an elliptic curve over $\mathbb{Q}_p$ and $k_n=\mathbb{Q}_p({\zeta_{p^n}})$. Let $T$ be the $p$-adic Tate module of $E$. Then there is a local Tate pairing, $$<,>_n: H^1(k_n, E[p^\...
user631874's user avatar
0 votes
0 answers
37 views

Lagrange Duality in Robust Optimization

I am learning Robust Optimization and been stuck on this example. I've brushed up on my knowledge of Lagrange duality and referred to a couple of textbooks on Linear Programming but not able to ...
stuckinlocal's user avatar
0 votes
0 answers
14 views

Optimal Table may change in LPP

If we solve a LPP with let's say 2 constraints with all slack starting variables with non negative right hand side. We get the optimal table. Now suppose we change the constraint coefficient of a ...
Upstart's user avatar
  • 2,632
0 votes
0 answers
42 views

How does this pair of Multivariable Calculus problems relate to the concept of duality?

Consider the following pair of a priori independent problems... A manufacturer's revenue is $\$100s^{\frac{1}{3}}h^{\frac{2}{3}}$, where $s$ is the number of tons of steel they purchase and $h$ is ...
user10478's user avatar
  • 1,922
1 vote
1 answer
78 views

Topology in the context of Pontryagin dual

Let $A$ be an abelian group. The definition of the Pontryagin dual of $A$ is $\text{Hom}_{\text{conti}}(A, \mathbb{Q}/\mathbb{Z})$. In this context, what are the topologies on $A$ and $\mathbb{Q}/\...
Poitou-Tate's user avatar
  • 6,351
0 votes
1 answer
30 views

If $A$ and $B$ are dualizable objects in a monoidal category, is the unit of the one duality the inverse of the counit of the other duality?

I'm currently trying to wrap my head around dualizable objects in monoidal categories and I was wondering whether the following claim holds: Let $A$ and $B$ be dualizable objects in a monoidal ...
user11718766's user avatar
0 votes
0 answers
41 views

Presentations of smooth manifolds

A presentation of a affine complex variety consists of finitely many polynomials $f_1,...,f_m$ in $\mathbb{C}[x_1,...,x_n]$. A presentation of a projective complex variety consists of finitely many ...
user avatar
0 votes
0 answers
38 views

I want to prove equivalence of norm on the dual of the Strichartz space

Let $(p,q)$ be an admissible pair if $2/p+n/q=n/2$, where $n$ is the space dimension and $2\leq q\leq \frac{2n}{n-2}$. Define $S^0=\{ u, sup_{(p,q)~admissible}||u||_{L^pL^q} <\infty\} $. I want to ...
Felipe's user avatar
  • 79
0 votes
0 answers
16 views

Duality for actions of H-spaces

I am thinking about two duality theorems for H-spaces and their actions. By H-space is meant a commutative monoid in the derived (homotopy) category of based connected CW-complexes. We can consider ...
user avatar
0 votes
0 answers
37 views

The duality problem of the optimal problem of 2 norm and 1 norm is included in the constraint

\begin{align*} \delta_r^*({\nu}) &= \max_{{\beta \in R^M}}\bigg\{{\beta}'{\nu}\mid \frac{1}{P}\|{z}-{Y}{\beta}\|_2^2+\lambda\|{\beta}\|_1\leq\hat{\rho}+r\bigg\} \\ ...
lin's user avatar
  • 1
1 vote
1 answer
102 views

Zero dual variables

I am struggling to prove the following claim: Primal problem (1) $\max_{x \geq 0} c^Tx$ subject to $Ax \leq b$ and $Dx \leq d$ Primal problem (2) $\max_{x \geq 0} c^Tx$ subject to $Dx \leq d$ Suppose ...
Anna  Vakarova's user avatar
1 vote
0 answers
29 views

How to determine the infimum with linear and logarithm term to dualise a convex problem?

I wanted to try and dualise an optimisation problem but I am struggling with the infimum. The problem looks as follows: $$ \begin{equation} \begin{aligned} \min_{x} \quad & 3x\\ \textrm{s.t.} \...
Michael's user avatar
  • 53
0 votes
0 answers
13 views

Obtaining tight edges from a graph to find an MST

As far as I understand, to obtain an optimal solution of the Dual of the MST, meaning: \begin{align} ~\max &~ z (|V|-1) + \sum_{S \subseteq V : |S| \neq \emptyset} (|S|-1) y_{s} \\ \label{DMST2} ...
Ragon's user avatar
  • 308
0 votes
0 answers
46 views

Dual of a Nonlinear Convex Problem

I am struggling in formulating the dual of a very simple problem: \begin{align} \max_{x_{i},y_{j}} \sum_{i=1}^{I}c_{i}x_{i} - \sum_{j=1}^{J}(\delta_{j}y_{j}+\gamma_{j}y_{j}^{2}) \hspace{0.2in} \\ s.t \...
econ_ugrad's user avatar
1 vote
2 answers
168 views

Pontryagin dual of 2-part of abelian groups

Let $A$ be an abelian group. Let $A[2]$ be a 2-part of $A$, which is a subgroup of $A$ killed by 2. Let $A'=Hom_{\text{conti}}(A,\Bbb{Q}/\Bbb{Z})$ be a Pontryagin dual of $A$. Is there a known formula ...
Poitou-Tate's user avatar
  • 6,351
1 vote
0 answers
49 views

Understanding the space defined by a 2 dimensional vector

I was watching a 3b1b video when he explained the relationship between a 1*2 matrix and a 2-dimensional vector, now he talks about how we can Interpret a 2-dimensional vector as a tilted number line, ...
samsamradas's user avatar
3 votes
1 answer
279 views

Use of min-max equality (strong duality) in proof

I'm attempting to follow a proof in a paper. In the proof, the authors make use of what I believe is the min-max inequality and exploit strong duality, but I'm unsure of the steps that are glossed ...
jmd's user avatar
  • 57

1
2 3 4 5
26