Quantitative stability of full random two-stage problems with quadratic recourse

ABSTRACT

In this paper, we discuss quantitative stability of two-stage stochastic programs with quadratic recourse where all parameters in the second-stage problem are random. By establishing the Lipschitz continuity of the feasible set mapping of the restricted Wolfe dual of the second-stage quadratic programming in terms of the Hausdorff distance, we prove the local Lipschitz continuity of the integrand of the objective function of the two-stage stochastic programming problem and then establish quantitative stability results of the optimal values and the optimal solution sets when the underlying probability distribution varies under the Fortet–Mourier metric. Finally, the obtained results are applied to study the asymptotic behaviour of the empirical approximation of the model.     

不等式约束随机非线性规划的扰动Karush-Kuhn-Tucker系统的解路径

论文聚焦概率测度发生扰动时的随机非线性规划的稳定性分析的研究.目标函数的Lipschitz连续性和可行集值映射的度量正则性条件可保证最优解集合的外半连续性和最优值的Lipschitz连续性.更重要地,本文证明了,如果原问题的极小点处线性无关约束规范和强二阶充分性条件成立,那么存在一Lipschitz连续的解路径满足扰动问题的Karush-Kuhn-Tucker条件.     

Continuity and Stability of a Quadratic Mixed-Integer Stochastic Program

For the two-stage quadratic stochastic program where the second-stage problem is a general mixed-integer quadratic program with a random linear term in the objective function and random right-hand sides in constraints, we study continuity properties of the second-stage optimal value as a function of both the first-stage policy and the random parameter vector. We also present sufficient conditions for lower or upper semicontinuity, continuity, and Lipschitz continuity of the second-stage problem's optimal value function and the upper semicontinuity of the optimal solution set mapping with respect to the first-stage variables and/or the random parameter vector. These results then enable us to establish conclusions on the stability of optimal value and optimal solutions when the underlying probability distribution is perturbed with respect to the weak convergence of probability measures.     

极大极小随机规划逼近问题最优解集和最优值的稳定性

研究了特殊的二层极大极小随机规划逼近收敛问题. 首先将下层初始随机规划最优解集拓展到非单点集情形, 且可行集正则的条件下, 讨论了下层随机规划逼近问题最优解集关于上层决策变量参数的上半收敛性和最优值函数的连续性. 然后把下层随机规划的epsilon-最优解向量函数反馈到上层随机规划的目标函数中, 得到了上层随机规划逼近问题的最优解集关于最小信息概率度量收敛的上半收敛性和最优值的连续性.     

Quantitative stability of full random two-stage stochastic programs with recourse

In this paper, we consider quantitative stability analysis for two-stage stochastic linear programs when recourse costs, the technology matrix, the recourse matrix and the right-hand side vector are all random. For this purpose, we first investigate continuity properties of parametric linear programs. After deriving an explicit expression for the upper bound of its feasible solutions, we establish locally Lipschitz continuity of the feasible solution sets of parametric linear programs. These results are then applied to prove continuity of the generalized objective function derived from the full random second-stage recourse problem, from which we derive new forms of quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet–Mourier probability metric. The obtained results are finally applied to establish asymptotic behavior of an empirical approximation algorithm for full random two-stage stochastic programs.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

Quantitative Stability Analysis of Two-Stage Stochastic Linear Programs with Full Random Recourse

Abstract

In this paper, we apply the parametric linear programing technique and pseudo metrics to study the quantitative stability of the two-stage stochastic linear programing problem with full random recourse. Under the simultaneous perturbation of the cost vector, coefficient matrix, and right-hand side vector, we first establish the locally Lipschitz continuity of the optimal value function and the boundedness of optimal solutions of parametric linear programs. On the basis of these results, we deduce the locally Lipschitz continuity and the upper bound estimation of the objective function of the two-stage stochastic linear programing problem with full random recourse. Then by adopting different pseudo metrics, we obtain the quantitative stability results of two-stage stochastic linear programs with full random recourse which improve the current results under the partial randomness in the second stage problem. Finally, we apply these stability results to the empirical approximation of the two-stage stochastic programing model, and the rate of convergence is presented.     

