Sensitivity analysis in convex quadratic optimization: simultaneous perturbation of the objective and right-hand-side vectors

Alireza Ghaffari Hadigheh (a-r-ghaffaritabrizu.ac.ir)
Oleksandr Romanko (romankomcmaster.ca)
Tamas Terlaky (terlakymcmaster.ca)

Abstract: In this paper we study the behavior of Convex Quadratic Optimization problems when variation occurs simultaneously in the right-hand side vector of the constraints and in the coefficient vector of the linear term in the objective function. It is proven that the optimal value function is piecewise-quadratic. The concepts of transition point and invariancy interval are generalized to the case of simultaneous perturbation. Criteria of convexity, concavity or linearity of the optimal value function on invariancy intervals are derived. Furthermore, differentiability of the optimal value function is studied, and linear optimization problems are given to calculate the left and right derivatives. An algorithm, that is capable to compute the transition points and optimal partitions on all invariancy intervals, is outlined. We specialize the method to Linear Optimization problems and provide a practical example of simultaneous perturbation parametric quadratic problem from electrical engineering.

Keywords: Parametric Optimization, Sensitivity Analysis, Simultaneous Perturbation, Quadratic Optimization, Linear Optimization, Interior Point Methods, Optimal Partition

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

Citation: AdvOL Report #2005/18, Advanced Optimization Laboratory, Dept. of Computing and Software, McMaster Univesity, Hamilton, ON, Canada. To appear in Algorithmic Operational Research.

Download: [PDF]

Entry Submitted: 02/23/2005
Entry Accepted: 02/23/2005
Entry Last Modified: 08/30/2007

Modify/Update this entry