All Questions
793 questions
1
vote
1
answer
667
views
Calculating vertex weights
Vertex weights are a metaphor for a constant value $\pi_i$ that is added to the weight of every edge $e_{ij}$ that is adjacent to vertex $v_i$ in a symmetric graph $G(V,E)$ with weighted edges.
The ...
- 13.2k
1
vote
1
answer
228
views
Weak duality sign
Let $\left\{\begin{matrix}
\operatorname{min}_xc^Tx\\Ax\leq b
\\ x\in \mathbb{R}^+
\end{matrix}\right.$ be a LP primal problem and $\left\{\begin{matrix}
\operatorname{max}_yb^Ty\\A^Ty\geq c
\\ y\in ...
- 11
4
votes
3
answers
2k
views
Duality of finite signed measures and bounded continuous functions
Let $E$ be a metric space, $C_b(E)$ denote the space of bounded continuous functions $E\to\mathbb R$ (equipped with the supremum norm), $\mathcal M(E)$ denote the space of finite signed measures on ...
- 167
8
votes
2
answers
1k
views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 361
0
votes
0
answers
68
views
Convex optimization under asymmetric loss in infinite dimensional space
The following problem is common in financial economics
$$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$
That is, given a random variable $y(\theta)$ ($\...
- 45
2
votes
1
answer
139
views
linear programming with $n$ choose $r$ variables
Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is ...
- 51
3
votes
0
answers
513
views
From $f$-divergence to its dual: the transformation of convex functions on $\mathbb R_+$ by $f^*(t) = 1 f(\frac 1 t)$
I would like to understand the relationship between minimising the KL divergence $P \mapsto D_{KL}[P,Q]$ and the reverse KL divergence $P\mapsto D_{KL}^*[P,Q]=D_{KL}[Q,P]$ for probability measures $P$ ...
- 203
2
votes
1
answer
763
views
Integer solution of optimal transport
Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...
- 407
5
votes
0
answers
60
views
Self-duality of cones associated with elementary symmetric polynomials
Let $n\ge3$ be an integer, and denote $\sigma_1,\ldots,\sigma_n$ the elementary symmetric polynomials in $n$ indeterminates:
$$\sigma_1(X)=X_1+\cdots+X_n,\quad\ldots\quad,\sigma_n(X)=X_1\cdots X_n.$$
...
- 52.3k
2
votes
0
answers
110
views
A strong duality for convex functional optimization that admits Lipschitz continuity constraints?
Problem Statement
I am looking for formal proof---hopefully textbook material---of two items:
an analogue to Slater's condition [1] that obtains strong duality for optimization of convex functionals; ...
1
vote
1
answer
3k
views
How to minimize l1-norm constrained by "infinity norm"
Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $. I have the following two problems:
P.1.
\begin{equation}
\underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\
\text{s.t. } \| x \...
- 13
0
votes
1
answer
126
views
An otherwise linear matrix equation with the presence of a signum function : reference request
Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$
$\pmb{c}$ is a $n\times1$ matrix.
$G$ is a $n\times n$ matrix which is also positive definite.
matrices $G$ and $c$ are real.
$L$ is a $n\...
- 698
1
vote
1
answer
331
views
Dual problem with integrals
I am reading a paper where the author derives the following Lagrangian dual problem :
$\min_v \int_R \frac{1}{4} \frac{\beta^2}{v-2\|x\|}dx+v\;\;\;\text{s.t.}\;\;\;v\geq 2\|x\|\;\;\;\forall x \in R$
...
- 67
3
votes
0
answers
122
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
- 287
2
votes
0
answers
43
views
Weak relaxation of a strongly lower semi-continuous functional
Let $F$ be a lower semicontinuous functional on a Banach space $X$, wrt its strong topology. Is there a known form for the relaxation (lower semicontinuous envelope) of $F$ with respect to the weak ...
- 5,405
0
votes
0
answers
108
views
Solutions to matrix equations in the non-negative integers
For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer ...
- 101
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
- 13.9k
1
vote
0
answers
147
views
Convergence of infinite linear programming
Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
- 53
3
votes
2
answers
718
views
Bi-annihilator of a subspace of the dual of an infinite-dimensional vector space
Let $V$ be an infinite-dimensional vector space and $V^*$ its dual.
For a linear subspace $W\subset V$ define $W^ \circ\subset V^*$ as the subspace of linear forms on $V$ vanishing on $W$.
Dually, for ...
- 417
-1
votes
1
answer
103
views
How to solve MILP problem on several linear subspaces
I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...
- 39
5
votes
0
answers
270
views
Riesz Representation Theorem for $L^2(\mathbb{R}) \oplus L^2(\mathbb{T})$?
The spaces $L^2(\mathbb{R})$ (square-integrable functions) and $L^2(\mathbb{T})$ (1-periodic square-integrable functions, considered over the real line $\mathbb{R}$) are two subspaces of the space of ...
- 2,306
0
votes
0
answers
124
views
When is the natural map of Tate cohomology an isomorphism?
First of all I want to say that I am not at all an expert in Group cohomology . Recently I attended a seminar where the speaker mentioned about something called Tate cohomology groups which in ...
- 1,215
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
1
vote
0
answers
82
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
- 1,826
3
votes
1
answer
163
views
Duality problem of an infinite dimensional optimization problem
I am reading the paper "OPTIMAL INEQUALITIES IN PROBABILITY THEORY: A CONVEX OPTIMIZATION APPROACH" by BERTSIMAS and POPESCU. In the paper, the authors derived a duality problem for an ...
- 53
1
vote
0
answers
78
views
Reference for the algorithm to find the intersection between a subspace and positive orthant
I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...
0
votes
1
answer
139
views
Linear programming with exponential inequalities and rational variables
If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...
- 1,826
2
votes
1
answer
591
views
Intersection of a vector subspace with a cone
Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating ...
1
vote
0
answers
67
views
What are the corners of this polytope?
Let $f$ be a non-negative function on the positive integers such that $f(s+t)\geq f(s) + f(t)$ for all $s,t\in\mathbb{Z}^+$. Consider the polytope consisting of all $x\in \mathbb{R}^n$ such that $$\...
- 11
0
votes
1
answer
81
views
If $\tau_1\subset \tau_2$ and $X^*$ is separable for $\tau_1$ then $X^*$ is separable for $\tau_2$?
Let $X$ be a Banach space the associated dual space is denoted by $X^*$. Take $\tau_1$ and $\tau_2$ two topologies in $X^*$ compatible with the duality $(X^*,X)$, such that $\tau_1\subset \tau_2$.
...
- 199
1
vote
0
answers
231
views
Dual space of mean-free Sobolev space
I am considering the space $V:=\{v \in H^1(\Omega): \int_\Omega v = 0\}$ of mean free functions. What is the dual space of this space? Is the dual space given by $D:= \{f \in (H^1(\Omega))^*: \langle ...
- 11
5
votes
1
answer
349
views
A generalization of integral Poincaré duality
In this paper, Felix, Halperin and Thomas define the notion of a Gorenstein space over a field $\mathbb{k}$:
An augmented differential graded algebra $R$ over $\mathbb{k}$ is Gorenstein if $\text{Ext}...
- 208
6
votes
1
answer
720
views
If $X$ is separable space then $X^∗$ is separable in all topologies $\tau$ such that $(X^∗,\tau)^∗ =X$?
Let $(X,\|.\|_{X})$ be a separable Banach space and the associated dual space is denoted
by $X^*$. By $w^*$ we shall indicate the weak$-*$ topology on $X^*$.
Let $B_{X^∗}= \{x^∗ \in X^∗ : \|x^∗\|_{X^∗...
- 117
1
vote
0
answers
245
views
Dual varieties and nodal sections
Let $X$ be a(n even dimensional) smooth complex projective variety in $\mathbb{P}^N$, and let $X^{\vee}$ be its dual variety; up to an higher degree Veronese embedding of $X$, I assume that $X^{\vee}$ ...
- 828
2
votes
0
answers
166
views
Do Poincaré duality algebras need to be defined over a field?
I asked the below question here on MSE, but after some time and a bounty offering I have not received an answer.
A graded commutative, connected $\mathbb{k}$-algebra $A$ is called a Poincaré duality ...
- 208
1
vote
1
answer
282
views
Poincare duality-differential geometry
Let $ M $ be a smooth and compact manifold with boundary $\partial M = X \times F $ on which the structure of a smooth locally trivial bundle $$ \pi: \partial M \longrightarrow X $$
where the $ X $ ...
- 27
16
votes
1
answer
1k
views
What is a module over a Boolean ring?
Recall that a (unital) Boolean ring is a (unital) commutative ring $A$ where every element is idempotent; it follows that $A$ is of characteristic 2. There is an equivalence of categories between ...
- 63.9k
0
votes
1
answer
226
views
Fractional values in linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 1,421
0
votes
1
answer
320
views
Sub optimal algorithm for linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 1,421
8
votes
0
answers
451
views
Does any 'logical' theory have a bounded ∞-pretopos as syntactic category?
Stone duality may be understood as providing a duality between syntax and semantics for propositional logic, so that a theory may be recovered from its models. In order to do likewise for first-order ...
- 5,094
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121
0
votes
1
answer
144
views
Maximize function on rotation matrices [closed]
Let $A$ be a fixed 3-by-3 matrix and $Q$ be a rotation matrix whose yaw, pitch, and roll angles are $\phi\in[0,\pi]$, $\theta\in[0,\pi]$, and $\psi\in[0,\pi/2]$, respectively:
\begin{equation}
Q=
\...
4
votes
1
answer
456
views
Which topological spaces admit embeddings into Euclidean spaces
I'm interested in the dual question to:
continuous images of open intervals, about surjections onto open intervals.
Namely, if $X$ is a topological space, when can we guarantee that there exists a ...
- 5,405
2
votes
1
answer
472
views
Why are Serre functors always exact?
Let $k$ be a field and $\mathcal{T}$ be a $k$-linear triangulated category with finite dimensional spaces of morphisms. Bondal and Kapranov proved that every Serre functor on $\mathcal{T}$ is exact (...
- 142
7
votes
2
answers
276
views
Completeness of coefficient functionnals
My questions is about Schauder bases and more specifically about coefficient functionals.
Let $(x_n)$ be a Schauder basis of a Banach space $X$. Thus for all $x$ in $X$, $x = \sum f_n(x) x_n$. The $...
- 183
10
votes
1
answer
1k
views
Dual space of continuous Banach-space-valued functions
Let $X$ be a Banach space and $K$ some compact Hausdorff space. I am interested in the dual space of the Banach space
$$C(K; X) = \lbrace f: K \to X, \ f \text{ is continuous}\rbrace, \qquad \lVert ...
- 381
3
votes
0
answers
163
views
A new "adversarial" Wasserstein distance?
Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
- 555
11
votes
2
answers
963
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 1,826
2
votes
1
answer
485
views
Odd cycle transversal
Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...
1
vote
2
answers
958
views
Integer linear programming (ILP) formulation of connectivity of induced subgraph
Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...