非线性参数规划问题$\varepsilon$-最优解集集值映射的连续性

对非线性参数规划问题$\varepsilon$-最优解集集值映射的连续性条件进行了研究.首先在可行集集值映射局部有界且正则的条件下,讨论了非线性参数规划问题最优值函数的连续性,然后针对$\varepsilon$-最优解集集值映射的结构特征并利用此结果和集值分析理论,给出了非线性参数规划问题$\varepsilon$-最优解集集值映射连续的一个充分条件.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

UNIQUENESS OF VISCOSITY SOLUTIONS OF STOCHASTIC HAMILTON-JACOBI EQUATIONS

This article is devoted to the study of fully nonlinear stochastic Hamilton-Jacobi(HJ) equations for the optimal stochastic control problem of ordinary differential equations with random coefficients. Under the standard Lipschitz continuity assumptions on the coefficients, the value function is proved to be the unique viscosity solution of the associated stochastic HJ equation.     

Stability analysis of stochastic programs with second order dominance constraints

In this paper we present a stability analysis of a stochastic optimization problem with stochastic second order dominance constraints. We consider a perturbation of the underlying probability measure in the space of regular measures equipped with pseudometric discrepancy distance (Römisch in Stochastic Programming. Elsevier, Amsterdam, pp 483–554, 2003). By exploiting a result on error bounds in semi-infinite programming due to Gugat (Math Program Ser B 88:255–275, 2000), we show under the Slater constraint qualification that the optimal value function is Lipschitz continuous and the optimal solution set mapping is upper semicontinuous with respect to the perturbation of the probability measure. In particular, we consider the case when the probability measure is approximated by an empirical probability measure and show an exponential rate of convergence of the sequence of optimal solutions obtained from solving the approximation problem. The analysis is extended to the stationary points.     

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.     

Regularity properties in a state-constrained expected utility maximization problem

We consider a stochastic optimal control problem in a market model with temporary and permanent price impact, which is related to an expected utility maximization problem under finite fuel constraint. We establish the initial condition fulfilled by the corresponding value function and show its first regularity property. Moreover, we can prove the existence and uniqueness of an optimal strategy under rather mild model assumptions. This will then allow us to derive further regularity properties of the corresponding value function, in particular its continuity and partial differentiability. As a consequence of the continuity of the value function, we will prove a dynamic programming principle without appealing to the classical measurable selection arguments. This permits us to establish a tight relation between our value function and a nonlinear parabolic degenerated Hamilton–Jacobi–Bellman (HJB) equation with singularity. To conclude, we show a comparison principle, which allows us to characterize our value function as the unique viscosity solution of the HJB equation.     

Optimal control of Markovian jump processes with partial information and applications to a parallel queueing model

We consider a stochastic control problem over an infinite horizon where the state process is influenced by an unobservable environment process. In particular, the Hidden-Markov-model and the Bayesian model are included. This model under partial information is transformed into an equivalent one with complete information by using the well-known filter technique. In particular, the optimal controls and the value functions of the original and the transformed problem are the same. An explicit representation of the filter process which is a piecewise-deterministic process, is also given. Then we propose two solution techniques for the transformed model. First, a generalized verification technique (with a generalized Hamilton–Jacobi–Bellman equation) is formulated where the strict differentiability of the value function is weaken to local Lipschitz continuity. Second, we present a discrete-time Markovian decision model by which we are able to compute an optimal control of our given problem. In this context we are also able to state a general existence result for optimal controls. The power of both solution techniques is finally demonstrated for a parallel queueing model with unknown service rates. In particular, the filter process is discussed in detail, the value function is explicitly computed and the optimal control is completely characterized in the symmetric case.     

Lipschitz continuity and semiconcavity properties of the value function of a stochastic control problem

We investigate the Cauchy problem for a nonlinear parabolic partial differential equation of Hamilton–Jacobi–Bellman type and prove some regularity results, such as Lipschitz continuity and semiconcavity, for its unique viscosity solution. Our method is based on the possibility of representing such a solution as the value function of the associated stochastic optimal control problem. The main feature of our result is the fact that the solution is shown to be jointly regular in space and time without any strong ellipticity assumption on the Hamilton–Jacobi–Bellman equation.     

