A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

Xiantao Xiao; Liwei Zhang; Jianzhong Zhang

doi:10.1016/j.cam.2008.01.028

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

Xiantao Xiao
, Liwei Zhang
, Jianzhong Zhang

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

16 Citations (Scopus)

Abstract

We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. The Karush-Kuhn-Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush-Kuhn-Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems. © 2008 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	485-498
Journal	Journal of Computational and Applied Mathematics
Volume	223
Issue number	1
DOIs	https://doi.org/10.1016/j.cam.2008.01.028
Publication status	Published - 1 Jan 2009
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

The research of Xiantao Xiao and Liwei Zhang is supported by the National Natural Science Foundation of China under project No. 10771026 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China. The research of Jianzhong Zhang is supported by the University Grant Council of Hong Kong under the grant CERG CityU 9041091 and CUHK 103105.

Research Keywords

Inverse optimization
Semi-definite quadratic programming
Smoothing Newton method

RGC Funding Information

RGC-funded

Access Output

10.1016/j.cam.2008.01.028Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{f0a6197f4df741d784ddb58ad9e2df53,

title = "A smoothing Newton method for a type of inverse semi-definite quadratic programming problem",

abstract = "We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. The Karush-Kuhn-Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush-Kuhn-Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems. {\textcopyright} 2008 Elsevier B.V. All rights reserved.",

keywords = "Inverse optimization, Semi-definite quadratic programming, Smoothing Newton method",

author = "Xiantao Xiao and Liwei Zhang and Jianzhong Zhang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2009",

month = jan,

day = "1",

doi = "10.1016/j.cam.2008.01.028",

language = "English",

volume = "223",

pages = "485--498",

journal = "Journal of Computational and Applied Mathematics",

issn = "0377-0427",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

AU - Xiao, Xiantao

AU - Zhang, Liwei

AU - Zhang, Jianzhong

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2009/1/1

Y1 - 2009/1/1

N2 - We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. The Karush-Kuhn-Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush-Kuhn-Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems. © 2008 Elsevier B.V. All rights reserved.

AB - We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. The Karush-Kuhn-Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush-Kuhn-Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems. © 2008 Elsevier B.V. All rights reserved.

KW - Inverse optimization

KW - Semi-definite quadratic programming

KW - Smoothing Newton method

UR - https://www.scopus.com/pages/publications/54249115069

UR - https://www.scopus.com/pages/publications/54249115069#tab=impact

U2 - 10.1016/j.cam.2008.01.028

DO - 10.1016/j.cam.2008.01.028

M3 - RGC 21 - Publication in refereed journal

SN - 0377-0427

VL - 223

SP - 485

EP - 498

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

IS - 1

ER -

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

Abstract

Bibliographical note

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this