Using Improved Directions of Negative Curvature for the Solution of Bound-Constrained Nonconvex Problems Articles uri icon

publication date

  • August 2017

start page

  • 474

end page

  • 499

issue

  • 2

volume

  • 174

international standard serial number (ISSN)

  • 0022-3239

electronic international standard serial number (EISSN)

  • 1573-2878

abstract

  • In this work, we describe the efficient use of improved directions of negative curvature for the solution of bound-constrained nonconvex problems. We follow an interior-point framework, in which the key point is the inclusion of computational low-cost procedures to improve directions of negative curvature obtained from a factorisation of the KKT matrix. From a theoretical point of view, it is well known that these directions ensure convergence to second-order KKT points. As a novelty, we consider the convergence rate of the algorithm with exploitation of negative curvature information. Finally, we test the performance of our proposal on both CUTEr/st and simulated problems, showing empirically that the enhanced directions affect positively the practical performance of the procedure.

keywords

  • nonconvex optimisation; negative curvature; interior-point methods; KKT conditions