Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Partial Lagrangian relaxation for general quadratic programming

Partial Lagrangian relaxation for general quadratic programming We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png 4OR Springer Journals

Partial Lagrangian relaxation for general quadratic programming

Faye, Alain; Roupin, Frédéric
4OR , Volume 5 (1) – Jul 21, 2006
Download PDF
14 pages

Loading next page...
 
/lp/springer-journals/partial-lagrangian-relaxation-for-general-quadratic-programming-geHjqSETON
Publisher
Springer Journals
Copyright
Copyright © 2006 by Springer-Verlag
Subject
Business and Management; Operation Research/Decision Theory; Optimization; Industrial and Production Engineering
ISSN
1619-4500
eISSN
1614-2411
DOI
10.1007/s10288-006-0011-7
Publisher site
See Article on Publisher Site

Abstract

We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.

Journal

4OR – Springer Journals

Published: Jul 21, 2006

References

  • A tight linearization and an algorithm for zero-one quadratic progamming problems
    Adams, WP; Sherali, HD
  • Different formulations for solving the heaviest k-subgraph problem
    Billionnet, A
  • A semidefinite approach to the Quadratic Knapsack Problem
    Helmberg, C; Rendl, F; Weismantel, R
  • A comparison of the Sherali-Adams, Lovasz-Schrijver, and Lasserre relaxations for 0–1 programming
    Laurent, M
  • The omnipresence of Lagrange
    Lemaréchal, C
  • Advances in convex analysis and global optim.
    Lemaréchal, C; Oustry, F
  • Cones of matrices and set-functions and 0–1 optimization
    Lovász, L; Schrijver, A
  • Linear and nonlinear programming
    Luenberger, DG
  • The mathematics of nonlinear programming
    Peressini, AL; Sullivan, FE; Uhl, JJ
  • A recipe for semidefinite relaxations for (0,1)-quadratic programming
    Poljak, S; Rendl, F; Wolkowicz, H
  • From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
    Roupin, F