On Optimality Conditions for Some Nonsmooth Optimization Problems over <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Spaces

The paper deals with the minimization of an integral functional over an L^p space subject to various types of constraints. For such optimization problems, new necessary optimality conditions are derived, based on several concepts of nonsmooth analysis. In particular, we employ the generalized differential calculus of Mordukhovich and the fuzzy calculus of proximal subgradients. The results are specialized to nonsmooth two-stage and multistage stochastic programs.The authors express their gratitude to Boris Mordukhovich (Detroit) for his extensive support during this research and to Marian Fabian (Prague) and Alexander Kruger (Ballarat) for valuable discussions. They are indebted also to two anonymous referees for helpful suggestions.The research of this author was partly supported by Grant 1075005 of the Czech Academy of SciencesThe research of this author was supported by the Deutsche Forschungsgemeinschaft     

Scenario tree reduction for multistage stochastic programs

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the L _r -distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.     

Generalized solutions of a stochastic partial differential equation

We discuss the Cauchy problem of a certain stochastic parabolic partial differential equation arising in the nonlinear filtering theory, where the initial data and the nonhomogeneous noise term of the equation are given by Schwartz distributions. The generalized (distributional) solution is represented by a partial (conditional) generalized expectation ofT(t)° _0,t ^–1 , whereT(t) is a stochastic process with values in distributions and _s,t is a stochastic flow generated by a certain stochastic differential equation. The representation is used for getting estimates of the solution with respect to Sobolev norms.Further, by applying the partial Malliavin calculus of Kusuoka-Stroock, we show that any generalized solution is aC -function under a condition similar to Hörmander's hypoellipticity condition.     

Stability in multistage stochastic programming

Multistage stochastic programs are regarded as mathematical programs in a Banach spaceX of summable functions. Relying on a result for parametric programs in Banach spaces, the paper presents conditions under which linearly constrained convex multistage problems behave stably when the (input) data process is subjected to (small) perturbations. In particular, we show the persistence of optimal solutions, the local Lipschitz continuity of the optimal value and the upper semicontinuity of optimal sets with respect to the weak topology inX. The linear case with deterministic first-stage decisions is studied in more detail.This research has been supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

Stochastic flows acting on Schwartz distributions

We define the compositionT° _s,t of a Schwartz distributionT with a stochastic flow _s,t generated by a stochastic differential equation. Then we establish a generalized Itô's formula for the composite processesT(t)° _s,t andT(t)° _s,t ^–1 , which describe a differential rule with respect to timet. The formula is then applied to two problems. One is the regularity of semigroups induced by the stochastic flow. The other is the existence and the continuity of the local time with respect to the spatial parameter, of a one dimensional stochastic flow.     

Implicit representation of generalized variable upper bounds in linear programming

In certain linear programs, especially those derived from integer programs, large numbers of constraints may have very simple form. Examples are:x _ij 1 (simple upper bounds [SUB]), _i x _ij = 1 (generalized upper bounds [GUB]) andx _ij y _i (variable upper bounds [VUB]). A class of constraints called generalized VUB [GVUB] is introduced which includes GUB and VUB as special cases. Also introduced is a method for representing GVUB constraints implicitly within the mechanics of the simplex method.Research supported in part by the Mobil Oil Corporation.     

Duality gaps in nonconvex stochastic optimization

We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.Mathematics Subject Classification (1991): 90C15Acknowledgments. This work was supported by the Priority Programme Online Optimization of Large Scale Systems of the Deutsche Forschungsgemeinschaft. The authors wish to thank Andrzej Ruszczyski (Rutgers University) for helpful discussions.     

Globally and superlinearly convergent trust-region algorithm for convex SC1-minimization problems and its application to stochastic programs

A function mapping from ⁿ to is called an SC¹-function if it is differentiable and its derivative is semismooth. A convex SC¹-minimization problem is a convex minimization problem with an SC¹-objective function and linear constraints. Applications of such minimization problems include stochastic quadratic programming and minimax problems. In this paper, we present a globally and superlinearly convergent trust-region algorithm for solving such a problem. Numerical examples are given on the application of this algorithm to stochastic quadratic programs.This work was supported by the Australian Research Council.We are indebted to Dr. Xiaojun Chen for help in the computation. We are grateful to two anonymous referees for their comments and suggestions, which improved the presentation of this paper.     

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.     

Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty

A dynamic (multi-stage) stochastic programming model for the weekly cost-optimal generation of electric power in a hydro-thermal generation system under uncertain demand (or load) is developed. The model involves a large number of mixed-integer (stochastic) decision variables and constraints linking time periods and operating power units. A stochastic Lagrangian relaxation scheme is designed by assigning (stochastic) multipliers to all constraints coupling power units. It is assumed that the stochastic load process is given (or approximated) by a finite number of realizations (scenarios) in scenario tree form. Solving the dual by a bundle subgradient method leads to a successive decomposition into stochastic single (thermal or hydro) unit subproblems. The stochastic thermal and hydro subproblems are solved by a stochastic dynamic programming technique and by a specific descent algorithm, respectively. A Lagrangian heuristics that provides approximate solutions for the first stage (primal) decisions starting from the optimal (stochastic) multipliers is developed. Numerical results are presented for realistic data from a German power utility and for numbers of scenarios ranging from 5 to 100 and a time horizon of 168 hours. The sizes of the corresponding optimization problems go up to 200000 binary and 350000 continuous variables, and more than 500000 constraints.     

