Duality results for optimising over thin convex sets

Add to your list(s) Download to your calendar using vCal

• Akshay Gupte (University of Edinburgh)
• Tuesday 20 June 2023, 14:00-15:00
• Arts Lecture Room 4.

If you have a question about this talk, please contact Sergey Sergeev.

A closed convex set is said to be thin if its support function has a closed domain. Examples include polyhedra, cones and compact sets. Our main focus is on optimising a linear function over a thin set and over the mixed-integer points in it. We note some correspondences between the finiteness of these two problems. Our first main result is on constraint qualifications (CQ) for strong duality of the continuous problem. We show that closedness of an adjoint image of the barrier cone is a sufficient condition for strong duality, and also make some remarks about its necessity. This sufficiency has been established for cones (but is not as well-known), and hence we provide a generalisation to thin sets. We also note that the Slater CQ is a special case of this, and provide some necessary and sufficient conditions on this CQ, along with a theorem of the alternative on almost feasibility and a semi-infinite characterisation for projection of a conic set onto a linear subspace.

The second part of this talk will give an infinite family of linear valid inequalities describing the convex hull of the mixed-integer feasible region. The main element of our proof is to establish a new strong subadditive dual that unlike the existing dual from literature, is much cleaner to describe since it does not include directional derivative constraints, and becomes a finite-dimensional problem when the input data is integral. It is known that a thin set with a rational recession cone has a polyhedral integer hull. We discuss which elements of our proof strategy are for arbitrary sets and which are for cones.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• Arts Lecture Room 4
• Optimisation and Numerical Analysis Seminars
• School of Mathematics events

Note that ex-directory lists are not shown.