The linear-programming tag has no wiki summary.

**6**

votes

**1**answer

261 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 ...

**-3**

votes

**1**answer

370 views

### Closed form solution for Least Squares Problem [closed]

I'm looking for closed form solution for the following equation:
$argmin_{X,y}(\sum_i{\parallel{a_i-Xb_i-y}\parallel^2})$, where $X \in\mathbb R_{m\times n}$ is a matrix and $y\in\mathbb R_{m\times ...

**3**

votes

**1**answer

145 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 |) ...

**1**

vote

**1**answer

255 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 ...

**4**

votes

**0**answers

116 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 ...

**1**

vote

**0**answers

45 views

### Nontrivial Matrix-estimate

I try to proof the following estimate:
\begin{align}
h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1)
\end{align}
where $h\in\mathbb{R}^{K-1}$ and ...

**1**

vote

**1**answer

138 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 = ...

**2**

votes

**2**answers

146 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. ...

**20**

votes

**4**answers

1k views

### Why are optimization problems called “programming”?

Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...

**4**

votes

**2**answers

408 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 ...

**0**

votes

**1**answer

66 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$.
...

**5**

votes

**0**answers

166 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**

votes

**1**answer

168 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 ...

**1**

vote

**0**answers

87 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 ...

**4**

votes

**2**answers

215 views

### point in polytope

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 ...

**0**

votes

**1**answer

511 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. ...

**2**

votes

**1**answer

362 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**

vote

**0**answers

145 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 ...

**3**

votes

**1**answer

159 views

### Explicit formula for an LMI solution

Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil):
$$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$
(The notation $X \succeq Y$ means that ...

**2**

votes

**0**answers

27 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 ...

**2**

votes

**0**answers

130 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 ...

**2**

votes

**1**answer

242 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 ...

**0**

votes

**1**answer

344 views

### Nonconvex optimization problem

I have a nonconvex optimization problem. It is actually optimizing a linear objective function over a set of linear constraints and a set of nonlinear, non convex constraints.
Is this problem ...

**0**

votes

**2**answers

121 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 ...

**1**

vote

**2**answers

173 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

176 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.
$$
...

**2**

votes

**2**answers

94 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 ...

**1**

vote

**1**answer

107 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< ...

**1**

vote

**0**answers

76 views

### Arrangements of graphs of linear functions

Fix $n>0$ and $X\subseteq\mathbb{R}^n$. Assume $X$ is unbounded.
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 ...

**2**

votes

**1**answer

156 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 ...

**0**

votes

**1**answer

629 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 ...

**0**

votes

**0**answers

69 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 ...

**6**

votes

**1**answer

596 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 ...

**2**

votes

**1**answer

378 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

41 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$, ...

**2**

votes

**1**answer

84 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 ...

**1**

vote

**1**answer

357 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 ...

**1**

vote

**1**answer

286 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.
...

**0**

votes

**2**answers

436 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 ...

**1**

vote

**2**answers

114 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 ...

**1**

vote

**0**answers

624 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

372 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 ...

**1**

vote

**1**answer

812 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$ ...

**10**

votes

**2**answers

793 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 ...

**1**

vote

**0**answers

99 views

### Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...

**2**

votes

**0**answers

140 views

### How to implement linear constraints that include several absolute values

Dear all,
I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1
Since the minimization problem includes quite a ...

**0**

votes

**1**answer

612 views

### Finding linearly independent columns of a large sparse rectangular matrix

I have a problem that necessitates solving a large non-negative least-squares
problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols)
and nearly binary. However, A is not ...

**3**

votes

**2**answers

286 views

### Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...

**5**

votes

**2**answers

276 views

### relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$:
$$
\max_j c' x_j
$$
Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...

**1**

vote

**2**answers

457 views

### Nonstandard Hessian approximations in Gauss-Newton

The Gauss-Newton algorithm optimizes functions
$$
E(x) = \sum f(x)^2
$$
by approximating f as (locally) linear, in which case the Hessian of $E$ is approximated as
$$
H = 2 \sum {J_f}^T J_f
$$
Now ...