26.1. Semismooth Methods

TAO has two implementations of semismooth algorithms [(ref munson.facchinei.ea:semismooth),(ref deluca.facchinei.ea:semismooth),(ref facchinei.fischer.ea:semismooth)] for solving mixed complementarity problems. Both are based upon a reformulation of the mixed complementarity problem as a nonsmooth system of equations using the Fischer-Burmeister function [(ref fischer:special)]. A nonsmooth Newton method is applied to the reformulated system to calculate a solution. The theoretical properties of such methods are detailed in the aforementioned references.

The Fischer-Burmeister function, , is defined as,

This function has the following key property

used when reformulating the mixed complementarity problem the system of equations where . The reformulation is defined component-wise as

We note that is not differentiable everywhere, but satisfies a semismoothness property [(ref mifflin:semismooth),(ref qi:convergence),(ref qi.sun:nonsmooth)]. Furthermore, the natural merit function, , is continuously differentiable.

The two semismooth TAO solvers both solve the system by applying a nonsmooth newton method with a line-search. We calculate a direction, dk, by solving the system where Hk is an element of the B-subdifferential [(ref qi.sun:nonsmooth)] of at xk. If the direction calculated does not satisfy a suitable descent condition, then we use the negative gradient of the merit function, , as the search direction. A standard Armijo search [(ref armijo:minimization)] is used to find the new iteration. Non-monotone searches [(ref grippo.lampariello.ea:nonmonotone)] are also available by setting appropriate run-time options. See Section for further details.

The first semismooth algorithm available in TAO is not guaranteed to remain feasible with respect to the bounds, , and is termed an infeasible semismooth method. This method can be specified using the TaoMethod tao_ssils. In this case, the descent test used is that

Both and can be modified using the run-time commands -tao_ssils_delta <delta> and -tao_ssils_rho <rho> respectively. By default, and .

An alternative is to remain feasible with respect to the bounds by using a projected Armijo line-search. This method can be specified using the TaoMethod tao_ssfls. The descent test used is the same as above where the direction in this case corresponds to the first part of the piece-wise linear arc searched by the projected line-search. Both and can be modified using the run-time commands -tao_ssfls_delta <delta> and -tao_ssfls_rho <rho> respectively. By default, and .

The recommended algorithm is the infeasible semismooth method, tao_ssils, because of its strong global and local convergence properties. However, if it is known that F is not defined outside of the box, , perhaps due to the presence of log functions, the feasible algorithm, tao_ssfls, is a reasonable alternative.