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
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