Questions tagged [duality-theorems]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...
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. ...
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}{...
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 ...
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^...
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 ...
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: ...
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 + \...
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 ...
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,...
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 ...
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 ...
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{...
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 $...
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 ...
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$$...
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 ...
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 ...
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?
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.
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 ...
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)}} = \...

1
2 3 4 5
24