Predictor-corrector Smoothing Methods For Quadratic Programs

The complementarity problem is considered a fundamental problem for op-timization theory since the optimality condition of many continuous optimizationproblems can be formulated as variational and complementarity problems[1]. Com-plementarity problems are widely found in many fields such as engineering physics,trafc management, economics. Therefore,it is significant to investigate algorithmsfor solving these problems.The mathematical language to describe that:Let F (x) : Rnâ†'Rnis a continuously diferentiable funetion, Rnis anonempty closed convex, variational inequality problemï¿¡VIP¤isμsolving a pointSince 1984 Karmarkar[2]solving linear programming projection algorithm pub-lished, already had a large number of articles appeared. But interior-point methodshave to start from the interior of the feasible region and guarantee the positivity ofthe primal and dual variables by an appropriate line search§so it is very difcultto find the initial point. More recently§so-called non-interior point methods(alsocalled smoothing-type methods)have been investigated, from which the most typi-cally one is non-interior-point path-following algorithm. Smoothing functions havebeen joined in these methods, using the properties of the smoothing functions, thesemethods do not necessarily belong to positive orthant.The advantages of non-point path tracking algorithm: (i) can arbitrarily se-lect the initial point; (ii) in each iteration requires only solve linear equations andcan fully select the step size; (iii) have the quadratic quadratic convergence rate.Viewing of the above-mentioned advantages of non-interior point algorithm, it isworth further study to weaken the constraints and solve real problems in the actualcalculation. In this paper, we mainly study the predictor-corrector smoothing methods.The a predictor-corrector smoothing method for convex quadratic programs is pro-posed. The predictor-corrector smoothing methods first structure the central pathconditions as a nonlinear system. In this way, smoothing method avoid the explicitinequality constraints, and so the iterates generated by this method do not neces-sarily belong to the positive orthant. It is very easy to find the initial point for themethod in this way. The globle convergence and local quadratic convergence resultsfor these algorithms are established. In the end, we using MATLAB programmingshow that the proposed algorithm is indeed efective.The content of this paper included four chapters. The content is organized asfollows:In the first chapter, we introduce the smoothing algorithms, discuss the naturesof the smooth functions.In the second chapter, we present a predictor-corrector smoothing-type methodbased on a scaled central path for the solution of quadratic programs Its main idea isto proof the method presented here is shown to be globally and locally quadraticallyconvergent under reasonable assumption.In the chapterâ…¢, we estimate based on the scaled central path—correctionsmoothing method of the uniformly convex programming problem and proved thatthe method has global convergence and local quadratic convergence.In the chapter IV, we do numerical experiments showing that the proposedalgorithm has some advantages in practical applications.