资源描述：
《1991 Quadratic programming with one negative eigenvalue is NP-hard》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、QuadraticProgrammingwithOneNegativeEigenvalueIsNP-HardPANOSM.PARDALOS’andSTEPHENA.VAVASIS2*‘DepartmentofComputerScience,PennsylvaniaStateUniversity,UniversityPark,PA16802,U.S.A.;‘DepartmentofComputerScience,CornellUniversity,Ithaca,NY14853,U.S.A.(Received:6Februar
2、y1991)Abstract.WeshowthattheproblemofminimizingaconcavequadraticfunctionwithoneconcavedirectionisNP-hard.Thisresultcanbeinterpretedasanattempttounderstandexactlywhatmakesnonconvexquadraticprogrammingproblemshard.Sahniin1974[8]showedthatquadraticprogram-mingwithane
3、gativedefinitequadraticterm(nnegativeeigenvalues)isNP-hard,whereasKozlov,TarasovandHacijan[2]showedin1979thattheellipsoidalgorithmsolvestheconvexquadraticproblem(nonegativeeigenvalues)inpolynomialtime.ThisreportshowsthatevenonenegativeeigenvaluemakestheproblemNP-h
4、ard.Keywords.Globaloptimization,quadraticprogramming,NP-hard.1.IntroductionNonlinearoptimizationincludesmanysubclassesofproblems.Uptodate,thebestmethodsseemnaturallytoexistforconvexprogrammingproblems;see,forexample[2].Nonconvexminimizationproblemsdonotappeartoadm
5、itefficientalgorithms.Theproblemofdesigningalgorithmsthatfindglobalsolutionsisverydifficult,sinceingeneral,therearenolocalcriteriaindecidingwhetheralocaloptimumisglobal[5],[6].Inthispaperweconsiderthecomplexityofaclassofnonconvexquadraticproblems.Thegeneralconcave
6、quadraticproblemhasthefollowingform:minj(x)=ixTQx+cTxs.t.AxGb,wherec,xElRE,AisanwzXnmatrix,bERm,andQisannXnsymmetricnegativesemidefinitematrix.ItiswellknownthatthisproblemisNP-hard[8].Infact,manywellknowncombinatorialoptimizationproblems(e.g.linearO-lprogramming)c
7、anbeformulatedasglobalconcaveminimizationproblems[6].Thesimplestcaseofconcaveprogrammingiswhenthecorrespondingsymmetric*Thisauthor’sworksupportedbytheAppliedMathematicalSciencesProgram(KC-04-02)oftheOfficeofEnergyResearchoftheU.S.DepartmentofEnergyundergrantDE-FGO
8、2-86ER25013.AOOOandinpartbytheNationalScienceFoundation,theAirForceOfficeofScientificResearch,andtheOfficeofNavalResearch,throughNSFgrantDMS8920550.Jour
