Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
914
questions
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?
