An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions

We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function.     

Block structured preconditioners in tensor form for the all-at-once solution of a finite volume fractional diffusion equation

We propose a tensor structured preconditioner for the tensor train GMRES algorithm (or TT-GMRES for short) to approximate the solution of the all-at-once formulation of time-dependent fractional partial differential equations discretized in time by linear multistep formulas used in boundary value form and in space by finite volumes.Numerical experiments show that the proposed preconditioner is efficient for very large problems and is competitive, in particular with respect to the AMEn algorithm.     

Distributionally robust chance constrained problem under interval distribution information

This paper is concerned with distributionally robust chance constrained problem under interval distribution information. Using worst-case CVaR approximation, we present a tractable convex programming approximation for distributionally robust individual chance constrained problem under interval sets of mean and covariance information. We prove the worst-case CVaR approximation problem is an exact form of the distributionally robust individual chance constrained problem. Then, our result is applied to worst-case Value-at-Risk optimization problem. Moreover, we discuss the problem under several ambiguous distribution information and investigate tractable approximations for distributionally robust joint chance constrained problem. Finally, we provide an illustrative example to show our results.     

Invariant discretization of partial differential equations admitting infinite-dimensional symmetry groups

This paper is concerned with the invariant discretization of differential equations admitting infinite-dimensional symmetry groups. By way of example, we first show that there are differential equations with infinite-dimensional symmetry groups that do not admit enough joint invariants preventing the construction of invariant finite difference approximations. To solve this shortage of joint invariants we propose to discretize the pseudo-group action. Computer simulations indicate that the numerical schemes constructed from the joint invariants of discretized pseudo-group can produce better numerical results than standard schemes.     

规避风险的多阶段最优库存研究

基于市场需求是随机的,并且在进行市场销售前,就要确定每个阶段的生产数量的背景下,建立了具有规避风险的多阶段库存凸随机规划模型.该模型以最小化损失函数的期望值为目标函数,以规避风险为约束条件,以价值风险(VaR)和条件价值风险(CVaR)为风险度量;采用样本平均近似方法(SAA)求解该模型,并分析样本平均近似方法的收敛性;最后,给出数值结果.     

Adaptive computation for boundary control of radiative heat transfer in glass

This paper is concerned with an optimal boundary control of the cooling down process of glass, an important step in glass manufacturing. Since the computation of the complete radiative heat transfer equations is too complex for optimization purposes, we use simplified approximations of spherical harmonics including a practically relevant frequency bands model. The optimal control problem is considered as a constrained optimization problem. A first-order optimality system is derived and decoupled with the help of a gradient method based on the solution to the adjoint equations. The arising partial differential–algebraic equations of mixed parabolic–elliptic type are numerically solved by a self-adaptive method of lines approach of Rothe type. Adaptive finite elements in space and one-step methods of Rosenbrock-type with variable step sizes in time are applied. We present numerical results for a two-dimensional glass cooling problem.     

Risk-averse feasible policies for large-scale multistage stochastic linear programs

We develop tractable semidefinite programming based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove that this approximation is exact for robust individual chance constraints with concave or (not necessarily concave) quadratic constraint functions, and we demonstrate that the Worst-Case CVaR can be computed efficiently for these classes of constraint functions. Next, we study the Worst-Case CVaR approximation for joint chance constraints. This approximation affords intuitive dual interpretations and is provably tighter than two popular benchmark approximations. The tightness depends on a set of scaling parameters, which can be tuned via a sequential convex optimization algorithm. We show that the approximation becomes essentially exact when the scaling parameters are chosen optimally and that the Worst-Case CVaR can be evaluated efficiently if the scaling parameters are kept constant. We evaluate our joint chance constraint approximation in the context of a dynamic water reservoir control problem and numerically demonstrate its superiority over the two benchmark approximations.     

Optimization methods for Dirichlet control problems

We discuss several optimization procedures to solve finite element approximations of linear-quadratic Dirichlet optimal control problems governed by an elliptic partial differential equation posed on a 2D or 3D Lipschitz domain. The control is discretized explicitly using continuous piecewise linear approximations. Unconstrained, control-constrained, state-constrained and control-and-state constrained problems are analysed. A preconditioned conjugate method for a reduced problem in the control variable is proposed to solve the unconstrained problem, whereas semismooth Newton methods are discussed for the solution of constrained problems. State constraints are treated via a Moreau–Yosida penalization. Convergence is studied for both the continuous problems and the finite dimensional approximations. In the finite dimensional case, we are able to show convergence of the optimization procedures even in the absence of Tikhonov regularization parameter. Computational aspects are also treated and several numerical examples are included to illustrate the theoretical results.     

