All Questions
685 questions
9
votes
4
answers
528
views
Software tools for medium-scale systems of polynomial equations
I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real ...
- 561
2
votes
2
answers
1k
views
Uniqueness of solution of a nonconvex optimization problem
What conditions need to be hold for a nonconvex optimization problem to have a unique solution?
Specifically, I have the following minimization problem that I'd like to know whether it has a unique ...
- 291
5
votes
1
answer
4k
views
Convergence rate of stochastic gradient decent with projections
Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of ...
- 619
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
3
votes
2
answers
437
views
convex polytope integer points
is there a simple proof for the following lemma:
An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.
- 39
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
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
1
vote
1
answer
624
views
a closed form lower bound solution for linear programming
Given a linear objective function and a system of linear constraints, is there any known closed form lower bounds for it?
to clearly express the problem assume that
$$
z(\mathbf{a,B,c})=\mathop {\inf} ...
- 275
3
votes
1
answer
340
views
Name search for special Linear Integer Program
I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
$...
- 31
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 ...
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
1
vote
1
answer
70
views
Heuristic for choosing n-vectors from n-sets
my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
- 11
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 151
3
votes
3
answers
349
views
Sensitivity analysis in conic optimization
I have a conic optimization of the form:
$$\min_x \langle c, x \rangle,\ \text{s.t.}\ Ax = b,\ x \in K.$$
where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a ...
- 143
0
votes
0
answers
113
views
Sufficient optimality condition for a non-smooth quasiconvex problem
The result of relaxing to an integer program is the following optimization problem:
$$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$
where $\textbf{...
- 127
2
votes
0
answers
91
views
Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings
In one paper from 1980 I found a note that there are no known algorithms for solving
homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring.
(The non-...
1
vote
2
answers
172
views
Linear Programm with matrix [closed]
Is there a name for problems like this
min norm(Cx)
Ax = b
where C is a matrix and norm is the maximum norm.
This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
- 11
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}...
4
votes
1
answer
750
views
submatrix of a given size with maximum frobenius norm
Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
- 859
2
votes
0
answers
120
views
integrality of a linear program -- binary equality constaints
Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...
- 127
4
votes
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
4
votes
2
answers
212
views
combinatorial and linear duality
Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...
- 987
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
1
vote
0
answers
75
views
Are there any known bounds on the value of solutions of linear integer programming?
Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...
- 111
1
vote
0
answers
214
views
range of the difference-of-two-qubit-$4 \times 4$-density-matrix-determinants
The determinant of a two-qubit $4 \times 4$ density matrix--that is, a Hermitian, nonnegative definite matrix with unit trace--lies between $0$ and $(\frac{1}{2})^8$. (A "pure state" has determinant ...
- 723
1
vote
1
answer
4k
views
Maximizing linear objective function with absolute values
This has be asked on other forums, though couldn't
find authoritative answer.
I have a linear program over the reals and don't
want to introduce integer or binary variables.
The objective function ...
- 25.4k
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
1
vote
0
answers
493
views
Complexity of Nested Linear Optimization
My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\...
- 13.2k
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
- 591
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
7
votes
1
answer
819
views
Has this generalization of a determinant (assigning multiplicities to the rows) been studied?
I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant:
Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
- 1,509
4
votes
1
answer
288
views
Equivalent method for maximum likelihood estimation of covariance parameters
My goal is to estimate the parameters of a covariance matrix $\Omega$, by maximizing the following log-likelihood function:
$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...
- 141
1
vote
1
answer
3k
views
Minimizing sum of absolute deviations
Suppose we want to find coefficients $b$ in $\underset{b}{\operatorname{argmin}} \displaystyle\sum\limits_{i=1}^n | y_{i}-b_{1}x_{i}-b_{0}\mid$.
If we rewrite this problem in terms of linear ...
- 99
2
votes
0
answers
154
views
Maximizing an integral over a convex region
Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
- 21
6
votes
0
answers
317
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
- 61
1
vote
1
answer
246
views
Eigenvalue problem with quadratic constraints
$\circ$ Consider the following eigenvalue problem : $$Ax=\lambda x \hspace{0.5cm} (1)$$
where matrice $A \in \mathbb{R}_{n \times n}$ is a positive semi-definite with eigenvectors $x = (x_{1},x_{2},.....
- 45
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
0
votes
0
answers
533
views
Constructing an $\epsilon$-net for a Lipschitz subspace of $L^2$
Let $X$ be a subset of $L^2([0,1])$ which contains only Lipschitz function.
Also, the member of $X$ are uniformly bounded
$$
|x(t)| < M, \text{ for all $x \in X$ and $t \in [0,1]$}.
$$
Let $F: X \...
user24451
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
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
5
votes
0
answers
194
views
A linear optimization problem on a graph
Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...
- 2,288
3
votes
1
answer
1k
views
For interior point methods of linear programming, what is the "L" in the computational complexity $\mathcal{O}(n^3 L)$?
My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...
- 31
1
vote
0
answers
196
views
Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method
I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
- 111
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
5
votes
1
answer
330
views
Compactness of a semi algebraic set
Suppose I have a polynomial $p\in R[x_1,\ldots,x_n]$ and I look at the set $S:=\{ x\in R^n : p(x)\geq 0\}$. Are there algebraic certificates on $p$ that will certify that $S$ is compact?
- 65
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
1
vote
1
answer
277
views
Maximum Dispersion of a Connected Geometric Graph
Let $\left\{\mathbf{p}_1,\dots, \mathbf{p}_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as:
$
U=\sum \limits_{i=1}^{k} ||\...
- 115