Zeit: 22.10.2007, 18:00

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

D.di Serafino (2a Univ.Napoli): Effective solution of the KKT system for effective large-scale optimization

The solution of the KKT system is often the most demanding task in optimization methods, especially when large-scale problems are considered. Thus, the effective use of such methods is highly dependent on the availability of efficient and reliable linear algebra solvers, able to combine modern linear algebra techniques with specific needs of optimization. This talk addresses key issues in the solution of the KKT system, focusing on the application of iterative solvers in the context of interior point methods for large-scale problems.

Joint work with: S. Cafieri, M. D'Apuzzo, V. De Simone, G. Toraldo

Zeit: 05.11.2007, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

J. Povh (Univ.Maribor): On approximations of hard combinatorial problems by semidefinite and copositive programming

Several NP hard combinatorial problems can be rewritten as linear programs over the cone of copositive or completely positive matrices. This opens new possibilities how to approximate the optimal values of these problems. We demonstrate this procedure for the quadratic assignment problem and the graph partitioning problem. We show that semidefinite lower bounds, which follow from semidefinite approximations of the cone of copositive or completely positive matrices, are significantly better then the existing eigenvalue lower bounds and are also at least as tight as other known semidefinite lower bounds.

Zeit: 19.11.2007, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

R. Beran (UC Davis): Regularized Regression: A Minimalist's Approach to Fitting and Extrapolating a Discrete Incomplete Multi-way Layout

The discrete multi-way layout is an abstract data-type associated with regression, experimental designs, digital images or videos, spatial statistics, gene or protein chips, and more. The factors influencing response can be nominal or ordinal. The observed factor level combinations
are finitely discrete and often incomplete or irregularly spaced. This paper develops low risk, biased estimators of the means at the observed factor level combinations; and extrapolates the estimated means to larger discrete complete layouts. Candidate penalized least squares (PLS)
estimators with multiple quadratic penalties express competing conjectures about each of the main effects and interactions in the ANOVA decomposition of the means. The candidate PLS estimator with smallest estimated quadratic risk attains, asymptotically, the smallest risk over all candidate PLS estimators. In the theoretical analysis, the dimension of the regression space tends to infinity. No assumptions are made about the unknown means or about replication.

Zeit: 26.11.2007, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

J. Lozano (Euskal Uni.San Seb.): Optimization by Means of Probabilistic Graphical Models

Probabilistic graphical models are powerful techniques in the field of probabilistic modeling. They simplify the codification of probability distributions by using the conditional (in)dependencies of the domain knowledge. Many algorithms have been developed in this field to carry out inference tasks and to learn the models from data.

In this talk two different ways of using probabilistic graphical models in optimization will be shown. On the one hand we will see how additive decomposable functions can be optimized by means of belief propagation algorithms in loopy graphs. The second approach to optimization is called Estimation of Distribution Algorithms. This is a set of algorithms inside the Evolutionary Computation field. They are characterized by the substitution of the reproductive operators of Genetic Algorithms by the learning and posterior sampling of a probability distribution. This probability distribution is codified by means of probabilistic graphical models in most cases.

Application examples will also be shown and some theoretical properties will be reviewed for both approaches.

Zeit: 03.12.2007, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

D. Filipovic (Univ.Wien): Non-monotone risk measures and monotone hulls

Using convex duality we characterize monotonicity and cash-invariance properties of convex risk measures. As a main result, for any risk measure f, we find its monotone and cash-invariant hull, that is, the greatest closed convex monotone and cash-invariant function majorized by f. We then apply our results to some well-known risk measures and problems arising in connection with insurance regulation.

This talk is based on two papers:

Monotone and Cash-Invariant Convex Functions and Hulls (with Michael Kupper), Insurance: Mathematics and Economics 41, 1-16, 2007

A Note on the Swiss Solvency Test Risk Measure (with Nicolas Vogelpoth), forthcoming in Insurance: Mathematics and Economics

