A stochastic algorithm for optimization problems with continua of inequalities

Optimization algorithms for solving mathematical programming problems involving continua of inequalities are presented. The algorithms use an outer-approximation method, by which they attempt to approximate, at each point, the maxima of sets of inequality constraints. They do so by performing random experiments, resulting in a finite number of points, over which the maximum is taken. They use constraint-dropping schemes, by which they eliminate points from the constraint set at hand, which are felt to be irrelevant. At each point that the algorithms construct, they evaluate a measure of optimality, which indicates the distance of the point from the set of solutions of the optimization problem. They use this measure to determine the number of random experiments performed. Thus, the number of such experiments tends to be small initially, when the points at hand are far from optimal, and they tend to increase when an optimal point is approached.     

A steepest-descent method for optimization of mechanical systems

Steepest-descent optimal control techniques have been used extensively for dynamic systems in one independent variable and with a full set of initial conditions. This paper presents an extension of the steepest-descent technique to mechanical design problems that are described by boundary-value problems with one or more independent variables. The method is illustrated by solving finite-dimensional problems, problems with distribution of design over one space dimension, and problems with distribution of design over two space dimensions.     

A finite branch-and-bound algorithm for two-stage stochastic integer programs

This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.The authors wish to acknowledge partial financial support from the IBM Research Division, ExxonMobil Upstream Research Company, and the National Science Foundation under awards DMI 95-02722, DMI 00-99726, and DMI 01-15166     

求解阵列天线自适应滤波问题的一种调比随机逼近算法

提出了求解阵列天线自适应滤波问题的一种调比随机逼近算法.每一步迭代中,算法选取调比的带噪负梯度方向作为新的迭代方向.相比已有的其他随机逼近算法,这个算法不需要调整稳定性常数,在一定程度上解决了稳定性常数选取难的问题.数值仿真实验表明,算法优于已有的滤波算法,且比经典Robbins-Monro （RM）算法具有更好的稳定性.     

A Strong Approximation Theorem for Stochastic Recursive Algorithms

The constant stepsize analog of Gelfand–Mitter type discrete-time stochastic recursive algorithms is shown to track an associated stochastic differential equation in the strong sense, i.e., with respect to an appropriate divergence measure.     

随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构,给出了原始。对偶（组合）3-近似算法．     

一类带有MaxEMin评判的补偿型随机规划算法

补偿型随机规划一般假定随机变量的概率分布具有完备信息, 但实际情况往往只能获得部分信息. 针对离散概率具有一类线性部分信息条件而建立了带有MaxEMin评判的两阶段随机规划模型, 借助二次规划和对偶分解方法得到了可行性切割和最优切割, 给出了基于L-型的求解算法, 并证明了算法的收敛性. 通过数值实验表明了算法的有效性.     

A regularized stochastic decomposition algorithm for two-stage stochastic linear programs

In this paper a regularized stochastic decomposition algorithm with master programs of finite size is described for solving two-stage stochastic linear programming problems with recourse. In a deterministic setting cut dropping schemes in decomposition based algorithms have been used routinely. However, when only estimates of the objective function are available such schemes can only be properly justified if convergence results are not sacrificed. It is shown that almost surely every accumulation point in an identified subsequence of iterates produced by the algorithm, which includes a cut dropping scheme, is an optimal solution. The results are obtained by including a quadratic proximal term in the master program. In addition to the cut dropping scheme, other enhancements to the existing methodology are described. These include (i) a new updating rule for the retained cuts and (ii) an adaptive rule to determine when additional reestimation of the cut associated with the current solution is needed. The algorithm is tested on problems from the literature assuming both descrete and continuous random variables.A majority of this work is part of the author's Ph.D. dissertation prepared at the University of Arizona in 1990.     

A stochastic approximation algorithm with multiplicative step size modification

An algorithm of searching a zero of an unknown function ϕ: ℝ → ℝ is considered: x _t = x _t−1 − γ _t−1 y _t , t = 1, 2, ..., where y _t = ϕ(x _t−1) + ξ _t is the value of ϕ measured at x _t−1 and ξ _t is the measurement error. The step sizes γ _t > 0 are modified in the course of the algorithm according to the rule: γ _t = min{uγ _t−1, } if y _t−1 y _t > 0, and γ _t = dγ _t−1, otherwise, where 0 < d < 1 < u, > 0. That is, at each iteration γ _t is multiplied either by u or by d, provided that the resulting value does not exceed the predetermined value . The function ϕ may have one or several zeros; the random values ξ _t are independent and identically distributed, with zero mean and finite variance. Under some additional assumptions on ϕ, ξ _t , and , the conditions on u and d guaranteeing a.s. convergence of the sequence {x _t }, as well as a.s. divergence, are determined. In particular, if P(ξ ₁ > 0) = P (ξ ₁ < 0) = 1/2 and P(ξ ₁ = x) = 0 for any x ∈ ℝ, one has convergence for ud < 1 and divergence for ud > 1. Due to the multiplicative updating rule for γ _t , the sequence {x _t } converges rapidly: like a geometric progression (if convergence takes place), but the limit value may not coincide with, but instead, approximate one of the zeros of ϕ. By adjusting the parameters u and d, one can reach arbitrarily high precision of the approximation; higher accuracy is obtained at the expense of lower convergence rate.      

