All Questions
1,020 questions
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(...
1
vote
1
answer
119
views
Adding linear constraint to the domain
I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm.
I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
0
votes
0
answers
32
views
Alternative equivalence results for the constructibility of real numbers
Everyone is aware of the standard result from undergraduate field theory that a real number $\alpha$ is constructible by straightedge and compass if and only if there exists a finite sequence of field ...
- 273
0
votes
1
answer
49
views
Constructing a polygon from another with collinearity constraints
Let $P$ be a closed polygon defined by the sequence
$p_0,\,\dots,\,p_{n-1},p_0$ of points.
Question:
how can one construct, with straightedge and compass alone, another sequence of points $q_0,\,\...
- 13.2k
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
2
votes
1
answer
155
views
Finding angle with geometric approach [closed]
I would like to solve the problem in this picture:
with just an elementary geometric approach. I already solved with trigonometry, e.g. using the Bretschneider formula, finding that the angle $ x = ...
- 29
1
vote
0
answers
335
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 988
7
votes
3
answers
277
views
Minimum diameter of set inscribed in a unit sphere
For a study of the stability of certain maps taking values in a sphere I have the following question.
Let $A$ be a subset of $\mathbb{R}^n$. Suppose $A$ lies in a unit ball, but in no ball of smaller ...
- 81
1
vote
1
answer
169
views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 47
2
votes
1
answer
61
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 3
-1
votes
2
answers
164
views
Condition to be concyclic [closed]
What condition would you impose upon $n$ points on a plane of which no three points are collinear so that they are
concyclic if the distances of each point from the all remaining points are known? (...
14
votes
1
answer
280
views
How many distances are required to calculate all distances among $n$ points in the Euclidean plane?
I want to know all the pairwise distances between points $P_1,P_2,\ldots,P_n$ in the Euclidean plane (or equivalently, I want to reconstruct the set of points up to congruence). Let's say I have an ...
- 523
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
1
vote
0
answers
47
views
Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?
EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...
0
votes
1
answer
82
views
Combining Dantzig-Wolfe and Benders decomposition
I'm now solving an LP that has a few coupling rows (as in Dantzig-Wolfe decomposition) and a few coupling columns (as in Benders decomposition) simultaneously; other rows and columns are block-angular....
- 3
16
votes
0
answers
391
views
Is "Escherian metamorphosis" always possible?
$\DeclareMathOperator\int{int}\DeclareMathOperator\diam{diam}\DeclareMathOperator\area{area}\DeclareMathOperator\cl{cl}\DeclareMathOperator\ran{ran}\DeclareMathOperator\dom{dom}$This is a tweaked ...
- 21.2k
0
votes
1
answer
36
views
Benefit of adding a trivial constraint to ILPs
let ILP be an integer linear program with constraints-matrix $\boldsymbol{\mathrm{M}}\in\mathbb{Z}^{m\times n}$ and cost vector $\boldsymbol{\mathrm{c}}\in\mathbb{Z}^n$,
${\boldsymbol{\mathrm{x}}^*}\...
- 13.2k
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
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
16
votes
1
answer
619
views
A textbook on foundations of geometry in spirit of Tarski
I am interested in a textbook for studying (and teaching) foundations of geometry in the spirit of Tarski. I know that there is a rather old German book [W. Schwabhäuser, W. Szmielew, A. Tarski, ...
- 41.8k
0
votes
1
answer
110
views
Orthogonal projection of a point centrally-symmetric closed convex subset of $\mathbb R^n$ never expands the coordinates of the point
Let $C$ be a closed convex subset of $\mathbb R^n$ which is symmetric about the standard coordinate axes. For example, think of $C$ as the unit-ball for an $\ell_p$-norm, for some $p \in [1,\infty]$. ...
- 6,853
0
votes
1
answer
538
views
Method for (binary) optimization under constraints
I would like to know if there is a method to solve the Problem.
Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...
- 3
1
vote
1
answer
96
views
A 'natural' enumerable metric space with integral distances which is essentially the Euclidean space
It is easy to construct a metric space $E_d$ such that all points
of $E_d$ are at mutually integral distance and such that there is a map $\varphi$ from $E_d$ into the $d$-dimensional Euclidean space ...
- 17.9k
1
vote
0
answers
59
views
How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?
I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
- 11
0
votes
1
answer
143
views
$\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem
Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...
- 13.2k
1
vote
1
answer
181
views
Linear programming with "nice" matrices
Consider the following linear programming problem
\begin{array}{ll}
\text{minimize} & \mathrm 1^{\top} \mathrm x\\
\text{subject to} & v\le \mathrm A \mathrm x \le u\\
& \mathrm x \geq ...
- 650
6
votes
0
answers
121
views
How many equilaterals have vertices intersections of angle trisectors of a triangle?
The celebrated Morley’s theorem ensures that the interior trisectors, proximal to sides respectively, meet at vertices of an equilateral.
In the paper Trisectors like Bisectors with Equilaterals ...
1
vote
0
answers
40
views
Fashioning higher precision tool from a lower precision tool
I'm not sure where to ask this question.
Suppose I have one or more rulers with which I can measure distances with up to 1 mm error. Is there a way I could make another tool of higher precision (e.g. ...
- 169
5
votes
0
answers
179
views
Generalization of IMO5 from 1987
The following question appeared as question 5 on the IMO in 1987:
Prove that for all $n \geq 3$ one can find $n$ distinct points on the Euclidean plane with the property that the distance between any ...
- 26.9k
2
votes
1
answer
875
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
- 1,171
0
votes
1
answer
64
views
Round Robin volleyball Tournament [closed]
Consider a set of N teams (N even number) that must make a
Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level
of interest si,j ∈ {1;2;3} of the match between them (1 =...
1
vote
0
answers
416
views
A metric geometry problem which calculates the limitation of human eyes
This is the update version of this question A functional inequality which calculates the limitation of human eyes
Let an Euclidean space $M$ (or a path connected metric space) be partitioned into ...
- 1,462
1
vote
1
answer
230
views
Does the cosine of a matrix have a geometric (non power series) interpretation? [closed]
You can adapt the power series definition of cosine to take in a matrix. Does this have a geometric interpretation/definition? Can it be used for various purposes? I actually have extended the matrix ...
- 65
16
votes
1
answer
444
views
Is there a conceptual reason why so many triplets of lines in a triangle are concurrent?
One of the striking phenomena one can't help but notice in elementary Euclidean geometry is how easy it appears to be to define triples of lines in a triangle which meet in a point. Now for each ...
- 32.5k
10
votes
1
answer
551
views
Formula for "cointersection" of three circles?
I am working on the problem of finding "rational" dodecahedrons, and I have run across an interesting subproblem: How do you tell if three circles have a common intersection point?
...
- 371
2
votes
1
answer
227
views
Solving linear programming without solving linear programming
Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...
- 9,501
3
votes
1
answer
2k
views
Does this hexagon theorem have a name?
Question : Do you know this property of a hexagon?
Consider the configuration: Six points $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, $A_6$ in a plane and let six points $B_i \in A_iA_{i+1}$ for $i=1, 2,\dots, ...
- 1,776
19
votes
1
answer
819
views
All saddles in the unit ball have area $<2\pi$?
Let $M$ be the saddle surface in $\mathbb R^3$ defined by $x^2-y^2+z=0$. For any $r\geq 0$ and $(x_0,y_0,z_0)\in\mathbb R^3$, let $rM+(x_0,y_0,z_0)$ denotes the surface obtained by scaling $M$ by $r$ ...
- 525
2
votes
1
answer
372
views
Who called Farkas' fundamental theorem a lemma?
Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
- 16.4k
2
votes
1
answer
155
views
Concyclic point made from Six arbitrary points
Let $A_1A_2A_3A_4A_5$ be irregular convex Pentagon and Let $P$ be arbitrary point anywhere in Plane geometry.
Let $X_1,X_2,X_3,X_4,X_5$ be Circumcircle of $\triangle PA1A3$; $\triangle PA2A4$; $\...
user423633
1
vote
1
answer
331
views
Finding a special solution in a solution set over F2
Given a solution set of a linear system of the following form
$$
\{ \begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...
- 51
0
votes
1
answer
396
views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
- 1
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
0
votes
1
answer
319
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
1
vote
0
answers
61
views
Linear programming robustness to input perturbations
I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...
- 11
2
votes
1
answer
644
views
How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]
I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
59
votes
4
answers
7k
views
Is orientability a miracle?
$\DeclareMathOperator\SO{SO}\DeclareMathOperator\O{O}$This question is prompted by a recent highly-upvoted question, Conceptual reason why the sign of a permutation is well-defined? The responses made ...
- 82.6k
0
votes
0
answers
115
views
Explicit equation for border of the Minkowski sum of sets
Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...
- 385
3
votes
1
answer
85
views
How big can a triangle be, whose sides are the perpendiculars to the sides of a triangle from the vertices of its Morley triangle?
Given any triangle $\varDelta$, the perpendiculars from the vertices of its (primary) Morley triangle to their respective (nearest) side of $\varDelta$ intersect in a triangle $\varDelta'$, which is ...
- 2,437