IOR Preprint 3/2013
O. Stein, N. Sudermann-Merx:
On smoothness properties of optimal value functions at the boundary of their domain under complete convexity
Abstract: This article studies continuity and directional differentiability properties of optimal value functions, in particular at boundary points of their domain. We extend and complement standard continuity results from W.W. Hogan, Point-to-set maps in mathematical programming, SIAM Review, Vol. 15 (1973), 591-603, for abstract feasible set mappings under complete convexity as well as standard differentiability results from W.W. Hogan, Directional derivatives for extremal-value functions with applications to the completely convex case, Operations Research, Vol. 21 (1973), 188-209, for feasible set mappings in functional form under the Slater condition in the unfolded feasible set.
In particular, we present sufficient conditions for the inner semi-continuity of feasible set mappings and, using techniques from nonsmooth analysis, provide functional descriptions of tangent cones to the domain of the optimal value function. The latter makes the stated directional differentiability results accessible for practical applications.
IOR Preprint 2/2013
P. Kirst, O. Stein, P. Steuermann:
An enhanced spatial branch-and-bound method in global optimization with nonconvex constraints
Abstract: We discuss some difficulties in determining valid upper bounds in spatial branch-and-bound methods for global minimization in the presence of nonconvex constraints. In fact, two examples illustrate that standard techniques for the construction of upper bounds may fail in this setting. Instead, we propose to perturb infeasible iterates along Mangasarian-Fromovitz directions to feasible points whose objective function values serve as upper bounds. These directions may be calculated by the solution of a single linear optimization problem per iteration. Numerical results show that our enhanced algorithm performs well even for optimization problems where the standard branch-and-bound method does not converge to the correct optimal value.
IOR Preprint 1/2013
N. Harms, C. Kanzow, O. Stein:
Smoothness properties of a regularized gap function for quasi-variational inequalities
Abstract: This article studies continuity and differentiability properties for a reformulation of a finite-dimensional quasi-variational inequality (QVI) problem using a regularized gap function approach. For a special class of QVIs, this gap function is continuously differentiable everywhere, in general, however, it has nondifferentiability points. We therefore take a closer look at these nondifferentiability points and show, in particular, that under mild assumptions all locally minimal points of the reformulation are differentiability points of the regularized gap function. The results are specialized to generalized Nash equilibrium problems. Numerical results are also included and show that the regularized gap function provides a valuable approach for the solution of QVIs.