PATHNLP

Introduction

This document describes the GAMS/PATHNLP solver for non-linear programs and the options unique to this solver.

PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems. The solution to the original NLP is extracted from the KKT solution and returned to GAMS. All of this takes place automatically - no special syntax or user reformulation is required.

Typically, PATHNLP works very well for convex models. It also has a comparative advantage on models whose solution via reduced gradient methods results in a large number of superbasic variables, since the PATH solver won't construct a dense reduced Hessian in the space of the superbasic variables as reduced gradient solvers do. For nonconvex models, however, PATHNLP is not as robust as the reduced gradient methods.

The theory relating NLP to their KKT systems is well-known: assuming differentiability without convexity, and assuming a constraint qualification holds, then a solution to the NLP must also be a solution to the KKT system. If we also assume convexity, then a solution to the KKT system is also a solution to the NLP - no further constraint qualification is required.

In case PATH fails to find a solution to the KKT system for the NLP, a phase I / phase II method is used in which the phase I objective is simply the feasibility error and the original objective is ignored. If a feasible point is found in phase I then phase II, an attempt to solve the KKT system for the NLP using the current feasible point, is entered.

PATHNLP is installed automatically with your GAMS system. Without a license, it will run in student or demonstration mode (i.e. it will solve small models only). If your GAMS license includes PATH, this size restriction is removed.

Usage

If you have installed the system and configured PATHNLP as the default NLP solver, all NLP models without a specific solver option will be solved with PATHNLP. If you installed another solver as the default, you can explicitly request that a particular model be solved using PATHNLP by inserting the statement

option NLP = pathnlp;

somewhere before the solve statement. Similar comments hold for the other model types (LP, RMINLP, QCP, etc.) PATHNLP can handle.

The standard GAMS model options iterlim and reslim can be used to control PATHNLP. A description of these options can be found in the GAMS Options section of the chapter on basic solver usage. In general this is enough to use PATHNLP effectively. In some cases, however, you may want to use some of the PATH or PATHNLP options to gain further performance improvements or for other reasons. The rules for using an option file are described in the chapter on basic solver usage. The options used to control PATH can also be used to control PATHNLP. There are also some options unique to PATHNLP.

Options

The tables that follow describe the options unique to PATHNLP as well as the options shared with the PATH solver for MCP models.

General options

Option Description Default
chen_lambda lambda parameter for Chen-Chen-Kanzow residual
Range: [0, 1]
0.8
convergence_tolerance stopping criterion 1e-6
crash_iteration_limit maximum iterations allowed in crash 50
crash_merit_function merit function used in crash method
normal Use the normal map
fischer Use the Fischer function
fischer
crash_method pnewton or none
pnewton Use projected Newton method
none
pnewton
crash_minimum_dimension minimum problem dimension to perform crash 1
crash_nbchange_limit number of changes to the basis allowed 1
crash_perturb perturb the problem using pnewton crash 1
crash_searchtype search type to use in the crash method
line Use a linesearch
arc Use an arcsearch
line
cumulative_iteration_limit maximum minor iterations allowed 10000
gradient_searchtype search type to use on a gradient step
line Use a linesearch
arc Use an arcsearch
arc
gradient_step_limit gradient steps allowed before restarting 5
interrupt_limit ctrl-C's required before killing job
Range: [1, ∞]
5
major_iteration_limit maximum major iterations allowed 500
merit_function merit function to use (normal or fischer)
normal Use the normal map
fischer Use the Fischer function
fischer
minor_iteration_limit minor iterations allowed in each major iteration 1000
nms allow line searching, watch-dogging, and nonmonotone descent 1
nms_initial_reference_factor controls size of initial reference value 20
nms_maximum_watchdogs maximum number of watchdog steps allowed 5
nms_memory_size number of reference values kept 10
nms_mstep_frequency frequency at which m-steps are performed 10
nms_searchtype search type to use
line Use a linesearch
arc Use an arcsearch
line
option_file option file name for PATHLIB to read
preprocess turns preprocessing on/off 1
proximal_perturbation initial perturbation 0
time_limit number of seconds algorithm is allowed to run
lemke_rank_deficiency_iterations number of attempts made to fix rank-deficient basis during Lemke start 10
lemke_start frequency of lemke starts
always Use a Lemke start for each LCP subproblem
automatic Determined by algorithm
first Use a Lemke start for the first LCP subproblem
automatic
lemke_start_type type of lemke start
advanced Start Lemke method using an advanced basis
slack Start Lemke method using and all-slack basis
slack

NLP-specific options

Option Description Default
allow_reform substitute out objective var and equ when possible
Many models have an objective variable and equation that can be substituted out of the model, e.g. f(x) =E= z; If this option is true, PATHNLP will substitute out the objective variable and equation where possible.
1
gmo_hess_factor maximum multiples of Jacobian size to allow Hessian storage: 0=no limit 0
nlp_lambda linesearch factor when using the NLP objective
If nlp_objective is true and nlp_lambda is positive, the PATH linesearch will be altered to take the objective function into account.
0
nlp_objective treat NLP objective differently in PATH linesearch 0
output_memory output breakdown of where memory is used 0
skip_kkt go right to Phase I / Phase II method
If true, PATHNLP will skip the initial attempt to solve the KKT system for the NLP and go directly into a Phase I / Phase II method that first attempts to get feasible and then attempts to solve the KKT system starting from the feasible point found in Phase I.
0

Output options

Option Description Default
output_crash_iterations output information on crash iterations 1
output_crash_iterations_frequency frequency at which crash iteration log is printed
Range: [1, ∞]
1
output_errors output error messages 1
output_final_degeneracy_statistics print information regarding degeneracy at the solution 0
output_final_point output final point returned from PATH 0
output_final_point_statistics output information about the point, function, and Jacobian at the final point 1
output_final_scaling_statistics display matrix norms on the Jacobian at the final point 0
output_final_statistics output evaluation of available merit functions at the final point 1
output_final_summary output summary information 1
output_initial_point output initial point given to PATH 0
output_initial_point_statistics output information about the point, function, and Jacobian at the initial point 1
output_initial_scaling_statistics display matrix norms on the Jacobian at the initial point 1
output_initial_statistics output evaluation of available merit functions at the initial point 0
output_linear_model output linear model at each major iteration 0
output_major_iterations output information on major iterations 1
output_major_iterations_frequency frequency at which major iteration log is printed
Range: [1, ∞]
1
output_maximum_zero_listing limits zero columns reported to listing file 1000
output_maximum_zero_log limits zero columns reported to log file 10
output_minor_iterations output information on minor iterations 1
output_minor_iterations_frequency frequency at which minor iteration log is printed
Range: [1, ∞]
500
output_options output all options and their values 0
output no turns all output off 1
output_preprocess_level control output of preprocessing information 1
output_restart_log output options during restarts 1
output_time output breakdown of where time is spent 0
output_warnings output warning messages 0