UBC Theses and Dissertations
Numerical solution of semidefinite constrained least squares problems Krislock, Nathan Gavin Beauregard
In this thesis, we are concerned with computing the least squares solution of the linear matrix equation AX = B subject to the constraint that the matrix X is positive semidefinite. For symmetric X, this is the previously studied semidefinite least squares (SDLS) problem; for nonsymmetric X, we introduce the nonsymmetric semidefinite least squares (NS-SDLS) problem. An application of this second problem is the estimation of the compliance matrix at some location on a deformable object. This is an important step in the process of making interactive computer models of de-formable objects, a technique which is used in the area of medical simulation. We also introduce a third semidefinite constrained least squares problem called the linear matrix inequality least squares (LMI-LS) problem, which is a generalization of the first two problems. Sufficient conditions for the existence and uniquenss of solutions for each of these three problems is provided. These solutions are characterized as solutions of nonlinear systems of equations known as the Karush-Kuhn-Tucker (KKT) equations. It is shown that the KKT equations for each of these problems can be stated as a semidefinite linear complementarity problem (SDLCP). Interior-point methods are proposed for the numerical solution of each of these three problems. Computational experiments are conducted which indicate that predictor-corrector interior-point methods solve these semidefinite constrained least squares problems efficiently. A noticable improvement is made over the current computational methods used for solving the SDLS problem.
Item Citations and Data