Novel nonmonotone line-search method for constrained nonlinear programming: Algorithmic concepts and preliminary computational studies

A new nonmonotone line-search procedure is presented for the generally constrained case of nonlinear programming problems. The new algorithm is based on the use of standard penalty methods for the definition of merit functions used during line search to find the next iterate in algorithms generating a search direction iteratively. The key concept is the discretization of the penalty parameter used over a finite range of orders of magnitude and the provision of a memory list for each such order, as in standard nonmonotone line-search procedures used for unconstrained optimization, Nonmonotonicity helps in escaping from local minima, while the discretized penalty parameters overcome the difficulties in choosing a penalty parameter that varies, but having the same definition as the problem while not underpenalizing the constraints to arrive at the desired KKT point. An implementation within a customized logarithmic barrier algorithm for bounds' handling is presented with capabilities for very large scale applications; the algorithm uses exact first and second derivative information, derived symbolically, and the search direction is generated by solution of the Lagrange-Newton equations. The case studies presented demonstrate the capabilities of the new line-search procedure, and comparisons with other methods are discussed. It is noted that we found a significantly better solution in case study 5. The new nonmonotone line-search procedure is, at present, a heuristic and from the computational point of view: future work will focus on the investigation of both the theoretical properties of the method and new implementation aspects.