Theory and application of p-regularized subproblems for p>2

Yong Hsia, Ruey Lin Sheu, Ya Xiang Yuan

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 (σ/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).

Original languageEnglish
Pages (from-to)1059-1077
Number of pages19
JournalOptimization Methods and Software
Volume32
Issue number5
DOIs
Publication statusPublished - 2017 Sep 3

Fingerprint

Minimizer
Combinatorial optimization
Trust Region Subproblem
Linear systems
Necessary and Sufficient Optimality Conditions
Overdetermined Systems
Quadratic Approximation
Computational complexity
Quadratic Assignment Problem
Least-squares Solution
Regularization Technique
Local Approximation
Tikhonov Regularization
Unconstrained Optimization
Combinatorial Optimization
Global Minimum
Linear Constraints
NP-hard Problems
Inequality Constraints
Numerical Approximation

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Optimization
  • Applied Mathematics

Cite this

Hsia, Yong ; Sheu, Ruey Lin ; Yuan, Ya Xiang. / Theory and application of p-regularized subproblems for p>2. In: Optimization Methods and Software. 2017 ; Vol. 32, No. 5. pp. 1059-1077.
@article{73e00c29e5e74dd5bec7a9985aedd18f,
title = "Theory and application of p-regularized subproblems for p>2",
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 (σ/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).",
author = "Yong Hsia and Sheu, {Ruey Lin} and Yuan, {Ya Xiang}",
year = "2017",
month = "9",
day = "3",
doi = "10.1080/10556788.2016.1238917",
language = "English",
volume = "32",
pages = "1059--1077",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor and Francis Ltd.",
number = "5",

}

Theory and application of p-regularized subproblems for p>2. / Hsia, Yong; Sheu, Ruey Lin; Yuan, Ya Xiang.

In: Optimization Methods and Software, Vol. 32, No. 5, 03.09.2017, p. 1059-1077.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Theory and application of p-regularized subproblems for p>2

AU - Hsia, Yong

AU - Sheu, Ruey Lin

AU - Yuan, Ya Xiang

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 -