Mixed-Integer Nonconvex Quadratic Optimization Relaxations and Performance Analysis

Abstract

The project addresses a fundamental question regarding the mixed integer quadratic programs (MIQP): how to find a provably high quality approximate solution efficiently? Given the nonconvex nature of the problem, two relaxation approaches are considered: one is based on convex semidefinite relaxation (SDR), while the other is based on quasic on quasi-convex relaxations. For SDR, a new probabilistic rounding procedure is proposed to account for both the binary and continuous variables. The performance of this rounding procedure is shown to deliver a constant factor approximation ratio for a class of the mixed integer quadratic optimization problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 14, 2015
Accession Number
AD1032104

Entities

People

  • Zhi-quan Luo

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Air Force Research Laboratories
  • Algorithms
  • Classification
  • Computational Complexity
  • Contracts
  • Electronic Mail
  • Intellectual Property
  • Mathematical Programming
  • Micro Air Vehicles
  • Nonlinear Programming
  • Numbers
  • Optimization
  • Patents
  • Resource Management
  • Scientific Research
  • Semidefinite Programming

Readers

  • Operations Research