## Invited Session Tue.3.H 3008

#### Tuesday, 15:15 - 16:45 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Combinatorics and geometry of linear optimization II

**Chair: Jesus Antonio De Loera and Antoine Deza**

**Tuesday, 15:15 - 15:40 h, Room: H 3008, Talk 1**

**Gabor Pataki**

Bad semidefinite programs: They all look the same

**Abstract:**

In the duality theory of semidefinite programming (SDP),

unlike in LP, "pathological'' phenomena occur: nonattainment of the optimal value, and

positive duality gaps between the primal and dual problems.

This research was motivated by the curious similarity of pathological SDP instances appearing in the literature.

We find an exact characterization of semidefinite systems, which are badly behaved from the viewpoint of duality,

i.e., show that "all bad SDPs look the same''.

We also prove an excluded minor type result: all badly behaved semidefinite systems can

be reduced (in a well defined sense) to a minimal such system with just one variable,

and two by two matrices. Our characterizations imply that recognizing badly behaved

semidefinite systems is in **NP*** ∩ *coNP

in the real number model of computing.

The main results follow from a fairly general characterization of badly behaved conic

linear systems, and hinge on a previous theorem

on the closedness of the linear image of a closed convex cone.

We show characterizations of badly behaved second order, and other conic systems as well.

**Tuesday, 15:45 - 16:10 h, Room: H 3008, Talk 2**

**Tamon Stephen**

The width of 4-prismatoids

**Coauthors: Francisco Santos, Hugh Thomas**

**Abstract:**

Santos' construction of a counterexample to the Hirsch conjecture highlights a particular 5-dimensional "prismatoid'' polytope. We use the Euler characteristic to prove that there is no analogous 4-dimensional prismatoid.

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

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