Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
1
vote
1answer
46 views
Find the Dual of a Primal Linear Programming Problem
Consider the problem $$\text{min}_{x\in\mathbb R^n}\lvert Ax-b\rvert,$$
where $A$ is a $m \times n$ matrix and $b\in\mathbb R^m.$
Rewrite the problem into the form$$(P)\qquad \text{Minimize }\lvert z\...
2
votes
0answers
58 views
(Strong) Duality for the integer programming for $\text{gcd}(c_1, c_2, \ldots, c_n)$
It is known that (quoted from CLRS, 3rd edition)
If $a$ and $b$ are any integers, not both zero, then $\text{gcd}(a, b)$ is the smallest positive element of the set $\{ax + by: x, y \in \mathbb{Z}\}...
1
vote
1answer
25 views
Non degenerate optimal solution in primal <=> non degenerate optimal solution in dual
I was trying to solve this exercise when my primal is $\min c'x$
$s.t: \ Ax=b \ , x \geq 0 $.
For the => proof i think i solved it. This helped me a lot.
But the reverse, i think is more ...
0
votes
0answers
14 views
Showing Weak Duality
Suppose we have the Linear program max{$c^Tx: Ax \geq b, x \leq 0$}, and thus its corresponding dual is min{$b^Ty: A^Ty \geq c, y \geq0$}. I am trying to prove that weak duality holds and that $b^Ty \...
1
vote
1answer
58 views
Duality Theorem for Minimum Distance Problems
The minimization of the one-norm can be stated as:
$$
\min_{u\in\ell_1} \|u\|_1 \qquad \text{subject to} \qquad Au=b,
$$
where $u\in\mathbb{R}^m = [u_1,u_2,...,u_m]^\intercal$ is the sequence that we ...
0
votes
0answers
12 views
KKT conditions and weak duality
KKT conditions are always necessary for optimality and are sufficient under strong duality.
Why is strong duality needed for sufficiency? Why is weak duality not sufficient?
1
vote
0answers
28 views
properties of identically self-dual matroids
I'm dealing with an identically self-dual matroid M on the vertices E=[2N], that is, if B is a basis of M also E-B is a basis of M itself. I need simple combinatorial properties of these, things like ...
0
votes
0answers
13 views
Show that LPs concerning $P(A,b)$ and $P^{=}(A^{'},b^{'})$ are equivalent
Define $P^{=}(A^{'},b^{'}):=\{x \in \mathbb R^{n}: A^{'}x=b^{'}, x \geq 0\}$
and $P=P^{=}(A,b)=\{x \in \mathbb R^{n}: Ax = b, x \geq 0\}$
Let $A \in \mathbb R^{m\times n}$ and $\operatorname{Rank}A&...
0
votes
0answers
34 views
The Dual Model of Primal Non Linear
I am working on the follwoing nonlinear model.
Min z=10(1-$\exp(-3x)$)
subject to:
x $\leq $ 3
How can I build the dual model of this nonlinear model ?
Thank you in advance
1
vote
0answers
22 views
Dual pairing and inner product in a Hilbert space (and in $L^2(V)$)
I put beforehand that there are some similar questions in this blog, but I nonetheless would like to pose my question as I did not find any explanatory answer.
Let us consider a vector space H, ...
0
votes
0answers
36 views
Optimization of $\min{ c^{T}x+b^{T}y}$
I am new to optimization, and whenever we get an LP of the sort:
$\min{ c^{T}x+b^{T}y}$
s.t.
$Ax\leq b$
$A^{T}y=-c$
$y \geq 0$
Assume that there is a valid point that fulfills the restrictions. ...
0
votes
1answer
28 views
Duality gap in non-convex optimization: Do KKT conditions+constraint qualification imply strong duality?
Consider the non-convex optimization problem:
$$\underset{x\in \mathbb{R}^n}{\min} ~f(x) \\
\mbox{s.t.}~h_i(x)=0 ~~~\mbox{for}~~~i=1,\ldots,p \\
~~~~~~ g_j(x)\leq0 ~~~\mbox{for}~~~j=1,\...
0
votes
0answers
19 views
Group Algebra of a Discrete Group and Different Notions of a Group Algebra?
I am reading these two wiki articles: https://en.wikipedia.org/wiki/Group_algebra and https://en.wikipedia.org/wiki/Pontryagin_duality
From my understanding, the group algebra of a topological group ...
2
votes
2answers
27 views
Duality between Ideal and Filters on a poset
I am studying Ideals and Filters on a poset, and it is clear to me that this are dual notions in the sense that reversing inclusions in the definition we can get the one from the other, or in the ...
2
votes
2answers
47 views
Which posets arise as $P\to\Bbb B$ for $P$ a poset?
Let $\Bbb B$ be the poset $\{\top,\bot\}$ with $\bot\leq\top$. Given a poset $P$ let $P\to\Bbb B$ be the poset of order-preserving functions from $p$ to $\Bbb B$, ordered by $f\leq g$ if and only if $...
1
vote
2answers
79 views
Show that the dual of $\min c^{T}x+d^{T}x^{'}$ and $\max a^{T}x+b^{T}x^{'}$ are equivalent
Show that $(1)$ can be written in the form $(2)$
$(1)$
$\min c^{T}x+d^{T}x^{'}$
$\operatorname{s.t.}$
$Ax+Bx^{'}\geq a$
$Cx+Dx^{'}= b$
where $x, x^{'} \geq 0$ and
and
$(2)$ $\max a^{T}y+b^{T}y^...
0
votes
0answers
13 views
How to find the dual of max flow using bounding?
I am learning about dual programs in a grad class, but the lectures are lacking. I had to teach myself the bounding method and I understand it, but I'm not sure how to apply it to the Max-flow ...
4
votes
1answer
58 views
If the dual of a module is finitely generated and projective, can we claim that the module itself is?
Assume that $R$ is a commutative ring and that $M$ is a (left) $R$-module. Assume also that we know for some reason that $M^*:=\mathsf{Hom}_R(M,R)$ is finitely generated and projective as (right) $R$-...
0
votes
0answers
31 views
Duality and bounds on Lebesgue measure
A nice exercise was posted yesterday on Google+ : given the ellipse of equation $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$, find the rectangle with maximal area whose corners lie on this ellipse. I realized ...
0
votes
1answer
13 views
Proving infeasibility using Duality
suppose we have the linear program min{$c^Tx: Ax \leq 0, x \leq 0$} and its corresponding dual
max{$0^Tx: A^Ty \geq 0, y \leq 0$}. How can we show that the Dual is infeasible? I started by ...
2
votes
2answers
48 views
Under what conditions, one of completeness and cocompleteness can imply the other in a category?
When I tried to prove the completeness and cocompleteness of the category of small categories $\mathbf{Cat}$, I thought that proving either one of them could imply the other by taking the dual ...
0
votes
1answer
20 views
Lagrange dual of quadratic optimization problem with quadratic equality constraints
What is the Lagrange dual of the following optimization problem in $w \in \mathbb{R}^2$?
$$\begin{array}{ll} \text{minimize} & w^T Q \, w\\ \text{subject to} & w_1^2 = 1\\ & w_2^2 = 1\end{...
1
vote
1answer
32 views
Strong Duality: If Dual is optimal then primal is optimal
Strong duality states that if the Primal has an optimal solution then the Dual has an optimal solution. Is the converse of this statement true? To me it would seem intuitive that it is, but I just ...
2
votes
2answers
85 views
Optimal Value of a Cost Function as a Function of the Constraining variable
Consider the optimization problem :
$
\textrm{min } f(\mathbf{x})
$
$
\textrm{subject to } \sum_i b_ix_i \leq a
$
Using duality and numerical methods (with subgradient method) i.e.
$d = \...
0
votes
1answer
45 views
Rudin functional analysis theorem 4.13, (a) and (b)
Let $U$ and $V$ be the open unit balls in the Banach spaces $X$ and $Y$, respectively. If $T \in \mathcal{B}(X,Y)$ and $\delta > 0$, the the implications
$$
(a)\to(b)\to(c)\to(d)
$$
hold among ...
0
votes
1answer
30 views
Rudin Functional analysis, theorem 4.12 corollary (b)
Suppose $X$ and $Y$ are Banach spaces, and $T \in \mathcal{B}(X,Y)$ Then
$$
\mathcal{N}(T^*) = \mathcal{R}(T)^{\perp} \;\;\text{and}\;\; \mathcal{N}(T) = ^{\perp}\mathcal{R}(T^*)
$$
The corollary ...
1
vote
0answers
28 views
Tate construction of the Anderson dual of the sphere spectrum
I am trying to understand example I.2.3 of the article "On Topological Cyclic Homology", i.e. im trying to see the necesity of the bounded below assumption in the Tate Orbit Lemma (Lemma I.2.1) by ...
4
votes
1answer
74 views
Obtaining the $L^p$ norm of a function via testing against $L^{p'}$ functions.
Let $f:\mathbb{R}^n\to\mathbb{C}$ be a locally integrable function and let $p\in[1,+\infty)$ and $p'\in(1,+\infty]$ such that $\frac{1}{p}+\frac{1}{p'}=1$. Denoting by $C^\infty_c(\mathbb{R}^n)$ the ...
1
vote
0answers
33 views
Finding the equilibrium conditions for the Chebyshev approximation problem
$$-x_0 ≤ \sum_{j=1}^n a_{ij}x_j-b_i ≤ x_0 $$
$$ i=1,...m$$ $$\mathrm {min} x_0 $$
(Forgive me if I made any formatting mistakes; I'm not familiar with MathJax)
I know better than to try and use ...
1
vote
0answers
16 views
Feasibility of dual programs
I am having trouble understanding the feasibility of dual programs. I am new in this topic and some help would be greatly appreciated :))
For example , here i have two problems in duality :
The ...
4
votes
0answers
55 views
Convergence of non-finite measures
Consider the sequence $(\mu_n)_{n\in \mathbb{N}}$ of Borel measures on $\mathbb{R}$ given by:
$$
\mu_n = \sum_{k\in \mathbb{Z}} \Delta x_{n,k} \, \delta_{x_{n,k}}
$$
where $\delta_x$ denotes the ...
2
votes
1answer
46 views
Taking Dual of a Linear Program
Take the dual of the following LP:
min $x_1 + x_2 + 4$
such that
$$\begin{bmatrix} 1 & 3 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\x_2 \end{bmatrix} \leq \begin{bmatrix} 10 \\ 21 \end{...
1
vote
0answers
7 views
The dual of an optimal problem subject to infinity norm of a matrix
The optimal problem comes from paper <Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data>, section 3.1 is
$$
\hat{y}:= \arg\min_y \{ y^T W^{-1} y:...
1
vote
2answers
50 views
Find the Dual of a Linear Programming Problem
I have a very simple linear programming problem with the following constraints:
Minimize $3x_1 + 2x_2 - 33x_3$
subject to
$x_1 - 4x_2 + x_3 \leq 15$
$9x_1 + 6x_3 \leq 12$
$5x_1 + 9x_2 \geq 3$
$...
2
votes
0answers
30 views
A construction of the Hodge Dual operator
This question about showing that an alternative construction of the Hodge dual operator satisfies to the universal property through which the Hodge dual is usually defined.
Let me give the ...
5
votes
1answer
100 views
Generalization of the fundamental theorem of duality
The "fundamental theorem of duality" states:
If $X$ is a real linear space and $f, f_1,...,f_n$ are linear functionals on $X$, then $f$ lies in the span of $f_1,...,f_n$ (i.e. $f = \sum_{i=1}^n \...
1
vote
1answer
59 views
Why are dual spaces called “dual spaces”, even when I don't see if they're really “complements”?
Why are dual spaces called "dual spaces", even when I don't see if they're really "complements" of the original space.
In optimization the primal-dual distinction seems to rely on logical complement. ...
1
vote
2answers
59 views
$C(X)$ not reflexive if $X$ has infinitely many points.
Let $X$ be a compact metric space with infinitely many points, then show $C(X)$ is not reflexive. I think I see why this is the case for $X=[a,b]$, but I don't see how one can extend it. Is there a ...
0
votes
0answers
14 views
Duality in multi-objective optimization
I hope that have a great time.
I have a vital problem. Actually, I need to work with duality for multi objective optimization problems. However, many of references have analysis basis. My question ...
1
vote
0answers
18 views
Fenchel-Moreau is an Involution of Convex functions on a Hilbert space?
The Fenchel-Moreau theorem states that for a function $f:X\rightarrow [-\infty,\infty]$ (not exactly $\mp \infty$) the following are equivalent.
f is proper, lsc, and convex
$f=f^{**}$.
Where $f^*$ ...
1
vote
1answer
37 views
Dual of a complete topological group
Let $(G,+)$ be an Hausdorff topological abelian group. Assume that $G$ is complete, i.e. every Cauchy sequence in $G$ converges in $G$.
Let $\widehat G:=\operatorname{Hom}_{\text{cont}}(G, S^{1})$ be ...
0
votes
1answer
31 views
in linear programming, why does the dual have constraints?
in introduction to linear optimization ($\text{p. 142}$), they take the standard form problem:
minimize $c'x$, s.t. $Ax = b$, $x\geq 0$
they relax the constraints and define:
$g(p) = \min_{x\geq 0}[...
0
votes
1answer
61 views
Isomorphism between tensor product of vector fields and their dual.
Consider two finite dimensional vector spaces $V_1,V_2$ and their duals denoted by $V_1^{*},V_{2}^{*}$. I am working on a problem that is asking me to prove a generalized version of the below, but I ...
0
votes
1answer
31 views
Dual of module isomorphic to module itself?
If $A$ is a finitely generated $B$-module, is it true that dual of $A$ is isomorphic to $A$,i.e.,$Hom(A,B)\cong A$?
I guess given $f \in Hom(A,B)$, if $f(a)=1$, then I can identify $f$ to $a$. Am I ...
0
votes
1answer
22 views
Image unit ball under Isometric Isomorphism
Let $X,Y$ be a normed spaces, not necessarily finitely dimensional and let $T\in B(X,Y)$ be an isometric isomorphism. I want to show the same holds for the dual of $T$, $T'\in B(Y',X')$. The ...
0
votes
1answer
45 views
Dual gradient ascent vs Primal Interior Point methods
When solving problems, particularly constrained optimization in the field of reinforcement learning, I have noticed the use of dual gradient descent. An example of this is in model-based reinforcement ...
3
votes
2answers
53 views
Do complete atomic boolean algebras form a full subcategory of boolean algebras?
I would like to know if a boolean morphism (that is an application that respects $\vee, \wedge, \neg, 0,1$) between two complete atomic boolean algebras is necessarily complete (it respects also ...
4
votes
1answer
38 views
Question on Banach-Alaoglu theorem: Bounded subset of a set contained in the dual space
So the Banach-Alaoglu theorem states:
Let $X$ be the dual space to some Banach separable space $Z$, i.e
$X=Z^*$. Take $M$ a bounded subset of $X$. Then any sequence in $M$
has a weak-* ...
0
votes
0answers
24 views
Binary Polymatroid Optimization Problem
Let $\mathcal{N}$ denote the finite set $\{1, 2, \ldots, n\}$, and let $\mathcal{S}_j$ denote the set $\{1, 2, \ldots, j\}$; let $f\colon \mathcal{N} \to \mathbb{N}$ be nondecreasing, submodular and ...
2
votes
2answers
77 views
Solving a LP problem
I am learning optimization and I came across this exercise to solve the following problem:
$$\min 2x_1+3x_2$$
$$x_1+x_2\geq 5$$
$$x_1\geq 1$$
$$x_2\geq 2$$
This exercise has been introduced just ...
