Return to the institutional site
    • español
    • English
View Item 
  •   Séneca Home
  • TRABAJOS DE GRADO
  • Maestría
  • View Item
    • español
    • English
  •   Séneca Home
  • TRABAJOS DE GRADO
  • Maestría
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

All of SénecaCommunities and CollectionsFaculties and ProgramsAuthorsTitlesSubjectsTypes of contentsAuthor profilesThis CollectionFaculties and ProgramsAuthorsTitlesSubjectsTypes of contents

My Account

LoginRegister

Statistics

View Usage Statistics

Information of interest

What is SénecaHow publishGuidelinesContact us

Semidefinite relaxations for copositive optimization

RISMendeley
URI: http://hdl.handle.net/1992/13572
Author: Camelo Gómez, Sergio Armando
Director(s)/Advisor(s): Velasco Gregory, Mauricio Fernando; Peña Briceño, Javier Francisco; Junca Peláez, Mauricio JoséUniandes authority
Content type: masterThesis
Keywords:
Optimización matemática - Investigaciones
Teoría de grafos - Investigaciones
Abstract:
Linear optimization over the copositive cone C*, (i.e. the cone of quadratic forms which are nonnegative on the positive orthant) has applications in polynomial optimization, graph theory and data analysis. Although convex, this problem is unfortunately not tractable. In this work we study two nested sequences of spectrahedral cones that approximate C*. One formulated by Barvinok, Veomett and Laserre {BVLn}n?N and the other proposed by Parrilo {SOSn}n?N. Since these approximations are one from above and one from below, they can be used to cal- culate upper and lower bounds on the solution of copositive programs efficiently. This proves particularly useful in bounding the independence number of a graph ?(G). In this case, the fact that ?(G) is an integer means the lower and upper bounds need not meet to find the optimal value of the problem. This work is divided in four parts, first, we give a comprehensive description of the geometry of the copositive cone, second, we describe its semidefinite approximations, third, we survey the applications of copositive programming, fourth, we give new results on the BVL hierarchy when applied to calculating lower bounds of ?(G), propose an algorithm for obtaining large independence sets on G, and evaluate its empirical performance on Hamming and DeBruijn graphs
Show full item record

Files in this item

Thumbnail
Name:
u728559.pdf
Size:
478.1Kb
Format:
PDF

Statistics

View Usage Statistics
Donaciones

Los Andes

Donaciones


Icono Repositorio

Los Andes

Repositorio


Icono Egresados

Los Andes

Egresados


Icono Eventos

Los Andes

Eventos



Cra 1 Nº 18A - 12

Bogotá - Colombia

Postal code: 111711

+(571) 339 49 99

+(571) 339 49 49


Normatividad Institucional

  • Actos internos e incremento
  • Bienestar
  • Derechos pecunarios
  • Estatuto docente
  • Estatuto general
  • Ley de transparencia
  • Porcentaje de incremento
  • Reglamentos de estudiantes
  • Uso de datos personales

Enlaces Rápidos

  • ATC (Acceso Temporal al Campus)
  • Universidad de los Andes Caribe
  • Convivencia y transparencia
  • Educación Continuada
  • Emergencias: Extensión 0000
  • Nuestros profesores
  • Mapa del sitio
  • Multimedia
  • Noticias
  • Preguntas frecuentes

Redes sociales

  • Facebook
  • twitter
  • youtube
  • linkedin
  • instagram
  • snapchat
  • vimeo
  • google

Directorio de redes