| A typical problem in discrete optimization requires choosing the best solution from a large but finite set of possibilities, for example, the best order in which a salesperson should visit clients so that the route travelled is as short as possible. The difficulty is that the number of possibilities is usually very large, so that enumerating them one by one is not an option. A similar challenge occurs with problems that exhibit a large number of local optima while the practical application requires knowledge of the global optimum. This typically happens with models involving quadratic or other nonlinear functions. In the last two decades, semidefinite programming has been developed as a possible way to cope with these phenomena. Here, one transforms the original problem to a higher-dimensional matrix space to obtain a problem which is efficiently solvable. However, in this transformation step some information is usually lost, so that the transformed problem is just a (possibly very good, possibly bad) approximation of the original problem. Only quite recently have researchers begun to understand that this loss of information can be avoided by using copositive programming instead of semidefinite programming, i.e., by optimizing over the set of copositive matrices instead of the semidefinite matrices. While semidefinite programming has been intensively studied, copositive programs are much less well-understood. The proposed research project will try to fill this gap and * provide a better understanding of copositive programming and its applicability to discrete and quadratic optimization problems; * develop algorithmic methods to solve copositive optimization problems;* use copositivity to improve existing semidefinite programming methods, for example by designing suitable cutting planes. The results of the project will lead to new powerful solution methods for classes of optimization problems that have up to now not been solvable in reasonable time. |
