Title of Paper:A Perturbation approach for an inverse quadratic programming problem

Hits:

Date of Publication:2010-12-01

Journal:MATHEMATICAL METHODS OF OPERATIONS RESEARCH

Included Journals:SCIE、EI、Scopus

Volume:72

Issue:3

Page Number:379-404

ISSN No.:1432-2994

Key Words:Inverse optimization; Quadratic programming; Perturbation approach; Inexact Newton method

Abstract:We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC(1)) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC(1) function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.