Research Seminar

Solving complex optimization problems with many parameters by means of optimally designed block-relaxation algorithms


Tom Wilderjans


KU Leuven

Abstract: Many data analysis problems involve the optimization of a criterion that is a function of many parameters, with these parameters being continuous, discrete, or a combination of both. To deal with such optimization problems, the class of block-relaxation algorithms (with alternating least squares algorithms being a specific instance of this class) may be most useful. The rationale behind the algorithms in this class is that the complex optimization problem is solved by alternatingly tackling a series of subproblems, each of which, considered separately, is easy to handle. For this purpose, the set of parameters is divided into a number of subsets, in such a way that the optimal values for the parameters in each subset (conditional on the current estimates of the parameters in all other subsets) can be determined easily (e.g., in terms of closed-form expressions). The algorithm then cycles through the different subsets and updates the parameters in each subset until there is no further improvement in the loss function value. When designing a block-relaxation algorithm, two choices need to be made, which may influence the performance of the algorithm: (1) the way in which the parameters are divided in subsets, and (2) the order in which the parameter subsets are updated.

In this presentation, based on theoretical and empirical arguments, guidelines for optimally designing block-relaxation algorithms will be derived. As an illustration, these guidelines will be applied to the estimation of the INDCLUS model (i.e., a mixed discrete-continuous optimization problem). Different alternating least-squares algorithms for fitting the INDCLUS model will be proposed and compared to each other in an extensive simulation study. The simulation results support the derived guidelines. In particular, it is advisable to group together parameters that highly depend on each other. Furthermore, in cases in which such a grouping is not fully possible, it is preferable when a set of parameters has been updated, to re-estimate as fast as possible other sets of parameters that are highly dependent on the first.
Date: Tue Mar 8, 12:15 pm - 1:15 pm
Place: room 02.60 (Department of Psychology, Tiensestraat 102, 3000 Leuven)