Header

UZH-Logo

Maintenance Infos

Sensitivity analysis of semidefinite programming problems


Wickström, Anna-Laura Haber. Sensitivity analysis of semidefinite programming problems. 2014, University of Zurich, Faculty of Science.

Abstract

In this thesis, we construct a parametrized model for the SDP problem and analyze the disturbance of the parameters. We discuss conditions for Lipschitz properties, namely: calmness, upper regularity, and strong regularity of non- linear SDP problems at feasible and stationary points, and present results that even apply to more general nonpolyhedral cones and convex sets. We work with two different techniques from the field of variational analysis to show different sensitivity characteristics. Our first approach is to rewrite the problem as a generalized function and construct generalized derivatives that are injective at a given solution if the stability of concern is given - upper and strong regularity. We construct a locally Lipschitz function of the Karush-Kuhn-Tucker conditions, a Kojima- like function, for an SDP problem. The Kojima function is the product of a continuously differentiable and a nonsmooth function. The latter contains the projection function onto the cone of positive semidefinite matrices. We look at the construction of its contingent derivative (graphical derivative) and Thibault derivative (strict graphical derivative). Moreover, we examine the relations between the Thibault derivative and the Clarke generalized Jacobian of these projections. In the second approach, we show that calmness is directly related to the convergence speed of a solution algorithm. We look at an SDP problem as a mapping of a system of finitely many inequalities with perturbations on the right-hand side and a fixed algebraic constraint. For this perturbed system, we study the calmness property of stationary points and create the structure of an algorithm to show calmness.
In this thesis, we construct and discuss the elements of the Thibault deriva- tive for some mappings in SDP, give new results on calmness of the projection mapping, and present sufficient and necessary conditions for calmness in SDP problems. Our results even apply to more general problems, beyond SDP.

3

Abstract

In this thesis, we construct a parametrized model for the SDP problem and analyze the disturbance of the parameters. We discuss conditions for Lipschitz properties, namely: calmness, upper regularity, and strong regularity of non- linear SDP problems at feasible and stationary points, and present results that even apply to more general nonpolyhedral cones and convex sets. We work with two different techniques from the field of variational analysis to show different sensitivity characteristics. Our first approach is to rewrite the problem as a generalized function and construct generalized derivatives that are injective at a given solution if the stability of concern is given - upper and strong regularity. We construct a locally Lipschitz function of the Karush-Kuhn-Tucker conditions, a Kojima- like function, for an SDP problem. The Kojima function is the product of a continuously differentiable and a nonsmooth function. The latter contains the projection function onto the cone of positive semidefinite matrices. We look at the construction of its contingent derivative (graphical derivative) and Thibault derivative (strict graphical derivative). Moreover, we examine the relations between the Thibault derivative and the Clarke generalized Jacobian of these projections. In the second approach, we show that calmness is directly related to the convergence speed of a solution algorithm. We look at an SDP problem as a mapping of a system of finitely many inequalities with perturbations on the right-hand side and a fixed algebraic constraint. For this perturbed system, we study the calmness property of stationary points and create the structure of an algorithm to show calmness.
In this thesis, we construct and discuss the elements of the Thibault deriva- tive for some mappings in SDP, give new results on calmness of the projection mapping, and present sufficient and necessary conditions for calmness in SDP problems. Our results even apply to more general problems, beyond SDP.

3

Statistics

Downloads

28 downloads since deposited on 27 Mar 2019
17 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation (monographical)
Referees:Klatte Diethard, Chipot Michel
Communities & Collections:UZH Dissertations
Dewey Decimal Classification:Unspecified
Language:English
Place of Publication:Zürich
Date:2014
Deposited On:27 Mar 2019 13:38
Last Modified:15 Apr 2021 15:01
Number of Pages:102
OA Status:Green

Download

Green Open Access

Download PDF  'Sensitivity analysis of semidefinite programming problems'.
Preview
Content: Published Version
Language: English
Filetype: PDF
Size: 699kB