Efficient cooperative solvers for nonlinear continuous constraint problems
In the past decade, significant progress has been made in understanding problem complexity of discrete constraint problems. In contrast, little similar work has been done for constraint problems in the continuous domain. In this paper, we study the complexity of several popular methods for nonlinear constraint problems and present cooperative solvers with improved performance. The methods include a sequential quadratic programming (SQP) method, a penalty method with a fixed penalty function, a penalty method with a sequence of penalty functions, and an augmented Lagrangian method. In our experiments, we apply these methods to solve a series of continuous constraint problems with increasing constraint-to-variable ratios and obtain novel results on complexity phase transition phenomena. Specifically, for constraint satisfaction problems, the SQP method is the best on weakly constrained problems, whereas the augmented Lagrangian method is the best on highly constrained ones. Although the static penalty method performs poorly by itself, by combining it with the SQP method, we show a cooperative solver that is significantly better than any of the individual methods on problems with moderate to large constraint-to-variable ratios.
Shang, Y. ; Fromherz, M. P. J. ; Crawford, L. S. Efficient cooperative solvers for nonlinear continuous constraint problems. Proceedings of the First International Congress of Mathematical Software (ICMS) 2002; 2002 August 17-19; Beijing; China. Singapore: World Scientific; 2002; 104-114.