All Questions
686 questions
2
votes
1
answer
240
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
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
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
70
views
Optimize a function with not-full knowledge of gradient
I want to optimize the following function:
$$
argmin_{x} f(x) = g(x) + h(x)
$$
, where I can get $\nabla_xg(x)$, but cannot calculate $\nabla_xh(x)$.
The derivative-free method, such as the Hill ...
- 53
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
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 ...
2
votes
1
answer
502
views
Feasibility Mixed integer Linear programming with quadratic constraints?
Consider the mixed integer program
$$Ax\leq b$$
$$By\leq c$$
$$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
- 13.9k
2
votes
1
answer
111
views
Where does the expected value in the restatement of the pseudoregret come from?
Given stochastic payoff functions $X_{1}(t) \dots X_{K}(t)$, each having a different probability distribution on $[0,1]$, denote the expected value of $X_i(t)$ by $\mu_i$, and define $\mu^* = \max_{i \...
- 45
2
votes
1
answer
418
views
Name for functions with local=global minimum
I have a simple question. We know that functions where every stationary point is a global minimum are invex functions. Is there a name for functions where every local minimum is a global minimum?
And ...
- 342
2
votes
1
answer
436
views
equality between the ratio trace and the determinant ratio
I have encountered the following equality
$\arg\max_{\text{tr}\left(\boldsymbol{S}^{H}\boldsymbol{S}\right)=1}\text{tr}\left(\boldsymbol{S}^{H}\boldsymbol{A}\boldsymbol{S}\left(\boldsymbol{S}^{H}\...
- 503
2
votes
2
answers
3k
views
Linear programming with infinitely many constraints
I wish to study the following linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
- 283
2
votes
1
answer
1k
views
Complementary slackness for approximately optimal Dual solution
Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
- 133
2
votes
2
answers
501
views
Limits of argmin ratios and sums
In my research on convergence properties of certain Bayesian methods I have encountered $\mathop{\mathrm{arg\,min}}$ limits of the forms
\begin{equation}
\lim_{n\to\infty} \mathop{\mathrm{arg\,min}}_{\...
user93829
2
votes
1
answer
201
views
Minimum cover for sets in which each element appears in exactly 2 sets?
Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
2
votes
1
answer
531
views
Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables
I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...
- 21
2
votes
1
answer
751
views
Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?
More precisely, The setting could be formulated as,
$min. F_{\lambda}(p)$ over permutation matrices $P$
Here $F_{\lambda}(p)$=$\lambda *F_{0}(p)+(1-\lambda)F_{1}(p)$
where both $F_{0}(p)$ and $F_{...
- 23
2
votes
1
answer
276
views
An optimization problem in complex space
Consider the following optimization problem
$$
\min \| \textbf{Ax-B}\|
$$
$$
s.t.|x_i|=1,i=1,...,n
$$
where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
- 21
2
votes
1
answer
143
views
Find base of kernel with as many 0 as possible
I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.
I want to find the linear ...
- 83
2
votes
1
answer
191
views
Optimization problem whose cardinality never exceeds 7 for some reason
I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...
2
votes
1
answer
227
views
Arrangements of hyperplanes
Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form
$$
f(\bar{x})=a_1x_1+\ldots+a_nx_n+b
$$
for some $a_i,b\in\mathbb{R}$.
Suppose we ...
- 3,274
2
votes
1
answer
130
views
Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?
In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...
- 121
2
votes
1
answer
126
views
Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?
I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise.
The other variables in the linear program,...
- 121
2
votes
3
answers
2k
views
Best algorithm/software for solving a planar transportation problem ?
I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need ...
- 341
2
votes
2
answers
411
views
Functional Minimization: When is this heuristic rigorous?
I'm trying to solve a functional minimization problem of the following form:
$$\arg\min_{f:\mathbb{R}\rightarrow [0,1]} h(f)$$
where $h$ is some expression in terms of several integrals over $f$.
I ...
- 21
2
votes
2
answers
402
views
Maximization of a matrix product by iterative methods
This might not be very difficult, but I think I may have gotten a little confused.
Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
- 949
2
votes
1
answer
308
views
Can subgradient infer convexity?
It is known that
If $f:U→ R$ is a real-valued convex function defined on a convex open set in the Euclidean space $R^n$, a vector v in that space is called a subgradient at a point $x_0$ in $U$ if for ...
- 95
2
votes
1
answer
91
views
Does approximately null gradient imply approximately global minimum for convex functions?
Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ - possibly unbounded. Usually, when one ...
- 225
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
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?
2
votes
1
answer
100
views
Maximizing a skew-symmetric 4D cross product
How do I find two orthonormal 4D vectors, $(x_0,x_1,x_2,x_3)$ and $(y_0,y_1,y_2,y_3)$, which maximize this function:
$-19x_1y_0 - 33x_2y_0 + 11x_3y_0 + 19x_0y_1 - 21x_2y_1 - 33x_3y_1 + 33x_0y_2 + ...
- 1,547
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
2
votes
1
answer
636
views
When does $\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$ hold for a real function $f(x,y)$?
Let $f(x,y)$ be a real function of the variables $x,y$ (which can be real vectors). Under what conditions do we have the following equality:
$$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$$
For ...
- 884
2
votes
1
answer
270
views
What optimization problems have solutions with few nonzeros?
Consider the following optimization problem, with $n$ variables and $m$ linear constraints:
\begin{align}
\text{maximize} && c_1 x_1 + \cdots + c_n x_n &
\\
\text{subject to} && a_{...
- 3,549
2
votes
1
answer
91
views
Linear program with one quadratic condition convex in domain of interest polynomial time solvable?
$c\leq xy$ is not a convex condition.
However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$.
Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,...
- 13.9k
2
votes
2
answers
402
views
Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative
$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative.
What should $A$ satisfy to guarantee the equation set have only zero solution?
- 23
2
votes
1
answer
148
views
Fast algorithm for large-scale, asymmetric transportation linear program
I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
- 4,049
2
votes
1
answer
508
views
Under what condition does Courant–Fischer–Weyl min-max principle hold in general?
From Wikipedia:
Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A :
\mathbf C^n \setminus \{0\} \to \...
- 155
2
votes
1
answer
171
views
Maximization of Binary Multilinear Fractional Function
Problem: Let $a_{i,j}$, $b_{i,j}\in\mathbb{R}$ for all $(i,j)\in\left[m\right]^2$ such that $a_{i,j}=a_{j,i}$ and $b_{i,j}=b_{j,i}$. Let $z_k\in\{0,1\}$ for $k\in\left[m\right]$. We wish to maximize,
...
2
votes
1
answer
529
views
Integer programming and Groebner basis
I enjoyed reading different papers about using Groebner basis to solve integer programming.
Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
- 337
2
votes
1
answer
3k
views
max-flow at max-cost
I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
- 121
2
votes
1
answer
229
views
Algorithm to find the vertices of the equidistant lines between N closed polygonal lines
I have a set $\{C_1, C_2, \ldots, C_N\}$ of $N$ nonintersecting closed piecewise linear curves on the Euclidean plane. For every point $x \in \mathbb{R}^2$ we say it belongs to a territory serviced by ...
- 329
2
votes
1
answer
426
views
Network flows with shared capacities
Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:
$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$
where $f(1, 2)$ denotes the flow through arc $(1, 2)$....
- 23
2
votes
1
answer
104
views
Standard names and methods for this type of fitting minimization
In material science research, we have come across the following type of problem.
Given a m by n matrix A, a m vector b, and error tolerance $\varepsilon$, we want to do this minimization
$$\eqalign{
...
- 867
2
votes
1
answer
301
views
books on very large scale linear optimization
Recently in my material science research, I have encountered problems of very large scale linear optimization. I read the introductory book "Introduction to Linear Optimization (Athena Scientific ...
- 867
2
votes
1
answer
134
views
Integer point in a non-empty polytope
I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...
- 243
2
votes
2
answers
840
views
Finding the maximum of a multivariate polynomial of degree one
I need to find the global maximum of the function
\begin{align}
f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\
&+\ldots \\
&+ p_n ...
user24451
2
votes
2
answers
798
views
Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method
If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ...
- 329
2
votes
1
answer
203
views
A Recursive Maximization Problem
Let $A\ge B>0$ be real constants. I say that a function $f:[0,1]\rightarrow[0,1]$ satisfies the $(A,B)$-condition if for all $p\in [0,1]$, the expression
$$q(A-Bp-Bf(q))$$
is maximized (not ...
- 23k
2
votes
1
answer
1k
views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
- 1,318
2
votes
2
answers
129
views
LP constraint enconding
I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...
- 21