Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...