Efficient Cooperative Solvers for Nonlinear Continuous Constraint Problems
Yi Shang, Markus P.J. Fromherz, and Lara S. Crawford
Abstract
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.
PDF file
Back to the top.