Yi Shang, Markus P.J. Fromherz, and Lara S. Crawford
Many science and engineering applications require finding solutions to satisfy a set of nonlinear constraints over real numbers or to optimize a nonlinear function subject to nonlinear constraints. Towards understanding the complexity of continuous constraint problems, we investigate complexity phase transition phenomena in solving such problems with increasing constraint-to-variable ratios. Based on a generic test-case generators that are modeled after control problems in robotics, we empirically study the complexities of several deterministic, stochastic, and cooperative solvers in solving constraint satisfaction and constrained optimization problems. The methods include sequential quadratic programming (SQP), static penalty method, dynamic penalty method, augmented Lagrangian method, Nelder-Mead simplex method and simulated annealing (SA). Our results show that problem parameters, such as constraint-to-variable ratio and constraint tightness, are useful in characterizing problem complexity. Deterministic local search method such as sequential quadratic programming (SQP) are efficient for weakly constrained problems, whereas combining cooperative solvers combining stochastic search (e.g., simulated annealing) or penalty method with SQP is much better for highly constrained, harder problems. For constrained optimization problems, the cooperative solver penalty method plus SQP also achieves much better solution quality than SQP using comparable amount of time.
This work has been supported in part by DARPA under contract F33615-01-C-1904.