# Tagged Questions

**1**

vote

**1**answer

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

**4**

votes

**2**answers

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

**0**

votes

**1**answer

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

**4**

votes

**2**answers

367 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

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

**0**

votes

**1**answer

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

vote

**2**answers

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

**10**

votes

**1**answer

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

**1**

vote

**1**answer

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

**1**

vote

**2**answers

352 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

**2**answers

482 views

### Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...

**3**

votes

**1**answer

2k views

### Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute
$\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$.
where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.
Can this be solved with a linear ...

**2**

votes

**4**answers

354 views

### Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two ...

**3**

votes

**4**answers

529 views

### efficient way to compute the inversion of the following matrix

Hi, there
I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...