All Questions
2,368 questions
0
votes
1
answer
113
views
How do I solve this integer programming problem with non convex constraints?
I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...
- 103
0
votes
1
answer
133
views
Reference request on Borsuk conjecture [closed]
I just heard of Borsuk conjecture. I want to ask if there are any references preferably looking at the problem from the point of view of Mathematical analysis I can study it from?
Thanks
- 139
0
votes
1
answer
57
views
Extremality of Triangles with Corners from Planar Convex Hulls
I am looking for proofs of or counterexamples to the following assumptions:
if the corners of a triangle are chosen from a compact subset $\mathcal{S}$ of the Euclidean plane then all three corners ...
- 13.2k
0
votes
1
answer
127
views
Maximum number of points in convex position on a grid
Guys this problem really bothers me (I don`t know how to prove it) please help:
What is the maximum number of points in convex position on a $n\times m$ grid?
(My guess would be $2*(m+n)-4$.)
- 51
0
votes
2
answers
120
views
Reference request: dependence on linear constraints
Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:
$$P(...
- 1,835
0
votes
1
answer
71
views
A bound on the Haussdorff distance
Let $X, Y \subset \mathbb{Z}^2$ be two discrete and bounded sets. Let $f_X$ be the Euclidean signed distance function of $X$ (similarly for $Y$) and $d_H(X,Y)$ the Euclidean Haussdorff distance ...
- 59
0
votes
1
answer
2k
views
When to use non-negative-least square and least-square [closed]
What are the typical case we need to use Non-negative least squares NNLS
$$
||Ax - B||^2
$$
instead of least-square $$ Ax-B$$ (or vice versa)?
And is there any drawback in applying them on large $A$...
- 135
0
votes
2
answers
244
views
Rewrite optimization objective
Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...
- 409
0
votes
2
answers
340
views
positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix
Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty) $ is a real non-negative number. I want to know the answer to the following optimization problem.
$$
\...
- 101
0
votes
1
answer
407
views
Counting integer points in a Minkowski sum
We have known from Ehrhart theory that if $P$ is a $d$-dimensional polytope of $\mathbb R^n$ which has integer vertices then the number of integer points in $nP$ is a polynomial of degree $d$. We also ...
- 13
0
votes
1
answer
2k
views
Find edge weights that fit given node weights
Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
- 340
0
votes
1
answer
456
views
Is the Simplex Method still polynomial when all inequalities are through the origin?
Hello,
I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
- 693
0
votes
2
answers
1k
views
Degenerate case of linear programming duality?
Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize $0\vec{...
- 2,009
0
votes
2
answers
530
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
- 21
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
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
0
votes
1
answer
99
views
When a polygonal line become a loop in hyperbolic plane?
Suppose we have a 5 tuple of positive real numbers $(l_1,l_2,m_1,m_2,m_3)$, with $m_i \in (0,\pi)$ for all $i$. Now fix a point $v_1$ in the hyperbolic plane. Then consider a geodesic of length $l_1$ ...
- 613
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
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
0
votes
1
answer
249
views
Oriented path in a graph
Let $G=(\mathcal{V}_G,\mathcal{A}_G)$ be an oriented acyclic graph. Assume that $G$ has a unique source $s\in \mathcal{V}_G$ and a unique sink $t\in \mathcal{V}_G$. Now, fix $u,v\in \mathcal{V}_G$ ...
- 353
0
votes
1
answer
150
views
What are all the possibilities of $A$ s.t. $\det(A)=k$?
Suppose we have $A \in M_3(\Bbb N\cup\{0\})$ s.t. sum of the elements of each row is $k $ for some fixed $k\in \Bbb N\cup\{0\}$. What are all the possibilities of $A$ s.t. $\det(A)=k$?
We can start ...
- 103
0
votes
1
answer
405
views
Computing discrete optimal transport
I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...
- 133
0
votes
1
answer
99
views
Finding dual of a scheduling LP formulation
Suppose I have an LP formulation as such:
$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$
$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$
$\sum\limits_{j}x_{ijt}\leq ...
- 103
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 193
0
votes
1
answer
145
views
How to solve this optimization problem efficiently? [closed]
Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...
- 111
0
votes
1
answer
212
views
Is an exact violated inequality constraint met as equal constraint in optimal solution?
We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the ...
- 25
0
votes
1
answer
67
views
Calculating a Measure of the Geometric Complexity of Planar Closed Polylines
Let $\lbrace p_1,\ \dots,\ p_n\rbrace$ be a set of points in the Euclidean plane and let $T_0 :=\left(p_1,\ \dots,\ p_n,p_1\right)$ be a Hamilton cycle through the set of points.
Question:
...
- 13.2k
0
votes
1
answer
129
views
Fundamental Surfaces in 3-manifolds
Given a 3-manifold $M$ with a triangulation $T$, will every essential surface in $M$ be a fundamental one? If not, then what are the conditions on $T$ so that these essential surfaces become ...
- 1
0
votes
1
answer
79
views
algorithms and tools available for a particular polytope computation
Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
- 867
0
votes
1
answer
201
views
Recursive linear programming on a linear subset of a simplex
The problem I am working on is:
Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
0
votes
1
answer
204
views
Is the linear production game a convex game?
In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...
- 17
0
votes
1
answer
543
views
Convert general optimization problem to LP problem
I am trying to convert the following problem into a linear programming problem:
There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
- 99
0
votes
1
answer
82
views
Introducton books for $\frak{E}_p(I)$
Are there any good books different from abstract harmonic analysis by hewitt to study $\frak{E}_p(I)$. where $\frak{E}_p(I)$ is: Let $I$ be an arbitrary index set. For each $i\in I$ let $H_i$ ...
- 209
0
votes
2
answers
118
views
Inner Product of Given Sum Positive Sequence
Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in A,\,\sup\...
- 2,239
0
votes
1
answer
546
views
Solution of infinite dimension linear system
Suppose that ${a_n}$ and $b_n$ is decreasing sequence such that $a_0=A$, $lim_{n->\infty}a_n=0$ and $b_0=B$, $lim_{n->\infty}b_n=0$.
For fix n,
we can construct n dimension linear equation ...
- 111
0
votes
2
answers
708
views
Approximate solution to large mixed integer programming problem
What are the available approaches to find an approximate solution to a large mixed integer programming problem?
I ran my problem in the Gurobi MIP solver.
It can find a feasible solution in ...
user24451
0
votes
1
answer
451
views
Large scale least squares of non symmetric and non square problems
Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$).
There is a large amount of algorithms for symmetric ...
- 125
0
votes
1
answer
99
views
generalization from linear programming solution [closed]
I have a series of similar linear programs that depend on an input vector $a\in A$ and whose solution is an output vector $b\in B$. I can solve them individually, but this is wasteful. I suspect that ...
- 109
0
votes
1
answer
85
views
About the suboptimality of linear estimators
Let $X$ be a random variable and $N$ a Gaussian noise independent from $X$. We observe $Y=X+N$ and want to estimate $X$ based on $Y$ to minimize the mean square error $mmse(X|Y):=E(\hat X(Y)-X)^2$.
...
- 29
0
votes
1
answer
73
views
Optimal radiating $(d{-}1)$-flats within a sphere
Permit me to revisit an earlier unresolved MO question,
"Chord arrangement that avoids confining small or large disks"
with a (very!) specific version, inspired by radiation therapy.
The main idea is ...
- 151k
0
votes
1
answer
2k
views
eigen-decomposition solution? is it unique?
Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
- 1
0
votes
1
answer
205
views
SDP Algorithms/ maximally complementary solutions
Hello,
I was wondering if there are algorithms for (linear) Semidefinite Programs (SDP) out there, that converge towards a maximally complementary solution, even if strict complementary does not hold.
...
- 1
0
votes
1
answer
504
views
$\ell_o$ Minimization (Minimizing the support of a vector)
I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
- 11
0
votes
1
answer
226
views
Continuity of Lexicographic Minimum Solution of a parametrized LP problem
Given a parametrized LP problem
find x, that minimizes F*x
such that Ax <=Bt+D
where t is a parameter.
And suppose C(t) is a set of all optimal solutions of LP with parameter t.
Let x_L(t) be ...
- 29
0
votes
1
answer
367
views
On the number of lines of given points
Hi all, I have a question Concerning Beck's theorem. I have read it from http://en.wikipedia.org/wiki/Beck%27s_theorem and I have two questions :
I suppose Beck's theorem doesn't hold when instead ...
- 1
0
votes
1
answer
695
views
Minimum distance between two data sets
Suppose we have two sets of data, $X$ and $Y$, each of which contains
$10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$,
$x_{1}\ge\cdots\ge x_{10}>0$ and ...
0
votes
1
answer
409
views
Need help to find an efficient algorithm for the following problem!
Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$.
Given $A_{n\times n}$ is the covariance matrix of $x$.
$u$ is a given n-dimensional vector of real ...
- 131
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
128
views
The smallest dihedral angle of convex polyhedrons
Given a set of points $\{x_{k}\}_{k=0}^{m} \subset \mathbb{R}^n$, is it always possible to find a constant $c=c(m,n)>0$, depending only on the dimension $n$ and the number $m$, such that, after ...
- 705
0
votes
0
answers
98
views
Number of tetrahedra inside a sphere with boundary A
I understand, that there are some combinatorial problems which are not yet solved regarding gluing triangulations in 3D. At least last time I checked, it was not yet known exactly how many ...
- 183