2nd CHILE-CCE SCHOOL IN OPTIMIZATION ABSTRACTS Shape Optimization

Giuseppe Buttazzo

Dipartimento di Matematica, Università di Pisa Via Buonarroti 2, 56127 PISA (Italy)

                         buttazzo@dm.unipi.it

Outline

1. Introduction to shape optimization problems

2. Classical examples and cases without optimal solutions

3. A general theory of relaxed optimal control problems

4. Existence of classical solutions under geometrical constraints 5. Existence of classical solutions for monotone costs

6. The case of functions of eigenvalues of Laplacian

7. Optimal shape design and Monge-Kantorovich equation

Inverse Problems in Optimization Theory and Microeconomics

Ivar Ekeland

Université Paris - Dauphine

Outline

1. The standard model of microeconomics.

2. Aggregation problems

3. Exterior differential calculus

4. The theorems of Frobenius and Darboux 5. The Cartan - Kähler theorem

6. Applications.

Semidefinite Programming and Combinatorial Optimization

Michel Goemans

CORE-Belgium

In this minicourse, we will study semidefinite programming and how it can be used for combinatorial optimization problems. Semidefinite programming is a special class of convex optimization problems in which the constraints involve the positive semidefiniteness of a matrix of variables. Semidefinite programming has a variety of applications, including for combinatorial optimization problems. An outline of the four lectures of the minicourse is given below.

1. In the first lecture, we will introduce semidefinite programming (SDP) and study its main properties from a convex programming perspective. Formulations, properties of the semidefinite cone, duality, complementary slackness, interior point algorithms and complexity issues will be discussed.

2. In the second lecture, we will present ways of deriving SDP relaxations for combinatorial optimization problems. We will highlight the relationship between eigenvalue bounds and SDP relaxations, and also discuss the derivation of SDP relaxations from integer quadratic programs. The various ways of deriving these relaxations will be illustrated on combinatorial optimization problems such as bisection, stable set or scheduling problems. In the process, we will also introduce the Lovasz theta function and study its main properties.

3. In the third lecture, we will consider the quality of the bounds obtained from semidefinite programming. We will introduce the random hyperplane technique and consider its application for the maximum cut and other problems. Computational results will be presented. We will also discuss other less easily approximable problems such as the stable set problem.

4. In the final lecture, we will consider the automatic generation of valid inequalities for general 0-1 integer programs, and discuss the matrix cut approach of Lovasz and Schrijver. We will study both its power and its limitations. If time permits, extensions of the approach will also be discussed.

Combinatorial Optimization

Martin Groetschel

Konrad-Zuse-Zentrum fuer Informationstechnik (ZIB), Berlin

1. Matroid Optimization

Matroids are simple but rich combinatorial structures with interesting connections to optimization. It is not the purpose of this lecture to introduce matroid theory! Only a few concepts of matroid theory (independent sets, bases, rank, cycles) suffice to state basic optimization problems (in matroid theory and elsewhere), to relate these to the design of heuristics, to analyse the performance of these heuristics, to outline the design of oracle-polynomial time algorithms, and to introduce important techniques in polyhedral combinatorics.

2. Stable Sets, Set Partitioning, and Applications

A stable set in an undirected graph G = (V, E) is a set S of nodes such that no two nodes are adjacent in G. Finding maximum (or maximum-weight) stable sets is one of the standard, NP-hard, and well-studied problems in graph theory and combinatorial optimization. It is closely related to the problem of finding, for a given finite set M, and a given system M_{i}, i = 1, ..., m, of subsets of M, each with a weight c(M_{i}), a minimum cost collection C of such sets M_{i} such that M = ⋃_{i}M_{i} ∈ C, M_{i} ⋂ M_{j} = ∅, i, j ∈ C. I will particularly focus on polyhedral aspects of these problems and the possibilities to solve them by linear programming techniques. Set partitioning has a wide range of interesting applications such as airline crew scheduling and bus routing. I will report here on our successful Telebus project, transporting disabled people in Berlin at low cost and with high service quality.

3. Combinatorial Optimization and Telecommunication

Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this talk I survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times.

The most general problem type I address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to

(i) minimize the building cost of the network,

(ii) satisfy all demands.

In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that

(iii) no path in the routing exceeds a given length,

(iv) no path can carry more than a given percentage of the demand.

We also have to make sure that

(v) for every single node or edge failure, a certain percentage of the demand is reroutable. Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile

