Hochbaum
Le
14 Novembre 2001 à 14h30
au LRI,
Salle 101
(Haas School of Business and Department of IE&OR, University of California,
Berkeley)
Efficient convex optimization algorithms for inverse problems
Résumé/Abstract :
Inverse problems span a wide variety of applications. These vary
from error detection and correction problems to tomography, to
identifying geophysical structures, to statistical estimation
with priors, to politics and economic utility theory (and revealed
preferences). The elements of a generic problem include a
feasible solution, estimated (or guessed) model parameters and
certain underlying physical rules or optimality conditions that
the solution should satisfy. The problem is to modify the
model's parameters so that the solution will obey the rules (for
inverse problems) or optimality conditions (for inverse
optimization). The generic problem's objective function is
convex separable representing penalties for deviation from
obeying underlying physical rules and from the given priors.
We present a sample of inverse problems in four categories along with
the key technical tool applied in each case that leads to polynomial
time algorithms.
1. Statistical inference subject to order restrictions and the use of
threshold theorem
2. Image segmentation and error correction and the use of threshold theorem
and convex dual of minimum cost network flow
3. Inverse minimum spanning tree and the use of threshold and reformulation
4. Inverse shortest paths and the use of a projected proximity theorem
in a proximity-scaling setup.
The discussion will focus on the particular challenges that arise
when studying the complexity of nonlinear optimization problems.