Numerical Methods for Disjunctive Programming

Scope of the proposed project is to develop efficient numerical methods for a class of mathematical programs with disunctive constraints. Prominent examples of such programs are given by equilibrium constraints or so-called vanishing constraints. Existing methods for solving such problems can be shown to converge only under some restrictive assumption and it cannot precluded that they converge to points where spurious directions of descent exist. Very recently the proposer has developed new stationarity concepts for the problem under consideration, which are based on generalized differentiation. The new algorithms shall rely on these new stationarity concepts and we want to prove global convergence properties under fairly mild assumptions. Further, superlinear convergence and the behaviour in the degenerate case are to be analyzed. The new method has a similar structure as the well-known SQP method from nonlinear programming: In each iteration step an auxialiary problem is solved, where a quadratic objective function built by an approximation of the Hessian of the Lagrangefunction and the gradient of the objective, is minimized over the linearization of the constarint. Then a search is performed along the arc computed when solving this auxiliary problem in order to reduce a suitable merit function.

Within this project, efficient numerical methods for a class of mathematical programs with disjunctive constraints were developed. Prominent examples of such programs are given by variational constraints or equilibrium constraints as appearing in bilevel optimization problems (Stackelber games). Another important type of such constraints are so-called vanishing constraints.Due to the disjunctive constraints such problems have a combinatorial structure which can be exactly handled only by some time-consuming enumeration procedure. Since the time effort for such techniques usually grows exponentially with the problem size, this approach is only feasible for small-sized problems.Therefore one often contents himself with local solutions or even stationary solutions, i.e. points which satisfy some necessary optimality conditions for a local minimizer.Convergence of existing methods can be shown only under some restrictive assumption. Moreover, it cannot precluded that these methods converge to points where spurious directions of descent exist.In this project, new theoretical solution concepts based on generalized differentiation were developed. These theoretical results formed the basis for a new, globally convergent algorithm. In each iteration step, some auxiliary problem with a quadratic objective and linear disjunctive constraints has to be solved. This is done by an algorithm based on a new stationarity concept which allows to resolve the inherent combinatorial structure of the auxiliary problem. Then the new iteration point is found by some search along a polygonal line built by the solution of the auxiliary problem. Numerical tests prove the efficiency and the reliability of the new method.