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


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


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


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.


  Payday Loans In Illinois. The new drug with unique properties was developed to help men to get rid of all sexual disorders, and its name is Cialis Super Force. Now you do not have to buy two different medications to solve sexual problems.