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
0answers
19 views

Can we use the duality notation such that the second variable is an element of the measure space?

I read article New Sequential Compactness Results for Spaces of Scalarly Integrable Functions by Erik J. Balder, on page 8 : Author defined the function $a: T\times E\to \mathbb{R}$ by the usual ...
-1
votes
0answers
19 views

Converting primal to dual

\begin{align} &\text{minimize } &z = 7x_1 – 4.2x_2 – 2x_3 + x_4 \\ &\text{subject to } &x_1 + 2x_3 + 2x_4 &\leq 20 \\ &&x_1 + 2x_2 &= 18 \\ &&x_1 + 2x_3 – 3x_4 &...
2
votes
1answer
58 views

Inequality for inner product with constraints.

Define $$\triangle := \ \{a\in \mathbb{R}^{n} \ \ : \ \ \sum_{i=1}^n a_i=1, \ \ a_i\ge0 \ \ \forall_{1\le i \le n} \}$$ Moreover, let $ \ L \ $ be any linear subspace of $ \ \mathbb{R}^{n}...
1
vote
1answer
38 views

How to write the dual problem (for stable matching)

How do you write the dual of the following problem - I know the basics behind the Lagrangian function but I'm getting a little confused with how to handle the Lagrangian multipliers when we are ...
0
votes
0answers
18 views

The dual of a linear program for weighted distance

My orignal problem is to simply find the minimum of $\sum_i^nq_i|x_i-u|$, where $q_i > 0$ I firstly convert to a standard linear program format as: $min_u\sum_i^nq_i*t_i$ $t_i >= u - ...
1
vote
1answer
34 views

Projective applications and projective duality

Let $P$ be a projective plane, and $p_{1},p_{2}$ different points of $P$. Consider now a projective line $L\subset P$ not passing for the aforementioned points. Let $F(p_{i})\,,\, i \in\{1,2\}$ be the ...
0
votes
1answer
17 views

Deriving the dual linear program.

The last optimization subject I took was so long ago, so I just grabbed a guide online to derive and verify the following claim from a lecture note This is the guide: http://pierrepinson.com/31761/...
0
votes
1answer
51 views

Theorem dual to trivial kernel $\iff$ injective in $\boldsymbol{Grp}$

Cokernels are "dual" to kernels. I've been told that if X dual to Y and there's a theorem about X then there's a "dual" theorem about Y. Theorem: In $\boldsymbol{Grp}$ a homomorphism has trivial ...
0
votes
2answers
24 views

How to check if a primal optimisation problem is feasible and bounded?

Consider the following Primal LP $$ \min_{x_1,x_2,x_3} x_1+x_2+x_3 $$ subject to constraints, $$ x_1+x_2 \ge a \\ x_1+x_3 \ge b \\ x_2+x_3 \ge c\\ x_1 \ge d \\ x_2 \ge e \\ x_3 \ge f $$ Here $$a,b,...
0
votes
1answer
34 views

Help solving Convex Optimization problem using KKT conditions?

Link to problem although I've still written the problem here. https://i.stack.imgur.com/6N8NN.jpg $$\ x \in \mathbb{R}^2$$ $$\ \text{minimize } f_0(x) =2x_1^2 + 4x_2^2 - 15x_1 - 30x_2 - 4x_1x_2$$ $$\ ...
0
votes
0answers
22 views

How to prove a solution not optimal using duality?

I have been given an LPP problem and asked to prove the basic solution (x1, x2) is not optimal. But every time I am solving it using simplex and the duality method the objective function keeps coming ...
1
vote
0answers
41 views

Dual problem to SDP problem

I'm having problem with formulating dual problem to Semidefinite programing problem: $$\max\;\;tr(X)$$ $$s.t.\;\; \left[ \begin{array}{cc} A & X \\ X & B \end{array} \right]\succeq0$$ where ...
0
votes
0answers
14 views

Difference between Lagrangian and Wolfe Dual

Does anyone know when the Wolfe dual is preferred over the Lagrangian Dual? I'm reading up on the optimization for SVMs and the presentation used the Wolfe Dual. Why can't we use the Lagrangian Dual?
-1
votes
0answers
16 views

Doubt regarding the optimality condition of a duality problem

In a LP problem does max z = min w indicate that the solution is not optimal? Or the opposite? Here min w is the dual of the primal max z
1
vote
0answers
15 views

Prove that if a canonical minimization problem is unbounded $\Leftrightarrow$ the dual canonical maximization problem is infeasible

I'm not sure exactly how to prove this given $g ≥ f$. I'm able to understand the proof for "if a canonical maximization linear programming problem is unbounded then the dual canonical minimization ...
-1
votes
0answers
14 views

How to solve the dual problem?

Derive the dual problem of the problem by using the Lagrange dual function. Min. f(X)=x1^2 + x2^2 s.t 4-x1-x2^2<=0 3x2-x1<=0 x1, x2>=0
2
votes
0answers
34 views

Generalizing linear duality via the $Hom$ functor

