Theory and application of p-regularized subproblems for p>2. (3rd September 2017) - Hsia, Yong; Sheu, Ruey-Lin; Yuan, Ya-xiang
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 ).