Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
1,210
questions
0
votes
0
answers
32
views
Why dual norm inequality is tight in $\mathbb{R}^{n}$
Let $\lVert \cdot \rVert $ be any norm on $\mathbb{R}^n$
I want to prove that
For any $x$, there is some $z$ such that $z^{T}x = \lVert x \rVert \lVert z \rVert _{*}$
where $\lVert y \rVert _{*} = \...
- 129
1
vote
1
answer
41
views
Lagrangian Duality problem
Suppose that $\lambda, N_0 \in \mathbb{R}$, $\boldsymbol{X}_{0} = (X_2',...,X_{m+1}')' \in \mathbb{R}^{m \times n} , X_1 \in \mathbb{R}^n$ is fixed, $\iota \in \mathbb{R}^n$ is the vector of ones, ...
- 369
0
votes
0
answers
19
views
How to solve minimisation using dual and simplex method
How would I minimise $2y_1 + y_2$ using the simplex method?
subject to:
$ 10y1 + y2 \ge 10 $
$ 2y1 + y2 \ge 8 $
$ y1 + y2 \ge 6 $
$ y1 + 2y_2 \ge 10 $
$ y1 + 12y_2 \ge 12 $
$ y1,y2 \ge 0 $
I have got ...
- 73
2
votes
0
answers
17
views
Dual operator of Markovian operator
I am trying to incorporate the definition of dual operator in a Markovian setting.
Say I have a Markov kernel $K:S\times S\to[0,1]$ i.e., a mapping such that
for every $A\in S$ $x\to K(x,A)$ is a ...
- 889
0
votes
1
answer
13
views
subdifferentiable implies conjugate equality
For function $f(x)=\max_i x_i, x\in\mathbb{R}^n$.
We define the Fenchel conjugate as
$$
f^*(x^*) = \sup_{x} \langle x^*,x\rangle-f(x)
$$
The standard subdifferential for $f(x)$ as
$$
\partial f(x)=\{x^...
- 77
2
votes
0
answers
90
views
Constrained Optimization using FFT to find function
I want to find the function $W(x)$ from the following optimization problem:
\begin{equation}
\textrm{min}
\left(I(x) - \int_{-\infty}^{\infty} W(x_0) d(x-x_0) dx_0\right)^2
\end{equation}
\begin{...
0
votes
0
answers
32
views
Operator norm as a dual norm?
Given a space $X$ endowed with a norm $\left\lVert \cdot \right\rVert$ then one can define a norm $\left\lVert \cdot \right\rVert_\star$ on the continuous dual space $X^\star$ considering the ...
- 889
0
votes
0
answers
38
views
Dual polygons: terminology
A question about terminology: is there a specific reason why, given a polygon $P$, the polygon $P^*$ constructed by connecting the midpoints of the edges of $P$ is called the 'dual polygon'? Thanks to ...
- 604
-1
votes
0
answers
23
views
Cplex solution and dual of a problem
I have the following problem:
I took its dual as follows:
However, when I solve it on CPLEX, I somehow do not get the same objective value. Do you think there is something wrong?
Also, do you know ...
- 111
1
vote
1
answer
26
views
If two elements are different there is a functional under where the image is different
I have the following exercise in functional analysis:
Let E be a normed space and $x,y$ different vectors. Prove or disprove finding a counterexample that it exist a function $f \in E^*$ such that $f(...
- 91
0
votes
0
answers
36
views
Kleiman's relative duality: What does the notation $\omega_f \otimes_Y N$ mean, for a sheaf $N$ on $X$?
In Kleiman's paper Relative duality for quasi-coherent sheaves he defines for a proper, finitely presentable morphism $f: X \to Y$ with fibers of dimension $\dim X(y) \leq r$:
An $r$-dualizing sheaf $...
- 6,071
0
votes
0
answers
23
views
What's the dual problem of this quadratic programming problem?
$$\min\left(\sum_{i=0}^n \sum_{j=0}^n ((V_i)_j)x_ix_j\right)$$
subject to
$$x_1 + \dots + x_n = 1,$$ $$m_1x_1 + \dots + m_nx_n = m,$$ $$x_i \ge 0$$
0
votes
0
answers
24
views
Functors and projective covers
I'm looking to understand how a covariant functor that is an equivalences of categories preserves projective covers, and how a contravariant functor that is a dual equivalence of categories maps ...
- 317
0
votes
0
answers
12
views
Total integrality concept
I do not understand the total integrality concept in the integer optimization.
According to the notes I have, a rational system on linear inequalities $Ax \le b$ with $A \in \mathbb{Q}^{m \times n}, b ...
- 457
2
votes
1
answer
34
views
Finding a dual plan of a linear plan of nutrition
Trying to solve the following question:
A final list of foods is given, and a final list of nutrients (such as protein, carbohydrates, etc.). Also non-negative numbers $r_{k,l}$ are given that ...
- 2,067
0
votes
0
answers
33
views
Providing a certificate for maximum cardinal matching
I have bipartite graph with six nodes on each side. I have found one of the maximum cardinal matches with 4 pairs.
How do I provide a certificate (which can be checked with O(|V | + |E|) elementary ...
- 101
0
votes
1
answer
37
views
Using minimum cover to find maximum matching in bipartite
I was shown an algorithm in a test for using minimum vertex coverage in bipartite graph to find maximum edge matching. It made a lot of sense to me and I failed to come up with an example that proves ...
- 33
0
votes
0
answers
42
views
Are pre-duals dense if the duals are dense?
Assume we have two Banach spaces $X,Y$ over $\mathbb R$ such that $X' \subset Y'$ is a dense subset (with respect to the norm of $Y'$). My question is: Is $Y \subset X$ a dense subset (with respect to ...
- 71
0
votes
0
answers
47
views
Maximum matching = Minimum odd vertex cover
Definition:
A set $C⊆V$ and a collection of subsets $𝐵_1,…,𝐵_𝑘⊆V$ is an odd vertex cover if for every edge 𝑒 either $𝑒∩𝐶≠∅$ or $𝑒 ⊆ B_i$ for some 𝑖.
The cost of the odd vertex cover is ...
- 7
0
votes
0
answers
34
views
Exchanging limsup with liminf
I am working on a problem where I think I might be able to complete my argument if I can show the following relation.
\begin{align*}
\limsup_{k \rightarrow \infty} \liminf_{x' \rightarrow x} \frac{1}{...
- 149
0
votes
0
answers
21
views
Strong Duality with quasi convex objective and linear constraints
Take the problem
$$
\min f(x) \ \ \text{ s.t. } A x - b \leq 0_M
$$
where $f:\mathbb{R}^N \to \mathbb{R}$ is a quasi convex function, $A \in \mathbb{R}^{M \times N}$ $b \in \mathbb{R}^M$, and $0_M$ is ...
- 71
2
votes
0
answers
46
views
Topoi of algebras vs co-algebras, right adjointness compared to left exactness
I am asking about topoi of coalgebras over a comonad and algebras over a monad.
The comonad statement I am aware of is as follows:
Let $\mathcal{E}$ be a topos. Then if a comonad $T \colon \mathcal{E}...
- 282
0
votes
2
answers
109
views
How to apply complementary slackness
Given the primal
$$\max z= 5x_1-4x_2+3x_3$$
subject to
$2x_1+x_2-6x_3=20$
$ 6x_1+5x_2+10x_3\leq 76$
$8x_1-3x_2+6x_3\geq 50$
with $x_1\in \mathbb{R}, x_2\geq 0,x_3\leq 0$.
The question is to construct ...
- 2,623
0
votes
0
answers
19
views
Degeneracy of dual solutions
I'm new to this forum.
I have a question regarding the degeneracy of dual Solution, which I received in my recent exercise and can't seem to get to a proper solution:
"If a primal LP has a ...
0
votes
0
answers
39
views
For 3 straights $l_1,l_2,l_3$ in a 2-dimensional projective space $P(V)$ so that they don’t intersect. How can I prove the following statement:
Given 3 straight lines $l_1,l_2,l_3$ in a 2-dimensional projective space $P(V)$ so that for two on two lines: $l_i \cap l_j=\emptyset$
And $\{V_i\vert i=1,2,3\}\subset V $ and $l_i= P(V_i)$
Can ...
- 97
-1
votes
1
answer
50
views
Is there a positive element on the dual of a Banach space [closed]
Let $ X $ be a Banach space (complex or real). Is this possible $$ \sup_{\Vert x^{∗}\Vert \leq 1} x^{∗}(x) ≥0 \quad \forall x\in X.$$
in some Banach spaces, particularly in the Lebesgue space $ X=L^...
- 11
1
vote
1
answer
57
views
A certain categorical duality exchanges heads and socles?
Let $K$ be a field. Let $\mathsf{C}$ be an essentially small abelian category in which every hom-space is a finite-dimensional $K$-vector space.
For an object $X\in \mathsf C$ denote by $\operatorname{...
- 575
0
votes
0
answers
23
views
Primal constraints satisfaction
Given $\min_x f(x)$ subject to $g(x) = 0$, we write the Lagrangian as $\mathcal{L}(x,\lambda) = f(x) + \lambda g(x)$ and the dual as $g(\lambda) = \min_x \mathcal{L}(x,\lambda)$.
Let $x^* = \arg\min_x ...
- 289
2
votes
2
answers
89
views
About Benders decomposition for MILP [closed]
I have been using Benders decomposition for the following MILP:
Original problem
I put the binary y variables into the residual subproblem, which is as follows:
Residual subproblem
The dual form is:
...
- 41
0
votes
0
answers
15
views
Does the value of the lagrangian of all KKT points lie between $[\max\min \mathcal{L} , \min \max \mathcal{L}]$?
Let a constrained optimization problem where $f$ is nonconvex, $g$ is convex:
\begin{align}
&\mathrm{min}~f(x)\\
&\mathrm{s.t.}~g(x)\leq 0.
\end{align}
Does the value of the Lagrangian ...
- 185
0
votes
0
answers
31
views
What will be the dual of the abelian simply connected Lie group with the trivial Poisson structure?
Let $(\mathfrak{g}, [\cdot, \cdot])$ be a finite-dimensional Lie algebra with trivial cobracket with the corresponding abelian simply connected Lie group $G$ having trivial Poisson structure. Then its ...
- 2,722
0
votes
1
answer
50
views
LP Duality. What is the correct dual to this linear program?
Suppose a linear program that is defined as follows with decision variables $ w, x, y, z$ and parameters $a, b, c_j, d_i$.
$\min \sum_{I}^{} a x_{i} + \sum_{I}^{} b y_{i}$
$s.t.$
$x_{i} \geq w + \...
- 45
0
votes
0
answers
37
views
How to prove strong duality in linear programming using minimax theorem?
Let me provide the details of my request step-by-step.
In the further description, I consider finite $n \in \mathbb{N}$ and $m \in \mathbb{N}$ and $\mathbb{R}$ without $\infty$ and $-\infty$. Set $\...
- 477
2
votes
0
answers
42
views
Approximations of BMO functions
I couldn't think of a good title. There was a small detail when I was trying to prove something about the norm of BMO functions. This small detail is not directly related to the problem itself, but ...
- 95
0
votes
0
answers
54
views
Dual linear Program for $\min c^Tx$ subject to $Ax\leq b$
For $A\in\mathbb R^{n\times n}, b\in \mathbb R^n, c\in \mathbb R^n$ what is the dual linear program of
a) $\min c^Tx$ subject to $Ax\leq b$ and
b) $\max c^Tx$ subject to $Ax=b$?
I thin the dual ...
- 338
0
votes
1
answer
20
views
Slater's Condition and Primal Optimal Value
I know that Slater's condition implies strong duality and that the dual problem's supremum is attained. Is the infimum for the primal also attained under Slater's condition?
- 1,408
0
votes
0
answers
12
views
Primal and dual definitions of maximization problem in terms of $\sup$ and $\inf$
I know that for minimization problem
$$
\begin{split}
&\text{min }f(x)\\
&\text{s.t. }g(x) = 0\text{ and }h(x) \leq 0
\end{split}
$$
its primal is $P = \inf\limits_{x \in X}\sup\limits_{(y,...
- 35
0
votes
1
answer
13
views
Dual Descent and Primal infeasibility (near feasible)?
Suppose one considers a constrained and convex primal optimization problem:
$$P=\max f(x), \text{s.t.}\quad Ax\leq c$$
Consider now its Lagrangian:
$$L=\max f(x)+ \lambda ^T(c-Ax) $$
Suppose we ...
- 351
0
votes
0
answers
22
views
Are Lagrangian multipliers and dual variables the same?
Suppose the primal problem is:
\begin{equation}
\begin{array}{l}
\mathop {\min }\limits_x f\left( x \right)\\
s.t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} h\left( x \right) = 0\\
{\kern 1pt} {\...
- 1
0
votes
0
answers
25
views
Linear Optimization Duality
I was wondering, how can a dual optimal solution be strictly less than the primal optimal solution under the weak duality?
Is there a simple example of an integer problem exhibiting this behavior?
- 1
0
votes
0
answers
37
views
Is every dual of an object, a dual in a specific category?
We can often have multiple duals for the same type of object. A simple example is the Pontryagin dual vs the Langlands dual of a group $G$. Is the use of the word "dual" here precise, i.e. ...
- 155
3
votes
1
answer
130
views
Riesz–Markov–Kakutani representation for symmetric matrix-valued measures
Let
$\Theta$ be a closed $d$-manifold (and hence a metric space with Borel-$\sigma$-algebra $\Sigma \subset 2^\Theta$),
$S^d$ the set of real symmetric $d \times d$ matrices, which we can identify ...
- 4,426
0
votes
0
answers
20
views
What standard resolution is written about?
On the page 71 of "Two kinds of derived categories, Koszul duality, and comodule-contramodule correspondence" the author writes that $\text{gr}K$ is isomorphic to the standard resolution of ...
- 103
1
vote
1
answer
30
views
Can strong duality holds for convex programs, where Slater's condition is not satisfied?
I know that for a convex program, if Slater's condition is satisfied, then strong duality holds. I also know examples of convex programs, where Slater's condition is not satisfied and there is a ...
- 41
0
votes
1
answer
78
views
How is pole-polar duality related to line-point duality.
The above image is my depiction of what I am calling line-point duality. We can either think of the "point" as the equivalence class of arrows parallel to the large silver arrow ($\mathfrak{...
- 3,180
2
votes
0
answers
52
views
Maximum number of pairwise vertex-disjoint paths
My problem is:
Let $G$ be a graph, and let $A, B ⊆ V (G)$ (not necessarily disjoint). Prove that the
maximum number of pairwise vertex-disjoint $A$, $B$-paths in $G$ equals the minimum size of a set
$...
- 21
1
vote
0
answers
71
views
Proof of characterization of positive zeros of linear map using linear programming
Prove that for every matrix $A \in \mathbb{R}^{m \times n}$ precisely one of the following statements is true:
a) $\exists x \in \mathbb{R}^n: (Ax = 0 \wedge x > 0)$, where $x > 0$ means that ...
- 515
2
votes
0
answers
30
views
How to describe the duality of the quantities $ab$ and $a^2 + b^2$?
For real numbers $a, b$, the quantity $ab$ has the property that
$$ab = 0 \iff a = 0 \textrm{ or } b = 0$$
On the other hand, the quantity $a^2 + b^2$ has the property that
$$a^2 + b^2 = 0 \iff a = 0 \...
- 22.8k
0
votes
1
answer
43
views
What does the objective of the primal tell us about the dual?
So lets say the primal of the problem is written like this:
$$\max \sum^n_{j=1}c_jx_j$$
$$\text{subject to } \sum^n_{j=1}a_{ij}x_j\le b_i\qquad i=1,2,\ldots,m$$
$$\qquad x_j\ge 0\qquad j=1,2,\ldots,n$$...
- 13
1
vote
1
answer
443
views
Both primal and dual are infeasible/unbounded
With regards to linear optimization using the simplex method, can someone provide an example:
where both the primal and dual of problem A are infeasible
where both the primal and dual of problem B ...
- 300