Invited Session Fri.2.H 1012

Friday, 13:15 - 14:45 h, Room: H 1012

Cluster 17: Nonsmooth optimization [...]

Nonsmooth optimization and applications


Chair: Dominikus Noll



Friday, 13:15 - 13:40 h, Room: H 1012, Talk 1

Dominikus Noll
Non-convex bundle algorithm with inexact sub-gradient and function values


We discuss a non-convex bundle method where function values and subgradients
are available only up to an error ε, which remains
unknown to the user. We show that even in that situation one can still
assure (under practical hypotheses) that every accumulation point x*
of the sequence xj of serious iterates is approximate critical
in the sense that

0 ∈ \partial f(x*) + δ(ε) B,

where B is the unit ball, and where the final precision δ(ε) depends on
the error precision ε of function and subgradient values. In the realm of convex
bundling results of this flavor have been pioneered by Hinterm├╝ller
and Kiwiel. The principal new difficulty in non-convex bundling it to
provide a substrate for the convex cutting plane mechanism, and this problem
was solved by the author for a large class of problems including all
instances of practical interest. Here we discuss the more specific case of
downshifted tangents, an oracle which we used successfully in a variety of
applications in automatic control.



Friday, 13:45 - 14:10 h, Room: H 1012, Talk 2

Frank Fischer
An asynchronous parallel bundle method for Lagrangian relaxation

Coauthor: Christoph Helmberg


Lagrangian relaxation is frequently used for decomposing discrete optimization problems and the standard parallel approach would solve the subproblems in parallel. Here we propose a different approach that optimizes, asynchronously in parallel, subspaces of multipliers that are selected dynamically. The algorithm starts several parallel processes and in a kind of parallel coordinated descent each process selects a subspace with large predicted decrease. Then each process optimizes the associated multipliers independently until a certain improvement level has been achieved and writes its solution back to the global data. Because this improvement may lead to increased violation of other constraints, the algorithm automatically detects and tracks these dependencies and respects them in future subspace selections ensuring global convergence. Preliminary computational results show that the presented approach may be turned into a viable alternative for applications of practical relevance.


  personal loan . This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.