Zeit: 14.01.2008, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

A. Munk (Univ. Göttingen): Jumps and inverse jumps

We study the asymptotics for jump-penalized least squares regression aiming at approximating a regression function by piecewise constant functions. Besides conventional consistency and convergence rates of the estimates in L^2([0,1]) our results cover other metrics like Skorokhod metric on the space of cądląg functions and uniform metrics on C([0,1]) as well as convergence of the scale spaces, the family of estimates under varying smoothing parameter.

We will show that the estimates used are in an adaptive sense rate optimal over a scale of approximation spaces. Our penalty is an l_0 penalty which typically leads to an optimization problem which cannot be computed in polynomial time. The present situation is different, however, and we discuss a dynamic program which allows to computes the LSE in O(n^2) steps. It turns out, that for data of size of a few thousands this is sufficent on a PC, for data sets of larger size this is still a severe burden.

To overcome this problem we combine this with a forward search algorithm, which allows to handle several millions observations. Our method is illustrated with the reconstruction of ion channel activity measured from impedance tomography. To select the proper number of jumps this is combined with a statistical multiscale analysis in order to estimate the number of jumps. Finally we address the situation of noisy inverse problems, where we focus on Hammerstein integral equations.

Zeit: 15.01.2008, 15:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

G. Eichfelder (Univ.Erlangen): Set-semidefinite optimization

In this talk set-semidefinite optimization is introduced as a new field of vector optimization in infinite dimensions. We study vector-valued optimization problems having an inequality constraint with a special partial order in the space of linear maps. This order considers quadratic forms being non-negative on a set K. In finite dimensions one obtains for K=R^n semidefinite and for K=R^n_+ copositive optimization problems.

For the associated ordering cone, the so-called K-semidefinite cone, calculation rules, characterizations, and results on the dual and on the interior are given. For K-semidefinite optimization problems optimality conditions, duality results and a penalty approach are presented.

Zeit: 21.01.2008, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

J. Judice (Univ.Coimbra): The eigenvalue complementarity problem

The Eigenvalue Complementarity Problem (EiCP) is discussed, which arises on a directional instability problem in systems with frictional contact. A few nonlinear programming formulations are introduced for the symmetric EiCP, that is, when the matrices of the problem are both symmetric, such that stationary points of the corresponding objective functions on appropriate convex sets lead to solutions of the problem. In the nonsymmetric case, it is shown that the EiCP reduces to a Mathematical Programming Problem with Linear Complementarity Constraints.

Necessary and sufficient conditions for the existence of a solution to the EiCP are discussed. A spectral projected gradient method and an enumerative algorithm are introduced for finding a solution to the symmetric and nonsymmetric EiCPs respectively. Computational experience is reported to illustrate the efficiency of the algorithms to deal with these two cases.

Zeit: 28.01.2008, 16:30

Ort: Leopold-Schmetterer-Seminarraum, 1010 Wien, Univ.str. 5/3.Stock

A. Albrecht (Univ. Herts.): Combinatorial Landscape Analysis for Search-Based Algorithms

Over the past fifteen years or so, landscape analysis has become a vital tool in tackling computationally demanding optimization problems from diverse areas of Science and Technology. The concept of fitness landscapes originated in the 1930s in Theoretical Biology as a notion for the dynamics of evolution. Despite its long history, the concept of fitness landscapes was over many years mainly used in a passive way for descriptorial purposes only, such as the definition of local and global optima, of neighbourhood relations and mutation/crossover operations in local search-based algorithms. Since the late 1990s, one can observe intensified efforts to incorporate landscape properties into the design of efficient optimization algorithms with proven convergence properties. We present an overview on recent developments in combinatorial landscape analysis, with focus on Combinatorial Optimization, Computational Biology, and Communication Technology, including methods from Statistical Mechanics applied to prominent optimization problems.

© 2004 by Daniel Bomze