Article ID: | iaor19941889 |
Country: | Netherlands |
Volume: | 59 |
Issue: | 1 |
Start Page Number: | 71 |
End Page Number: | 85 |
Publication Date: | Mar 1993 |
Journal: | Mathematical Programming (Series A) |
Authors: | Hearn Donald W., Ventura Jose A. |
The strategy of Restricted Simplicial Decomposition is extended to convex programs with convex constraints. The resulting algorithm can also be viewed as an extenstion of the (scaled) Topkis-Veinott method of feasible directions in which the master problem involves optimization over a simplex rather than the usual line search. Global convergence of the method is proven and conditions are given under which the master problem will be solved a finite number of times. Computational testing with dense quadratic problems confirms that the method dramatically improves the Topkis-Veinott algorithm and that it is competitive with the generalized reduced gradient method.