On the lower bound for a quadratic problem on the Stiefel manifold
- PDF / 114,384 Bytes
- 7 Pages / 595.276 x 793.701 pts Page_size
- 83 Downloads / 231 Views
ON THE LOWER BOUND FOR A QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD
UDC 519.8
O. A. Berezovskyi
We study the problem of finding the global minimum of a homogeneous quadratic function of special kind over the Stiefel manifold. For two variants of this problem, a low bound is proposed that is the dual Lagrange bound in the quadratic statement obtained using a family of redundant restrictions. The dual bound is proved to be exact in the case where the problem is considered over Boolean variables. Keywords: quadratic optimization problem, dual Lagrangian estimate, functionally redundant constraints, dual variables, positive definite matrix.
The problem considered in the paper (for which the lower estimate is proposed) consists in finding the global k r r r r minimum of the sum of quadratic forms f ( x ) = f ( x1 ,K , x k ) = å x iT A i x i on the Stiefel manifold, where A i = {A ijl : i =1
r j = 1, n, l = 1, n}, i = 1, k, are given real symmetric n ´ n matrices, x i = ( x i1 , x i 2 ,K , x in ) Î R n , i = 1, k, are vectors of variables, r r r and k £ n. By the Stiefel manifold is meant the set of all orthonormalized systems of vectors {x1 , x 2 , K, x k } in the space R n . Generally, this is a multiextremal nonlinear programming problem; it is rather difficult to solve it even for small dimensions [1, 2]. In this connection, of certain interest is estimating the global minimum of the problem, for example, using dual Lagrangian estimates for quadratic problems [3]. Briefly, the essence of the approach consists in considering maximization in dual variables of the Lagrangian function L( x, u ) , constructed for the original quadratic optimization problem, on a narrower domain of definition, on which the quadratic form L( x, u ) with respect to direct variables is positive definite and the inner problem is convex. In [4], Shor et al. formulate the original problem as a boundary-value optimization problem k r r f * = min å x iT A i x i
(1)
i =1
under the constraints
r r x iT x i = 1, i = 1,K , k ,
(2)
r r x iT x j = 0, i = 1,K , k - 1, j = i + 1,K , k,
(3)
(constraints (2) and (3) correspond here to the normality and orthogonality conditions, respectively, for vectors r x i , i = 1,K , k). Dual Lagrangian estimates for the quadratic statement (1)–(3) (and the fact that it is homogeneous) were used to obtain the lower estimate in [4]: f * ³ y1* = y1 ( u * ) =
max y1 ( u ) ,
u : K ( u ) ³0
(4)
V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 95–103, September–October 2008. Original article submitted September 26, 2007. 1060-0396/08/4405-0709
©
2008 Springer Science+Business Media, Inc.
709
k
where y1 ( u ) = -å u ii , K ( u ) ³ 0 means that the family of symmetric ( kn ´ kn ) matrices of the form i =1
k
K ( u ) = K 0 + å u ii K ii + i =1
1 k -1 å 2 i =1
k
å u ij (K ij + K ji )
j=i+1
is negative definite, u is the vector of Lagrangian multipliers for the problem (1)–(3),
Data Loading...
