TITLE

Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

AUTHOR(S)
Xia, Yong
PUB. DATE
September 2011
SOURCE
Acta Mathematica Sinica;Sep2011, Vol. 27 Issue 9, p1803
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.
ACCESSION #
64458769

 

Related Articles

  • A polynomial case of unconstrained zero-one quadratic optimization. Allemand, Kim; Fukuda, Komei; Liebling, Thomas M.; Steiner, Erich // Mathematical Programming;2001, Vol. 91 Issue 1, p49 

    Unconstrained zero-one quadratic maximization problems can be solved in polynomial time when the symmetric matrix describing the objective function is positive semidefinite of fixed rank with known spectral decomposition.

  • MAPPING THE CONVERGENCE OF GENETIC ALGORITHMS. Drezner, Zvi; Marcoulides, George A. // Journal of Applied Mathematics & Decision Sciences;2006, Vol. 2006 Issue 4, p1 

    This paper examines the convergence of genetic algorithms using a cluster-analytic-type procedure. The procedure is illustrated with a hybrid genetic algorithm applied to the quadratic assignment problem. Results provide valuable insight into how population members are selected as the number of...

  • Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. Peng, Jiming; Zhu, Tao; Luo, Hezhi; Toh, Kim-Chuan // Computational Optimization & Applications;Jan2015, Vol. 60 Issue 1, p171 

    Quadratic assignment problems (QAPs) are known to be among the most challenging discrete optimization problems. Recently, a new class of semi-definite relaxation models for QAPs based on matrix splitting has been proposed (Mittelmann and Peng, SIAM J Optim 20:3408-3426, ; Peng et al., Math...

  • Practical ABC intelligence solution for Quadratic Assignment. Behzadi, Golnar; Sundarakani, Balan // Proceedings of the International Conference on Industrial Engine;2014, p959 

    One of the key challenges in the scope of NP-hard problems is associated with finding a suitable solution algorithm as a result of degrees of complexity integrated in such problems. Among that, Quadratic assignment problems (QAPs) have considerable popularity because of various real-world...

  • AUTOMATIC VERIFICATION OF OPTIMIZATION ALGORITHMS:: A CASE STUDY OF A QUADRATIC ASSIGNMENT PROBLEM SOLVER. MERKEL, ROBERT; WANG, DAOMING; LIN, HUIMIN; CHEN, TSONG YUEH // International Journal of Software Engineering & Knowledge Engine;Mar2011, Vol. 21 Issue 2, p289 

    Metamorphic testing is a technique for the verification of software output without a complete testing oracle. Mathematical optimization, implemented in software, is a problem for which verification can often be challenging. In this paper, we apply metamorphic testing to one such optimization...

  • DOMAIN CONTRACTION IN NONLINEAR PROGRAMMING: MINIMIZING A QUADRATIC CONCAVE OBJECTIVE OVER A POLYHEDRON. Thakur, Lakshman S. // Mathematics of Operations Research;May91, Vol. 16 Issue 2, p390 

    Using linear underestimating approximations and their dual solutions, we develop new results for the nonconvex problem of minimizing a quadratic concave function under linear constraints. For solving this problem, which has such important management applications as economies of scale, fixed...

  • Recognition of Graphs with Convex Quadratic Stability Number. Pacheco, Maria F.; Cardoso, Domingos M. // AIP Conference Proceedings;9/9/2009, Vol. 1168 Issue 1, p1366 

    A stable set of a graph is a set of mutually non-adjacent vertices. The determination of a maximum size stable set, which is called maximum stable set, and the determination of its size, which is called stability number, are central combinatorial optimization problems. However, given a...

  • $${{\mathcal {D}(\mathcal {C})}}$$-optimization and robust global optimization. Hoang Tuy // Journal of Global Optimization;Jul2010, Vol. 47 Issue 3, p485 

    For solving global optimization problems with nonconvex feasible sets existing methods compute an approximate optimal solution which is not guaranteed to be close, within a given tolerance, to the actual optimal solution, nor even to be feasible. To overcome these limitations, a robust solution...

  • On some interior-point algorithms for nonconvex quadratic optimization. Tseng, Paul; Ye, Yinyu // Mathematical Programming;2002, Vol. 93 Issue 2, p217 

    Recently, interior-point algorithms have been applied to nonlinear and nonconvex optimization. Most of these algorithms are either primal-dual path-following or affine-scaling in nature, and some of them are conjectured to converge to a local minimum. We give several examples to show that this...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics