Solving quadratic convex bilevel programming problems using a smoothing method

In this paper, we present a smoothing sequential quadratic programming to compute a solution of a quadratic convex bilevel programming problem. We use the Karush-Kuhn-Tucker optimality conditions of the lower level problem to obtain a nonsmooth optimization problem known to be a mathematical program with equilibrium constraints; the complementary conditions of the lower level problem are then appended to the upper level objective function with a classical penalty. These complementarity conditions are not relaxed from the constraints and they are reformulated as a system of smooth equations by mean of semismooth equations using Fisher-Burmeister functional. Then, using a quadratic sequential programming method, we solve a series of smooth, regular problems that progressively approximate the nonsmooth problem. Some preliminary computational results are reported, showing that our approach is efficient.     

A general MPCC model and its solution algorithm for continuous network design problem

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.     

A Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints

We consider a mathematical program whose constraints involve a parametric P-matrix linear complementarity problem with the design (upper level) variables as parameters. Solutions of this complementarity problem define a piecewise linear function of the parameters. We study a smoothing function of this function for solving the mathematical program. We investigate the limiting behaviour of optimal solutions, KKT points and B-stationary points of the smoothing problem. We show that a class of mathematical programs with P-matrix linear complementarity constraints can be reformulated as a piecewise convex program and solved through a sequence of continuously differentiable convex programs. Preliminary numerical results indicate that the method and convex reformulation are promising.     

Solution of bilevel optimization problems using the KKT approach

ABSTRACT

Using the Karush–Kuhn–Tucker conditions for the convex lower level problem, the bilevel optimization problem is transformed into a single-level optimization problem (a mathematical program with complementarity constraints). A regularization approach for the latter problem is formulated which can be used to solve the bilevel optimization problem. This is verified if global or local optimal solutions of the auxiliary problems are computed. Stationary solutions of the auxiliary problems converge to C-stationary solutions of the mathematical program with complementarity constraints.     

Convergence Properties of a Smoothing Approach for Mathematical Programs with Second-Order Cone Complementarity Constraints

This paper discusses the convergence properties of a smoothing approach for solving the mathematical programs with second-order cone complementarity constraints (SOCMPCCs). We first introduce B-stationary, C-stationary, M(orduckhovich)-stationary, S-stationary point, SOCMPCC-linear independence constraint qualification (denoted by SOCMPCC-LICQ), second-order cone upper level strict complementarity (denoted by SOC-ULSC) condition at a feasible point of a SOCMPCC problem. With the help of the projection operator over a second-order cone, we construct a smooth optimization problem to approximate the SOCMPCC. We demonstrate that any accumulation point of the sequence of stationary points to the sequence of smoothing problems, when smoothing parameters decrease to zero, is a C-stationary point to the SOCMPCC under SOCMPCC-LICQ at the accumulation point. We also prove that the accumulation point is an M-stationary point if, in addition, the sequence of stationary points satisfy weak second order necessary conditions for the sequence of smoothing problems, and moreover it is a B-stationary point if, in addition, the SOC-ULSC condition holds at the accumulation point.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

Stochastic mathematical programs with hybrid equilibrium constraints

This paper considers a stochastic mathematical program with hybrid equilibrium constraints (SMPHEC), which includes either “here-and-now” or “wait-and-see” type complementarity constraints. An example is given to describe the necessity to study SMPHEC. In order to solve the problem, the sampling average approximation techniques are employed to approximate the expectations and smoothing and penalty techniques are used to deal with the complementarity constraints. Limiting behaviors of the proposed approach are discussed. Preliminary numerical experiments show that the proposed approach is applicable.     

Convergence of a continuous approach for zero-one programming problems

In this paper a new continuous formulation for the zero-one programming problem is presented, followed by an investigation of the algorithm for it. This paper first reformulates the zero-one programming problem as an equivalent mathematical programs with complementarity constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of approximate smooth variational principle, and with convergence properties established. To our benefit, the sequence of solutions generated converges to feasible solutions of the original problem, which provides a necessary basis for the convergence results.     

A Smoothing Method for Zero–One Constrained Extremum Problems

In this paper, the zero–one constrained extremum problem is reformulated as an equivalent smooth mathematical program with complementarity constraints (MPCC), and then as a smooth ordinary nonlinear programming problem with the help of the Fischer–Burmeister function. The augmented Lagrangian method is adopted to solve the resulting problem, during which the non-smoothness may be introduced as a consequence of the possible inequality constraints. This paper incorporates the aggregate constraint method to construct a uniform smooth approximation to the original constraint set, with approximation controlled by only one parameter. Convergence results are established, showing that under reasonable conditions the limit point of the sequence of stationary points generated by the algorithm is a strongly stationary point of the original problem and satisfies the second order necessary conditions of the original problem. Unlike other penalty type methods for MPCC, the proposed algorithm can guarantee that the limit point of the sequence is feasible to the original problem.     

隐互补约束优化问题的磨光SQP算法

本文提出了一类隐互补约束优化问题的磨光SQP算法.首先,我们给出了这类优化问题的最优性和约束规范性条件.然后,在适当假设条件下,我们证明了算法具有全局收敛性.     

非线性互补约束优化问题的可行性条件

本文研究了非线性互补约束优化问题的可行性条件，其中约束条件除互补问题外还包括第一水平(设计)变量和第二水平(状态)变量同时出现的其它非线性约束，它是线性互补约束优化问题的可行性条件的推广。     

Stationarity Conditions and Their Reformulations for Mathematical Programs with Vertical Complementarity Constraints

We consider the mathematical program with vertical complementarity constraints. We show that the min-max-min problems and the problems with max-min constraints can be reformulated as the above problem. As a complement of the work of Scheel and Scholtes in 2000, we derive the Mordukhovich-type stationarity conditions for the considered problem. We further reformulate various popular stationarity systems as nonlinear equations with simple constraints. A modified Levenberg–Marquardt method is employed to solve these constrained equations.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

A semismooth sequential quadratic programming method for lifted mathematical programs with vanishing constraints

Mathematical programs with vanishing constraints are a difficult class of optimization problems with important applications to optimal topology design problems of mechanical structures. Recently, they have attracted increasingly more attention of experts. The basic difficulty in the analysis and numerical solution of such problems is that their constraints are usually nonregular at the solution. In this paper, a new approach to the numerical solution of these problems is proposed. It is based on their reduction to the so-called lifted mathematical programs with conventional equality and inequality constraints. Special versions of the sequential quadratic programming method are proposed for solving lifted problems. Preliminary numerical results indicate the competitiveness of this approach.     

A note on stability of stationary points in mathematical programs with generalized complementarity constraints

We consider parameter-dependent mathematical programs with constraints governed by the generalized non-linear complementarity problem and with additional non-equilibrial constraints. We study a local behaviour of stationarity maps that assign the respective C- or M-stationarity points of the problem to the parameter. Using generalized differential calculus rules, we provide criteria for the isolated calmness and the Aubin properties of stationarity maps considered. To this end, we derive and apply formulas of some particular objects of the third-order variational analysis.     

Optimality Conditions for Nonsmooth Equilibrium Problems via Hadamard Directional Derivative

In this paper, we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. We obtain necessary conditions of Fritz John (FJ) and Karush-Kuhn-Tucker (KKT) types for a nonsmooth (MPEC) problem in terms of the lower Hadamard directional derivative. In particular sufficient conditions for MPECs are given where the involved functions have pseudoconvex sublevel sets. The functions with pseudoconvex sublevel sets is a class of generalized convex functions that include quasiconvex functions.     

Global Convergence of a Smooth Approximation Method for Mathematical Programs with Complementarity Constraints

A new smoothing approach was given for solving the mathematical programs with complementarity constraints (MPCC) by using the aggregation technique. As the smoothing parameter tends to zero, if the KKT point sequence generated from the smoothed problems satisfies the second-order necessary condition, then any accumulation point of the sequence is a B-stationary point of MPCC if the linear independence constraint qualification (LICQ) and the upper level strict complementarity (ULSC) condition hold at the limit point. The ULSC condition is weaker than the lower level strict complementarity (LLSC) condition generally used in the literatures. Moreover, the method can be easily extended to the mathematical programs with general vertical complementarity constraints.     

A new smoothing scheme for mathematical programs with complementarity constraints

In this paper, we consider a mathematical program with complementarity constraints (MPCC). We present a new smoothing scheme for this problem, which makes the primal structure of the complementarity part unchanged mostly. For the new smoothing problem, we show that the linear independence constraint qualification (LICQ) holds under some conditions. We also analyze the convergence behavior of the smoothing problem, and get some sufficient conditions such that an accumulation point of stationary points of the smoothing problems is C (M, B)-stationarity respectively. Based on the smoothing problem, we establish an algorithm to solve the primal MPCC problem. Some numerical experiments are given in the paper.     

First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints

In this paper we consider a mathematical program with semidefinite cone complementarity constraints (SDCMPCC). Such a problem is a matrix analogue of the mathematical program with (vector) complementarity constraints (MPCC) and includes MPCC as a special case. We first derive explicit formulas for the proximal and limiting normal cone of the graph of the normal cone to the positive semidefinite cone. Using these formulas and classical nonsmooth first order necessary optimality conditions we derive explicit expressions for the strong-, Mordukhovich- and Clarke- (S-, M- and C-)stationary conditions. Moreover we give constraint qualifications under which a local solution of SDCMPCC is a S-, M- and C-stationary point. Moreover we show that applying these results to MPCC produces new and weaker necessary optimality conditions.     

On the convergence of general regularization and smoothing schemes for mathematical programs with complementarity constraints

We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization.