Tagged Questions

0
votes
1answer
25 views

Find a point in a polytope that always cuts off a constant fraction of the polytope.

I have $k$ linear inequalities in $\mathbb{R}^n$, which we can express as $Ax \ge c$ (where $A \in \mathbb{R}^{k \times n}$ and $c \in \mathbb{R}^k$). Assume that the set of $x \in \mathbb{R}^n$ that ...
2
votes
1answer
55 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
1
vote
0answers
21 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
1
vote
1answer
33 views

Is this a linear programming problem

If $x \in R^n$, then $\min \|x\|_{\infty}$ sub to $Ax = b$, $x \geq 0$ where $\|x\|_{\infty}$ is the infinity norm which is $\max\{\|x_1\|,\|x_2\|,\ldots,\|x_n\|\}$. If not then how can ...
3
votes
1answer
55 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
4
votes
5answers
149 views

Find a convex combination of scalars given a point within them.

I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me. Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
0
votes
2answers
165 views

Convex function from Hessian

Am I correct to say that the following function is convex? $$\begin{align} & f(x,y)=-\sqrt{xy} \\ & x>0,y>0 \\ \end{align}$$ After computing the Hessian: $$ Hf =\left[ \begin ...
6
votes
1answer
392 views

Farkas Lemma proof

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia: Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
0
votes
0answers
37 views

Some questions on Linear Programming in Low Dimensions

I am trying to answer questions of a combinatorial nature about the number of hyperplanes we draw in an LP type problem such as finding the center point of a given point set P having n points. The ...
1
vote
1answer
206 views

Convex hull of sets defined by (in)equalities

If you define the convex hull of a set $X$ as the set of all convex combinations of elements of $X$, it becomes difficult to decide if a given element $w$ belongs or not to $conv(X)$ (You have to ...
4
votes
1answer
522 views

Proving Helly's theorem

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality. Helly's theorem Let $B_{1},...,B_{m}$ be a collection of convex ...