Homehome Contactcontact
» Abstract Submission System «

Invited Speakers

 

Immanuel M. Bomze
University of Vienna
A nasty cone with nice properties – new issues in copositive optimization
(abstract; homepage)

Mirjam Dür
University of Groningen
Optimally Fitting Hyperplanes to Data
(abstract; homepage)

Alexander Shapiro
Georgia Tech
Risk averse stochastic programming
(abstract; homepage)

Tamás Terlaky
Lehigh University
Linear Optimization: Algorithms and Conjectures
(abstract; homepage)

Luís Nunes Vicente
University of Coimbra
Direct Search for Single and Multiobjective Optimization
(abstract; homepage)

Henry Wolkowicz
University of Waterloo
Theory and Applications of Degeneracy in Cone Optimization
(abstract; homepage)

 

Special Lecture on Hirsh Conjecture

 

Francisco Santos
Universidad de Cantábria
A counter-example to the Hirsch conjecture
(abstract; homepage)

 

Talk Abstracts

 

A nasty cone with nice properties – new issues in copositive optimization

Immanuel M. Bomze, University of Vienna

A symmetric matrix is called copositive, if it generates a quadratic form taking no negative values over the positive orthant. Contrasting to positive-semidefiniteness, checking copositivity is NP-hard. In a copositive optimization problem, we have to minimize a linear function of a symmetric matrix over the copositive cone subject to linear constraints. This convex program has no non-global local solutions. On the other hand, there are several hard non-convex programs which can be formulated as copositive programs, among them mixed-binary QPs or Standard QPs. Applications range from machine learning to several combinatorial optimization problems, including the maximum-clique problem or the maximum-cut problem.

The dual conic program, unlike the more popular SDP case, involves a different matrix cone, that of completely positive matrices (those which allow for a symmetric, possibly rectangular factorization with no negative entries). This conic optimization technique shifts complexity from global optimization towards sheer feasibility questions. Therefore it is of central importance to devise positive and negative certificates of copositivity and/or complete positivity.

Three new copositivity tests based upon difference-of-convex (d.c.) decompositions are presented, and combined to a branch-and-bound algorithm of omega-subdivision type. The tests employ LP or convex QP techniques, but also can be used heuristically if educated guesses are available and preferred. We also propose some preprocessing ideas, which result in a normal form for copositivity. Switching to complete positivity, a heuristic factorization procedure for obtaining an explicit factorization is also presented.

 

Optimally Fitting Hyperplanes to Data

Mirjam Dür, University of Groningen

Suppose you are interested in estimating the slope of a line fitted to data points. How should you fit the line if you want to treat each variable on the same basis?

Least squares regression is inappropriate here since it’s purpose is the predictions of one of the variables, so it requires to specify which variables are the independent variables and which one is the dependent variable. A change in this setting will lead to a completely different least squares estimate. Moreover, the least squares model is based on the assumption that only the dependent variable is subject to measurement errors; the independent variables are assumed to be known exactly, a premise that is often not fulfilled.

We will present an approach that avoids these shortcomings. The basic idea is that a different criterion is chosen to be minimized for the optimal hyperplane: instead of minimizing the sum of the squares of the residuals, we consider the deviations for each variable and multiply them. The new estimate possesses desirable theoretical properties and comes with a nice geometrical interpretation. However, in contrast to least squares regression it requires the solution of a global optimization problem.

 

Risk averse stochastic programming

Alexander Shapiro, Georgia Tech

In recent years a theory of the so-called coherent risk measures had emerged. Its application to static (two-stage) stochastic programming is well established and generally accepted by the scientific community. The multistage case, on the other hand, is much more delicate. In this talk we discuss various approaches to multistage risk averse stochastic programming and point to involved conceptual and numerical difficulties.

 

Linear Optimization: Algorithms and Conjectures

Tamás Terlaky, Lehigh University

In this talks we briefly review some fundamental algorithmic concepts for Linear optimization. The algorithms include elimination and pivot algorithms, ellipsoid and interior point methods and the perceptron algorithm. Complexity and convergence of the algorithms will be discussed. Open problems and conjectures related to both pivot algorithms and interior point methods will be discussed. Finally, we consider how the various algorithms could utilize the readily available multi-core architectures.

 

Direct Search for Single and Multiobjective Optimization

Luís Nunes Vicente, University of Coimbra

Direct search is a popular class of algorithms for the minimization of a function without derivatives. Most direct-search methods are based on evaluating the objective function at a set of (poll) points defined by a positive spanning set.

In this talk we will characterize the behavior of direct-search methods under adverse conditions by (i) studying its global convergence properties and numerical behavior when the objective function is discontinuous and (ii) presenting a worst case complexity bound on the number of function evaluations.

Then, we will briefly introduce an extension of direct search to multiobjective optimization (called direct multisearch) by essentially changing the polling paradigm to incorporate nondominancy tests. Direct multisearch enjoys rigorous global convergence properties and exhibits excellent numerical performance (as it will be shown in the contributed talk by A. L. Custódio).

 

Theory and Applications of Degeneracy in Cone Optimization

Henry Wolkowicz, University of Waterloo

The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones.

We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility.

Surprisingly, many instances of semidefinite programming, SDP, problems that arise from relaxations of hard combinatorial problems are degenerate (CQ fails). Rather than being a disadvantage, we show that this degeneracy can be exploited. In particular, several huge instances of SDP completion problems can be solved quickly and to extremely high accuracy.

 

A counter-example to the Hirsch conjecture

Francisco Santos, Universidad de Cantabria

The Hirsch conjecture, stated in 1957, said that if a polyhedron is defined by n linear inequalities in d variables then its combinatorial diameter should be at most n-d. That is, it should be possible to travel from any vertex to any other vertex in at most n-d steps (traversing an edge at each step). The unbounded case was disproved by Klee and Walkup in 1967. In this talk I will describe the construction of the first counter-example to the bounded case (a polytope).

The conjecture was posed and is relevant in the context of the simplex method in linear programming. The simplex method, after all, finds the optimal solution by moving from vertex to vertex along the edges of the feasibility polyhedron. Experimentally, the simplex method usually finishes in a linear number of steps, but examples where certain choices of pivot rules lead to exponentially long paths exist, and no pivot rule is known that can be proved to always finishes in polynomial number of steps. Although other methods for linear programming are proved to be polynomial (Karmakar, Khachiyan), the simplex method remains one of the methods most often used in practice.

From a complexity theory point of view, it is also significant that the known methods are polynomial in the "bit complexity" model, but a polynomial pivot rule for the simplex method would provide a "strongly polynomial" algorithm, that is, one that is polynomial also in the "real machine" model. The question whether such a "strongly polynomial" method exists for linear programming was included by S. Smale in his list of "Mathematical problems for the next century" (AMS, 2000). Of course, a polynomial pivot rule can only exist if the combinatorial diameter is polynomially bounded.