C Gurwitz.

A globally convergent algorithm for minimizing over the rotation group of quadratic forms online

. (page 1 of 1)
Online LibraryC GurwitzA globally convergent algorithm for minimizing over the rotation group of quadratic forms → online text (page 1 of 1)
Font size
QR-code for this ebook


Robotics Research
Ifechnical Report



S:,




A Globally Convergent Algorithm for

Minimizing Over the Rotation Group of

Quadratic Forms

by

C. Gurwitz *
M.L. Overton '*

Technical Report No. 292

Robotics Report No. 108

April, 1987



/
I
f




\



\\







New York University
l^t Institute of Mathematical Sciences

Computer Science Division

251 Mercer Street New York, N.Y 10012




V



A Globally Convergent Algorithm for

Minimizing Over the Rotation Group of

Quadratic Forms

by

C. Gurwitz *
M.L. Overton **

Technical Report No. 292

Robotics Report No. 108

April, 1987



Department of Computer Science and Information Science
Brooklyn College
City University of New York
Department of Computer Science

** Courant Institute of Mathematical Sciences
New York University



* The work of this author was conducted at New York University with the support of the

Office of Naval Research Graduate Fellowship Program.

** The work of this author was supported in part by National Science Foundation Grant No.

DCR-85-02014.



A Globally Convergent Algorithm for Minimizing Over the
Rotation Group of Quadratic Forms

Chaya Gurwitz*

Department of Computer and Information Science

Brooklyn College

City University of New York

Michael L. Overton f

Department of Computer Science

Courant Institute of Mathematical Sciences

New York University



ABSTRACT

We describe a numerical procedure for solving problems involving mmimi-
zation over the rotation group of quadratic forms which arise in connection with
problems of computer vision. The algorithm presented is a sequential quadratic
programming method which takes advantage of the special structure of the prob-
lem constraints. We conclude by proving that our method is globally convergent.



•The work of this author was conducted at New York University with the support of the Office of Naval

Research Graduate Fellowship Program.

tThe work of this author was supported in part by National Science Foundation Grant No. DCR-85-020U,



A Globally Convergent Algorithm for Minimizing Over the
Rotation Group of Quadratic Forms

Chaya Gurwitz*

Department of Computer and Information Science

Brooklyn College

City University of New York

Michael L. Overton f

Department of Computer Science

Courant Institute of Mathematical Sciences

New York University

1. Introduction

The classical theory of eigenvalue problems grows out of a quadratic minimization problem,
to wit: minimize one quadratic form x K iX while holding another quadratic form i K nx con-
stant. (Here it is best to assume that A'o is positive definite). This simplest observation makes it
clear that the eigenvalue problem is the most rudimentary form of a more general problem,
namely:

(1) minimize the quadratic form x^ Kx while holdmg n other quadratic forms x -^ A', j
constant.

Introduction of Lagrange multipliers, as in the standard eigenvalue case, reduces this to an
algebraic problem having a 'generalized eigenvalue' form: solve the equations



•The work of this author was conducted at New York University with the support of the Office of Naval

Research Graduate Fellowship Program.

■fXhe work of this author was supported in part by National Science Foundation Grant No. DCR-85-020H.



- 2-

(2) (K-\iKi - ■ ■ -\i,K,)x =0, x^KiX=Ci, i=l,...,k

However, only inefficient numerical procedures for solving algebraic systems of this generality are
known, nor is any systematic theoretical analysis of problems of this form available.

Several minimization problems of this class having to do with minimization over the rota-
tion group of quadratic forms arise naturally in connection with problems of computer vision.
The general problem of this somewhat more restricted form can be written as

3

(3) minimize Y^ «.-^A',y uy

over all mutually orthogonal sets of unit-length vectors (u,,Uo,«3), where the coefficient matrices
K^- satisfy AT,-.- = iv.'. The present report describes a numerical procedure for solving a
significant case of the quadratic minimization problem (3), namely that in which the off-diagonal
matrices K^j all vanish, reducing the problem to

(4) minimize f (u ,v ,w ) ^ u ^ Au + v^ Bv + w"^ Cw

subject to u ■^ u = 1
v"^ V =1

WW =1

« ^t; =
u ^ u) =
v^ u; =

when the matrices A , B , C are all symmetric. Note that by adding an appropriate positive mul-
tiple of u'^+v'^+w' to the form (4), we can suppose that the matrices A , B , and C are also posi-
tive definite.



2. Description of the Algorithm

The problem under consideration is a special case of the general equality constrained non-
hnear programmmg problem



-3-

(5) mm / {x )

s.t. c, (x ) = 0, « ^ 1, ■ • • ,m.

Let g denote the gradient of the objective function and let A be the matrix whose rows consist of
the transposes of the gradients of the constraint functions. Let G and G, denote the Hessians of
the objective and constraint functions, respectively. We now define F to be a matrix with
orthogonal columns spanning the range space of A^ and Z to be a similar matrix whose columns
form a basis for the null space of A .

The first-order necessary conditions for (u ,v ,w ) to be a local minimum of (5) are that
the constraints are satisfied and that there exists a vector of Lagrange multipliers, X , such that

(6) g {u ' ,v ' ,w ' ) = A '^ \' .

This condition is equivalent to requiring (u ,v ,w ) to be a stationary point of the Lagrangian
function

m

L {u ,V ,W ,\) = f {u ,V ,w) - Y] ^i '^i (" i^' ."•' )

1=1

when X ^ X' . Alternatively, this condition can be stated as Z g ^ 0.

Second-order optimality conditions are expressed in terms of the Hessian with respect to
(u ,v ,w ) of the Lagrangian function, which is defined by

m
W (u ,V ,W ,X) = G (u ,V ,w) - Yj^i ^i (" '^ '"' )■

l' =1

The second-order necessary condition for (u ,v ,w ) to be a solution of (4) is that the projected
Hessian, Z (u ' ,v ' ,w ' ) W (u ' ,v ' ,w ' ,\' )Z {u ' ,v ' ,w ' ), be positive semi-definite; strict posi-
tive definiteness of the projected Hessian together with the satisfaction of the first-order condi-
tions is a sufTicient condition. (See Fletcher (1981) for more detail.)

Algorithms based on sequential quadratic programming have been found particularh'
efi'ective for solvmg problems of this nature. Methods of this type approximate the minimizer of
(5) by solving a sequence of quadratic programming (QP) subproblems. In these subproblems a



- 4-

local model of the nonlinear problem is posed in which the curvature of the Lagrangian function is
approximated by a suitable matrix and linear approximations are made to the constraints. The
solution of the k th QP is used to provide a search direction p * . The algorithm then determines
a step length, o , such that x + a* p * is a sufficiently better approximation to 2 ' .

The QP subproblem for (5) is given by

min It p ^ Wp + p^ g
pen'

s.t. Ap = -c

The solution can be easily computed by solving two systems of linear equations. The solution,
p , can be written as

p = yp„ + Zp.

where >' and Z are defined as described above. The vectors p^' and p.* can be found by solving
(7a) AYp^' = -c

(7b) Z ^ WZp/ =-Z'^ g - Z ^ UTp/

The solutions are unique when .4 has full row rank and Z ^ \VZ is positive definite. This method
of computing p * is discussed by Murray and Wright (1982). The solution of the QP subproblem
can also be viewed as the result of applying one step of Newton's method to the nonlinear system
of equations





1

Online LibraryC GurwitzA globally convergent algorithm for minimizing over the rotation group of quadratic forms → online text (page 1 of 1)