All Questions
552 questions with no upvoted or accepted answers
1
vote
0
answers
628
views
Totally unimodular Matrices
A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
- 11
1
vote
0
answers
1k
views
How to solve simple bilinear equations under extra linear constraints
Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T u_{...
- 53
1
vote
0
answers
552
views
Computing the intersection of dual affine subspaces
Suppose we have a convex function , $\phi(x): R^d \to R$. It is well known that the Legendre transform of $\phi$ is also a convex function, and can (loosely) be thought of as the dual or derivative ...
- 111
1
vote
0
answers
439
views
Does the dual Banach space $B(\ell^\infty)$ have weak* normal structure?
Let $K$ be a bounded closed convex subset of a Banach space $E$. A point $x$ in $K$ is called a diametral point if
$$
\sup_{y\in K} \|x-y\|={\rm diam}(K).
$$
where ${\rm diam}(K)$ denotes the ...
- 1,222
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
0
votes
0
answers
15
views
On $N$-partition of some common subsets $\Omega\subset\mathbb R^d$
Let $\Omega\subset\mathbb R^d$ be compact and convex, and denote by $\ell$ the normalised Lebesgue measure such that $\ell(\Omega)=1$. Let $N$ be an arbitrary but fixed integer.
In this post we set $d=...
- 1,389
0
votes
0
answers
15
views
A question on Ibragimov's theorem on strong unimodality
I am not a mathematics student and unfortunately have some confusion about a (well-known) theorem about strong unimodality of distributions. First of all let me clarify some terminologies and then ask ...
- 51
0
votes
0
answers
35
views
Converse of Scherk–Segre theorem on the number of vertices of a convex space curve
It is well known that any smooth simple closed convex curve $\gamma$ in $\mathbb{R}^{3}$ that meets no plane in more than 4 points has exactly 4 vertices, i.e., points of vanishing torsion; here "...
- 965
0
votes
0
answers
35
views
Describing the boundary of the feasible direction cone to a convex open subset of $\mathbb{R}^n$ at a boundary point: connection via subdifferential?
Let $U\subset \mathbb{R}^n$ be a convex, open set with nonempty boundary. Let $x_0\in \partial{U}.$ We can describe $U$ locally near $x_0$ as a super level set of a suitable continuous concave ...
- 1,467
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
0
answers
28
views
How to calculate the vertices of a convex polytope (k-DOP)
I am currently reading Christer Ericson's Real-Time Collision Detection Book. The topic I'm particularly interested in, is the chapter about Discrete-orientation Polytopes (k-DOPs). In his words "...
- 1
0
votes
0
answers
37
views
Constructing a minimum-volume outer approximation polytope with fewer facets
I am tackling the following problem:
Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
- 101
0
votes
0
answers
27
views
Projection onto polytopes as tropical polynomial
Let $C$ be a convex polytope in $\mathbb{R}^n$ with $m$ extremal points. Let $p\in \{1,2\}$.
Can the $\ell^p$-projection $\Pi_C:\mathbb{R}^n\to C$
$$
\Pi_C(x) \in \operatorname{argmin}_{z\in C}\, \|x-...
- 364
0
votes
0
answers
69
views
Degree of reflectional symmetry of (unbounded) convex polyhedra in Euclidean spaces
Let $U \subset \mathbb{R}^m$ be an open domain. I'm trying to come up with a measure of its degree of reflectional symmetry and I have a question. The post in two-part, where in PART I I introduce the ...
- 1,467
0
votes
0
answers
67
views
Projection of a gaussian random vector onto a convex body
Let $K \subset \mathbb{R}^n$ denote a convex body. Let $\Pi_K$ denote the projection onto $K$,
$$
\Pi_K(y) = \mathrm{arg\,min}_{x \in K} \|y - x\|,
$$
where $\|\cdot\|$ denotes the usual Euclidean ...
- 400
0
votes
0
answers
21
views
Largest inscribed parallelepiped of the convex set defined by partial sum of Fourier series
Let $\mathcal{X}$ be the set consisting of all $(2n+1)$-dimensional real vectors $\mathbf{x}=\left( a_0,a_1,\ldots,a_n,b_1,\ldots,b_n\right)^{\intercal}$ satisfying
$$
\left| f_{\mathbf{x}}(t) \right|...
- 550
0
votes
0
answers
45
views
Support function of the intersection of two $\ell_p$ balls
Denote $\|\cdot \|_p$ for the norm in $\ell_p^n$, where $1 \leq p \leq \infty$, and $n \geq 1$.
Let $(x^\star_i)$ denote a nonincreasing arrangement of the sequence $(|x_i|) \in \mathbb{R}^n$.
We ...
- 400
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
0
votes
0
answers
82
views
On 'Bisecting sections' of 3D convex bodies
Following shadows and planar sections, we ask about bisecting sections. This post also continues Convex planar regions with all area bisectors having equal length and A claim on the concurrency of ...
- 5,979
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
0
votes
0
answers
72
views
Probability of being inside a convex n-dimensional polytop
I am currently conducting some post-grad research about wireless transmissions with uncertain transmission delays.
As part of the research, each individual transmission is modelled using a probability ...
0
votes
0
answers
42
views
On cutting polyhedrons into convex polyhedral pieces all with same volume, surface area and total edge length
This is a constrained version of the 'fair partition' ('spicy chicken' - https://arxiv.org/abs/1306.2741) question.
It seems that there are convex polyhedrons that cannot be cut into n convex pieces ...
- 5,979
0
votes
0
answers
40
views
Iterating partially-unconstrained optimization with projection
Let $f:H\to \mathbb{R}$ be a strictly convex Fréchet differentiable, coercive function on a separable Hilbert space $H$ and let $C_1,C_2\subseteq H$ be closed and convex.
I want to optimize
$$
\tag{(A)...
- 5,405
0
votes
0
answers
27
views
'$\alpha$-moments' and '$\alpha$-centers' of planar convex regions
We try to proceed from Least area and least perimeter triangles that contain a convex planar region - how different can they be?
The partial answer given to the above question shows a convex ...
- 5,979
0
votes
0
answers
32
views
Set of enclosed convex polyhedra in a graph
Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...
- 1
0
votes
0
answers
22
views
Directions of differentiability of log-concave measures with infinite-dimensional support
I recently came across the very nice review "Differentiable Measures and the Malliavin Calculus" by Bogachev (1997) which begins by discussing measures $\mu$ on locally convex spaces $X$ ...
- 651
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 101
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
0
votes
0
answers
49
views
Which planar convex region with specified area and perimeter maximizes/minimizes Moment of Inertia?
By moment of inertia of a planar convex region C, here we mean its moment of inertia about an axis passing through the center of mass of C and perpendicular to the plane of C.
Question: For specified ...
- 5,979
0
votes
0
answers
43
views
For a convex body $K\subset R^n$, does the quantity $\min_{t>0} E[t^{-1} \|tg - \pi_K( t g)\|_2]$ have a name? Where has it been studied?
Consider a convex compact set $K\subset R^n$ (with non-empty interior if that helps).
Let $\Pi_K:R^n\to K$ be the projection onto $K$, defined as
$$
\Pi_K(x) = \operatorname{argmin}_{k\in K} \|k-x\|
$$...
- 1,724
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 13.2k
0
votes
0
answers
171
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 129
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
0
votes
0
answers
56
views
Zero flux along lines
I am considering the $L^1$ ball in $\mathbb{R}^d$, and a conservative vector field $V$ on it, which arises as the gradient of a bounded, almost-everywhere Lipchitz-function. Denoting by $e_i$ as the i’...
- 232
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
0
votes
0
answers
47
views
On convexity of special fractals in the plane
Let $X \subset \mathbb{R}^2$ be a subset of the plane with Hausdorff dimension $1<dim_H(X)<2$.
For a subset $Y \subset \mathbb{R}^n$ we define $Y$ to be convex if for every $y_1,y_2 \in Y$ the ...
- 1,343
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439
0
votes
0
answers
84
views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...
0
votes
0
answers
141
views
Support function of the intersection of a hyper-ellipsoid and a Euclidean ball
Le $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_d$ be positive numbers. For any $x \in \mathbb R^d$ and $r \ge 0$, define $\gamma(x,r) := \sup_{z \in E(r)}x^\top z$, where
$$
E(r) := E \cap B_2^d(r)...
- 6,853
0
votes
0
answers
74
views
The closest ellipse and circle to a given triangle - 2
We add a little more to The closest ellipse to a given triangle.
The above linked discussion used the Hausdorff distance to quantify how close two planar convex regions are.
In an earlier post - ...
- 5,979
0
votes
0
answers
126
views
Question about symmetric bilinear form and convex geometry
Consider a Finsler norm $\varphi$ in $R^4$, and a positive definite symmetric bilinear form $S$, there also exists a vector-valued symmetric linear form $Q$, such that if $S(v, w) = 0$, then $Q(v, w)$ ...
- 21
0
votes
0
answers
272
views
Finding the eigenvectors of a submatrix
Let $A=(a_{kl})$ be a matrix in $M_n(\mathbb{R})$ when $n$ is even. Let $B=(b_{kl})$ be the symmetric $2n$ by $2n$ matrix whose entries are given by,
$b_{k,l}=a_{kl}$ if $1\leq k,l\leq n$.
$b_{n+k,l}=...
- 4,058
0
votes
0
answers
79
views
Number of tiles inside a region of a hyperbolic tiling
Let $\mathbb{D}$ be the Poincare disc model of hyperbolic geometry with $\{p,q\}$ tiling on it.
In this, paper authors calculated the number of tiles on any circular region centered at a vertex or ...
- 613
0
votes
0
answers
94
views
Boolean operation on n dimensional polyhedron
A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
- 21
0
votes
0
answers
140
views
Anti-concentration of the $\ell_2$ norm of log-concave measures
This question is regarding a special case of this question, for which it is plausible the details are known.
The Carbery-Wright inequality is an "anti-concentration inequality" that states ...
- 2,183
0
votes
0
answers
119
views
Polynomial-time algorithm for exact projection to polyhedral cone
Given $c \in \mathbb{R}^d$ and $A \in \mathbb{R}^{n \times d}$, project $c$ to the polyhedral cone $\{x \in \mathbb{R}^d \mid A x \leq 0\}$. Is there an algorithm that outputs an exact solution to ...
- 2,203