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

**David Bremner**

Minimum norm points on the boundary of convex polytopes

**Coauthor: Yan Cui**

**Abstract:**

Given two sets of vectors in *P, Q ⊂ ***R**^{d} the *maximum*

margin hyperplane is defined by the solution to the following

\begin{equation*}

\mathrm{margin}(P,Q) = \sup_{w ∈ \mathrm{bd} **B**^{*}} ∈ f_{p ∈ P, q ∈ Q} ⟨ w, p-q ⟩

\end{equation*}

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"** [...]