phone provider. I describe our MIP-formulation of this model and report on computational results with data from practice.

I will also discuss the frequency (or channel) assignment problem for mobile phone systems. My group has developed a new mathematical model for this problem and designed and implemented algorithms that are used in practice in Germany to assign chancels to antennas. This problem is closely related to node coloring in graphs.

4. Combinatorial Online Optimization

In “classical” optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In adddition, decisions once made, cannot be changed. How should one act “best” in such an environment?

In this talk I will survey online problems coming up in combinatorial optimization. I will focus on real-world applications and report, in particular, on problems arising in transportation and the control and optimization of material handling systems. I will outline theoretical ways to analyse online problems (e.g., the concept of competitiveness); but I will also show what can be (and is) done in practice. Online optimization is a field wide open for innovative research and modelling. In practical situations it is often not clear what really is to be optimized, thus, often auxiliary problems are considered that reflect a compromise between various points of view. Similarly, it is not apparent what an optimal online strategy is. I will also discuss such issues.

Nondifferentiable Optimization: An Interior Point Perspective

Jean-Philippe Vial

University of Geneva

                      jean-philippe.vial@hec.unige.ch

1. Nondifferentiable and Large Scale Optimization

Nondifferentiable optimization (in short NDO) often results from a reformulation of a large-scaled structured optimization problem, for example by using a Lagrangian relaxation scheme or Benders decomposition. Another reformulation leading to a NDO problem is the dual gap function associated with a variational inequalities problem. Other sources of NDO problems are minmax problems, semi-infinite programming, and column generation techniques.

There are well-known examples for which standard optimization techniques fail to solve NDO problems. There is thus a need for adapted methods. We shall briefly review existing methods such as the subgradient optimization, the bundle method and the level set bundle methods, the ellipsoid method, and the family of cutting plane methods. The latter include Kelley-Cheney-Goldstein cutting plane, and various centering methods, e.g., Levin’s center of gravity, Cebysev center or the largest inscribed sphere, center of the maximum volume ellipsoid, analytic center, volumetric center. The analytic center cutting plane method (ACCPM) will be the focus of the mini-course.

2. Interior point methods

the analysis of ACPPM heavily relies on the theory of of interior point methods (IPM) for linear and convex structural programming. We need thus review some basic facts in the theory of IPM’s for linear programming. In particular, we discuss Newton method with damped steps and prove useful convergence results.

3. The analytic center cutting plane method

The convergence analysis of ACCPM is based on the behavior of the barrier method at successive analytic centers. The interior point methodology is used to bound this variation, and to derive a bound on the number of calls to the cut generation mechanism. We also show that the number of Newton iterations to compute a new center is bounded; this yields an overall complexity estimate for the method.

4. Implementation, extensions, and applications

We discuss two types of extensions. The first type is motivated by the need to handle practical situations such as deep cuts, or multiple cuts that arise in many applications. We show how it can be done in order to maintain the complexity result for the method. This leads to a description of the actual implementation of ACCPM. The other type is motivated by the desire to sharpen the complexity result. We show that by embedding the problem into a homogeneous space, we can solve a larger class of problems: minimizing a function under constraints described by a general barrier function and solving variational inequalities.

We conclude with a brief review of some classical examples such as stochastic programming, multiregional planning, survivability in telecommunications networks, capacitated lotsizing problems…

Lectures on Stochastic Programming

Roger J-B Wets

Department of Mathematics, University of California, Davis

                          rjbwets@math.ucdavis.edu

1. Model description: Basic features

A. What it is not: Random linear programs B. Stochastic programs: A model for decision making under uncertainty C. Mathematical formulation: Basic recourse model D. Solution procedures: The multi-dimensional integration hurdle E. The appraisal function, the cost to go

2. Model formulation: Basic Properties

A. The two-stage recourse model, the linear case B. The multistage recourse model C. The equivalent deterministic program D. The extensive (functional) formulation: structural properties E. Key lemma: Interchange of minimization and integration F. The nonanticipativity restriction G. Optimality conditions, duality theory H. Induced constraints I. Problem classification

3. Algorithmic Procedures

A. The L-shaped method: 2-stage and multistage versions B. The method of progressive hedging C. Stochastic quasi-gradient methods

4. Approximation and sampling

A. Lower and upper bounding problems, linear case B. Approximation theory for variational problems C. Epi-convergence and epi-distance D. Stability under perturbation of the probability measure E. An ergodic theorem for random lsc functions F. Sampling: importance sampling