Improved constraint consensus methods for seeking feasibility in nonlinear programs
The Constraint Consensus method moves quickly from an initial infeasible point to a point that is close to feasibility for a set of nonlinear constraints. It is a useful first step prior to launching an expensive local solver, improving the probability that the local solver will find a solution and the speed with which it is found. The two main ingredients are the method for calculating the feasibility vector for each violated constraint (the estimated vector to the closest point that satisfies the constraint), and the method of combining the feasibility vectors into a single consensus vector that updates the current point. We propose several improvements: (i) a simple new method for calculating the consensus vector, (ii) a predictor-corrector approach to adjusting the consensus vector, (iii) an improved way of selecting the output point, and (iv) ways of selecting subsets of the constraints to operate on at a given iteration. These techniques greatly improve the performance of barrier method local solvers. Quadratic feasibility vectors are also investigated. Empirical results are given for a large set of nonlinear and nonconvex models.
|Keywords||Constraint consensus, Heuristics, Nonlinear programming, Seeking feasibility|
|Journal||Computational Optimization and Applications|
Smith, L. (Laurence), Chinneck, J, & Aitken, V. (2013). Improved constraint consensus methods for seeking feasibility in nonlinear programs. Computational Optimization and Applications, 54(3), 555–578. doi:10.1007/s10589-012-9473-z