Stochastic programming approach to optimization under uncertainty

In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the number of stages. We discuss an extension of coherent risk measures to a multistage setting and, in particular, dynamic programming equations for such problems.      

On spectral stability for the fractional Laplacian perturbed by unbounded obstacles

In this paper we give integral conditions for the stability of the absolutely continuous spectrum for the fractional Laplacian H₀ = , where α ∈ (0, 2), perturbed by an unbounded obstacle Γ ? R ^d . We use the stochastic representation of the associated semigroups to derive conditions in terms of the capacity of certain subsets of Γ. In particular, obstacles with infinite capacity are allowed (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Estimating the Diffusion Coefficient for Diffusions Driven by fBm

When the Hurst coefficient of a fBm B _t ^H is greater than 1/2, it is possible to define a stochastic integral with respect to B _t ^H as the pathwise limit of Riemann sums. In this article we consider diffusion equations of the type X_t = x₀ + ₀ ^T (X_s) dB_s ^H. We then construct a simple-to-use estimator of the diffusion coefficient (x), based on the number of crossings of level x of the process X _t. We then study consistency in probability of this estimator and calculate convergence rates in probability.     

Existence,uniqueness and invariant measures for stochastic semilinear equations on Hilbert spaces

Summary A class of stochastic evolution equations with additive noise and weakly continuous drift is considered. First, regularity properties of the corresponding Ornstein-Uhlenbeck transition semigroupR _t are obtained. We show thatR _t is a compactC ₀-semigroup in all Sobolev spacesW ^n,p which are built on its invariant measure . Then we show the existence, uniqueness, compactness and smoothing properties of the transition semigroup for semilinear equations inL ^p() spaces and spacesW ^1,p . As a consequence we prove the uniquencess of martingale solutions to the stochastic equation and the existence of a unique invariant measure equivalent to . It is shown also that the density of this measure with respect to is inL ^p() for allp1.This work was done during the first author's stay at UNSW supported by ARC Grant 150.346 and the second author's stay at ód University supported by KBN Grant 2.1020.91.01     

Finite element approximation of the volume-matching problem

Summary Optimal orderH ¹ andL error bounds are obtained for a continuous piecewise linear finite element approximation of the volume matching problem. This problem consists of minimising |v| _1, ² overvH ¹() subject to the inequality constraintv0 and a number of linear equality constraints. The presence of the equality constraints leads to Lagrange multipliers, which in turn lead to complications with the standard error analysis for variational inequalities. Finally we consider an algorithm for solving the resulting algebraic problem.Supported by a SERC research studentship     

A remark on the weak convergence of processes in the Skorohod topology

A Skorohod representation type theorem is proved for the weak convergence of stochastic processes in the Skorohod topology. This allows the time changes arising from the Skorohod topology to be considered as stochastic processes. While thenth time change processA _t ⁿ is not adapted to thenth filtration ( _t ⁿ ) _t0, it is possible to choose the processesA ⁿ such that they are adapted to, where, where _n is a sequence of constants decreasing to 0 asn tends to .Supported in part by NSF Grant No. DMS-9103454.     

CONVEX CONCENTRATION INEQUALITIES FOR CONTINUOUS GAS AND STOCHASTIC DOMINATION

In this article, we consider the continuous gas in a bounded domain ∧ of R^＋ or R^d described by a Gibbsian probability measure μη∧ associated with a pair interaction φ, the inverse temperature β, the activity z 〉 0, and the boundary condition η. Define F ∫ωf（s）wA（ds）. Applying the generalized Ito＇s formula for forward-backward martingales （see Klein et M. [5]）, we obtain convex concentration inequalities for F with respect to the Gibbs measure μη∧. On the other hand, by FKG inequality on the Poisson space, we also give a new simple argument for the stochastic domination for the Gibbs measure.     

A variable dimension algorithm with the Dantzig-Wolfe decomposition for structured stationary point problems

Given a set ofR ⁿ and a functionf from intoR ⁿ we consider a problem of finding a pointx ^* in such that(x–x ^*) ^t f(x ^*)0 holds for every pointx in. This problem is called the stationary point problem and the pointx ^* is called a stationary point. We present a variable dimension algorithm for solving the stationary point problem with an affine functionf on a polytope defined by constraints of linear equations and inequalities. We propose a system of equations whose solution set contains a piecewise linear path connecting a trivial starting point in with a stationary point. The path can be followed by solving a series of linear programs which inherit the structure of constraints of. The linear programs are solved efficiently with the Dantzig-Wolfe decomposition method by exploiting fully the structure.Part of this research was carried out when the first author was supported by the Center for Economic Research, Tilburg University, The Netherlands and the third author was supported by the Alexander von Humboldt-Foundation, Federal Republic of Germany.     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.