TY - JOUR
T1 - Theory and application of p-regularized subproblems for p>2
AU - Hsia, Yong
AU - Sheu, Ruey Lin
AU - Yuan, Ya Xiang
N1 - Funding Information:
This research was supported by National Natural Science Foundation of China under grants 11331012, 11321061, 11471325 and 11571029, by Taiwan MOST 103-2115-M-006-014-MY2, and by fundamental research funds for the Central Universities under grant YWF-16-BJ-Y-11.
PY - 2017/9/3
Y1 - 2017/9/3
N2 - 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 (σ/p)σXσp 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-RSm), 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-RSm) with p=4. In the end, we develop an algorithm for solving (p-RSm).
AB - 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 (σ/p)σXσp 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-RSm), 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-RSm) with p=4. In the end, we develop an algorithm for solving (p-RSm).
UR - http://www.scopus.com/inward/record.url?scp=84991035189&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84991035189&partnerID=8YFLogxK
U2 - 10.1080/10556788.2016.1238917
DO - 10.1080/10556788.2016.1238917
M3 - Article
AN - SCOPUS:84991035189
VL - 32
SP - 1059
EP - 1077
JO - Optimization Methods and Software
JF - Optimization Methods and Software
SN - 1055-6788
IS - 5
ER -