On the comparison of risk-neutral and risk-averse newsvendor problems

The objective of this paper is to investigate and compare the relationship between risk-neutral and risk-averse newsvendor problems under three different decision criteria: expected utility (EU) maximization, mean-variance (MV) analysis, and conditional value-at-risk (CVaR) minimization. Several models in the literature have shown that for special cases of the newsvendor problem (eg, no salvage value, no shortage penalty, and with recourse option), a risk-averse newsvendor orders less than a risk-neutral newsvendor. First, we present an observation about the EU maximization models with such special cases where a risk-averse newsvendor orders less than a risk-neutral one. We note that this observation does not extend to the newsvendor problem with positive shortage penalty. Using several counterexamples, we demonstrate that the common wisdom that a risk-averse newsvendor orders less than a risk-neutral newsvendor is not true in general. Second, we demonstrate, analytically where possible and numerically if not, that the comparison of the optimal order quantities of risk-neutral and risk-averse newsvendors depends on the key assumptions regarding the model inputs, namely, the decision criterion, the demand distribution and the cost parameters such as shortage penalty and unit ordering cost. Third, we show that EU and the MV criteria yield consistent results while EU and CVaR criteria may yield consistent or conflicting results depending on the loss function used for the CVaR criterion.     

Tensor products and successive approximations for partial differential equations

A method for successive approximations for partial differential equations is presented. The limiting function in the process depends on the initial value. Convergence is proved by means of some identities and inequalities involving tensor products between multi-linear functions on a vector space. The author is an Alfred P. Sloan Research Fellow.     

Galerkin approximations with embedded boundary conditions for retarded delay differential equations

Finite-dimensional approximations are developed for retarded delay differential equations (DDEs). The DDE system is equivalently posed as an initial-boundary value problem consisting of hyperbolic partial differential equations (PDEs). By exploiting the equivalence of partial derivatives in space and time, we develop a new PDE representation for the DDEs that is devoid of boundary conditions. The resulting boundary condition-free PDEs are discretized using the Galerkin method with Legendre polynomials as the basis functions, whereupon we obtain a system of ordinary differential equations (ODEs) that is a finite-dimensional approximation of the original DDE system. We present several numerical examples comparing the solution obtained using the approximate ODEs to the direct numerical simulation of the original non-linear DDEs. Stability charts developed using our method are compared to existing results for linear DDEs. The presented results clearly demonstrate that the equivalent boundary condition-free PDE formulation accurately captures the dynamic behaviour of the original DDE system and facilitates the application of control theory developed for systems governed by ODEs.     

The risk-averse newsvendor problem with random capacity

We study the effect of capacity uncertainty on the inventory decisions of a risk-averse newsvendor. We consider two well-known risk criteria, namely Value-at-Risk (VaR) included as a constraint and Conditional Value-at-Risk (CVaR). For the risk-neutral newsvendor, we find that the optimal order quantity is not affected by the capacity uncertainty. However, this result does not hold for the risk-averse newsvendor problem. Specifically, we find that capacity uncertainty decreases the order quantity under the CVaR criterion. Under the VaR constraint, capacity uncertainty leads to an order decrease for low confidence levels, but to an order increase for high confidence levels. This implies that the risk criterion should be carefully selected as it has an important effect on inventory decisions. This is shown for the newsvendor problem, but is also likely to hold for other inventory control problems that future research can address.     

Solving stochastic systems with low-rank tensor compression

For parametrised equations, which arise, for example, in equations dependent on random parameters, the solution naturally lives in a tensor product space. The application which we have in mind is a stochastic linear elliptic partial differential equation (SPDE). Usual spatial discretisation leads to a potentially large linear system for each point in the parameter space. Approximating the parametric dependence by a Galerkin ‘ansatz’, the already large number of unknowns—for a fixed parameter value—is multiplied by the dimension of the Galerkin subspace for the parametric dependence, and thus can be very large. Therefore, we try to solve the total system approximately on a smaller submanifold which is found adaptively through compression during the solution process by alternating iteration and compression. We show that for general linearly converging stationary iterative schemes and general adaptation processes—which can be seen as a modification or perturbation of the iteration—the interlaced procedure still converges. Our proposed modification can be used for most stationary solvers for systems on tensor products. We demonstrate this on an example of a discretised SPDE with a simple preconditioned iteration. We choose a truncated singular value decomposition (SVD) for the compression and give details of the implementation, finishing with some examples.     

基于再生核三次样条基底的构造及其应用

