Lecture hall on the ground floor
John M. Sullivan (TU Berlin) (14:00 - 14:20 )
Surface Evolver
Konrad Polthier (ZIB), Klaus Hildebrandt (ZIB) (14:20 - 14:40 )
Surface optimization and feature extraction
Rene Henrion (WIAS) (14:40 - 15:00 )
Calculating values and gradients of polyhedral chance constraints
Many applications in engineering sciences or mathematics of finance leed to optimization problems with probabilistic or chance constraints. These allow to model inequalities which are effected by random parameters.
The talk presents a solution approach to a special type of frequently encountered chance constraints. The main numerical difficulty occurs when the number of inequalities exceeds the dimension of the random vector. Even if the latter has a regular normal distribution, the mentioned situation will inevitably lead to the consideration of singular normal distirubtions.
Our approach relies on an inclusion exclusion formula for polyhedra which allows to get back to regular distributions again. The numerical solution procedure combines Fukuda's Scdd+ - code for corner determination of polyhedra with efficient codes for evaluating regular normal distributions (e.g., Genz, Szantai).
We demonstrate
the advantages of our method - which are striking in problems of moderate size -
by comparison with competing methods (e.g. crude Monte Carlo, Deak's code
for the probability of convex sets, Genz' code for singular normal
distributions by numerical integration). A corresponding implementation as a
software tool is under development.
Download talk (PDF)
Andreas Rathsfeld (WIAS), J.Elschner (WIAS), G.Schmidt (WIAS) (15:00 - 15:20 )
Optimisation of diffraction gratings with DIPOG
Many modern optical devices include
diffractive optical elements. Clearly, the
optimization of their performance is an
important task.
The program package
DIPOG provides fast and rigorous simulation
tools for optical gratings based on the
approximation of Maxwell's equations
by FEM.
Additionally, DIPOG is also able to optimize the geometrical shape of binary gratings, i.e., of gratings composed of rectangular blocks. The optimization routines are based on local gradient methods like Projected Conjugate Gradient Methods or Interior Point Methods.
The gradients expressed as a function of
Maxwell solutions are computed by FEM.
Currently, we extend these algorithms to
cover optimal design problems for general
polygonal shapes.
Download talk (PDF)
Thorsten Koch (ZIB) (15:50 - 16:10 )
Soplex (Simplex based LP Solver) and ZIMPL (Modeling language)
SoPlex is an implementation of the revised simplex algorithm.
It features primal and dual solving routines for linear programs,
i.e., min c^T x subject to Ax <= b, x >= 0,
and is implemented as a C++ class library that can be used with other
programs. An example program to solve standalone linear programs given
in .mps or .lp format files is also included.
Zimpl is a little language to translate the mathematical model of a
problem into a linear or (mixed-) integer mathematical program
expressed in .lp or .mps file format which can be read and (hopefully)
solved by a LP or MIP solver, for example, SoPlex (LP) and
SCIP (MIP).
Download talk (PDF)
Tobias Achterberg (ZIB) (16:10 - 16:30 )
Solving Constraint Integer Programs (SCIP)
The software package SCIP is a solver and a framework for
Constraint Integer Programming. It integrates solving techniques from
the two fields
Mixed Integer Programming
originated in the OR community. A Mixed Integer Program (MIP) is an
optimization problem with linear objective function and linear
constraints. Additionally, some or all of the variables may be
restricted to integral values. These integrality conditions render the
problem NP hard. For solving MIPs, one usually applies a
branch-and-bound algorithm in which the problem is successively
divided into smaller subproblems. For each subproblem, the LP
relaxation is solved (and possibly strengthened by so-called cutting
planes) in order to generate a dual bound.
Constraint Programming originated in the AI community.
Constraint Programs (CPs) are much more general than MIPs. Both, the
objective function and the constraints may be non-linear. If the
domains of the variables are finite, a CP can be solved by
(implicitly) enumerating all potential solutions, similar to the
branch-and-bound algorithm for MIPs. In contrast to MIP solvers, which
rely on the LP relaxation, CP solvers employ so-called domain
propagation in the subproblems to deduce additional restrictions on
the variables' domains and thereby pruning the search tree.
SCIP is oriented towards the needs of Mathematical Programming
experts who want to have total control of the solution process and
access detailed information down to the guts of the solver. It has the
following features:
Ivo Nowak, Lufthansa Systems Berlin (16:30 - 16:50 )
LaGO - A solver for mixed integer nonlinear programs
In this talk we give a short overview of the Lagrangian Global Optimizer (LaGO), which solves general mixed integer nonlinear programs.
We will describe the basic optimization tools
and present numerical results.
Download talk (PDF)
Steffen Weider (LBW) (16:50 - 17:10 )
Bundlemethods
In this talk we present a bundle method to solve unconstrained convex
minimization problems. This bundle method also provides primal information
for Lagrangean relaxations of linear programs and can therefore be used as a
fast replacement of a simplex solver, if accuracy of the solution is not
crucial. We will outline how the algorithm works and show some applications
of our bundle method.
Download talk (PDF)
Jan Riehme (HU), Andreas Griewank (HU Berlin & Matheon) (17:30 - 17:50 )
Software for Evaluating Derivatives of Programs
Software for solving nonlinear optimization problems typically expects the user to provide routines for evaluating objectives and constraints as well as their first derivatives. When first derivatives are not provided, most solvers resort to divided difference approximations, a rather crude approach which severely limits efficiency and solution accuracy. A rather tedious task for the user is also the specification of the sparsity patterns of derivative matrices. Many rather academic problems have now been specified in AMPL, GAMS or another modeling environment, where gradients and even Hessians are available without any significant effort to the user.
On the other hand many industrial practicioners resort to derivative free search methods or abstain from systematic optimization alltogether, because their models appear too complicated for the evaluation of derivatives. While some obstacles like heterogenous and proprietory codes are certainly serious, others can be overcome with the help of algorithmic differentiation software and some user training. The key assumption remains to date that the problem functions are provided as source code in a Fortran or C variant.
We present two of the most important tools for these programming languages
and discuss small examples. Finally we show briefly, how checkpointing
techniques can be used to solve time dependent problems efficiently.
Download talk (PDF)
Tobias Gaenzler (ZIB) (17:50 - 18:10 )
Function space interior point methods in KASKADE
The finite element software KASKADE and its commercial counterpart
JCMsolve were primarily designed for the solution of partial
differential equations in 1D, 2D and 3D.
Types of PDE's which
can be solved include Maxwell's equations,
static convection-diffusion, linear elasotomechanics and timeharmonic
Helmholtz problems.
Recently KASKADE has been extended to solve
PDE-constrained optimization problems
with a convex objective and
bound constraints on the control u and the state y.
In this talk we will present the software and how the optimization
problem is solved by function-space interior point methods.
Download talk (PDF)
Marc Steinbach (ZIB) (18:10 - 18:30 )
Modular codes for NLP, QP, and KKT systems
The talk describes research codes that have been developed for solving quadratic and nonlinear programs, particularly in the areas of discretized multistage stochastic programs and DAE boundary value problems.
The codes include an SQP method, an Interior Point Method for QP, and various
special solvers for structured KKT systems, or meta-solver in the case of multi-
stage stochastic programs. They also include a convenient C/C++ interface to the
BLAS and LAPACK libraries.
Download talk (PDF)