Questions tagged [duality-theorems]
For question about the concept of dual, either in the sense of vector spaces, topological group or dual problems.
1,200
questions
2
votes
1
answer
23
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,047
0
votes
0
answers
15
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 ...
- 65
0
votes
1
answer
24
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 ...
- 13
0
votes
0
answers
34
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 densely imbedded. My question is: Is $Y \subset X$ densely imbedded?
Here, $X'$ denotes the dual space of $X$, i.e. ...
- 71
0
votes
0
answers
38
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 ...
- 9
0
votes
0
answers
28
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
17
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
44
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
79
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,605
0
votes
0
answers
15
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
38
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
47
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
55
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
22
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
80
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:
...
- 21
0
votes
0
answers
13
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
29
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,647
0
votes
1
answer
44
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
23
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 $\...
- 487
2
votes
0
answers
38
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
48
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 ...
- 300
0
votes
1
answer
17
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,388
0
votes
0
answers
11
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
10
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
18
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
22
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
36
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
-1
votes
1
answer
52
views
Dual of maximum volume ellipsoid problem. [closed]
I was looking over some tasks in Convex Optimization book by Boyd & Vandenberghe. Currently, I am having hard time understanding why $B^{-1}=(1/2)\sum_{i=1}^m{(a_iz_i^T+z_ia_i^T)}$ instead of just ...
- 35
3
votes
1
answer
122
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,385
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 ...
- 113
1
vote
1
answer
29
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
61
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,034
2
votes
0
answers
38
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
70
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 ...
- 473
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.6k
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
215
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
0
votes
0
answers
36
views
Converting a primal-dual pair into an equivalent feasibility problem to prove strong duality in LP
Suppose we have the following primal-dual pair
Primal
$$\text{minimize: } c'x$$
Subject to,
$$Ax = b $$
$$x\geq0$$
Dual
$$\text{maximize: } p'b$$
Subject to,
$$p'A \leq c' $$
To convert it into a ...
- 67
0
votes
1
answer
53
views
Pontryagin Dual of $\mathbb{F_p}[[T]]$
Let $\mathbb{F_p}$ be the field with $p$-elements and $\mathbb{F_p}[[T]]$ denotes the power series ring of one variable.
Question: Can we say what will be the Pontryagin dual Hom$_{\text{cont}}$ $(\...
- 300
0
votes
0
answers
28
views
basic question about infinite-dimensional optimization and semi-infinite dual
I study distributionally robust optimization by myself.
Someone may think this question is easy, but it is difficult for me to understand proof in below paper.So I post this question to understand the ...
- 31
1
vote
0
answers
102
views
Dual of sum of two sigmoid functions
Suppose we have 2 samples with features $\mathbf{x}_1,\mathbf{x}_2 \in \mathbb{R}^d$ and there is an uncertain parameter $\mathbf{\theta} \in \mathbb{R}^d$. Also, let's define $\mu(y)$ as a sigmoid/...
- 45
0
votes
0
answers
10
views
What are some applications of convex polars?
I know there are applications in optimization. A resource would be appreciated. But what are some other applications?
- 11
1
vote
1
answer
71
views
Proof of Strong Duality via Simplex Method
I am study the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The proof of strong duality (Theorem 4.4)
Theorem 4.4 (Strong duality) If a linear programming problem has an ...
- 445
0
votes
0
answers
16
views
Derive the dual problem for SVC algorithm with the decision function f(x) = <w, x> + b.
I'm trying to work on this problem and I don't know how to do with the decision function, f(x)=<w,x>+b. Could you please help me out? Thanks a lot.
- 23
0
votes
1
answer
55
views
Duality Theory Question (Exericse 4.34 in Bertsimas)
Suppose $P = \{x \in \mathbb{R}^n : Ax \ge b\} \ne \emptyset$ is a polyhedron where all inequalities are elementwise for the vectors $Ax$ and $b$ and suppose $0 \not \in P$. I want to find a ...
- 1,388
0
votes
0
answers
11
views
Dual Problems in Economics - Conceptual Question
Assume that I am solving a typical consumer problem in Economics in which I want to maximize the utility of an agent that consumes good $x$ and good $y$ and has a utility function $U=xy$ and a budget ...
- 91
0
votes
1
answer
41
views
Different versions of Duality principles
The duality principle for projective geometry states that the roles of the words "points" and "lines" in the theorems/definitions are interchangeable. Wikipedia says that it can be ...
- 83
1
vote
0
answers
31
views
What is the dual of norm function in form $\|x-y\|$?
I want to get the dual of the following norm function:
$$\max_\alpha\sum_i \alpha_i \|\lambda_i - \sum_j \alpha_j \lambda_j \|^2$$
And I know that the dual of this function is:
$$\min_\alpha \sum_i \...
3
votes
1
answer
118
views
Understanding the weak* topology on the space of distributions
I am studying distributions from Folland's book on real analysis. In this text he says
A distribution on $U$ is a continuous linear functional on $C_C^\infty(U)$ (where $U$ is an open subset of $\...
- 2,499
1
vote
1
answer
70
views
A dual norm optimization problem
I'm reading this machine learning optimization paper https://arxiv.org/pdf/2010.01412.pdf. At the last formula of page 3, they derived an optimization problem like this:
${\bf{\epsilon^*(w)}} = \...
- 51