On preserving long-time features of a linear stochastic oscillator

A method for the numerical solution of stochastic differential equations is presented. The method has mean-square order equal to 1/2 when it is applied to a general stochastic differential equation and equal to 1 if the equation has additive noise. In addition, it is shown that the method captures some long-time properties of a linear stochastic oscillator: It reproduces exactly the growth rate of the second moment and the oscillation property of the solution. AMS subject classification (2000)  60H10, 34F05, 65U05, 60K40     

Efficient solution of two-stage stochastic linear programs using interior point methods

Solving deterministic equivalent formulations of two-stage stochastic linear programs using interior point methods may be computationally difficult due to the need to factorize quite dense search direction matrices (e.g., AA ^T ). Several methods for improving the algorithmic efficiency of interior point algorithms by reducing the density of these matrices have been proposed in the literature. Reformulating the program decreases the effort required to find a search direction, but at the expense of increased problem size. Using transpose product formulations (e.g., A ^T A) works well but is highly problem dependent. Schur complements may require solutions with potentially near singular matrices. Explicit factorizations of the search direction matrices eliminate these problems while only requiring the solution to several small, independent linear systems. These systems may be distributed across multiple processors. Computational experience with these methods suggests that substantial performance improvements are possible with each method and that, generally, explicit factorizations require the least computational effort.     

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.     

An approximation of stochastic hyperbolic equations: case with Wiener process

In the present paper, the two‐step difference scheme for the Cauchy problem for the stochastic hyperbolic equation is presented. The convergence estimate for the solution of the difference scheme is established. In applications, the convergence estimates for the solution of difference schemes for the numerical solution of four problems for hyperbolic equations are obtained. The theoretical statements for the solution of this difference scheme are supported by the results of the numerical experiment. Copyright © 2012 John Wiley & Sons, Ltd.     

Monte-Carlo simulation of stochastic differential systems — a geometrical approach

We develop some numerical schemes for d$d$-dimensional stochastic differential equations derived from Milstein approximations of diffusions which are obtained by lifting the solutions of the stochastic differential equations to higher dimensional spaces using geometrical tools, in the line of the work [A.B. Cruzeiro, P. Malliavin, A. Thalmaier, Geometrization of Monte-Carlo numerical analysis of an elliptic operator: Strong approximation, C. R. Acad. Sci. Paris, Ser. I 338 (2004) 481–486].     

基于随机搜索的一个约束优化问题的全局收敛算法

讨论了具有一般约束的全局优化问题,给出该问题的一个随机搜索算法,证明了该算法依概率1收敛到问题的全局最优解．数值结果显示该方法是有效的．     

State-space stochastic volatility models: A review of estimation algorithms

Stochastic volatility models (SVMs) represent an important framework for the analysis of financial time series data, together with ARCH-type models; but unlike the latter, the former, at least from the statistical point of view, cannot rely on the possibility of obtaining exact inference, in particular with regard to maximum likelihood estimates for the parameters of interest. For SVMs, usually only approximate results can be obtained, unless particularly sophisticated estimation strategies like exact non-gaussian filtering methods or simulation techniques are employed. In this paper we review SVM and present a new characterization for them, called ‘generalized bilinear stochastic volatility’. © 1996 John Wiley & Sons, Ltd.     

小批量随机块坐标下降算法

针对机器学习中广泛存在的一类问题：结构化随机优化问题（其中“结构化”是指问题的可行域具有块状结构,且目标函数的非光滑正则化部分在变量块之间是可分离的）,我们研究了小批量随机块坐标下降算法（mSBD）。按照求解非复合问题和复合问题分别给出了基本的mSBD和它的变体,对于非复合问题,分析了算法在没有一致有界梯度方差假设情况下的收敛性质。而对于复合问题,在不需要通常的Lipschitz梯度连续性假设条件下得到了算法的收敛性。最后通过数值实验验证了mSBD的有效性。     

A resource portfolio planning model using sampling-based stochastic programming and genetic algorithm

Resource portfolio planning optimization is crucial to high-tech manufacturing industries. One of the most important characteristics of such a problem is intensive investment and risk in demands. In this study, a nonlinear stochastic optimization model is developed to maximize the expected profit under demand uncertainty. For solution efficiency, a stochastic programming-based genetic algorithm (SPGA) is proposed to determine a profitable capacity planning and task allocation plan. The algorithm improves a conventional two-stage stochastic programming by integrating a genetic algorithm into a stochastic sampling procedure to solve this large-scale nonlinear stochastic optimization on a real-time basis. Finally, the tradeoff between profits and risks is evaluated under different settings of algorithmic and hedging parameters. Experimental results have shown that the proposed algorithm can solve the problem efficiently.