Theory and application of p-regularized subproblems for p>2. (3rd September 2017)

• Record Type: Journal Article
• Authors: Hsia, Yong; Sheu, Ruey-Lin; Yuan, Ya-xiang
• Is Part Of: Optimization methods and software. Volume 32:Number 5(2017)
• Page Start: 1059
• Page End: 1077
• Publication Date: 2017-09-03
• Subjects: nonlinear optimization -- combinatorial optimization -- weighted regularization -- trust-region subproblem -- extended trust-region subproblem -- local non-global minimizer; 49K30 -- 90C46 -- 90C26; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1238917
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : The p -regularized subproblem ( p -RS) is the key content of a regularization technique in computing a Newton-like step for unconstrained optimization. The idea is to incorporate a local quadratic approximation of the objective function with a weighted regularization term and then globally minimize it at each iteration. In this paper, we establish a complete theory of the p -RSs for general p >2 that covers previous known results on p =3 or p =4. The theory features necessary and sufficient optimality conditions for the global and also for the local non-global minimizers of ( p -RS). It gives a closed-form expression for the global minimum set of ( p -RS) and shows that ( p -RS), p >2 can have at most one local non-global minimizer. Our theory indicates that ( p -RS) have all properties that the trust region subproblems do. In application, ( p -RS) can appear in natural formulation for optimization problems. We found two examples. One is to utilize the Tikhonov regularization to stabilize the least square solution for an over-determined linear system; and the other comes from numerical approximations to the generalized Ginzburg–Landau functionals. Moreover, when ( p -RS) is appended with m additional linear inequality constraints, denoted by ( p - ), the problem becomes NP-hard. We show that the partition problem, the k -dispersion-sum problem and the quadratic assignment problem in combinatorial optimization can be equivalently formulated as special types of ( p -RS ) with p =4. In the end, we develop an algorithm for solving ( p -RS ).