All Questions
783 questions
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
3
votes
0
answers
256
views
What would be a better method for numerical diagonalization of a certain Vandermonde-like matrix?
For the fractional iteration of the $\exp()$-function Hellmuth Kneser had 1942 proposed an analytic solution valid on the real numbers; there is a technical implementation for Pari/GP of this method ...
- 5,342
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
1
vote
0
answers
377
views
The rationale of QR algorithm for computing eigenvectors
For a symmetric matrix $A$, the rationale for the success of applying QR to compute the spectral decomposition of $A = UDU^T$ is, for large $k$, the QR factorization of $A^k = Q_kR_k$ obeys,
\begin{...
- 55
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
15
votes
2
answers
7k
views
Efficient rank-two updates of an eigenvalue decomposition (or more generally SVD)
Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al.1 and Bunch, et al.2 have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...
- 947
5
votes
0
answers
392
views
Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix
I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D -...
- 500
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
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
140
views
QR alogrithm for eigenvalue problem [closed]
Considering pure QR algorithm (without shifts and preliminary tridiagonal reduction) are there sufficient conditions for algorithm to converge to quasi-diagonal form?
For the the following matrix
$$
...
5
votes
0
answers
112
views
Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices
I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e.
$(A_1+A_2)^{-1},(A_1+A_3)^{-1},(A_2+A_3)...
- 71
3
votes
2
answers
3k
views
Sparse approximation of the inverse of a sparse matrix
Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
- 2,205
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
1
vote
0
answers
256
views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
- 111
1
vote
2
answers
2k
views
Alternative to Choleski Decomposition for Correlation Matrix
Let $\Sigma$ be a correlation matrix, ie. symmetric. The Choleski decompositon gives upper triangular $A$ such that $A^TA = \Sigma$. Instead of upper triangularity, we are looking for $A$ that is not ...
- 11
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 21
2
votes
0
answers
163
views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
2
votes
1
answer
689
views
Why does the LP Formulation of the MST Problem need Topology Constraints?
I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...
- 13.2k
16
votes
2
answers
4k
views
The singular values of the Hilbert matrix
The $n\times n$ Hilbert matrix $H$ is defined as follows
$$H_{ij} = \frac{1}{i+j-1}, \qquad 1\leq i,j\leq n$$
What is known about the singular values $\sigma_1 \geq \cdots \geq \sigma_n$ of $H$?
...
- 3,217
6
votes
3
answers
148
views
Algorithm to quickly compute the individual inverses of a linear sequence of matrices
Fix $n \times n$ real symmetric positive definite matrices $A$ and $B$. Fix vectors $x$ and $y$ in $\mathbf{R}^n$. I want to compute the following bilinear products quickly: $\{x^T (A+mB)^{-1} y\}_{m=...
- 328
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
1
vote
2
answers
306
views
Name of operations on two vectors
Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...
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
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
1
vote
1
answer
296
views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
- 185
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
1
vote
1
answer
4k
views
What does "Vertex Solution" mean?
Hello!
I come across the word "vertex solution" in the context
" We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any ...
- 13
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
2
votes
0
answers
883
views
Error bound on matrix vector multiplication
I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate.
Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...
- 489
4
votes
1
answer
128
views
Conjugate gradient algorithm where first search direction is not equal to residual
In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...
- 489
8
votes
0
answers
481
views
Problems where Conjugate gradient works much better than GMRES
I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
- 489
7
votes
1
answer
318
views
Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?
Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
- 325
9
votes
1
answer
3k
views
Inverse of a totally unimodular matrix
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
- 93
13
votes
0
answers
591
views
What are the difficulties in proving almost-everywhere stability of Gaussian elimination?
It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...
5
votes
1
answer
3k
views
Maximizing supermodular functions
I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...
2
votes
0
answers
63
views
Put positive polynomial in finite intersection of half-spaces
This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...
- 621
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
4
votes
1
answer
316
views
standard practice for large dense truncated svd computations?
What are the standard methods of computing the rank-k truncated SVD of large dense matrices? My literature search yields results only for large sparse matrices.
I assume for k small that you use a ...
- 922
2
votes
3
answers
752
views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
- 13.2k
2
votes
0
answers
86
views
Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case
I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...
- 21
2
votes
1
answer
2k
views
Finding a point farthest away from $k$ points in a polygon
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...
- 57
1
vote
2
answers
1k
views
Efficient algorithm finding 'a' solution of system of linear inequalities
I'm working on rational number field $\mathbb{Q}$.
Is there an efficient algorithm finding a solution of system of linear inequalities?
In many computer algebra systems like Sage or Maple,
there ...
- 627
3
votes
2
answers
791
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 13.2k
1
vote
0
answers
1k
views
Robust optimization in matlab using fmincon [closed]
I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...
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
3
votes
1
answer
4k
views
Schur complement and negative definite matrices
Hello,
My question regards to the Schur complement lemma. Consider the matrix $M=\left( \begin{array}{cc}
A & B\\\
B^T & C \end{array}\right)
$.
According to the lemma $M\geq0$ iff $C>0$ ...
- 155
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k