# Tagged Questions

204 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 ...
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 ...
47 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 ...
366 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 ...
64 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$. ...
367 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. ...
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 ...
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 ...
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 ...
351 views

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