I am a beginner in category theory, so the following question could be either obvious or of no interest. Anyhow, I cannot find a statisfactory framing, and possibly an answer for the following ...
1
vote
0answers
23 views

Dual definition of self-duality

We can define the notion of self-duality on lattices as follow : A lattice $L$ is self-dual if there is a permutation $\pi$ such that : for all $a \in L$, $\ \downarrow \pi(a)$ is antiisomorphic ...
0
votes
0answers
23 views

Strong duality as optimality condition

My understanding of strong duality (for linear programming) is that if the dual form is optimal, then the primal is also optimal, and vice versa. Therefore, we only need to optimize one problem (...
0
votes
0answers
21 views

Verifying dual transform properties

I am reading a computational geometry book and it gives some claims about a dual transform, which I am trying to verify via linear algebra (linear operator) theory. Let $p:=(p_x, p_y)$ be a point ...
0
votes
1answer
34 views

Dual of a function in closed form.

Consider the optimization problem f(x) = infimum $(−x^2) s.t. 0 ≤ x ≤ 1$. What will be its dual in simplified closed form with no 'inf'. I know its Lagrangian function will be $ L(x,𝜆) = -x^2 +𝜆...
0
votes
1answer
13 views

If dual problem is infeasible (feasible), is the primal problem infeasible/unbounded (feasible)?

For a convex optimization problem, say $\cal P$, and its dual problem, say $\cal D$, is the following statement right? If $\cal D$ is infeasible (feasible), then $\cal P$ is infeasible/unbounded (...
0
votes
1answer
19 views

How to solve a dual Lp graphically?

I am working on the following exercise: Consider the following LP: $$\min 24x_1-9x_2+8x_4 $$ such that \begin{align} 4x_1-9x_2+3x_3+4x_4 &= 2 \\ 3x_1-x_2-10x_3-x_4 &= 1 ...
1
vote
1answer
75 views

Understanding derivation of dual for Infinite Linear Program

I'm reading the section on Linear Programming in Barbu and Precupanu's Convexity and Optimization in Banach Spaces (p. 206 in the 4th edition), and had a couple of questions concerning their ...
0
votes
1answer
37 views

Why does strong duality apply here?

I am working on the following exercise: Consider the following LP $(P)$: $$\min_{x \in \mathbb{R}^n} x_1 + 2x_2 + \ldots + nx_n$$ with \begin{align} x_1 &\ge 1 \\ x_1 + x_2 &...
1
vote
1answer
30 views

Understanding step in derivation of convex conjugate

I'm reading the section on Fenchel's Duality Theorem in Barbu and Precupanu's Convexity and Optimization in Banach Spaces, and was reading the derivation of the dual problem for a special class of ...
1
vote
1answer
37 views

Clarification on the dual expression of a Boolean algebra.

I need to get some clarification on if i got some answers right. Question: Let B be a Boolean algebra. For x, y, z ∈ B find the dual expressions of $i)\; (x + \bar y) · \overline {(\bar z + y)}\...
4
votes
0answers
25 views

On the monotonicity of angles between dual basis vectors

I want to show that if I make the angles between basis vectors $e_1,...,e_n\in\Bbb R^n$ smaller, then the angles between the dual basis vectors $e_1^*,...,e_n^*\in\Bbb R^n$ become larger. More ...
2
votes
3answers
63 views

A basis with $e_i\cdot e_j<0$ implies a dual basis with $f_i\cdot f_j>0$?

I have a basis $\{e_1,e_2,e_3\}\subset\Bbb R^3$ of the 3-dimensional Euclidean space with $e_i\cdot e_j <0$ for all $i\not= j$ (where $\cdot$ denotes the standard inner product). Question: If $\...
0
votes
1answer
50 views

Dualizing 2-categorical results in the context of locally small categories

Monad, comonad and adjunction are 2-categorical notions. Results about them can be dualized as shown in this answer. In the second part the answer, the dualization is successfully applied to the ...
0
votes
0answers
16 views

Connection between two minimax theorems

According to Wikipedia, Parthasarathy's theorem is a generalization of Von Neumann's minimax theorem, but I don't see how how this connection is made. Can someone clarify this please?
2
votes
1answer
107 views

Is it true that $\dim({\rm im}(f))=\dim({\rm im}(f^{*}))$?

I have a question regarding dimensions of finite vectors spaces. Let $f$ be a linear map between two vector spaces $f:E_{1}\longrightarrow E_{2}$ with dimensions $m$ and $n$ respectively in a field $\...
0
votes
0answers
22 views

Does the canonical line bundle coincide with dualizing sheaf when the base scheme is arbitrary

Let $X$ be a smooth projective curve over an algebarically closed field $k$. Consider the commutative diagram where the left square is cartesian. where $S,S'$ are schemes over $k$ and $X_S:=X\times ...
0
votes
0answers
23 views

The relationship between the LP and its dual problem

Given a linear programming problem $\min c^Tx$ s.t. $Ax=b,\ x\geq0$. The solution to this problem is $z_0=c^T x_0$, and the solution to the dual of this problem is $\lambda^T b$. The solution to $\min ...
0
votes
1answer
20 views

How to find the dual problem of this LP?

I want to find the dual problem of the following LP: $\min c'x$ s.t. $Ax=b,x\ge a$ where a>0. I'm considering substitute $y=x-a$ so that it becomes: $\min c'y+c'a$ s.t. $Ax=b-Aa,y\ge 0$. I know I ...
0
votes
0answers
44 views

Dual Theorem Problem

Suppose that a column for the primal tableau involves a slack variable, s, and we have a column of the identity, say ⃗ei corresponding to s in matrix A. Show that in the optimal row 0, the value under ...
1
vote
1answer
29 views

Duality for free abelian groups and for finite abelian groups

Let $L$ be a lattice (finitely generated free abelian group), and $M\subseteq L$ be a subgroup of finite index (which is again a lattice). Consider the dual lattices $$L^\vee={\rm Hom}(L,\mathbb Z)\...
2
votes
1answer
37 views

Exercise 1.2 item 3. in Brezis Functional Analysis: Duality map of $l_p$ in finite dimensions

Consider the following problem, item 3. of the exercise 1.2 in Brezis's Functional Analysis, Sobolev Spaces and Partial Differential Equations: Let $E$ be a vector space of dimension $n$ and let $(...
1
vote
1answer
21 views

Motivation and applications of the duality map

The duality map is defined, according to Brezis (Functional Analysis, Sobolev Spaces and Partial Differential Equations) as follows, where $E$ is a Banach space and $x \in E$: $$F(x) = \{f \in E^* \ :...
0
votes
0answers
38 views

Derivation of Lagrangian dual problem

I am new to Lagrangians, and I am not sure if what I am doing is correct. The original problem was to find $\min\limits_{\theta}-log(\theta(1-\theta)^2), .5 \leq \theta \leq 1$, write the Lagrangian, ...
0
votes
2answers
32 views

Primal and dual feasibility and boundedness

Suppose we have a primal maximization LP: $$ \text{maximize } c^Tx \\ \text{subject to } Ax \le b, x \ge 0 $$ If $x$ is a feasible solution to the primal LP, and $y$ is a feasible solution to the ...
0
votes
0answers
19 views

Dual of quadratic program

Given this problem $\min c^Tx + \frac{1}{2}x^tHx$ subject to $b \leq Ax \leq b+r$ $l \leq x \leq u$ by adding slacks the subject becomes: $Ax - w = b$ $x - g = l$ $x + t = u$ $w + p = r$ $g, w, ...
2
votes
1answer
112 views

Can the Fenchel conjugate be characterized through the Fenchel-Young inequality?

It is known (see for example this question), that the Fenchel conjugate of a smooth function $f: \mathbb{R}^d \to \mathbb{R}$ verifies the identity $$ f(x) + f^\star(\nabla f(x)) = \langle x, \nabla f(...
0
votes
0answers
21 views

Finding the dual problem with exponential equation

I need to find the dual problem of this: but I have no idea how to work with the norm or the exponential function
1
vote
0answers
31 views

Finding Optimal Dual Solution without solving de Dual Problem (knowing the Optimal Primal Solution)

I've been asked to solve this problem using the Dual Simplex Method. $$ \begin{array}{ll} \min: & x_1+6x_2+3x_3 \\ \text{s.t}: & -4x_1-4x_2-2x_3+x_4=-18 \\ & 2x_1+2x_2-4x_3+x_5 = -16 \\ ...
4
votes
2answers
75 views

Equality in trace duality

For $A,B\in\mathbb{R}^{n\times m}$ we have the trace duality property $$|\langle A, B \rangle|\leq \|A\|_1 \|B\|_{\infty}$$ where $\|A\|_p$ is the Schatten $p$-norm (i.e. $\|\cdot \|_1$ is the ...
0
votes
0answers
16 views

Linear programming - Dual

I am trying to derive the dual of the following problem: \begin{equation} \underset{\mathbf{g}, \mathbf{r}, \boldsymbol{\alpha}, \underline{\mathbf{t}}_j, \underline{\mathbf{u}}} {\text{minimize}}~~ \...
1
vote
0answers
30 views

If there exists a $\phi \in W'$ so $\text{null}(T') = \text{span}(\phi)$, prove that $\text{range}(T) = \text{null}(\phi)$

I've already proven this question, however, my proof is much more complicated than an answer I saw posted on another website. However, I cannot seem to make sense of why the answer on the website is ...
1
vote
1answer
28 views

Rewriting max-min problem using strong duality

I have rewritten a max-min problem as a unique maximisation problem using strong duality. I have built a Matlab code which seems to show that my derivations are wrong. However, the code itself may be ...
1
vote
0answers
31 views

Example of non reflexive Banach space

I searched online but did not find any example of non-reflexive Banach space. Can you give me some examples of non-reflexive Banach space?

1
2 3 4 5
19