# Questions tagged [duality-theorems]

For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.

1,288 questions
Filter by
Sorted by
Tagged with
50 views

• 6,351
1 vote
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 ...
• 7,499
1 vote
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 ...
1 vote
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 ...
• 23.1k
1 vote
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 ...
• 49
1 vote
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 ...
• 335
1 vote
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 ...
62 views

• 6,351
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: $$\min_{x,y} \ ||x-y||^2 \\s.t. \ A_x x \leq b_x, \ A_y y \leq b_y$$ into: \...
24 views

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 ...
• 2,224
1 vote
132 views

• 6,351
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 ...
• 6,351
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 ...
• 6,351
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 ...
• 6,351
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 ...
• 589
1 vote
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) ...
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 ...
• 291
31 views

• 291
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 ...
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 ...
• 2,632
42 views

• 6,351
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 ...
• 371
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 ...
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 ...
• 79
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 ...
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\} \\ ...
• 1
1 vote
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 ...
1 vote
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{aligned} \min_{x} \quad & 3x\\ \textrm{s.t.} \...
• 53
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} ...
• 308
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 \...
• 101
1 vote
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 ...
• 6,351
1 vote
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, ...
• 541