The many faces of positivity to approximate structured optimization problems

Olga Kuryatnikova

Research output: ThesisDoctoral ThesisScientific

23 Downloads (Pure)

Abstract

The PhD dissertation proposes tractable linear and semidefinite relaxations for optimization problems that are hard to solve and approximate, such as polynomial or copositive problems. To do this, we exploit the structure and inherent symmetry of these problems. The thesis consists of five essays devoted to distinct problems. First, we consider the kissing number problem. The kissing number is the maximum number of non-overlapping unit spheres that can simultaneously touch another unit sphere, in n-dimensional space. In chapter two we construct a new hierarchy of upper bounds on the kissing number. To implement the hierarchy, in chapter three we propose two generalizations of Schoenberg's theorem on positive definite kernels. In the fourth chapter, we derive new certificates of non-negativity of polynomials on generic sets defined by polynomial equalities and inequalities. These certificates are based on copositive polynomials and allow obtaining new upper and lower bounds for polynomial optimization problems. In chapter five, for any given graph we look for the largest k-colorable subgraph; that is, the induced subgraph that can be colored in k colors such that no two adjacent vertices have the same color. We obtain several new semidefinite programming relaxations to this problem. In the final sixth chapter, we consider the problem of allocating tasks to unrelated parallel selfish machines to minimize the time to complete all the tasks. For this problem, we suggest new upper and lower bounds on the best approximation ratio of a class of truthful task allocation algorithms.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • Sotirov, Renata, Promotor
  • Vera Lizcano, Juan, Co-promotor
  • Zuluaga, Luis F., Co-promotor, External person
Award date20 Sep 2019
Place of PublicationTilburg
Publisher
Print ISBNs978 90 5668 603 1
Publication statusPublished - 2019

Fingerprint

Positivity
Optimization Problem
Polynomial
Certificate
Unit Sphere
Upper and Lower Bounds
Positive Definite Kernels
Semidefinite Programming Relaxation
Semidefinite Relaxation
Linear Relaxation
Task Allocation
Nonnegativity
Induced Subgraph
Best Approximation
n-dimensional
Subgraph
Equality
Adjacent
Upper bound
Distinct

Cite this

Kuryatnikova, O. (2019). The many faces of positivity to approximate structured optimization problems. Tilburg: CentER, Center for Economic Research.
Kuryatnikova, Olga. / The many faces of positivity to approximate structured optimization problems. Tilburg : CentER, Center for Economic Research, 2019. 186 p.
@phdthesis{6c6ab29aa41c492a84dc76b827684025,
title = "The many faces of positivity to approximate structured optimization problems",
abstract = "The PhD dissertation proposes tractable linear and semidefinite relaxations for optimization problems that are hard to solve and approximate, such as polynomial or copositive problems. To do this, we exploit the structure and inherent symmetry of these problems. The thesis consists of five essays devoted to distinct problems. First, we consider the kissing number problem. The kissing number is the maximum number of non-overlapping unit spheres that can simultaneously touch another unit sphere, in n-dimensional space. In chapter two we construct a new hierarchy of upper bounds on the kissing number. To implement the hierarchy, in chapter three we propose two generalizations of Schoenberg's theorem on positive definite kernels. In the fourth chapter, we derive new certificates of non-negativity of polynomials on generic sets defined by polynomial equalities and inequalities. These certificates are based on copositive polynomials and allow obtaining new upper and lower bounds for polynomial optimization problems. In chapter five, for any given graph we look for the largest k-colorable subgraph; that is, the induced subgraph that can be colored in k colors such that no two adjacent vertices have the same color. We obtain several new semidefinite programming relaxations to this problem. In the final sixth chapter, we consider the problem of allocating tasks to unrelated parallel selfish machines to minimize the time to complete all the tasks. For this problem, we suggest new upper and lower bounds on the best approximation ratio of a class of truthful task allocation algorithms.",
author = "Olga Kuryatnikova",
note = "CentER Dissertation Series Volume: 602",
year = "2019",
language = "English",
isbn = "978 90 5668 603 1",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

Kuryatnikova, O 2019, 'The many faces of positivity to approximate structured optimization problems', Doctor of Philosophy, Tilburg University, Tilburg.

The many faces of positivity to approximate structured optimization problems. / Kuryatnikova, Olga.

Tilburg : CentER, Center for Economic Research, 2019. 186 p.

Research output: ThesisDoctoral ThesisScientific

TY - THES

T1 - The many faces of positivity to approximate structured optimization problems

AU - Kuryatnikova, Olga

N1 - CentER Dissertation Series Volume: 602

PY - 2019

Y1 - 2019

N2 - The PhD dissertation proposes tractable linear and semidefinite relaxations for optimization problems that are hard to solve and approximate, such as polynomial or copositive problems. To do this, we exploit the structure and inherent symmetry of these problems. The thesis consists of five essays devoted to distinct problems. First, we consider the kissing number problem. The kissing number is the maximum number of non-overlapping unit spheres that can simultaneously touch another unit sphere, in n-dimensional space. In chapter two we construct a new hierarchy of upper bounds on the kissing number. To implement the hierarchy, in chapter three we propose two generalizations of Schoenberg's theorem on positive definite kernels. In the fourth chapter, we derive new certificates of non-negativity of polynomials on generic sets defined by polynomial equalities and inequalities. These certificates are based on copositive polynomials and allow obtaining new upper and lower bounds for polynomial optimization problems. In chapter five, for any given graph we look for the largest k-colorable subgraph; that is, the induced subgraph that can be colored in k colors such that no two adjacent vertices have the same color. We obtain several new semidefinite programming relaxations to this problem. In the final sixth chapter, we consider the problem of allocating tasks to unrelated parallel selfish machines to minimize the time to complete all the tasks. For this problem, we suggest new upper and lower bounds on the best approximation ratio of a class of truthful task allocation algorithms.

AB - The PhD dissertation proposes tractable linear and semidefinite relaxations for optimization problems that are hard to solve and approximate, such as polynomial or copositive problems. To do this, we exploit the structure and inherent symmetry of these problems. The thesis consists of five essays devoted to distinct problems. First, we consider the kissing number problem. The kissing number is the maximum number of non-overlapping unit spheres that can simultaneously touch another unit sphere, in n-dimensional space. In chapter two we construct a new hierarchy of upper bounds on the kissing number. To implement the hierarchy, in chapter three we propose two generalizations of Schoenberg's theorem on positive definite kernels. In the fourth chapter, we derive new certificates of non-negativity of polynomials on generic sets defined by polynomial equalities and inequalities. These certificates are based on copositive polynomials and allow obtaining new upper and lower bounds for polynomial optimization problems. In chapter five, for any given graph we look for the largest k-colorable subgraph; that is, the induced subgraph that can be colored in k colors such that no two adjacent vertices have the same color. We obtain several new semidefinite programming relaxations to this problem. In the final sixth chapter, we consider the problem of allocating tasks to unrelated parallel selfish machines to minimize the time to complete all the tasks. For this problem, we suggest new upper and lower bounds on the best approximation ratio of a class of truthful task allocation algorithms.

M3 - Doctoral Thesis

SN - 978 90 5668 603 1

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Kuryatnikova O. The many faces of positivity to approximate structured optimization problems. Tilburg: CentER, Center for Economic Research, 2019. 186 p. (CentER Dissertation Series).