Tuesday, 16:15 - 16:40 h, Room: H 3008


David Bremner
Minimum norm points on the boundary of convex polytopes

Coauthor: Yan Cui


Given two sets of vectors in P, Q ⊂ Rd the maximum
margin hyperplane
is defined by the solution to the following
\mathrm{margin}(P,Q) = \supw ∈ \mathrm{bd B*} ∈ fp ∈ P, q ∈ Q ⟨ w, p-q ⟩
where B is the relevant unit ball.
In the case where \mathrm{margin}(P,Q) ≥ 0, (the separable case),
this problem is dual to finding the minimum norm point in the
Minkowski sum P\ominus Q of \mathrm{conv} P and \mathrm{conv} -Q and can thus be
solved efficiently.
When 0 ∈ \mathrm{int} (P\ominus Q), margin is dual to finding the
smallest translation that makes the two sets separable. It turns out
this is defined by the minimum norm point on the boundary of P
\ominus Q
. In this case the feasible is only piecewise convex, and
the problem is NP-hard.
In this talk I will discuss experimental results from two approaches
to the non-seperable case. The first approach solves one convex
minimization per facet of P \ominus Q. The second approach
(applicable only to polytopal norms) solves one LP per vertex of the
unit ball B.


Talk 3 of the invited session Tue.3.H 3008
"Combinatorics and geometry of linear optimization II" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.