*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion Plenum
Mittwoch, 20.09.2000, 9.00 Uhr, Großer Mathematik-Hörsaal, Trefftz-Bau

Modern Convex Optimization and Engineering Design

Aharon Ben-Tal, MINERVA Optimization Center Technion – Israel Institute of Technology

We briefly describe the evolution of theoretical and computational ideas underlying the progress in optimization. We then concentrate on three main topics which are at the core of modern optimization.

(a) Efficiency estimates of algorithms, i.e., bounds on the error induced by an iterative algorithm at each iteration — in contrast to asymptotic convergence.
(b) Complexity of algorithms, i.e., the number of arithmetic operations needed to solve a problem within a prescribed error bound — in contrast to asymptotic speed of convergence.
(c) Tractable optimization problems, i.e., problems with specific structure, yet rich in modeling possibilities, for which efficient polynomial-time algorithms are available.
The central model for tractable problems is the conic convex program

(P)                       inf {cTx |Ax  - b  (-  K}
where K is one of the three convex cones
K = Rn (for which problem (P) is a linear program)
K = the second order (Lorentz) cone
(for which problem (P) is a conic quadratic program)
K = the cone of symmetric positive-semi-definite matrices
(for which problem (P) is a semi-definite program).
We summarize the state-of-the-art complexity theory for problem (P). Finally, we demonstrate the new possibilities offered by modern optimization methods in other disciplines:
Combinatorial Optimization (example: the MAXCUT problem);
Dynamic Systems and Control (example: Lyapunov stability of uncertain dynamic systems);
Uncertain Engineering Design (examples: Synthesis array of antennae, truss topology design).