|
Article Excerpt
For a locally optimal solution to the nonlinear semidefinite programming problem, under Robinson's constraint qualification, the following conditions are proved to be equivalent: the strong second-order sufficient condition and constraint nondegeneracy; the nonsingularity of Clarke's Jacobian of the Karush-Kuhn-Tucker system; the strong regularity of the Karush-Kuhn-Tucker point; and others.
Key words: nonlinear semidefinite programming; strong second-order sufficient condition; constraint nondegeneracy; strong regularity
MSC2000 subject classification: Primary: 90C31, 65K10; secondary: 90C26, 90C22
ORMS subject classification: Primary: programming/nonlinear
History: Received May 16, 2005; revised November 21, 2005.
1. Introduction. Consider the optimization problem
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
where f: X [right arrow] 9 and G: X [right arrow] Y are twice continuously differentiable functions, X and Y are two finite-dimensional real vector spaces, each equipped with a scalar product denoted by and its induced norm denoted by [parallel]x[parallel]; and K is a closed convex set in Y. We reserve Z to represent an arbitrary real vector space with a scalar product (x, x). We denote by [J.sub.x]f(x) and [J.sup.2.sub.xx]f(X) the derivative and the second-order derivative of f with respect to x [member of] X, respectively. For any given linear operator A, we denote its adjoint by [A.sup.*]. The first-order optimality condition, namely the Karush-Kuhn-Tucker (KKT) condition, for (OP) takes the following form:
[J.sub.x]L(x, [mu]) = and [mu] [member of] [N.sub.k] (G(x)), (2)
where the Lagrangian function L: X x Y [right arrow] R is defined by
L(x, [mu]) := f(x) + , (x, [mu]) [member of] X x Y, (3)
[J.sub.x]L(X, [mu]) is the derivative of L(x, [mu]) at (x, [mu]) with respect to x [member of] X, and [N.sub.K](y) denotes the normal cone of K at y in the sense of convex analysis (Rockafellar [35]):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
For any (x, [mu]) satisfying (2), we call x a stationary point and (x, [mu]) a KKT point of (OP), respectively.
During the last three decades, tremendous progress has been achieved toward sensitivity and stability analysis of solutions to the optimization problem (OP) subject to data perturbation (Bonnans and Shapiro [4], Facchinei and Pang [12], Klatte and Kummer [18], Rockafellar and Wets [36]). When K is a polyhedral set, the corresponding theory is quite complete. This is especially the case for the conventional nonlinear programming
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)
where f: X [right arrow] R, h: X [right arrow] [R.sup.m], and g: X [right arrow] [R.sup.P] are twice continuously differentiable functions.
For the case in which K is a general nonpolyhedral set, much less is known. However, when K is [C.sup.2]-cone reducible in the sense of Bonnans and Shapiro [4, Definition 3.135], the full picture of sensitivity and stability of solutions for problem (OP) emerges (Bonnans et al. [6, 7], Bonnans and Shapiro [3, 4]). The class of [C.sup.2]-cone reducible sets is rich. It includes, notably, the polyhedral set, the second-order cone (ice-cream cone or Lorentz cone), the cone of symmetric positive semidefinite matrices, and their Cartesian product (Bonnans and Shapiro [4], Shapiro [39]).
Compared to the conventional nonlinear programming (NLP), the theory for (OP) with [C.sup.2]-cone reducible sets is evolving and yet to be completed. Let [bar.x] be a feasible solution to (OP). Robinson's constraint qualification (CQ) (Robinson [29]) is said to hold at [bar.x] if
[member of] int{G([bar.x]) + [I.sub.x]G([bar.x])X-K}, (5)
where "int" denotes the topological interior part of a given set. If [bar.x] is a locally optimal solution to (OP) and Robinson's CQ holds at [bar.x], then there exists a Lagrangian multiplier [??] [member of] Y, together with [bar.x], satisfying the KKT condition:
[I.sub.x]L([??],[??]) = [??] [member of] [N.sub.K] (G([bar.x])). (6)
For any closed (not necessarily convex) set D [??] y and y [member of] Y, denote
dist(y, D):= inf{[parallel]y-d[parallel]: d [member of D}.
For any closed set D [??] y, we write [T.sup.i.sub.D] (y) and [T.sub.D] (Y) for the inner tangent cone and the contingent (Bouligand) cone of D at y, respectively. That is,
[T.sup.i.sub.D] (y) = {d [member of] Y: dist(y + td, D) = o(t), t [greater than or equal to] 0},
and
[T.sub.d] (Y) = {d [member of] Y: [there exists][t.sub.k] [down arrow] O, dist(y + [t.sub.k]d, D) = o([t.sub.k])}.
When D is a closed convex set, the inner tangent cone and the contingent cone are equal:
[T.sub.D] (y) = [T.sup.i.sub.D] (y) = {d [member of] Y: dist(y + td, D) = o(t), t [greater than or equal to] 0}, y [member of] D,
and will be simply called the tangent cone of D at y. Because Y is assumed to be a finite-dimensional space and K is a closed convex set, Robinson's CQ (5) can be equivalently written as
[I.sub.x]G([bar.x])X + [T.sub.K]-(G([bar.x])) = Y, (7)
which reduces to the well-known Mangasarian-Fromovitz constraint qualification (MFCQ) for the conventional nonlinear programming (NLP) (Mangasarian and Fromovitz [22]):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
where the active set J ([bar.x]) of g(x) at [bar.x] is defined by
J(bar.x]) := {j: [g.sub.j]([bar.x]) = O, j = 1 ,..., p}.
For a proof of this equivalence, see Robinson [28, Theorem 3]. A stronger notion than the MFCQ in (NLP) is the linear independence constraint qualification (LICQ):
[{[I.sub.x][h.sub.i]([bar.x]}.sup.m.sub.i=l] and [{[I.sub.x][g.sub.j]([bar.x])}j[member of]J([bar.x])] are linearly independent. (9)
Let M([bar.x]) denote the set of Lagrangian multipliers satisfying (6). Then M([bar.x]) is nonempty and bounded if and only if Robinson's CQ holds at [bar.x] (Bonnans and Shapiro [4, Theorem 3.9 and Proposition 3.17]), which generalizes an analogous assertion for (NLP): M([bar.x]) is nonempty and bounded if and only if the MFCQ holds [bar.x] (cf., Gauvin [13]). For (NLP), the LICQ implies that M([bar.x]) is a singleton.
In one of his seminal papers, Robinson [30] introduced the important concept of strong regularity for generalized equations, which include the KKT system (6) as a special case, and defined a strong second-order sufficient condition for (NLP). He also showed that the strong second-order sufficient condition and the LICQ imply the strong regularity of the solution to the KKT system (6). Interestingly, the converse is also true; see Jongen et al. [17], Bonnans and Sulem [5], Dontchev and Rockafellar [10], and Bonnans and Shapiro [4] (Proposition 5.38).
The primary objective of this paper is to build up the connections between the strong second-order sufficient condition and strong regularity for the nonlinear semidefinite programming
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)
where f: X [right arrow] R, h: X [right arrow] [R.sup.m], and g: X [right arrow] [L.sup.p] are twice continuously differentiable; [L.sup.p] is the linear space of all p x p real symmetric matrices; and [L.sup.p] is the cone of all p x p positive semidefinite matrices. Problem (NLSDP) is a special case of (OP) with
G(x) := (h(x), g(x)), x [member of] X, y := [R.sup.m] x [L.sup.p], and K := {0} x [L.sup.p.sub.+]. (11)
We achieve this objective via the study of the nonsingularity of generalized Jacobian of the system of nonsmooth equations reformulated from (2). Consequently, we show that if J is a locally optimal solution to (NLSDP) and Robinson's CQ holds at [bar.x], then the nonsingularity of Clarke's Jacobian of the corresponding nonsmooth system is not only sufficient but also necessary for the strong regularity. Because the nonsingularity of Clarke's Jacobian is a stronger condition than many other conditions posed for general nonsmooth equations (Kummer [20], Pang et al. [26]), this actually establishes the equivalence of many conditions discussed in a wide range of literatures for (NLSDP).
The organization of this paper is as follows. In [section]2, we study some useful properties of Clarke's Jacobian for Lipschitz functions, in particular for the metric projector over [L.sup.p.sub.+] We propose a strong second-order sufficient condition for the nonlinear semidefinite programming (NLSDP) in [section]3. It is shown that this strong secondorder sufficient condition and constraint nondegeneracy imply the nonsingularity of Clarke's Jacobian of the corresponding nonsmooth system. The promised equivalent conditions are discussed in [section]4. We conclude this paper in [section]5 by pointing out some possible research topics.
2. Jacobian properties. Let X, Y, and Z be three arbitrary finite-dimensional real vector spaces each equipped with a scalar product and its induced norm [parallel]x[parallel]....
|
