Support Research supported by Deutsche Forschungsgemeinschaft, grant WE 1066/11-1.
Today randomization plays a major role in virtually all parts
of computer science. Stochastic optimization methods are optimization
algorithms that incorporate random elements. The inputs of the algorithm
may be chosen randomly, or even for a fixed input the algorithm may use
random decisions as a powerful algorithmic resource to speed
up the optimization process.
In this context robustness stands for the sensitivity of the time
or space complexity of the algorithms to slight changes of the input
or the parameters of the algorithm.
For example, the input to an optimization algorithm might be obtained
by a noisy measurement that has slight random fluctuations.
Clearly, it is highly undesirable that the random fluctuations
have a major impact on the time complexity of the optimization algorithm.
Therefore the optimization algorithm should be robust with respect
to slight changes of the input.
Some optimization algorithms have additional parameters besides the input
that have a substantial influence on the performance of the algorithm.
Often there is no simple rule for the choice of good parameters and the
parameters are chosen by some rule of thumb. This situation calls
for optimization algorithms that are robust with respect to the parameters.
The aim of this project is the development and analysis of stochastic optimization algorithms that are robust with respect to different aspects such as