All Questions
279 questions with no upvoted or accepted answers
0
votes
0
answers
96
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 29
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 ...
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
0
votes
0
answers
92
views
Lines through the origin every pair of which meet at the same angle
This item isn't getting attention, so I'll try it here:
begin quote
The three lines through antipodal pairs of centers of faces of a cube meet each other pairwise at $90^\circ$ angles.
The three lines ...
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
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
0
votes
0
answers
109
views
Comparing Euclidean norm of two normal vectors
Let $X_i$ ($i = 1,2$) be two random vectors in $\mathbb R^n$, with normal distribution with scalar covariance matrix $\sigma_i^2$ and center $\mu_i$ (in my case, $n = 2$). Is there a way to estimate ...
- 101
0
votes
0
answers
43
views
Minimizing along independent directions, nonlinear programming
Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...
- 193
0
votes
0
answers
101
views
How can we analytically solve this max-sum-min problem?
Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...
- 167
0
votes
0
answers
35
views
Converting a vector in a cone statement to inequality constraints
I would like to convert the following condition for $x$
\begin{align}
x = N \lambda, \lambda \geq 0
\end{align}
to a pure linear inequality form, i.e. find an $L$ and eliminate $\lambda$
\begin{...
- 1
0
votes
0
answers
232
views
What do square roots as minimums have to do with Harmonic numbers?
In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series:
$$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...
- 1,183
0
votes
0
answers
89
views
Why there isn't lexicographically smallest solution to a bounded linear program?
I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
- 1
0
votes
0
answers
136
views
Inequality on simplex with circumscribed sphere
I'm looking for a proof for this problem on simplex which I think it is true
Question. Let $\mathcal{A}=A_0A_1...A_n$ be a simplex in $\Bbb E^n$. $(S)$ is circumscribed sphere of $\mathcal{A}$ with ...
- 705
0
votes
0
answers
99
views
Is this Graph Iteration Already Known?
When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...
- 13.2k
0
votes
0
answers
46
views
linear inequalities and reference request
I have proved and am using the following simple lemma in my current research problem:
Let $\{a_1,...,a_m\}$ and $\{b_1,b_2,...,b_n\}$ be set of positive numbers such that $\sum_{i=1}^m a_i < \sum_{...
- 1,269
0
votes
0
answers
369
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
- 136
0
votes
0
answers
68
views
A seemingly easy integer programming question
Let $k, m \in \mathbb{Z}_{ > 1}$. Let $a \in \mathbb{Z}_{> 0}^m$ and $t \in \mathbb{Z}^k$. Let $\varepsilon = (\varepsilon_{i,j})_{1 \leq i \leq m \\1 \leq j \leq k}$ be a matrix with entries in ...
- 501
0
votes
0
answers
890
views
Maximum shortest path problem
I have the following problem. You have a graph and every edge has a certain set of possible weights. The question is to find the assignment of those weight which will maximize the shortest path.
In ...
- 342
0
votes
0
answers
917
views
Inverse problem with a rank-1 update
I hope you can help me out with this. I have to find the solution x to an inverse system
$$
x=A^{-1}b
$$
This inverse problem is basically a least square problem with a rank-1 update.
$$
x=[uv^{T}...
0
votes
0
answers
126
views
About the area of the region where the paper is twofold when you double a piece of paper in the shape of a triangle
Suppose that you have a piece of paper in the shape of a triangle $ABC$ whose area is $S_0$ and that the area of the region where the paper is twofold when you double the paper in two along a line is ...
- 4,757
0
votes
0
answers
104
views
Big eigenvalues of a special stochastic matrix
Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq |\lambda_2|(M)....
- 105
0
votes
0
answers
103
views
Gauss-Newton for quotient functions
I'm optimizing a function of the form
$$
\sum \frac{ \|\mathbf{f_i}(x)\|^2 }{ g_i(x)^2 + h_i(x)^2 }
$$
where $x$ is a real vector, $\mathbf{f}(x)$ is a real vector, and $g(x)$ is a scalar. My first ...
- 561
0
votes
0
answers
194
views
A linear program related question
Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, \alpha_2^...
- 769
0
votes
0
answers
79
views
Computing maximum point for minimal function of a family of linear functions
Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such that:...
- 11
0
votes
0
answers
783
views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0
answers
114
views
Error Metric which incorporates both mean & standard deviation of data in euclidean space
For simplicities sake (the actually problem is more complex)...Let say I have a set of n 3d points, whose position move over time. For all pairs, I have calculated the mean and standard deviation of ...
- 101
0
votes
0
answers
191
views
Inertia/Gravity in Distance Geometry
The Cayley-Menger Determinant, D(N), slickly calculates the N-dimensional simplex
volume of any N+1 points. One constraint in our 3D world is that D(4)=0.
Give each point a mass (Mi) and dynamic ...
- 1,547
0
votes
0
answers
118
views
sparsest cut always has solution
Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
- 1