All Questions
793 questions
1
vote
0
answers
37
views
Sum of all integer binary solutions of a TUM linear system
I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
- 11
1
vote
0
answers
138
views
$L_p$ estimate in mixed boundary problem for elliptic equation
Let $Q$ be convex polygon, $\Gamma$ be a portion of boundary
$\partial Q$ and $H^1_\Gamma(Q)=\lbrace u\in H^1(Q):
u|_\Gamma=0\rbrace$. For $f\in (L_2(Q))^2$ consider the problem
$$
\int_Q A(x)\nabla u ...
- 46
1
vote
1
answer
211
views
Does coercivity/supercoercivity conjugates?
According to Wikipedia, a function $f: \mathbb{R}^n \to \mathbb{R} \cup \{-\infty, +\infty\}$ is called coercive if,
$$f(x) \to +\infty \text{ as } \|x\| \to +\infty$$
and it is super-coercive if
$$\...
- 125
1
vote
1
answer
97
views
Self-dual hypergraph on $\omega$
Let $H=(V,E)$ be a hypergraph. For $v\in V$ we let $v^* = \{e\in E:v\in e\}$. We define the dual of $H$ by $H^*= (E, V^*)$ where $V^* = \{v^*: v\in V\}$. We say that a $H$ is self-dual if $H \cong H^*$...
- 48.8k
13
votes
0
answers
800
views
Reference request for a complete and formal Duality Principle in category theory
Most textbooks on category theory only sketch the meaning of the Duality Principle. But even when they do it more formally, I have only seen a version so far which concerns the language of a (single) ...
- 63.1k
0
votes
0
answers
165
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
- 235
0
votes
0
answers
137
views
Any technique for linearization, or linear approximation?
Consider the following Matrix constraint:
$$
\begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0
$$
where $\Sigma_b$ is a known positive definite ...
5
votes
1
answer
338
views
Does rigidity imply a unique dualizing functor?
Let $\mathcal{C}$ be a rigid, monoidal category. Can I talk about $\mathcal{C}$ as having a unique, well-defined, dualizing functor (i.e. one that maps objects and morphisms onto their respective ...
- 1,389
0
votes
1
answer
131
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
38
votes
2
answers
1k
views
What are all the natural maps between iterated duals of vector spaces, and equations between these?
Fix a field. Given a vector space $V$ it has a dual $V^\ast$, which has its own dual $V^{\ast \ast}$, which has its own dual $V^{\ast \ast \ast}$, and so on ad infinitum.
There are lots of natural ...
- 22.3k
2
votes
0
answers
96
views
Evolution PDE in dual space : Generalization of a result of Gelfand
The following result is proved in "Generalized functions", Volume 3, Chapter 2.2 by Gelfand :
Let $\Phi$ be a Fréchet space with dual space $\Phi'$ endowed with the weak topology. For ...
- 233
3
votes
0
answers
282
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
- 781
0
votes
1
answer
213
views
How do you call a linear programming problem when the solution should be "constrained" to a norm?
(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...
- 143
2
votes
0
answers
211
views
Effect of dualization of density
Let $D\subset X$ be a dense subset of a complete separable locally convex space $X$ over $\mathbb{R}$. Though the question seems simple enough, I can't seem to find the answer in the literature:
If $...
- 109
5
votes
2
answers
193
views
Category with binary biproducts but no zero morphism
Is there a category with binary biproducts but no zero morphism?
I'm wondering if the definition of biproducts as objects that are simultaneously products and coproducts that obey some identities on ...
- 10.1k
5
votes
0
answers
488
views
Dual norm for weighted Sobolev space
Consider a "weight" function $\rho: \mathbb{R}^{d} \rightarrow \mathbb{R}$ and the following weighted Sobolev norm:
\begin{equation}
\|h\|_{\dot{H}^{1}(\rho;\mathbb{R}^{d})}:=(\int_{\mathbb{...
- 407
3
votes
0
answers
162
views
Reference for duality inducing bijections between subobjects and quotients?
I'm not the most category-theoretic person but I have run into the following statement in my work. Suppose we have a category duality $\mathcal F:\mathcal C\to\mathcal D$. For my needs you can ...
- 3,513
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
0
votes
1
answer
110
views
Detecting non-negativity of a single constraint by polyhedral constraints - $I$
We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
- 13.9k
0
votes
1
answer
116
views
Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem
This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...
- 1,421
6
votes
1
answer
272
views
Top cohomology of profinite Poincaré duality group
The paper "Cohomology of p-adic analytic groups" by Symonds and Weigel is considered one of the main references for continuous cohomology of profinite groups. There is a passage I do not ...
- 767
35
votes
12
answers
3k
views
No canonical isomorphism [duplicate]
I thought that it would be interesting to collect into a big list various instances of isomorphic structures with no preferred isomorphism between them. I expect the examples to be interesting since ...
5
votes
1
answer
875
views
Generalization of Bernstein’s inequality
I'm using Muscalu and Schlag's textbook to study harmonic analysis and I encountered the following claim:
Given some function $f \in \mathcal{S}(\mathbb{R}^{d})$, where $\mathcal{S}(\mathbb{R}^{d})$ ...
- 91
2
votes
1
answer
695
views
Confusing definition of homogeneous Sobolev norm of order -1
Let $\Omega \subset \mathbb{R}^{d}$ and $\|.\|$ is the standard euclidean $2$-norm. I came across a definition of $\dot{H}^{-1}(\Omega)$ which is a bit confusing. In [1] authors define the following ...
- 407
0
votes
0
answers
93
views
Number of vertices in a polyhedron
Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...
- 13.9k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
2
votes
0
answers
308
views
Maxwell $U(1)$ gauge theory's electric and magnetic sources turned on simultaneously in the classical differential geometry
Question:
How do we couple $U(1)$ electric (E) and magnetic (M) sources simultaneously in the classical differential geometry language, in a $U(1)$ gauge theory based on $U(1)$ gauge bundle and its $U(...
- 10.5k
1
vote
1
answer
98
views
Optimality gap between a joint linear program and decoupled sub programs
Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants.
Consider the linear ...
- 1,421
1
vote
0
answers
81
views
Algorithm for deciding feasibility of linear programs [closed]
Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...
1
vote
0
answers
191
views
Dual of union of Reproducing Kernel Hilbert Spaces
I have a union of Reproducing Kernel Hilbert Spaces $\mathcal{B}$. I am interested in finding the dual of $\mathcal{B}$. Knowing what the dual is might help to write an alternate formulation for the ...
- 171
8
votes
0
answers
1k
views
Wasserstein distance and Monge-Kantorovich-Rubinstein duality
The definition of Wasserstein $p$-distance between two measures $\mu$ and $\nu$ on a Polish space $X$ is given by
$$
W_p(\mu, \nu)^p = \inf_{\gamma \in \Pi(\mu, \nu)} \int_{X \times X} d(x, y)^p\; d\...
- 1,407
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
9
votes
1
answer
306
views
Origin and context of adjunctions inducing equivalences between full subcategories
The following is well-known.
Theorem. Let $F\dashv U$ be a pair of adjoint functors
$$F\colon \mathcal C\to \mathcal D, \qquad U\colon \mathcal D\to\mathcal C$$
with unit $(\eta_A\colon A\to U(F(A)))_{...
- 111
2
votes
0
answers
51
views
Conjugate of composition in Bochner spaces
Let $H$ be a separable Hilbert space (of non-zero dimension), let $(\Omega,\Sigma,\mu)$ be a finite measure space, and let $L^2(\mu;H)$ be the Bochner-space $\mu$-integrable $H$-valued functions. ...
8
votes
2
answers
429
views
Comparison: Formal Wirthmüller isomorphism of Fausk-Hu-May vs. Balmer et. al
$\newcommand{\Cc}{\mathcal{C}}$
$\newcommand{\Dd}{\mathcal{D}}$
$\newcommand{\tensor}{\otimes}$
$\DeclareMathOperator{\Sp}{Sp}$
This question is about comparing the approaches for a formal Wirthmüller ...
- 556
1
vote
0
answers
322
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
0
votes
1
answer
76
views
A question on graph partitioning
Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
- 1,216
8
votes
1
answer
551
views
Can one characterize maximal antichains in terms of distributive lattices?
This is inspired by the recent question Verification of a maximal antichain
The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them ...
- 18.4k
1
vote
1
answer
1k
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
14
votes
1
answer
1k
views
Are Spanier-Whitehead duals of general spaces expressible through some generalization of normal bundles?
The question is inspired by an answer to The concept of Duality
It is explained in that answer that the Spanier-Whitehead dual of a compact manifold is given by the Thom spectrum of normal bundles of ...
- 18.4k
3
votes
0
answers
87
views
Additional symmetries of the Traveling Salesman Polytope
Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
- 13.6k
2
votes
1
answer
290
views
On the dimension of the dual variety of a singular hypersurface
I was primarily interested in the following question. Let $n\geq 3$, and let $X\subset \mathbb{P}^n$ be a degree $d$ hypersurface. Assume that its singularity locus $S$ (with reduced structure) is ...
- 287
1
vote
1
answer
157
views
Constructing representations of probability revision functions
Let $P$ be a probability distribution over a finite Boolean algebra $\mathfrak{B}$, and fix a parameter $t_{P} \in (\frac{2}{3}, 1)$. Define the `revision function of $P$', $R_{P}: \mathfrak{B}\...
- 631
3
votes
1
answer
309
views
Duality argument for elliptic regularity
M. Dauge proved in [1] the regularity property "$\Delta u \in (W^1_{p'})^*$ $\Rightarrow$ $u \in W^1_p$" for Dirichlet and Neumann problem in domains with piecewise smooth boundaries, for $p&...
user171871
7
votes
1
answer
319
views
Is every sequentially $\sigma(E',E)$-continuous linear functional on a dual Banach space $E'$ necessarily a point evaluation?
$\newcommand{\bf}[1]{\mathbb #1}\newcommand{\sc}[1]{\mathscr #1}$
A duality between two vector spaces $E$ and $F$ over $\bf K$ ($= {\bf R}$ of ${\bf C}$)
is, by definition, a bilinear form
$$
\...
- 2,263
1
vote
1
answer
628
views
Allowing an "OR" option between equations in a linear program
I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.
I will explain what I mean precisely: Lets say I have a set of ...
- 141
9
votes
2
answers
341
views
Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?
A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...
- 13.6k