A Wide Neighborhood Arc-search Interior-point Algorithm For Convex Quadratic Programming Subject To Box Constraints And Linear Constraints

Convex quadratic programming(CQP)is a special mathematical programming in nonlinear programming.In the past ten years,CQP has become the basic research model of operational research,combinatorial optimization and systems analysis.The convex quadratic programming subject to box constraints and linear constraints(BLCQP)is a kind of box constraint added on the basis of CQP.This kind of optimization problem has many applications,such as box-constrained integer least squares problems[1,2],support vector machine training[3,4],convex quadratic knapsack problem[5,6] and continuous quadratic knapsack problem[7,8],etc.Beginning with Karmarkar’s groundbreaking work[9],interior-point methods(IPMs)have been one of the most intensive areas of development in optimization theory.It not only has good polynomial time complexity,but also has good practical calculation effect.Because of this,IPM has also been extended to other optimization models,such as CQP[10,11,12],second-order cone optimization[13],semidefinite programming[14],symmetric cone optimization[15]and complementarity problem[16,17].Recently,Yang[19,20] presented an arc-search IPM for LP,which searches for optimizers along an ellipse that is an approximation of the central path.The author also showed that the proposed arc-search infeasible interior-point method(IIPM)is a more reliable and efficient algorithm than Mehrotra’s algorithm by extensive numerical experiments[21].For other arc-search IPMs proposed by the Yang,see [22-28].Moreover,several authors generalized the arc-search method for LP to other optimization models,such as semidefinite optimization[29-31],complementarity problem[17,32],linear complementarity problem over symmetric cones[33,34],symmetric optimization[35-39].This paper designed a wide neighborhood arc-search IPMs for BLCQP.By overcoming the difficulties caused by the non-orthogonality of the iterative directions,establishing some new technical lemmas,we obtained the iteration complexity bounds of the corresponding algorithm,and through extensive numerical experiments showed that the algorithm is effective.The whole paper is divided into five chapters.The first chapter briefly explains the background of IPM,arc-search and BLCQP,as well as some basic lemmas and symbol conventions;Chapter 2 proposes a wide neighborhood arc-search IPM for BLCQP,the iteration complexity bound of the algorithm and the numerical test results are also given;Chapter 3 designs a different wide neighborhood arc-search IPM for BLCQP,obtains the best known iteration complexity bounds,and gives the numerical experiment results;The fourth chapter specially designs an initial point rule for BLCQP.On this basis,this chapter proposes a wide neighborhood arc-search IIPM for BLCQP,gives the iteration complexity of the algorithm and the numerical results;Finally,Chapter 5 summarizes the several types of algorithms proposed in this paper,and gives a prospect for the follow-up work.