Efficient algorithms for linearly constrained convex programming and some proximity problems

Abstract

This thesis addresses the following problems:

Linearly constrained convex programming problem in n constraints and d dimensions for a fixed d.

Some proximity problems between two convex polyhedra A and B, each polyhedron being given as a sum of the convex hull of points and the affine hull of rays. Let n be the total number of points and rays, and let the polyhedra be in a space of fixed dimension d. The problems we consider are: • P1: Check if A and B intersect. • P2: If A and B intersect, check if they are just touching. • P3: If A and B do not intersect, find the Euclidean distance between them. • P4: If A and B intersect, find the intensity of collision between them.

A very large linear programming problem arising in recursive neural network design.

Our results are the following:

We have extended Megiddo’s fixed?dimension LP algorithm to linearly constrained convex programming and obtained complexity results similar to those obtained by Megiddo.

For proximity problems, we show: • P1–P3 can be solved in O(n) time for fixed d, and in polynomial time for variable d. • P4 and a related problem of depth of a polyhedron are NP?complete. • We show that one more related problem is NP?hard.

The neural network design problem is such that traditional large?scale linear programming methods are unsuitable. We recast the problem as a norm?minimization problem and develop a practical algorithm. Using this algorithm, we solve an LP (arising in neural net design) having about 4 × 10? variables and 10?+ constraints.