# Questions tagged [duality-theorems]

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

1,210 questions
Filter by
Sorted by
Tagged with
32 views

Let $\lVert \cdot \rVert$ be any norm on $\mathbb{R}^n$ I want to prove that For any $x$, there is some $z$ such that $z^{T}x = \lVert x \rVert \lVert z \rVert _{*}$ where $\lVert y \rVert _{*} = \... 1 vote 1 answer 41 views ### Lagrangian Duality problem Suppose that$\lambda, N_0 \in \mathbb{R}$,$\boldsymbol{X}_{0} = (X_2',...,X_{m+1}')' \in \mathbb{R}^{m \times n} , X_1 \in \mathbb{R}^n$is fixed,$\iota \in \mathbb{R}^n$is the vector of ones, ... • 369 0 votes 0 answers 19 views ### How to solve minimisation using dual and simplex method How would I minimise$2y_1 + y_2$using the simplex method? subject to:$ 10y1 + y2 \ge 10  2y1 + y2 \ge 8  y1 + y2 \ge 6  y1 + 2y_2 \ge 10  y1 + 12y_2 \ge 12  y1,y2 \ge 0 $I have got ... • 73 2 votes 0 answers 17 views ### Dual operator of Markovian operator I am trying to incorporate the definition of dual operator in a Markovian setting. Say I have a Markov kernel$K:S\times S\to[0,1]$i.e., a mapping such that for every$A\in Sx\to K(x,A)$is a ... • 889 0 votes 1 answer 13 views ### subdifferentiable implies conjugate equality For function$f(x)=\max_i x_i, x\in\mathbb{R}^n$. We define the Fenchel conjugate as $$f^*(x^*) = \sup_{x} \langle x^*,x\rangle-f(x)$$ The standard subdifferential for$f(x)\$ as $$\partial f(x)=\{x^... • 77 2 votes 0 answers 90 views ### Constrained Optimization using FFT to find function I want to find the function W(x) from the following optimization problem: \begin{equation} \textrm{min} \left(I(x) - \int_{-\infty}^{\infty} W(x_0) d(x-x_0) dx_0\right)^2 \end{equation} \begin{... 0 votes 0 answers 32 views ### Operator norm as a dual norm? Given a space X endowed with a norm \left\lVert \cdot \right\rVert then one can define a norm \left\lVert \cdot \right\rVert_\star on the continuous dual space X^\star considering the ... • 889 0 votes 0 answers 38 views ### Dual polygons: terminology A question about terminology: is there a specific reason why, given a polygon P, the polygon P^* constructed by connecting the midpoints of the edges of P is called the 'dual polygon'? Thanks to ... • 604 -1 votes 0 answers 23 views ### Cplex solution and dual of a problem I have the following problem: I took its dual as follows: However, when I solve it on CPLEX, I somehow do not get the same objective value. Do you think there is something wrong? Also, do you know ... • 111 1 vote 1 answer 26 views ### If two elements are different there is a functional under where the image is different I have the following exercise in functional analysis: Let E be a normed space and x,y different vectors. Prove or disprove finding a counterexample that it exist a function f \in E^* such that f(... 0 votes 0 answers 36 views ### Kleiman's relative duality: What does the notation \omega_f \otimes_Y N mean, for a sheaf N on X? In Kleiman's paper Relative duality for quasi-coherent sheaves he defines for a proper, finitely presentable morphism f: X \to Y with fibers of dimension \dim X(y) \leq r: An r-dualizing sheaf ... • 6,071 0 votes 0 answers 23 views ### What's the dual problem of this quadratic programming problem?$$\min\left(\sum_{i=0}^n \sum_{j=0}^n ((V_i)_j)x_ix_j\right)$$subject to$$x_1 + \dots + x_n = 1,m_1x_1 + \dots + m_nx_n = m,x_i \ge 00 votes 0 answers 24 views ### Functors and projective covers I'm looking to understand how a covariant functor that is an equivalences of categories preserves projective covers, and how a contravariant functor that is a dual equivalence of categories maps ... • 317 0 votes 0 answers 12 views ### Total integrality concept I do not understand the total integrality concept in the integer optimization. According to the notes I have, a rational system on linear inequalities Ax \le b with A \in \mathbb{Q}^{m \times n}, b ... • 457 2 votes 1 answer 34 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,067 0 votes 0 answers 33 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 ... • 101 0 votes 1 answer 37 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 42 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 a dense subset (with respect to the norm of Y'). My question is: Is Y \subset X a dense subset (with respect to ... 0 votes 0 answers 47 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 ... 0 votes 0 answers 34 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 21 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 46 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 109 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,623 0 votes 0 answers 19 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 39 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 50 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 57 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 23 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 89 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 15 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 31 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,722 0 votes 1 answer 50 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 37 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 \... • 477 2 votes 0 answers 42 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 54 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 ... • 338 0 votes 1 answer 20 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,408 0 votes 0 answers 12 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 13 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 22 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} {\... 0 votes 0 answers 25 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 37 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 3 votes 1 answer 130 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,426 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 ... • 103 1 vote 1 answer 30 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 78 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,180 2 votes 0 answers 52 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 71 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.8k
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$$...