Change search
ReferencesLink to record
Permanent link

Direct link
Convex Optimization for Assignment and Generalized Linear Regression Problems
KTH, School of Electrical Engineering (EES), Signal Processing.
2014 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

This thesis considers optimization techniques with applications in assignment and generalized linear regression problems. The first part of the thesis investigates the worst-case robust counterparts of combinatorial optimization problems with least squares (LS) cost functions, where the uncertainty lies on the linear transformation of the design variables. We consider the case of ellipsoidal uncertainty, and prove that the worst case robust LS optimization problem, although NP-hard, is still amenable to convexrelaxation based on semidefinite optimization. We motivate our proposed relaxation using Lagrangian duality, and illustrate that the tightness of the Lagrange bidual relaxation is strongly dependent on the description of the feasible region of the worst-case robust LS problem. The results arising from this analysis are applicable to a broad range of assignment problems.

The second part of the thesis considers combinatorial optimization problems arising specifically in the context of conference program formation. We start by arguing that both papers and reviewers can be represented as feature vectors in a suitable keyword space. This enables rigorous mathematical formulation of the conference formation process. The first problem, paper-to-session assignment, is formulated as a capacitatedk-means clustering problem. We formally prove that it is NP-hard and propose a variety of approximate solutions, ranging from alternating optimization to semidefinite relaxation. Suitable convex relaxation methods are proposed for the paper-to-reviewer assignment problem as well. Our methods are tested using real conference data for both problems, and show very promising results.

In a related but distinct research direction, the third part of the thesis focuses on preference measurement applications: Review profiling, i.e., determining the reviewer’s expertise (and thus identifying the associated feature vector for the reviewer) on the basis of their past and present review preferences, or ‘bids’, is an excellent example of preference measurement. We argue that the need for robust preference measurement is apparent in modern applications. Using conjoint analysis (CA) as a basis, we propose a new statistical model for choice-based preference measurement, a part of preference analysis where data are only expressed in the form of binary choices. The model uses deterministic auxiliary variables to account for outliers and to detect the salient features that influence decisions. Contributions include conditions for statistical identifiability, derivation of the pertinent Cramér-Rao Lower Bound (CRLB), and ML consistency conditions for the proposed nonlinear model. The proposed ML approach lends itself naturally to ℓ1-type convex relaxations which are well-suited for distributed implementation, based on the alternating direction method of multipliers (ADMM). A particular decomposition is advocated which bypasses the apparent need for outlier variable communication, thus maintaining scalability.

In the last part of the thesis we argue that this modeling has greater intellectual merits than preference measurement, and explain how related ideas can be put in the context of generalized linear regression models, drawing links between ℓ1-methods, stochastic convex optimization, and the field of robust statistics.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. , vii, 140 p.
TRITA-EE, ISSN 1653-5146
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-150338ISBN: 978-91--7595-236-9OAI: diva2:742429
Public defence
2014-09-19, Kollegiesalen, Brinellvägen 8, KTH, Stockholm, 14:00 (English)

QC 20140902

Available from: 2014-09-02 Created: 2014-09-01 Last updated: 2014-09-02Bibliographically approved

Open Access in DiVA

Thesis(2408 kB)515 downloads
File information
File name FULLTEXT01.pdfFile size 2408 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Tsakonas, Efthymios
By organisation
Signal Processing
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 515 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 745 hits
ReferencesLink to record
Permanent link

Direct link