Seminar: Alternating Maximization: Unifying Framework for 8 Sparse PCA Formulations
2013-05-16 14:00 UTC
Title: Alternating Maximization: Unifying Framework for 8 Sparse PCA FormulationsSpeaker: Dr. Selin AhipasaogluAffiliation: Singapore University of Technology and DesignLocation: CPSE seminar room (C615 Roderic Hill)Time: 2:00pm
Abstract. Given a multivariate data set, sparse principal component analysis (SPCA) aims to extract several linear combinations of the variables that together explain the variance in the data as much as possible, while controlling the number of nonzero loadings in these combinations. In this paper we consider 8 different optimization formulations for computing a single sparse loading vector; these are obtained by combining the following factors: we employ two norms for measuring variance (L2, L1) and two sparsity-inducing norms (L0, L1), which are used in two different ways (constraint, penalty). Three of our formulations, notably the one with L0 constraint and L1 variance, have not been considered in the literature. We give a unifying reformulation which we propose to solve via a natural alternating maximization (AM) method. Besides this, we provide a package which contains implementations for various parallel architectures and briefly discuss how these algorithms can be used to achieve better object recognition in challenging data sets.
About the speaker. Selin Damla Ahipasaoglu is an Assistant Professor at the Singapore University of Technology and Design. She received her PhD in 2009 from Cornell University and specialises in developing algorithms for large scale optimization problems, in particular first-order methods for convex problems and applications in image processing. She held research positions at Princeton University and London School of Economics before joining SUTD. She is also a very keen teacher and an advocate of active and innovative classroom teaching for undergraduates.

Seminar: Hard-to-Solve Bimatrix Games
2013-05-22 14:00
Title: Hard-to-Solve Bimatrix GamesSpeaker: Prof. Bernhard von StengelAffiliation: Depatment of Mathematics – London School of Economics and Political ScienceLocation: CPSE seminar room (C615 Roderic Hill)Time: 2:00pm
Abstract. A bimatrix game is a two-player game in strategic form, a basic model in game theory. A Nash equilibrium is a pair of (possibly randomized) strategies, one for each player, so that no player can do better by unilaterally changing his or her strategy. In this talk, which will introduce the main concepts and geometric tools, we show that the commonly used Lemke-Howson algorithm for finding one equilibrium of a bimatrix game is exponential. The algorithm is a pivoting method similar to the simplex algorithm for linear programming. We present a class of square bimatrix games for which the shortest Lemke-Howson path grows exponentially in the dimension d of the game. We construct the games using pairs of dual cyclic polytopes with 2d facets in d-space. The paths are recursively composed so that their lengths grow like Fibonacci numbers. We also mention subsequent results and open problems in the area.
About the speaker. Diploma in Mathematics from Aachen, MSc in Computer Sciences at Austin/Texas (student of Edsger W. Dijkstra), PhD in Passau, Habilitation in Munich, Postdoc at Berkeley, Tilburg and ETH Zurich (with a Heisenberg grant), at LSE Mathematics since 1998. Interested in algorithmic game theory longer than the research area has that name.

Seminar: CVaR Approximations for Minimax and Robust Convex Optimization
2013-05-28 14:00
Title: CVaR Approximations for Minimax and Robust Convex OptimizationSpeaker: Prof. Huifu XuAffiliation: School of Engineering and Mathematical Sciences at City University of LondonLocation: Room 218 Huxley BuildingTime: 2:00pm
Abstract. Conditional value at risk (CVaR) has been widely used as a risk measure in finance. In this work, we propose to randomize decision variables of a deterministic parametric maximization problem and approximate the optimal (maximum) value by the CVaR of the randomized function. One of the main advantages of this approach is that computing CVaR is down to solving a one dimensional convex optimization problem even when the original problem is multi-dimensional and nonconvex. We apply the approximation scheme to a minimax (robust) optimization problem and a convex optimization problem with semi-infinite constraints indexed by uncertain parameters. In the latter application we use CVaR to approximate the semi-infinite constraint and then apply the Monte Carlo sampling method to discretize the CVaR approximated constraint. This approach is closely related to a popular randomization approach proposed by Calafiore and Campi where the continuum of uncertainty parameters is discretized through sampling. Error bounds for the optimal solutions of the approximate problems are derived under some moderate conditions and some numerical test results are reported. The proposed methods can be applied to distributional optimization where the distribution set is constructed through moments.
About the speaker. Huifu Xu is a Professor of Operational Research in the School of Engineering and Mathematical Sciences at City University of London. Before joining City University, he was a Senior Lecturer of Operational Research in the School of Mathematics at the University of Southampton. His expertise is in continuous optimization and operational research, including developing numerical methods and underlying theory for continuous optimization problems, particularly those involving uncertain data and/or equilibrium constraints. Over the past ten years, he has been actively working on stochastic mathematical programs with equilibrium problems and is recently developing interest in robust approaches for stochastic optimization and equilibrium problems. Huifu has published about 60 papers most of which are in the international journals of optimization and operational research.
