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. With a demo or community license, 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
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 |