KK Reformulation Functions And Their Applications In Solving Optimization Problems Over Symmetric Cones

Optimization problems over symmetric cones is a broad class of optimiza-tion problems, which contains optimization problems over the non-negativecone in n ( +n), the second-order cone (L+n), and the cone of positive semi-definite symmetric matrices (S+n) as special cases. Recently, there is muchinterest in studying optimization problems over symmetric cones. Variousmethods, such as, the interior-point algorithm, smoothing algorithm and meritfunction method, have been extended to solve optimization problems over sym-metric cones.In the merit function method for solving optimization problems over sym-metric cones, the coerciveness of the merit function is an very important prop-erty. The coerciveness of the merit function means the level set of the meritfunction is bounded, so when we apply some descending algorithm for solvingoptimization problems over symmetric cones, the iteration sequence generatedby this algorithm has an accumulation point. In this paper, based on KKcomplementarity function, we introduce KK merit function and penalized KKmerit function. The coerciveness of the two classes of merit functions is inves-tigated. The KK merit function is a broad class of merit function includingthe FB merit function and the natural residual merit function which are oftenused in the literature as special cases. We obtain that the KK merit functionis coercive under some assumptions which are strictly weaker than that"F isstrongly monotone and Lipschitz continuous". The penalized KK merit func-tion is a generalization of FY merit function. We obtain that the penalizedKK merit function is coercive under an assumption which is strictly weakerthan that"F is weakly coercive"(and hence, it is strictly weaker than that"F is strongly monotone").Based on the KK complementarity function, we introduce KK smoothingfunction. It is a broad class of symmetric cone complementarity function in- cluding the FB smoothing function and the CHKS smoothing function whichare usually used in the literature as special cases. Based on the KK smoothingfunction, by using the theory of Euclidean Jordan algebras, we extend Qi-Sun-Zhou smoothing Newton algorithm to solve the linear programming over sym-metric cone (SCLP). We prove that under suitable assumptions the algorithmis well-defined. we show that the algorithm is globally convergent under suit-able conditions. Moreover, the algorithm is locally quadratically convergentif we add a nonsingularity assumption. Some preliminary numerical resultsof this algorithm are reported, and the numerical results are compared withthat of the interior-point algorithm. The numerical results of this algorithmare satisfying.Based on the KK complementarity function, we introduce the regularizedversion of the KK smoothing functions. Based on this class of smoothingfunctions, by using the theory of Euclidean Jordan algebras, we extenda smoothing Newton algorithm with a nonmonotone line search to solvethe generalized complementarity problem over symmetric cones (GSCCP).The coerciveness of the reformulation functions H?τμis investigated. Bymaking use of the coerciveness of H?τμ, we show that the algorithm is globallyconvergent under suitable assumptions. Furthermore, under a nonsingularityassumption, the algorithm is proved to be locally superlinearly convergent.