8 June 2018       School of Mathematics, Edinburgh
Home       Keynote Speaker       Abstracts       Schedule       Registration       NATCOR      


Immanuel Bomze   (University of Vienna, Austria)

Talk title: Different duals in conic optimization - closure can tighten the duality gap

Abstract: One of the most powerful methods for obtaining efficient bounds for hard optimization problems is based upon (Lagrangian) duality, i.e. linearly combining the original objective and (some of) the constraints. In general there will be a gap between the best such bound, i.e., the optimal dual value, and the originally sought optimal primal value.
Most frequently, a positive duality gap is blamed upon failure of convexity; however, even in a linear context (over convex cones), positive or even infinite duality gaps can also occur (in sharp contrast to the familiar linear optimization over polyhedra), and this is due to a failure of closedness of related sets, rather than a convexity problem.
Likewise, attainability can fail in this context as witnessed by the celebrated Frank-Wolfe theorem and related all-quadratic counterexamples over convex feasible sets.
Moreover, the dual problem significantly depends on the choice how to model the primal problem: one and the same primal problem can have several dual formulations with different gaps and attainability properties; the talk will address a recently investigated hierarchy of these dual models: we consider a primal-dual pair of conic optimization which deals with optimizing a linear function over an affine subset of a closed, convex cone. Well investigated and widely used examples include the positive orthant (LP), the semidefinite cone (SDP), the copositive cone (COP) or the completely positive cone (CPP).
The latter two occur in reformulations or tight relaxations of hard optimization problems, among them indefinite quadratic (fractional or binary) programs, and several combinatorial optimization problems.
This talk presents a construction which transforms any such primal-dual pair with an arbitrary (zero, positive or infinite) duality gap into another pair with the same optimal objective values, where either the primal or the dual optimal value is not attained. The construction basically doubles the size of the problems and establishes all possible combinations of gaps and attainability.
Further, a quite recent fresh look at mixed-binary quadratic problems will be offered, establishing a hierarchy of dual problems with different tightness of dual bounds and time permitting, we will shortly address the Semi-Lagrangian tightening of all-quadratic problems with a copositive reformulation. As is well-known, (COP) or (CPP) cannot be solved directly since the involved cones are intractable, but they can be approximated to arbitrary accuracy, e.g. the copositive cone from inside by polyhedral cones yielding a sequence of LPs which all tighten classical Lagrangian bounds considerably in case of a positive classical duality gap.
Based upon joint work with:
Jianqiang Cheng, Univ. Arizona;
Peter J.C. Dickinson, Univ. Twente;
Abdel Lisser, Univ. Paris Sud;
Jia Liu, Xi'an Jiatong Univ.;
Werner Schachinger and Gabriele Uchida, Univ. Vienna.

Emre Alper Yildirim   (Koc University, Turkey)

Talk title: Alternative mixed integer linear programming formulations for globally solving standard quadratic programs

Abstract: Standard quadratic programs have numerous applications and play an important role in copositivity detection. We consider reformulating a standard quadratic program as a mixed integer linear programming (MILP) problem. We propose alternative MILP reformulations. We report computational results on various classes of instances and discuss the advantages and drawbacks of MILP reformulations.
This is joint work with Jacek Gondzio.

Francisco N. C. Sobral   (University of Maringa, Brazil)

Talk title: Two-phase derivative-free constrained optimization

Abstract: Derivative-free optimization is used to solve problems where the cost of computing derivatives is very high, sometimes prohibitive. This is because derivatives are very difficult to compute or implement (user cost) or because the functions associated are costly, black-boxes or cannot even be coded (computer cost). In this talk, we will present algorithms to solve problems where the derivatives of the objective function are unavailable, whereas the derivatives of the constraints can be used if needed. Moreover, it is supposed that the computational cost of evaluating the objective function is the most expensive part of the algorithm. The algorithms are based on a two-phase idea, splitting the optimization process into two steps: feasibility and optimality. In the feasibility step, there are no function evaluations and the aim is to decrease infeasibility. In the optimality phase, the aim is to decrease the current objective function value without loosing feasibility. Theoretical results will be discussed and the numerical experiments show that the strategies are flexible and robust.

Julian Hall   (University of Edinburgh, UK)

Talk title: A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

Abstract: This talk will present and analyse an established but previously undocumented technique which aims to obtain an approximate solution to linear programming problems prior to applying the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is used. Later the technique corresponds closely to a classical quadratic penalty method. There will also be a discussion of the extent to which it can be used to obtain fast approximate solutions of LP problems, in particular when applied to linearizations of quadratic assignment problems.