将三次样条理论与再生核理论相结合,利用再生核函数巧妙地构造了三次样条函数空间的一组基底.基于三次样条插值的高收敛特点,得到了微分方程边值问题近似解的一种新的求解方法.数值算例展现出算法简单、有效.     

Explicit solution of the incompressible Navier–Stokes equations with linear finite elements

A three-field finite element scheme for the explicit iterative solution of the stationary incompressible Navier–Stokes equations is studied. In linearized form the scheme is associated with a generalized time-dependent Stokes system discretized in time. The resulting system of equations allows for a stable approximation of velocity, pressure and stress deviator tensor, by means of continuous piecewise linear finite elements, in both two- and three-dimensional space. Convergence in an appropriate sense applying to this finite element discretization is demonstrated, for the stationary Stokes system.     

Tensor Approximation of Generalized Correlated Diffusions and Functional Copula Operators

In this paper we develop a class of applied probabilistic continuous time but discretized state space decompositions of the characterization of a multivariate generalized diffusion process. This decomposition is novel and, in particular, it allows one to construct families of mimicking classes of processes for such continuous state and continuous time diffusions in the form of a discrete state space but continuous time Markov chain representation. Furthermore, we present this novel decomposition and study its discretization properties from several perspectives. This class of decomposition both brings insight into understanding locally in the state space the induced dependence structures from the generalized diffusion process as well as admitting computationally efficient representations in order to evaluate functionals of generalized multivariate diffusion processes, which is based on a simple rank one tensor approximation of the exact representation. In particular, we investigate aspects of semimartingale decompositions, approximation and the martingale representation for multidimensional correlated Markov processes. A new interpretation of the dependence among processes is given using the martingale approach. We show that it is possible to represent, in both continuous and discrete space, that a multidimensional correlated generalized diffusion is a linear combination of processes originated from the decomposition of the starting multidimensional semimartingale. This result not only reconciles with the existing theory of diffusion approximations and decompositions, but defines the general representation of infinitesimal generators for both multidimensional generalized diffusions and, as we will demonstrate, also for the specification of copula density dependence structures. This new result provides immediate representation of the approximate weak solution for correlated stochastic differential equations. Finally, we demonstrate desirable convergence results for the proposed multidimensional semimartingales decomposition approximations.     

Approximate solutions of partial differential equations by some Meshfree Greedy Algorithms

In this article, we use some greedy algorithms to avoid the ill‐conditioning of the final linear system in unsymmetric Kansa collocation method. The greedy schemes have the same background, but we use them in different settings. In the first algorithm, the optimal trial points for interpolation obtained among a huge set of initial points are used for numerical solution of partial differential equations (PDEs). In the second algorithm, based on the Kansa's method, the PDE is discretized to a finite number of test functional equations, and a greedy sparse discretization is applied for approximating the linear functionals. Each functional is stably approximated by some few trial points with an acceptable accuracy. The third greedy algorithm is used to generate the test points. This paper shows that the greedily selection of nodes yields a better conditioning in contrast with usual full meshless methods. Some well‐known PDE examples are solved and compared with the full unsymmetric Kansa's technique. © 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 1884–1899, 2017     

Interior‐point methods and preconditioning for PDE‐constrained optimization problems involving sparsity terms

Partial differential equation (PDE)–constrained optimization problems with control or state constraints are challenging from an analytical and numerical perspective. The combination of these constraints with a sparsity‐promoting L¹ term within the objective function requires sophisticated optimization methods. We propose the use of an interior‐point scheme applied to a smoothed reformulation of the discretized problem and illustrate that such a scheme exhibits robust performance with respect to parameter changes. To increase the potency of this method, we introduce fast and efficient preconditioners that enable us to solve problems from a number of PDE applications in low iteration numbers and CPU times, even when the parameters involved are altered dramatically.     

A porous thermoviscoelastic mixture problem: numerical analysis and computational experiments

In this paper, we study, from the numerical point of view, a porous thermoviscoelastic mixture problem. The mechanical problem is written as a linear coupled system of two hyperbolic partial differential equations for the porosities and a parabolic partial differential equation for the temperature field. An existence and uniqueness result and an energy decay property are stated. Then, fully discrete approximations are introduced by using the finite element method to approximate the spatial variable and the backward Euler scheme to discretize the time derivatives. A priori error estimates are proved from which, under suitable regularity conditions, the linear convergence of the algorithm is derived. Finally, some numerical simulations are presented to demonstrate the accuracy of the approximations in an academical one-dimensional example and the behaviour of the solutions in one- and two-dimensional problems.