The linear-programming tag has no wiki summary.

**0**

votes

**1**answer

489 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

968 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

818 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

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

**3**

votes

**1**answer

222 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

719 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

365 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

309 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

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

**1**

vote

**2**answers

160 views

### Levenberg-Marquadt near the minima for non-zero-residual problems

I'm using the LM algorithm to do gradient descent in a model fitting context. I'm minimizing:
$$
c(x) = \sum ( f_i(x) - y_i )^2
$$
I'm noticing that after a few steps when I'm close to the minima, I ...

**0**

votes

**1**answer

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

**0**

votes

**0**answers

93 views

### Gauss-Newton for quotient functions

I'm optimizing a function of the form
$$
\sum \frac{ \|\mathbf{f_i}(x)\|^2 }{ g_i(x)^2 + h_i(x)^2 }
$$
where $x$ is a real vector, $\mathbf{f}(x)$ is a real vector, and $g(x)$ is a scalar. My first ...

**1**

vote

**1**answer

285 views

### Results for minimizing the norm w.r.t a unitary matrix

Suppose $x \in \mathbb{R}^n$, $B,U \in \mathbb{R}^n\times\mathbb{R}^n$ and $U$ a unitary matrix. Define $g_{U}(x) = || BUx||$ where $||.||$ is some norm or norm-ish function on $\mathbb{R}^n$ (not ...

**-1**

votes

**1**answer

3k views

### If then condition on mixed linear integer programming [closed]

Hi all. Let $a$ and $b$ be two real variables such that $0 \le a \le a_{max}$ and $0 \le b \le b_{max}$. I must write the following if-then-else condition with linear inequalities:
if $a < ...

**0**

votes

**0**answers

180 views

### A linear program related question

Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, ...

**0**

votes

**0**answers

71 views

### Computing maximum point for minimal function of a family of linear functions

Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such ...

**0**

votes

**1**answer

107 views

### Cascading minimization problems

Hi all. Suppose I have a linear programming problem on the vector variable $x$ that has many solutions and let $U$ be the set of these solutions. Suppose I have a second LP problem on $y \in U$. ...

**0**

votes

**2**answers

595 views

### linear programming with OR restrictions

Hi all. I have a linear program with the restriction that every variable can be zero or greater than or equal to a positive constant. That is:
minimize: $w^Tx$
subject to: $Ax=b$, $Cx \le d$ and for ...

**0**

votes

**2**answers

471 views

### Find both maximum and minimum values in linear programming problem

Hi all. I have a linear programming problem where I need to find both maximum and minimum values of the objective function. The optimal points are not relevant.
Is there an efficient way to do so?

**1**

vote

**2**answers

112 views

### LP/QP with not-so-constant linear constaints

I have an otherwise standard LP or PSD QP problem as below:
$\min\limits_x {c}' x$ subject to $Ax\leq b$
or
$\min\limits_x \frac{1}{2}{x}' Qx + {c}' x$ subject to $Ax\leq b$
the only exception ...

**0**

votes

**0**answers

197 views

### LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...

**1**

vote

**1**answer

279 views

### Solving a system of linear inequalities

Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. How this system can be solved without ...

**0**

votes

**1**answer

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

**0**

votes

**1**answer

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

**2**

votes

**1**answer

1k views

### sum of maxima vs the maximum of the sum

Consider the following integer program
$$
\begin{align}
\max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\
\text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant ...

**1**

vote

**2**answers

190 views

### what method can I employ to solve this optimization problem which involves \min?

The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N ...

**2**

votes

**2**answers

1k views

### Dual Norm For Sum of 2-Norms

What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$
$\|\mathbf{x}\| = ...

**1**

vote

**2**answers

287 views

### constructing a curve dividing two sets of points

Lets assume I have two sets of points, each characterized as being "A" or "B", respectively, that are in a Euclidean plane. Theoretically these two sets are samplings from a space that has ...

**2**

votes

**3**answers

721 views

### Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:
$\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2
\;\;
...

**1**

vote

**0**answers

161 views

### Consistency of a system of linear equations

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...

**1**

vote

**0**answers

249 views

### Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...

**3**

votes

**1**answer

265 views

### Grading a non-graded poset as squeezed as possible

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage).
Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...

**10**

votes

**1**answer

274 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**0**

votes

**1**answer

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

**2**

votes

**1**answer

399 views

### Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...

**1**

vote

**1**answer

177 views

### Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...

**0**

votes

**1**answer

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

**1**

vote

**2**answers

465 views

### Sherali-Adams relaxation

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...

**4**

votes

**1**answer

224 views

### Checking if one polytope is contained in another

Hi,
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...

**2**

votes

**1**answer

106 views

### Design constraint systems over the reals

This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...

**2**

votes

**2**answers

724 views

### how to model a linear program with step-like cost function in the objective

I have a large linear program with the following details.
d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form
d1 < d3 < d7 < d23 ...

**7**

votes

**2**answers

1k views

### How do you tell if a system of linear inequalities has a solution?

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.

**3**

votes

**0**answers

854 views

### 0,1 solution to system of linear integer equations.

I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...

**3**

votes

**0**answers

179 views

### Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...

**7**

votes

**1**answer

276 views

### Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...

**2**

votes

**2**answers

1k views

### Solving a system of equations/inequalities that have trigonometric functions on the left-hand side

Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...

**4**

votes

**1**answer

961 views

### Closest 3D rotation matrix in the Frobenius norm sense

Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...

**1**

vote

**1**answer

184 views

### Conditions for differentiability of minima and minimizers of linear functionals?

Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$.
For every continuous linear functional $F$ on $B$, define
$V(F)=min_{c\epsilon C} F(c)$ and
$S(F)= { \lbrace c \epsilon C ...

**3**

votes

**1**answer

384 views

### Solving for Hamiltonian path with constraints on allowable routes through vertices

Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...

**0**

votes

**1**answer

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