Stability of the Solution Set of Perturbed Nonsmooth Inequality Systems and Application

Stability properties of the solution set of generalized inequality systems with locally Lipschitz functions are obtained under a regularity condition on the generalized Jacobian and the Clarke tangent cone. From these results, we derive sufficient conditions for the optimal value function in a nonsmooth optimization problem to be continuous or locally Lipschitz at a given parameter.     

A one-parametric class of merit functions for the symmetric cone complementarity problem

In this paper, we extend the one-parametric class of merit functions proposed by Kanzow and Kleinmichel [C. Kanzow, H. Kleinmichel, A new class of semismooth Newton-type methods for nonlinear complementarity problems, Comput. Optim. Appl. 11 (1998) 227-251] for the nonnegative orthant complementarity problem to the general symmetric cone complementarity problem (SCCP). We show that the class of merit functions is continuously differentiable everywhere and has a globally Lipschitz continuous gradient mapping. From this, we particularly obtain the smoothness of the Fischer-Burmeister merit function associated with symmetric cones and the Lipschitz continuity of its gradient. In addition, we also consider a regularized formulation for the class of merit functions which is actually an extension of one of the NCP function classes studied by [C. Kanzow, Y. Yamashita, M. Fukushima, New NCP functions and their properties, J. Optim. Theory Appl. 97 (1997) 115-135] to the SCCP. By exploiting the Cartesian P-properties for a nonlinear transformation, we show that the class of regularized merit functions provides a global error bound for the solution of the SCCP, and moreover, has bounded level sets under a rather weak condition which can be satisfied by the monotone SCCP with a strictly feasible point or the SCCP with the joint Cartesian R₀₂-property. All of these results generalize some recent important works in [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104 (2005) 293-327; C.-K. Sim, J. Sun, D. Ralph, A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function, Math. Program. 107 (2006) 547-553; P. Tseng, Merit function for semidefinite complementarity problems, Math. Program. 83 (1998) 159-185] under a unified framework.     

On the Lipschitz Modulus of the Argmin Mapping in Linear Semi-Infinite Optimization

This paper is devoted to quantify the Lipschitzian behavior of the optimal solutions set in linear optimization under perturbations of the objective function and the right hand side of the constraints (inequalities). In our model, the set indexing the constraints is assumed to be a compact metric space and all coefficients depend continuously on the index. The paper provides a lower bound on the Lipschitz modulus of the optimal set mapping (also called argmin mapping), which, under our assumptions, is single-valued and Lipschitz continuous near the nominal parameter. This lower bound turns out to be the exact modulus in ordinary linear programming, as well as in the semi-infinite case under some additional hypothesis which always holds for dimensions n ? 3. The expression for the lower bound (or exact modulus) only depends on the nominal problem’s coefficients, providing an operative formula from the practical side, specially in the particular framework of ordinary linear programming, where it constitutes the sharp Lipschitz constant. In the semi-infinite case, the problem of whether or not the lower bound equals the exact modulus for n > 3 under weaker hypotheses (or none) remains as an open problem.     

参数弱向量平衡问题解集的似Holder性和相依导数

本文研究了一类参数弱向量平衡问题解集的似Hölder性和相依导数. 首先, 讨论了该问题的一类实值间隙函数的Lipschitz连续性和Hadamard方向可微性. 然后, 借助这些性质, 建立了该问题解集的似Hölder性和Hölder连续性以及相依导数的具体表达式.     

Nonlinear scalarizing functions in set optimization problems

In this paper, we obtain Hölder continuity of the nonlinear scalarizing function for l-type less order relation, which is introduced by Hernández and Rodríguez-Marín (J. Math. Anal. Appl. 2007;325:1–18). Moreover, we introduce the nonlinear scalarizing function for u-type less order relation and establish continuity, convexity and Hölder continuity of the nonlinear scalarizing function for u-type less order relation. As applications, we firstly obtain Lipschitz continuity of solution mapping to the parametric equilibrium problems and then establish Lipschitz continuity of strongly approximate solution mappings for l-type less order relation, u-type less order relation and set less order relation to the parametric set optimization problems by using convexity and Hölder continuity of the nonlinear scalarizing functions.