In this paper, we study parametric analysis of semidefinite optimization problems with respect to the perturbation of objective function. We investigate the behavior of the optimal partition and optimal set mapping in a so called nonlinearity interval. Furthermore, we investigate the sensitivity of the approximation of the optimal partition, which have been recently studied by Mohammad-Nezhad and Terlaky. The approximation of the optimal partition was obtained from a bounded sequence of interior solutions on, or in a neighborhood of the central path. We derive an upper bound on the distance between the invariant subspaces spanned by the approximation of the optimal partition.
Adler and Monteiro @cite_34 studied the parametric analysis of LO problems using the concept of optimal partition. Another treatment of sensitivity analysis for LO based on the optimal partition approach was given by @cite_15 and Greenberg @cite_3 . @cite_12 @cite_33 extended the optimal partition approach to linearly constrained quadratic optimization (LCQO) with perturbation in the right hand side vector and showed that the optimal value function is convex and piecewise quadratic. There have been further studies on optimal partition and parametric analysis of conic optimization problems. In contrast to LO, the optimal partition of SDO is defined as a 3-tuple of mutually orthogonal subspaces of @math , see . Goldfarb and Scheinberg @cite_22 considered a parametric SDO problem, where the objective is perturbed along a fixed direction. They derived auxiliary problems to compute the directional derivatives of the optimal value function and the so-called invariancy set of the optimal partition. Yildirim @cite_18 extended the concept of the optimal partition and the auxiliary problems in @cite_22 for linear conic optimization problems.
@cite_18 @cite_33 @cite_22 @cite_3 @cite_15 @cite_34 @cite_12
2144600542 1490853808 1983800681 2055716186 2062716676 1496393375
We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as functions of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the optimal partition approach to sensitivity analysis in LP and SDP, the range of perturbations for which the optimal partition remains constant can be computed by solving two conic optimization problems. Under a weaker notion of nondegeneracy, this range is simply given by a minimum ratio test. We discuss briefly the properties of the optimal value function under such perturbations. In this paper we consider a semidefinite programming (SDP) problem in which the objective function depends linearly on a scalar parameter. We study the properties of the optimal objective function value as a function of that parameter and extend the concept of the optimal partition and its range in linear programming to SDP. We also consider an approach to sensitivity analysis in SDP and the extension of our results to an SDP problem with a parametric right-hand side. In this chapter we describe the optimal set approach for sensitivity analysis for LP. We show that optimal partitions and optimal sets remain constant between two consecutive transition-points of the optimal value function. The advantage of using this approach instead of the classical approach (using optimal bases) is shown. Moreover, we present an algorithm to compute the partitions, optimal sets and the optimal value function. This is a new algorithm and uses primal and dual optimal solutions. We also extend some of the results to parametric quadratic programming, and discuss differences and resemblances with the linear programming case. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math .