Projection Onto Convex Sets (POCS) is an iterative technique which finds an intersection of closed, convex sets. Primarily, I am interested in extending Projections Onto Convex Sets to nonconvex sets. We have two POCS-based algorithms that converge to the solution of the two-dimensional linear complementarity problem (which is equivalent to finding the intersection of several (nonconvex) bent lines). Further, we can show that the algorithms converge to the solution of the two-dimensional generalized linear complementarity problem. Numerical results are provided and indicate that the algorithm works in higher dimensions. Relaxation is employed to accelerate convergence.

A convex set is one where any two points in the set can be joined by a line segment and that line segment is completely contained in the set, e.g. a line or a solid cirle. Suppose you have a laser and you shoot a light beam from the laser onto a surface. The beam can hit the surface at many different points depending on where you shoot the beam. Now suppose you shoot it to the closest place on the surface from the source of the beam. Then the place where it hits is the projection of the light source onto the surface. In other words, it minimizes the distance from the source to the surface.

Projections Onto Convex Sets (POCS) is a method of finding a common intersection point of a number of (nonempty) intersecting convex sets. The basic idea is that if you project from one set to the next, and the sets are all closed and convex, then you will eventually end up in the intersection. My research involves the classification of nonconvex sets where alternating projections can be used to find an intersection point. In addition, it involves writing and implementing algorithms used for finding the intersections of such sets and proving that these methods converge to the solution of the given problem.

The types of applications where projections have been used include, but are not limited to, Reconstruction of Images from Phase and Magnitude (reconstructing photographs from partially stored data), Tomography (used in MRI technology in hospitals) and Learning Algorithms for Neural Nets (to simulate artificial intelligence in computers). In addition to the theoretical aspects, the algorithms must be programmed.

The main type of application that I have focused on is finding the solutions to Linear Complementarity Problems, find x where x is a vector in n-dimensions, x >= 0, Ax - b >= 0 and x (Ax - b) = 0, given b, a vector in n-dimensions and A, an nxn matrix. Solving these is equivalent to finding intersections of bent hyperplanes (which are simple nonconvex sets).

Numerical results are found by testing the algorithm on different systems. These are then compared to other well-known methods for solving Complementarity Problems such as Murty's Algorithm, Lemke's Algorithm and Cryer's Projective Successive Over-relaxation Method. Numerically our methods always converge to the solution for arbitrary n when A is a P-matrix (all principle minors are positive). I am currently focused on comparisons with Cryer's Method.

We have proofs to show that our algorithms converge for n = 2 when the matrix A is a P-matrix . We have extended these results to the Generalized Complementarity Problem for n = 2. I will continue to work with my thesis advisor, Dr. George Habetler, at Rensselaer Polytechnic Institute, to extend these results to an arbitrary n. I have also begun a collaboration with Dr. David Hipfel of Clarion University to characterize Generalized Complementarity Problems.