Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
TRITA-EE, ISSN 1653-5146
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-150338ISBN: 978-91--7595-236-9 OAI: oai:DiVA.org:kth-150338DiVA: diva2:742429
Public defence
2014-09-19, Kollegiesalen, Brinellvägen 8, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20140902

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

Open Access in DiVA

Thesis(2408 kB)673 downloads
File information
File name FULLTEXT01.pdfFile size 2408 kBChecksum SHA-512
89bab7217978d4e58894a76d9735c2ecdb74c53b479533c99fa67995382b315b1da6089ace88c67231d486244201c8499df733cdabe4b2e49107c1b36443e7f1
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: 673 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 834 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf