A smoothing SAA method for a stochastic mathematical program with complementarity constraints

A smoothing sample average approximation (SAA) method based on the log-exponential function is proposed for solving a stochastic mathematical program with complementarity constraints (SMPCC) considered by Birbil et al. (S. I. Birbil, G. Gürkan, O. Listes: Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res. 31 (2006), 739–760). It is demonstrated that, under suitable conditions, the optimal solution of the smoothed SAA problem converges almost surely to that of the true problem as the sample size tends to infinity. Moreover, under a strong second-order sufficient condition for SMPCC, the almost sure convergence of Karash-Kuhn-Tucker points of the smoothed SAA problem is established by Robinson’s stability theory. Some preliminary numerical results are reported to show the efficiency of our method.     

A note on the sample average approximation method for stochastic mathematical programs with complementarity constraints

Meng and Xu (2006) [3] proposed a sample average approximation (SAA) method for solving a class of stochastic mathematical programs with complementarity constraints (SMPCCs). After showing that under some moderate conditions, a sequence of weak stationary points of SAA problems converge to a weak stationary point of the original SMPCC with probability approaching one at exponential rate as the sample size tends to infinity, the authors proposed an open question, that is, whether similar results can be obtained under some relatively weaker conditions. In this paper, we try to answer the open question. Based on the reformulation of stationary condition of MPCCs and new stability results on generalized equations, we present a similar convergence theory without any information of second order derivative and strict complementarity conditions. Moreover, we carry out convergence analysis of the regularized SAA method proposed by Meng and Xu (2006) [3] where the convergence results have not been considered.     

Stochastic mathematical programs with equilibrium constraints,modelling and sample average approximation

In this article, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate the structure of both–the lower level equilibrium solution and objective integrand. We show almost sure convergence of optimal values, optimal solutions (both local and global) and generalized Karush–Kuhn–Tucker points of the SAA program to their true counterparts. We also study uniform exponential convergence of the sample average approximations, and as a consequence derive estimates of the sample size required to solve the true problem with a given accuracy. Finally, we present some preliminary numerical test results.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Generalized Equation

The aim of this paper is to investigate the convergence properties for Mordukhovich’s coderivative of the solution map of the sample average approximation (SAA) problem for a parametric stochastic generalized equation. It is demonstrated that, under suitable conditions, both the cosmic deviation and the ρ-deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic generalized equation converge almost surely to zero as the sample size tends to infinity. Moreover, the exponential convergence rate of coderivatives of the solution maps to the SAA parametric generalized equations is established. The results are used to develop sufficient conditions for the consistency of the Lipschitz-like property of the solution map of SAA problem and the consistency of stationary points of the SAA estimator for a stochastic mathematical program with complementarity constraints.     

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.     

A log-exponential smoothing method for mathematical programs with complementarity constraints

In this paper a log-exponential smoothing method for mathematical programs with complementarity constraints (MPCC) is analyzed, with some new interesting properties and convergence results provided. It is shown that the stationary points of the resulting smoothed problem converge to the strongly stationary point of MPCC, under the linear independence constraint qualification (LICQ), the weak second-order necessary condition (WSONC), and some reasonable assumption. Moreover, the limit point satisfies the weak second-order necessary condition for MPCC. A notable fact is that the proposed convergence results do not restrict the complementarity constraint functions approach to zero at the same order of magnitude.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Variational Inequality

The aim of this paper is to investigate the convergence properties for Mordukhovich’s coderivative of the solution map of the sample average approximation (SAA) problem for a parametric stochastic variational inequality with equality and inequality constraints. The notion of integrated deviation is introduced to characterize the outer limit of a sequence of sets. It is demonstrated that, under suitable conditions, both the cosmic deviation and the integrated deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic variational inequality converge almost surely to zero as the sample size tends to infinity. Moreover, the exponential convergence rate of coderivatives of the solution maps to the SAA parametric stochastic variational inequality is established. The results are used to develop sufficient conditions for the consistency of the Lipschitz-like property of the solution map of SAA problem and the consistency of stationary points of the SAA estimator for a stochastic bilevel program.     

Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush–Kuhn–Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network.     

