Nonconvex quadratic problems and games with separable constraints

Zazo Ruiz, Javier (2017). Nonconvex quadratic problems and games with separable constraints. Tesis (Doctoral), E.T.S.I. Telecomunicación (UPM).


Título: Nonconvex quadratic problems and games with separable constraints
  • Zazo Ruiz, Javier
  • Zazo Bello, Santiago
Tipo de Documento: Tesis (Doctoral)
Fecha: 26 Julio 2017
Palabras Clave Informales: Nonconvex quadratic optimization
Escuela: E.T.S.I. Telecomunicación (UPM)
Departamento: Señales, Sistemas y Radiocomunicaciones
Grupo Investigación UPM: Aplicaciones del Procesado de Señal GAPS
Licencias Creative Commons: Reconocimiento

Texto completo

Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa


Quadratic programs are generally hard and difficult to solve, where many instances are known to be NP-hard. However, there are some few cases in which the quadratic problem has some hidden convexity and there are methods to solve the problems optimally in polynomial time. When this occurs, we say that strong duality holds, and that the primal problem has zero gap with its dual counterpart. We study this property in nonconvex quadratic problems with separable constraints. We exploit the disjoint structure of the constraints to analyze when strong duality may occur. We consider problems that may have both inequality or equality quadratic constraints, and we provide sufficient conditions that guarantee zero duality gap. Our results consider any number of constraints as long as they do not overlap between each other. In addition to these results, we propose two distributed algorithms that aim to solve the quadratic problem optimally whenever the strong duality holds. The first proposal uses a dual formulation and convergence relies on gradient or subgradient methods, depending on the nature of the problem. The second proposal uses a modern decomposition technique from the literature called NOVA and uses successive convex approximations to converge to the optimal solution, which is generally considered faster than first order methods. We then study two localization problems with ranged measurements. We reformulate them as nonconvex quadratic problems with quadratic constraints and explore their solutions. We refer to the first one as target localization and propose several distributed methods based on primal descent as well as dual ascent methods. On the one hand, descent methods assume the nonconvexity of the localization problem and may converge to local solutions if the number of measuring nodes is small. They are however fast and require little communication. On the other hand, dual ascent methods aim to solve the localization problem optimally assuming that there is zero duality gap between the primal and dual problem. The second localization problem we consider is the sensor network localization problem in which a set of nodes try to locate themselves having distance measurements between each other. This is a harder problem, and as before, we propose both distributed methods based on descent techniques as well as based in a dual decomposition. Finally, we also study the connection of nonconvex quadratic optimization with Nash equilibria in game theory. In order to do so, we propose a robust demand-side management problem in a smart grid, where the agents try to minimize their monetary expenditure. Because there is uncertainty in the real-time energy demand, the cost of energy is prone to variations and a robust model that attends to a worst-case scenario is proposed. This formulation is presented as a min-max game where the maximization game is nonconvex and where the agents have coupled constraints. We study this game and propose a distributed scheme with convergence guarantees to the NE of the game. We also study the game model under a real-time energy market where prices have been set on a day-ahead robust optimization.

Más información

ID de Registro: 47855
Identificador DC:
Identificador OAI:
Identificador DOI: 10.20868/UPM.thesis.47855
Depositado por: Javier Zazo
Depositado el: 04 Oct 2017 10:43
Ultima Modificación: 04 Abr 2018 22:30
  • InvestigaM
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM