For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.

learn more… | top users | synonyms

1
vote
1answer
4 views

Duality theorem between Cycle Space and Cut Space in terms of Matrices?

The book Graphs and Matrices by Bapat formulates linear algebra on graph theory, yet I cannot find important theorems such as Duality theorem between the cycle space and the cut space (Diestel p.26, ...
0
votes
1answer
10 views

Extending a bounded linear operator of finite rank

Let $X$ and $Y$ be normed spaces and let $W$ be a subspace of $X$. Assume that $T$ is a bounded linear operator from $W$ to $Y$, that is of finite rank. Show that $T$ can be extended to a bounded ...
1
vote
0answers
18 views

Represent of multilinear map [duplicate]

Let $V_1,V_2$ be vector space and $\{e_i\},\{\overline e_i\}$ are basis respectively. $\forall ~l\in L(V_1,V_2; F)$ ,why $l$ can be represented as $$ l=\sum\limits_{ij} a_{ij} \omega^i\otimes ...
2
votes
2answers
43 views

linear programming infeasibility, dual & primal relation

By the strong duality theorem we know that LP can have 4 possible outcomes: dual and primal are both feasible, dual is unbounded and primal is infeasible, dual is infeasible and primal is unbounded, ...
1
vote
0answers
16 views

Dual of a point which is in the convex cone of a set, contains the dual cone of that set

Let $\Lambda\subseteq R^n$ contains $m$ elements, where $\lambda_i$ is the $ith$ element, and $co(\Lambda)$ is the smallest convex cone contains $\Lambda$. Also, consider any point $u\in R^n$. Now, I ...
0
votes
0answers
13 views

Convex solver returns disordered dual variables, how to re-order?

I have the following convex optimization problem: $$ \begin{align*} \min_{x} &f(x) \\ \text{subject to} \\ x_{k+1} &= x_k+\cdots\qquad k=0,1,2,\ldots,N-1 \end{align*} $$ I managed to solve ...
0
votes
1answer
17 views

Why the dual and the canonical dual may have the same optimal solution?

For instance let be \begin{cases} \max & 3x_1 &+2x_2 &+4x_3 & -x_4\\ &x_1 &+x_2 &-2x_3&&\le4\\ &2x_1&+3x_3&&-4x_4&\ge 5\\ ...
0
votes
0answers
21 views

References for Duality Theory

I was wondering if anyone had any recommendations for Duality Theory. I've touched on Duality before in various courses but it's coming up quite a lot in my studies at the moment. I guess what I'm ...
1
vote
0answers
34 views

Some intuition about the second dual of $l^1$

In Functional Analysis we treated the Hahn-Banach theorem, and if I understood correctly, the dual space of $l^1$ (space of all absolutely summable sequences) is isomorphic to the space of all bounded ...
0
votes
0answers
11 views

Dual of cartesian product of duals of polytopes

I am working on the following problem. Let $P\subseteq \mathbb{R}^d, Q\subseteq \mathbb{R}^e$ be full-dimensional polytopes, both with the origin in the interior. Describe $(P^{\circ }\times ...
0
votes
1answer
33 views

Characterization of elements of $X^*$ via the Radon-Nikodym theorem

I am reading Lindenstrauss' Classical Banach Spaces II and I am having trouble with the following characterization of integrals. First a couple of preliminary definitions: Let $(\Omega, \Sigma, ...
1
vote
1answer
35 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
0
votes
1answer
36 views

Linear Optimization proof. Duality proof.

I need help with this problem. The exact problem is in this link http://d2vlcm61l7u1fs.cloudfront.net/media%2F959%2F959d289e-6f26-4e21-875e-bb71f3f5a49f%2Fphprimn1q.png Sorry for the poor formatting. ...
2
votes
1answer
37 views

If $H$ is a Hilbert space, are we able to identify the derivative ${\rm D}f(x)$ at some $x\in H$ of a differentiable $f\in H'$ with an element of $H$?

I'm confused about some equation I've seen in a book and want to write down some thoughts. I would appreciate, if somebody could tell me whether I'm terribly mistaken or not: Let ...
1
vote
1answer
59 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 ...
0
votes
0answers
6 views

Solving the primal problem via dual, the solution of the Lagrangian function L(x,λ∗) has to be unique.

Solving the primal problem via dual, the solution of the Lagrangian function L(x,λ∗) has to be unique. This is a subtlety requirement made by convex optimization book written by Prof. Boyd. Who can ...
0
votes
0answers
26 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. My book says that this is a corollary to complementary slackness. What's ...
0
votes
1answer
17 views

Perfect Pairing, non-degeneracy and dimension.

On this wikipedia entry https://en.wikipedia.org/wiki/Bilinear_form#Different_spaces it tells us that if $B: V \times W \to K$ is a bilinear map, then In finite dimensions, [a perfect pairing] is ...
1
vote
0answers
28 views

Quadratic dual help

I'm trying to figure out the whether the quadratic dual of the following algebra is anti-commutative. My algebra is $A=T(V)/J$ where $J=\langle I\rangle$ and $I\subseteq\bigwedge^2(V)$. Firstly I ...
1
vote
0answers
12 views

Variant of conjugate function: $V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$

Consider one variant of conjugate function: $$V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$$ You can think $s$ as a linear functional. If I do the following steps: ...
0
votes
0answers
14 views

Unbounded variables and dual of a linear program

I have to find the dual of \begin{cases} \max & -x_1 &-2x_2+x_3\\ & -3x_1 &+x_2&\le-1\\ & x_1 &-x_2&\ge 1\\ & -2x_1 &+7x_2&\le6\\ & -5x_1 & ...
0
votes
0answers
28 views

How to form a dual problem in convex optimization (in a broad view)

After reading some papers, this problem confuses me. There are different forms of dual problem to the primal problem: $$\underset{x}\min \ \ f(x)$$ where $f(x)$ is a convex function. By ...
0
votes
1answer
30 views

The dual space of a dual space

Eh, I don't quite understand the first question. Can someone explain it? And for the second question, can I say that they have the same dimension. And since the kernel is ${0}$, it is injective. ...
0
votes
3answers
21 views

vProve that the $\phi's$ form a basis for $V^*$

Hey guys. I've learned linear algebra before, but I kinda forget the part about dual space. For this problem, I think that because $V^*$ has the same dimension as V, which is n in this problem. And ...
0
votes
2answers
38 views

Find the dual of the lp problem

The problem given is and I need to find the dual: Min $Z=x_1$ st. $x_1+x_2 \leq 4$ $x_2 \geq 0$ So this is what I did, I said: Let $x_1=x_1'-x_1''$ where $x_1',x_1'' \geq 0$ So now ...
0
votes
0answers
43 views

Dual curve of an algebraic curve in affine coordinates

$F$ is an irreductible algebraic curve and we consider the application that sends a non-singular point $(a : b : c)$ in homogenius coordinates, to $\phi(a, b, c) = \bigl(f_x(a, b, c), f_y(a, b, c), ...
0
votes
0answers
10 views

Convert the Matching Polytope LP to Dual Program

For my course in discrete optimization I am studying about Polytopes and their dual programms. They state that the convex hull of Perfect Matchings in grahph $G=(V,E)$ is given by: $$ x\geq 0\\ ...
0
votes
1answer
42 views

Is this dual transform incidence and order preserving?

I am trying to understand duality explained in the book Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al. Unfortunately, I have some problem of solving a question in this ...
-1
votes
1answer
23 views

Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$ Then we come to the ...
0
votes
0answers
9 views

Finding the lower bound of a linear program with the duality method

The issue I have some difficulties understanding the lower bound of a program when applying the duality method. It seems that it comes from $$c^T\underbrace{\le}_{x\ge 0\\y^TA\ge c^T} ...
0
votes
0answers
9 views

Lower bound of averaging gradient method (Prof. Yurii Nesterov's paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The last inequality confuses me: (p.231) Note: 1. The ...
0
votes
1answer
18 views

What varialbes enter the $\min/\max$ in dual problem?

Having the following linear program: \begin{cases} \max & -x_1 & -2 x_2&+x_3\\ & -3 x_1 &+x_2 & &\le -1\\ & x_1 &-x_2 & &\ge 1\\ &-2x_1 & +7 x_2 ...
1
vote
1answer
14 views

Relationship between Primal and Dual problems

Considering the following program: \begin{cases} \max & 8x_1 & + 3x_2\\ & x_1 &-6x_2&\ge2\\ & 5x_1 +&7x_2&=-4\\ &x_1&&\le 0\\ && x_2&\ge 0 ...
0
votes
0answers
13 views

Primal + Dual relation with Complementary Slackness.

If let's say there exist an optimal solution to the primal with $x_1 = 0$, what can we deduce about the dual? Here is my attempt to answer this particular question: Since there exist an optimal ...
1
vote
1answer
26 views

Proximal-type support function properties - nonnegative & strongly convex (proof)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The following part confuses me: $\\$ $\\$ ...
2
votes
0answers
69 views

LASSO constrained and penalised forms: first - order conditions?

The LASSO problem can be formulated in two ways: 1) Constrained formulation: $$ \|Xw-y\|^2\to\min_{w}\\ \text{s.t. } \sum_{i}|w_i|\leq{t}. $$ 2)Penalised formulation: $$ ...
3
votes
1answer
31 views

Density and Dual Spaces

Let $X$ be Banach, and $Y \subset X$ a (strict) linear subspace with the property that for any $f,g \in X^*$, if $f \neq g$ then $f|_Y \neq g|_Y$. What can we say about the density of $Y$ in $X$? ...
0
votes
1answer
30 views

Do we complement Boolean variables in the Dual?

The Principle of Duality states that starting with a Boolean expression, another Boolean expression can be obtained by : 1. Changing OR to AND 2. Changing AND to OR 3. Changing 0 to 1 4. Changing 1 ...
1
vote
0answers
31 views

Extending $L^{p}$ Duality to $\sigma$-finite Spaces

Let $1 \leq p < \infty$, $(X,\mathcal{M},\mu)$ be a sigma-finite measure space. Let $L$ be a continuous linear form on $L^{p}(X,\mathcal{M},\mu)$. Then, show that $\exists g \in L^{p'}$ such that: ...
0
votes
0answers
25 views

How does changing the cost vector of a primal linear programming problem affect the solution of the dual?

Say the linear program: max $p'x$ such that $Ax=b$ and $x \geq 0$ is primal and dual feasible, and $\bar{u}$ is known to be the optimal solution to the dual. If the $\lambda \ne 0$ times the $i$th row ...
0
votes
1answer
31 views

Formulating the Dual of a linear program

I have a linear program: Maximize 18x + 12y subject to: x+y <= 20 x <= 12 y <= 16 x,y >=0 I have found ...
1
vote
2answers
25 views

Proving that there exists a basis for a given dual basis

I need some guidance with the following proof: Let V be a finite dimensional vector space, and V* its dual. Let C = $(f1, ... , fn)\subset{V*}$ be a basis for V*. Let $w\in{V*}$. Prove that there ...
4
votes
0answers
65 views

Nature of the Hessian of the dual function?

I originally posted this over at MathOverflow but it did not receive much (...any) attention. I'm hoping someone can point me in the right direction over here. Consider a nonlinear optimization ...
0
votes
0answers
32 views

Is this statement true? (characterize elements of dual group)

Let $\mathbb{K}$ be a local field. Definition of local field: Let $\mathbb{K}$ be a field and a topological space. Then $\mathbb{K}$ is called a locally compact field if both $\mathbb{K}^+$ ...
0
votes
0answers
57 views

If $W$ is a subspace of the finite-dimensional vector space $V$, show that $W^* \cong V^*/A(W)$.

If $W$ is a subspace of the finite-dimensional vector space $V$, show that $W^* \cong V^*/A(W)$. Conclude that $\dim A(W) = \dim V - \dim W$. Hint: Define a map $\psi: V^* \rightarrow W^*$ by ...
0
votes
1answer
33 views

Goldstine theorem

Given the embedding $j:X\to X''$ defined by, $$j=(x\mapsto(\phi\mapsto\phi(x)))\,,$$ according to my interpretation of the wikipedia page, Goldstine theorem says the following: ...
1
vote
1answer
47 views

Show that $A(W)$ is a subspace of $V^*$. Show also that if $W' \subseteq W$ then $A(W) \subseteq A(W')$.

Given the subset $W$ of the vector space $V$, call $A(W)$ = {$\phi\in V^* | \phi$ annihilates $W$} the annihilator of $W$. Show that $A(W)$ is a subspace of $V^*$. Show also that if $W' \subseteq W$ ...
2
votes
1answer
60 views

If $\phi \in W^*$, show that we can find a $\widetilde{\phi} \in V^*$ such that $\widetilde{\phi}\Bigr|_{W} = \phi$

Let W be a subspace of the vector space $V$. If $\phi \in W^*$, show that we can find a $\widetilde{\phi} \in V^*$ such that $\widetilde{\phi}\Bigr|_{W} = \phi$ So, this is what I know: For $W$ to ...
0
votes
0answers
27 views

Why are Duals of Two Equivalent compound propositions Equivalent?

I know that if we have two equivalent propositions p and q then p* and q* will also be equivalent where p* and q* are duals of p and q respectively. I am looking for some explanation to why duals of ...
1
vote
1answer
36 views

Weak closure and dual space

Let $X$ be a normed space and let $W\subset X^*$ be a subspace which separates the points in $X$. Let $\psi \in X^*$ such that $\ker \psi $ is $W$-weakly closed. Show that $\psi \in W$. Any ideas?