Approximating Stationary Points of Stochastic Mathematical Programs with Equilibrium Constraints via Sample Averaging

We investigate sample average approximation of a general class of one-stage stochastic mathematical programs with equilibrium constraints. By using graphical convergence of unbounded set-valued mappings, we demonstrate almost sure convergence of a sequence of stationary points of sample average approximation problems to their true counterparts as the sample size increases. In particular we show the convergence of M(Mordukhovich)-stationary point and C(Clarke)-stationary point of the sample average approximation problem to those of the true problem. The research complements the existing work in the literature by considering a general constraint to be represented by a stochastic generalized equation and exploiting graphical convergence of coderivative mappings.     

A special newton-type optimization method

The Kuhn–Tucker conditions of an optimization problem with inequality constraints are transformed equivalently into a special nonlinear system of equations T ₀(z) = 0. It is shown that Newton's method for solving this system combines two valuable properties: The local Q-quadratic convergence without assuming the strict complementary slackness condition and the regularity of the Jacobian of T ₀ at a point z under reasonable conditions, so that Newton’s method can be used also far from a Kuhn–Tucker point     

Convergence theory for nonconvex stochastic programming with an application to mixed logit

Monte Carlo methods have extensively been used and studied in the area of stochastic programming. Their convergence properties typically consider global minimizers or first-order critical points of the sample average approximation (SAA) problems and minimizers of the true problem, and show that the former converge to the latter for increasing sample size. However, the assumption of global minimization essentially restricts the scope of these results to convex problems. We review and extend these results in two directions: we allow for local SAA minimizers of possibly nonconvex problems and prove, under suitable conditions, almost sure convergence of local second-order solutions of the SAA problem to second-order critical points of the true problem. We also apply this new theory to the estimation of mixed logit models for discrete choice analysis. New useful convergence properties are derived in this context, both for the constrained and unconstrained cases, and associated estimates of the simulation bias and variance are proposed. Research Fellow of the Belgian National Fund for Scientific Research     

Stochastic Multiobjective Optimization: Sample Average Approximation and Applications

We investigate one stage stochastic multiobjective optimization problems where the objectives are the expected values of random functions. Assuming that the closed form of the expected values is difficult to obtain, we apply the well known Sample Average Approximation (SAA) method to solve it. We propose a smoothing infinity norm scalarization approach to solve the SAA problem and analyse the convergence of efficient solution of the SAA problem to the original problem as sample sizes increase. Under some moderate conditions, we show that, with probability approaching one exponentially fast with the increase of sample size, an ϵ-optimal solution to the SAA problem becomes an ϵ-optimal solution to its true counterpart. Moreover, under second order growth conditions, we show that an efficient point of the smoothed problem approximates an efficient solution of the true problem at a linear rate. Finally, we describe some numerical experiments on some stochastic multiobjective optimization problems and report preliminary results.     

Stochastic Optimization Problems with CVaR Risk Measure and Their Sample Average Approximation

We provide a refined convergence analysis for the SAA (sample average approximation) method applied to stochastic optimization problems with either single or mixed CVaR (conditional value-at-risk) measures. Under certain regularity conditions, it is shown that any accumulation point of the weak GKKT (generalized Karush-Kuhn-Tucker) points produced by the SAA method is almost surely a weak stationary point of the original CVaR or mixed CVaR optimization problems. In addition, it is shown that, as the sample size increases, the difference of the optimal values between the SAA problems and the original problem tends to zero with probability approaching one exponentially fast.     

Stability Analysis of One Stage Stochastic Mathematical Programs with Complementarity Constraints

We study the quantitative stability of the solution sets, optimal value and M-stationary points of one stage stochastic mathematical programs with complementarity constraints when the underlying probability measure varies in some metric probability space. We show under moderate conditions that the optimal solution set mapping is upper semi-continuous and the optimal value function is Lipschitz continuous with respect to probability measure. We also show that the set of M-stationary points as a mapping is upper semi-continuous with respect to the variation of the probability measure. A particular focus is given to empirical probability measure approximation which is also known as sample average approximation (SAA). It is shown that optimal value and M-stationary points of SAA programs converge to their true counterparts with probability one (w.p.1.) at exponential rate as the sample size increases.     

一般约束最优化的拟乘子—强次可行方向法

本文讨论一般等式和不等式约束的优化问题，首先提出了问题的拟Ｋｕｈｎ－Ｔｕｃｋｅｒ点和拟乘子法两个新概念，然后借助于不等式约束优化问题强次可行方向法的思想和技巧建立问题的两个新算法。     

Constraint Qualifications and Stationary Conditions for Mathematical Programming with Non-differentiable Vanishing Constraints

This paper aims at studying a broad class of mathematical programming with non-differentiable vanishing constraints. First, we are interested in some various qualification conditions for the problem. Then, these constraint qualifications are applied to obtain, under different conditions, several stationary conditions of type Karush/Kuhn–Tucker.     

Partial Exact Penalty for Mathematical Programs with Equilibrium Constraints

It is well known that mathematical programs with equilibrium constraints (MPEC) violate the standard constraint qualifications such as Mangasarian–Fromovitz constraint qualification (MFCQ) and hence the usual Karush–Kuhn–Tucker conditions cannot be used as stationary conditions unless relatively strong assumptions are satisfied. This observation has led to a number of weaker stationary conditions, with Mordukhovich stationary (M-stationary) condition being the strongest among the weaker conditions. In nonlinear programming, it is known that MFCQ leads to an exact penalization. In this paper we show that MPEC GMFCQ, an MPEC variant of MFCQ, leads to a partial exact penalty where all the constraints except a simple linear complementarity constraint are moved to the objective function. The partial exact penalty function, however, is nonsmooth. By smoothing the partial exact penalty function, we design an algorithm which is shown to be globally convergent to an M-stationary point under an extended version of the MPEC GMFCQ.     

Is bilevel programming a special case of a mathematical program with complementarity constraints?

Bilevel programming problems are often reformulated using the Karush–Kuhn–Tucker conditions for the lower level problem resulting in a mathematical program with complementarity constraints(MPCC). Clearly, both problems are closely related. But the answer to the question posed is “No” even in the case when the lower level programming problem is a parametric convex optimization problem. This is not obvious and concerns local optimal solutions. We show that global optimal solutions of the MPCC correspond to global optimal solutions of the bilevel problem provided the lower-level problem satisfies the Slater’s constraint qualification. We also show by examples that this correspondence can fail if the Slater’s constraint qualification fails to hold at lower-level. When we consider the local solutions, the relationship between the bilevel problem and its corresponding MPCC is more complicated. We also demonstrate the issues relating to a local minimum through examples.     

Convergence analysis of stationary points in sample average approximation of stochastic programs with second order stochastic dominance constraints

Sample average approximation (SAA) method has recently been applied to solve stochastic programs with second order stochastic dominance (SSD) constraints. In particular, Hu et al. (Math Program 133:171–201, 2012) presented a detailed convergence analysis of $\epsilon $ -optimal values and $\epsilon $ -optimal solutions of sample average approximated stochastic programs with polyhedral SSD constraints. In this paper, we complement the existing research by presenting convergence analysis of stationary points when SAA is applied to a class of stochastic minimization problems with SSD constraints. Specifically, under some moderate conditions we prove that optimal solutions and stationary points obtained from solving sample average approximated problems converge with probability one to their true counterparts. Moreover, by exploiting some recent results on large deviation of random functions and sensitivity analysis of generalized equations, we derive exponential rate of convergence of stationary points.     

An approximate strong KKT condition for multiobjective optimization

In this paper, we introduce a sequential approximate strong Karush–Kuhn–Tucker (ASKKT) condition for a multiobjective optimization problem with inequality constraints. We show that each local efficient solution satisfies the ASKKT condition, but weakly efficient solutions may not satisfy it. Subsequently, we use a so-called cone-continuity regularity (CCR) condition to guarantee that the limit of an ASKKT sequence converges to an SKKT point. Finally, under the appropriate assumptions, we show that the ASKKT condition is also a sufficient condition of properly efficient points for convex multiobjective optimization problems.