## Contributed Session Fri.3.H 2053

#### Friday, 15:15 - 16:45 h, Room: H 2053

**Cluster 9: Global optimization** [...]

### Advances in global optimization VI

**Chair: Daniel Aloise**

**Friday, 15:15 - 15:40 h, Room: H 2053, Talk 1**

**Holger Diedam**

Global optimal control using direct multiple shooting

**Coauthor: Sebastian Sager**

**Abstract:**

Motivated by state-of-the-art algorithms for mixed integer optimal control problems (MIOCP), where lower bounds on the solution are necessary, we developed a numerical method to combine direct multiple shooting with convex relaxation techniques for optimal control problems.

Embedded into an extended branch and bound framework and applied to a MIOCP with relaxed integer decisions, the lower bounds on the solutions allow to determine if the objective value of the resulting optimal control problem is, at least up to a desired epsilon accuracy, close to the global solution. Afterwards, we apply integer approximation methods like the Sum Up Rounding strategy to the relaxed solution in order to obtain arbitrarily close approximations of the global integer solution for a wide range of MIOCPs.

Finally, we present first numerical results on selected benchmark problems from the literature and new challenging problems including mixed integer decisions with relaxed problems that exhibit multiple local minima.

**Friday, 15:45 - 16:10 h, Room: H 2053, Talk 2**

**Daniel Aloise**

A column generation algorithm for semi-supervised clustering

**Coauthors: Pierre Hansen, Caroline Rocha**

**Abstract:**

Clustering is a powerful tool for automated analysis of data. It addresses the following problem: given a set of entities find subsets, called clusters, which are homogeneous and/or well separated. In addition to the entities themselves, in many applications, information is also available regarding their relations in the space. This work presents

a column generation algorithm for minimum sum-of-squares clustering in the presence of must-link and cannot-link pairwise constraints. The computational results show that the proposed algorithm is faster

than the current state-of-the-art method.

**Friday, 16:15 - 16:40 h, Room: H 2053, Talk 3**

**Syuuji Yamada**

Global optimization methods utilizing partial separating hyperplanes for a canonical dc programming problem

**Coauthors: Tamaki Tanaka, Tetsuzo Tanino**

**Abstract:**

In this talk, we consider a canonical dc programming problem (CDC) to minimize a linear function over the difference between a compact convex set and an open bounded convex set. It is known that many global optimization problems can be transformed into (CDC). Hence, for (CDC), many approximation algorithms based on outer approximation methods and branch-and-bound procedures have been proposed. However, since the volume of data necessary for executing such algorithms increases in proportion to the number of iterations, such algorithms are not effective for large scale problems. Hence, to calculate an approximate solution of a large scale (CDC), we propose new iterative solution methods. To avoid the growth of data storage, the proposed methods find an approximate solution of (CDC) by rotating a partial separating hyperplane around a convex set defining the feasible set at each iteration. Moreover, in order to improve the computational efficiency of the proposed methods, we utilize the polar coordinate system.