Search

Using counterdiabatic (CD) driving—aiming at suppression of diabatic transition—in digitized adiabatic evolution has garnered immense interest in quantum protocols and algorithms. However, improving the approximate CD terms with a nested commutator ansatz is a challenging task. In this work, we propose a technique of finding optimal coefficients of the CD terms using a variational quantum circuit. By classical optimization routines, the parameters of this circuit are optimized to provide the coefficients corresponding to the CD terms. Then their improved performance is exemplified in Greenberger–Horne–Zeilinger state preparation on the nearest-neighbour Ising model. Finally, we also show the advantage over the usual quantum approximation optimization algorithm, in terms of fidelity with bounded time. This article is part of the theme issue 'Shortcuts to adiabaticity: theoretical, experimental and interdisciplinary perspectives'. [ABSTRACT FROM AUTHOR]

It is well known that ergodicity and the strong law of large numbers (SLLN) play important roles in stochastic control and stochastic approximations. For a class of regime-switching functional diffusion processes with infinite delay, this paper establishes exponential ergodicity in a Wasserstein distance under certain "averaging conditions." It follows from such an ergodicity property that an SLLN for additive functionals of the regime-switching diffusions is obtained based on the property of uniform mixing. Finally, an example is presented to illustrate the application of ergodicity and the SLLN to a numerical algorithm for stochastic optimization. [ABSTRACT FROM AUTHOR]

In this study, we propose the use of a first-order gradient framework, the adaptive moment estimation (Adam), in conjunction with a stochastic gradient approximation, to well location and trajectory optimization problems. The Adam framework allows the incorporation of additional information from previous gradients to calculate variable-specific progression steps. As a result, this assists the search progression to be adjusted further for each variable and allows a convergence speed-up in problems where the gradients need to be approximated. We argue that under computational budget constraints, local optimization algorithms provide suitable solutions from a heuristic initial guess. Nonlinear constraints are taken into account to ensure the proposed solutions are not in violation of practical field considerations. The performance of the proposed algorithm is compared against steepest descent and generalized pattern search, using two case studies — the placement of four vertical wells and placement of 20 nonconventional (deviated, horizontal and/or slanted) wells. The results indicate that the proposed algorithm consistently outperforms the tested methods in terms computational efficiency and final optimum value. Additional discussions regarding nonconventional parameterization provide insights into simultaneous perturbation gradient approximations. [ABSTRACT FROM AUTHOR]

Field development and control optimization aim to maximize the economic profit of oil and gas production while considering several sources of uncertainty. This results in a high-dimensional optimization problem with a computationally demanding and uncertain objective function based on the simulated reservoir model. The limitations of many current robust optimization methods are: 1) it is single-level optimization (e.g. optimization of well locations/placement only; or of well production/injection control variables only) that ignores interference between the control variables from different levels; and 2) they provide a single optimal solution, whereas operational problems often add unexpected constraints likely to reduce that optimal, inflexible solution to a sub-optimal scenario. This paper presents a robust, multi-solution framework based on sequential iterative optimization of control variables at multiple levels using the Simultaneous Perturbation Stochastic Approximation (SPSA) optimization algorithm. A systematic realization selection process, tailored to the objective of the subsequent optimization stage, is used to select a small representative ensemble of reservoir model realizations to be used for calculating the expected objective value. The estimated gradients are calculated using a 1:1 ratio mapping ensemble of control variables perturbations at each iteration onto the ensemble of selected reservoir model realizations to reduce the computational cost. An ensemble of close-to-optimum solutions is then chosen from each level (e.g. from the well placement optimization level) and transferred to the next level of optimization (e.g. where the control settings are optimized), and this loop continues until no significant improvement is observed in the expected objective value. Fit-for-purpose clustering techniques are developed to systematically select an ensemble of solutions, with maximum differences in control variables but close-to-optimum objective values, at each optimization level. The proposed framework has been tested on a benchmark case study (Brugge field). Multiple solutions are obtained with different well locations and control settings but close-to-optimum objective values. We show that suboptimal solutions from an early optimization level can approach and even outdo the optimal one at the next level(s). Results demonstrate the advantage of the developed framework in more efficient exploration of the search space and providing the much-needed operational flexibility to field operators. [ABSTRACT FROM AUTHOR]

The present study applies a mathematical optimization method to solve the portfolio selection problem. This is formulated as a semi-infinite programming (SIP) problem and is solved by using a version of the stochastic outer approximation method in MATLAB. This method replaces the original problem with a sequence of optimization finite problems. The results are compared with other portfolio selection strategies such as Markowitz. Numerical experiments are performed using five years of data from eight Colombian companies that trade in the stock market. The results show that the SIP portfolio is similar to the minimum variance portfolio and that both are diversified portfolios. The maximum return portfolio is not diversified and should be discarded. Even though the naive portfolio is diversified, its performance and returns are lower than expected, but its risks are less than that of minimum variance and SIP. It is concluded that the proposed method provides satisfactory solutions when compared to the Markowitz method. [ABSTRACT FROM AUTHOR]

Quantum state tomography is a process for estimating an unknown quantum state; which is innately probabilistic. The exponential growth of unknown parameters to be estimated is a fundamental difficulty in realizing quantum state tomography for higher dimensions. Iterative optimization algorithms like self-guided quantum tomography have been effective in robust and accurate ascertaining a quantum state even with exponential growth in Hilbert space. We propose a faster convergent simultaneous perturbation stochastic approximation algorithm which is more practical in a resource-deprived situation for determining the underlying quantum states by incorporating the Barzilai–Borwein two-point step size gradient method with minimal loss of accuracy. [ABSTRACT FROM AUTHOR]

We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence { θ n } n ⩾ 0 of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function Ψ such that the geometric convergence of Ψ (θ n) implies – in the case of an optimization algorithm – the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for Ψ (θ n) to decrease at a geometric rate: Ψ should decrease "exponentially" along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by Ψ) should be bounded by Ψ (θ n) times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on Ψ (θ n) , so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains. [ABSTRACT FROM AUTHOR]

We present an unbiased online Monte Carlo method for rendering with many lights. Our method adapts both the hierarchical light clustering and the sampling distribution to our collected samples. Designing such a method requires us to make clustering decisions under noisy observation, and making sure that the sampling distribution adapts to our target. Our method is based on two key ideas: a coarse-to-fine clustering scheme that can find good clustering configurations even with noisy samples, and a discrete stochastic successive approximation method that starts from a prior distribution and provably converges to a target distribution. We compare to other state-of-the-art light sampling methods, and show better results both numerically and visually. [ABSTRACT FROM AUTHOR]

We consider a distributed stochastic optimization problem in networks with finite number of nodes. Each node adjusts its action to optimize the global utility of the network, which is defined as the sum of local utilities of all nodes. While Gradient descent method is a common technique to solve such optimization problem, the computation of the gradient may require much information exchange. In this paper, we consider that each node can only have a noisy numerical observation of its local utility, of which the closed-form expression is not available. This assumption is quite realistic, especially when the system is either too complex or constantly changing. Nodes may exchange partially the observation of their local utilities to estimate the global utility at each timeslot. We propose a distributed algorithm based on stochastic perturbation, under the assumption that each node has only part of the local utilities of the other nodes. We use stochastic approximation tools to prove that our algorithm converges almost surely to the optimum, given that the objective function is smooth and strictly concave. The convergence rate is also derived, under the additional assumption of strongly concave objective function. It is shown that the convergence rate scales as O (K−0.5) after a sufficient number of iterations K > K0, which is the optimal rate order in terms of K for our problem. Although the proposed algorithm can be applied to general optimization problems, we perform simulations for a typical power control problem in wireless networks and present numerical results to corroborate our claims. [ABSTRACT FROM AUTHOR]

This paper proposes a stochastic approximation method for solving a convex stochastic optimization problem over the fixed point set of a quasinonexpansive mapping. The proposed method is based on the existing adaptive learning rate optimization algorithms that use certain diagonal positive-definite matrices for training deep neural networks. This paper includes convergence analyses and convergence rate analyses for the proposed method under specific assumptions. Results show that any accumulation point of the sequence generated by the method with diminishing step-sizes almost surely belongs to the solution set of a stochastic optimization problem in deep learning. Additionally, we apply the learning methods based on the existing and proposed methods to classifier ensemble problems and conduct a numerical performance comparison showing that the proposed learning methods achieve high accuracies faster than the existing learning method. [ABSTRACT FROM AUTHOR]

• An efficient simulation system is proposed for the urban rail networked operation. • The interaction between passenger and train is delicately depicted in simulation. • A simulation-based constrained SPSA algorithm is used to coordinate train timetables. • The improved solution reduces passenger waiting time without adding operating cost. Synchronous optimization of train timetables is to solve the problem of train service coordination among different lines in the urban rail transit network, which can reduce passenger waiting time and subsequently enhance passenger satisfaction. This paper develops an efficient simulation system to reproduce the train operation of an urban rail network. It takes into account the realistic characteristics of urban rail operations, including time-dependent demand, dynamic dwell time, and train capacity constraint. In the simulations, both the train trajectories and the passenger waiting time can be easily obtained. On this basis, a simulation-based algorithm (i.e., simultaneous perturbation stochastic approximation, SPSA) is designed to search an improved flexible-interval dispatch solution in the network. A case study of the Chengdu urban rail transit network is implemented to verify the effectiveness of the simulation system and the optimization algorithm. The simulation system is found to be time efficient since it takes less than 1 s to simulate the network with 4 h of operation and more than 200,000 passengers. The optimization algorithm is also effective as it can reduce the average passenger waiting time by 9.52 % compared to the equal-interval dispatch solution without increasing the train service frequency. It is also found that the reduction in waiting time is mainly due to the improved coordination of train services in the transfer station. [ABSTRACT FROM AUTHOR]

Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and typically either rely on "light-tail" noise assumptions or exhibit worse sample complexity. In this work, we show that a wide class of stochastic optimization algorithms for strongly convex problems can be augmented with high confidence bounds at an overhead cost that is only logarithmic in the confidence level and polylogarithmic in the condition number. The procedure we propose, called proxBoost, is elementary and builds on two well-known ingredients: robust distance estimation and the proximal point method. We discuss consequences for both streaming (online) algorithms and offline algorithms based on empirical risk minimization. [ABSTRACT FROM AUTHOR]

This paper presents an energy-efficient downlink precoding scheme in a multi-cell Massive MIMO system. We approach the precoder design problem to maximize the system energy efficiency by jointly considering power control, interference management, antenna switching and user throughput in a cluster of base stations. This is computationally difficult as it requires solving a sparsity-inducing non-convex optimization problem, which is NP-hard. To alleviate the solution complexity, first a stochastic smooth approximation of zero-norm is applied in the antenna power management to enable fast, gradient-based algorithms. For efficient convergence, we develop a novel optimization algorithm combining augmented multiplier (AM) and quadratic programming (QP), and show how this scheme permits decentralized implementation by offloading parts of the computation to the individual base stations to reduce communication overhead. We provide theoretical proof that the proposed algorithm converges both locally and globally under realistic assumptions. Numerical results confirm that our method achieves higher energy efficiency with a superior convergence rate compared to different types of existing methods, and illustrate the relationship between energy efficiency performance and system design parameters. [ABSTRACT FROM AUTHOR]

Topology optimization under uncertainty (TOuU) often defines objectives and constraints by statistical moments of geometric and physical quantities of interest. Most traditional TOuU methods use gradient-based optimization algorithms and rely on accurate estimates of the statistical moments and their gradients, e.g., via adjoint calculations. When the number of uncertain inputs is large or the quantities of interest exhibit large variability, a large number of adjoint (and/or forward) solves may be required to ensure the accuracy of these gradients. The optimization procedure itself often requires a large number of iterations, which may render TOuU computationally expensive, if not infeasible. To tackle this difficulty, we here propose an optimization approach that generates a stochastic approximation of the objective, constraints, and their gradients via a small number of adjoint (and/or forward) solves, per optimization iteration. A statistically independent (stochastic) approximation of these quantities is generated at each optimization iteration. The total cost of this approach is only a small factor larger than that of the corresponding deterministic topology optimization problem. We incorporate the stochastic approximation of objective, constraints, and their design sensitivities into two classes of optimization algorithms. First, we investigate the stochastic gradient descent (SGD) method and a number of its variants, which have been successfully applied to large-scale optimization problems for machine learning. Second, we study the use of the proposed stochastic approximation approach within conventional nonlinear programming methods, focusing on the globally convergent method of moving asymptotes (GCMMA). The performance of these algorithms is investigated with structural design optimization problems utilizing a solid isotropic material with penalization (SIMP), as well as an explicit level set method. These investigations, conducted on both two- and three-dimensional structures, illustrate the efficacy of the proposed stochastic gradient approach for TOuU applications. [ABSTRACT FROM AUTHOR]

Large-Scale Parallel Bayesian Optimization Bayesian optimization is a machine-learning-based method for optimizing time-consuming-to-evaluate black-box objective functions without derivatives. It is most widely used for optimizing deep learning models, tuning systems through A/B testing, aircraft designing, and developing new materials and drugs. Bayesian optimization relies on optimizing a fast-to-evaluate function, called the acquisition function, to decide where to evaluate the time-consuming objective. This is easy for single-threaded objective function evaluations but is much harder when we want to evaluate the time-consuming objective in parallel. Wang et al. [1] provides a more efficient approach to optimizing the parallel version of the most widely used acquisition function for Bayesian optimization, expected improvement. This enables practical large-scale Bayesian optimization. Numerical experiments in Wang et al. [1] demonstrate this new approach scales to at least 128 parallel function evaluations. This new approach was a core component of the widely used open-source Bayesian optimization codebase, the Metrics Optimization Engine (MOE), and was also implemented within Facebook's Bayesian optimization codebase, BoTorch. [1] Jialei Wang, Scott C. Clark, Eric Liu, Peter I. Frazier, "Parallel Bayesian Global Optimization of Expensive Functions" We consider parallel global optimization of derivative-free expensive-to-evaluate functions, and propose an efficient method based on stochastic approximation for implementing a conceptual Bayesian optimization algorithm proposed by Ginsbourger in 2008. At the heart of this algorithm is maximizing the information criterion called the "multipoints expected improvement," or the q-EI. To accomplish this, we use infinitesimal perturbation analysis (IPA) to construct a stochastic gradient estimator and show that this estimator is unbiased. We also show that the stochastic gradient ascent algorithm using the constructed gradient estimator converges to a stationary point of the q-EI surface, and therefore, as the number of multiple starts of the gradient ascent algorithm and the number of steps for each start grow large, the one-step Bayes-optimal set of points is recovered. We show in numerical experiments using up to 128 parallel evaluations that our method for maximizing the q-EI is faster than methods based on closed-form evaluation using high-dimensional integration, when considering many parallel function evaluations, and is comparable in speed when considering few. We also show that the resulting one-step Bayes-optimal algorithm for parallel global optimization finds high-quality solutions with fewer evaluations than a heuristic based on approximately maximizing the q-EI. A high-quality open source implementation of this algorithm is available in the open source Metrics Optimization Engine (MOE). [ABSTRACT FROM AUTHOR]

Purpose: The purpose of this paper is to design a quadrotor with collective morphing using the simultaneous perturbation stochastic approximation (SPSA) optimization algorithm. Design/methodology/approach: Quadrotor design is made by using Solidworks drawing program and some mathematical performance relations. Modelling and simulation are performed in Matlab/Simulink program by using the state space model approaches with the parameters mostly taken from Solidworks. Proportional integral derivative (PID) approach is used as control technique. Morphing amount and the best PID coefficients are determined by using SPSA algorithm. Findings: By using SPSA algorithm, the amount of morphing and the best PID coefficients are determined, and the quadrotor longitudinal and lateral flights are made most stable via morphing. Research limitations/implications: It takes quite a long time to model the quadrotor in Solidworks and Matlab/Simulink with the state space model and using the SPSA algorithm. However, this situation is overcome with the proposed model. Practical implications: Optimization with SPSA is very useful in determining the amount of morphing and PID coefficients for quadrotors. Social implications: SPSA optimization method is useful in terms of cost, time and practicality. Originality/value: It is released to improve performance with morphing, to determine morphing rate with SPSA algorithm and to determine PID coefficients accordingly. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimizing an expectation function over a closed convex set, coupled with a function or expectation constraint on either decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the constraint on devision variables. We show that this algorithm exhibits the optimal O (1 / ϵ 2) rate of convergence, in terms of both optimality gap and constraint violation, when the objective and constraint functions are generally convex, where ϵ denotes the optimality gap and infeasibility. Moreover, we show that this rate of convergence can be improved to O (1 / ϵ) if the objective and constraint functions are strongly convex. We then present a variant of CSA, namely the cooperative stochastic parameter approximation (CSPA) algorithm, to deal with the situation when the constraint is defined over problem parameters and show that it exhibits similar optimal rate of convergence to CSA. It is worth noting that CSA and CSPA are primal methods which do not require the iterations on the dual space and/or the estimation on the size of the dual variables. To the best of our knowledge, this is the first time that such optimal SA methods for solving function or expectation constrained stochastic optimization are presented in the literature. [ABSTRACT FROM AUTHOR]

This paper introduces the stochastic Fejér-monotone hybrid steepest descent method (S-FM-HSDM) to solve affinely constrained and composite convex minimization tasks. The minimization task is not known exactly; noise contaminates the information about the composite loss function and the affine constraints. S-FM-HSDM generates sequences of random variables that, under certain conditions and with respect to a probability space, converge point-wise to solutions of the noiseless minimization task. S-FM-HSDM enjoys desirable attributes of optimization techniques such as splitting of variables and constant step size (learning rate). Furthermore, it provides a novel way of exploiting the information about the affine constraints via fixed-point sets of appropriate nonexpansive mappings. Among the offsprings of S-FM-HSDM, the hierarchical recursive least squares (HRLS) takes advantage of S-FM-HSDM's versatility toward affine constraints and offers a novel twist to LS by generating sequences of estimates that converge to solutions of a hierarchical optimization task: minimize a convex loss over the set of minimizers of the ensemble LS loss. Numerical tests on a sparsity-aware LS task show that HRLS compares favorably to several state-of-the-art convex, as well as non-convex, stochastic-approximation, and online-learning counterparts. [ABSTRACT FROM AUTHOR]

Stochastic computer simulations enable users to gain new insights into complex physical systems. Optimization is a common problem in this context: users seek to find model inputs that maximize the expected value of an objective function. The objective function, however, is time-intensive to evaluate, and cannot be directly measured. Instead, the stochastic nature of the model means that individual realizations are corrupted by noise. More formally, we consider the problem of optimizing the expected value of an expensive black-box function with continuously-differentiable mean, from which observations are corrupted by Gaussian noise. We present parallel simultaneous perturbation optimization (PSPO), which extends a well-known stochastic optimization algorithm, simultaneous perturbation stochastic approximation, in several important ways. Our modifications allow the algorithm to fully take advantage of parallel computing resources, like high-performance cloud computing. The resulting PSPO algorithm takes fewer time-consuming iterations to converge, automatically chooses the step size, and can vary the error tolerance by step. Theoretical results are supported by a numerical example. [ABSTRACT FROM AUTHOR]

We propose dynamic sampled stochastic approximation (SA) methods for stochastic optimization with a heavy-tailed distribution (with finite 2nd moment). The objective is the sum of a smooth convex function with a convex regularizer. Typically, it is assumed an oracle with an upper bound σ 2 on its variance (OUBV). Differently, we assume an oracle with multiplicative noise. This rarely addressed setup is more aggressive but realistic, where the variance may not be uniformly bounded. Our methods achieve optimal iteration complexity and (near) optimal oracle complexity. For the smooth convex class, we use an accelerated SA method a la FISTA which achieves, given tolerance ε > 0 , the optimal iteration complexity of O (ε - 1 2 ) with a near-optimal oracle complexity of O (ε - 2) [ ln (ε - 1 2 ) ] 2 . This improves upon Ghadimi and Lan (Math Program 156:59–99, 2016) where it is assumed an OUBV. For the strongly convex class, our method achieves optimal iteration complexity of O (ln (ε - 1)) and optimal oracle complexity of O (ε - 1) . This improves upon Byrd et al. (Math Program 134:127–155, 2012) where it is assumed an OUBV. In terms of variance, our bounds are local: they depend on variances σ (x ∗) 2 at solutions x ∗ and the per unit distance multiplicative variance σ L 2 . For the smooth convex class, there exist policies such that our bounds resemble, up to absolute constants, those obtained in the mentioned papers if it was assumed an OUBV with σ 2 : = σ (x ∗) 2 . For the strongly convex class such property is obtained exactly if the condition number is estimated or in the limit for better conditioned problems or for larger initial batch sizes. In any case, if it is assumed an OUBV, our bounds are thus sharper since typically max { σ (x ∗) 2 , σ L 2 } ≪ σ 2 . [ABSTRACT FROM AUTHOR]

In this paper, we propose a stochastic approximation algorithm for optimization of functions based on an adaptive extremum seeking method. The essence of this method is to approximate the gradient direction by introduction of a probing sequence, that is added to approximations and subsequently demodulated using an adaptive gain. Assuming that the probing and the demodulation signals are martingale difference sequences with adaptive diminishing gains, it is proved that the approximations converge almost surely to the optimizing value, under mild constraints on the measurement disturbance, and without assuming a priori boundedness of the approximation sequence. The measurement disturbance can contain a stochastic component, as well as a mean-square bounded deterministic component. The stochastic component can be nonstationary colored noise or a state-dependent random sequence. [ABSTRACT FROM AUTHOR]

Acquiring channel state information (CSI) at the base station (BS) is a critical requirement for successfully employing transmit beamforming in multiantenna systems. In practice, channel estimation/quantization errors, feedback delays, and fast fading can make it difficult to obtain accurate CSI at the BS. In this paper, we consider an outage-based approach for transmit beamforming in order to deal with the channel uncertainty at the BS. Our formulation is applicable to both point-to-point transmit beamforming as well as single-group multicasting scenarios. A key difference from prior works is that we do not assume knowledge of the underlying channel distribution; instead, stochastic approximation is used for computing approximate solutions of a nonconvex stochastic optimization problem via simple first-order methods (FOMs). We evaluate the performance of our FOMs in two settings: First) where we design a beamformer at the BS based on historical channel realizations collected over a relatively long time window before deployment, and second) in a post-deployment phase where we perform incremental updates of our beamformer based on intermittent, delayed, or peer feedback. Simulation results reveal the effectiveness of FOMs for our problem compared to other alternatives. [ABSTRACT FROM AUTHOR]

Concerning the discrete stochastic multi-attribute decision making (SMADM) problems in which attribute values are interval neutrosophic numbers and the attribute weight is incompletely known, a novel SMADM method based on the cumulative prospect theory (CPT) and generalized Shapley function is proposed. Firstly, the value prospect of each attribute under interval neutrosophic environment is calculated as well as subjective probability weights respectively, and the prospect function values are obtained according to the formulation of prospect function. Then, following the maximum deviation principle, the optimization model with respect to the incompletely known attribute weight information is constructed to obtain the optimal fuzzy measure, and the optimal weights of each attribute based on the formulation of generalized Shapley function are generated. Further, by aggregating the above prospect function values and the optimal weights, the values of the comprehensive prospect function are obtained and then alternatives are ranked. Finally, an illustrate example is presented to demonstrate the validity and feasibility of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we consider a modified version of the control problem in a model free Markov decision process (MDP) setting with large state and action spaces. The control problem most commonly addressed in the contemporary literature is to find an optimal policy which maximizes the value function, i.e., the long run discounted reward of the MDP. The current settings also assume access to a generative model of the MDP with the hidden premise that observations of the system behaviour in the form of sample trajectories can be obtained with ease from the model. In this paper, we consider a modified version, where the cost function is the expectation of a non-convex function of the value function without access to the generative model. Rather, we assume that a sample trajectory generated using a priori chosen behaviour policy is made available. In this restricted setting, we solve the modified control problem in its true sense, i.e., to find the best possible policy given this limited information. We propose a stochastic approximation algorithm based on the well-known cross entropy method which is data (sample trajectory) efficient, stable, robust as well as computationally and storage efficient. We provide a proof of convergence of our algorithm to a policy which is globally optimal relative to the behaviour policy. We also present experimental results to corroborate our claims and we demonstrate the superiority of the solution produced by our algorithm compared to the state-of-the-art algorithms under appropriately chosen behaviour policy. [ABSTRACT FROM AUTHOR]

In this paper, we study a resource allocation problem in which a group of agents cooperatively optimize a separable optimization problem with a linear network resource constraint and allocation feasibility constraints, where the global objective function is the sum of agents’ local objective functions. Each agent can only get noisy observations of its local gradient function and its local resource, which cannot be shared by other agents or transmitted to a center. There also exist communication uncertainties such as time-varying topologies (described by random graphs) and additive channel noises. To solve the resource allocation with uncertainties, we propose a stochastic approximation based distributed algorithm, and prove that agents can collaboratively achieve the optimal allocation with probability one by virtue of the ordinary differential equation (ODE) method for stochastic approximation. Finally, simulations related to the demand response management in power systems verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We consider stochastic influence maximization problems arising in social networks. In contrast to existing studies that involve greedy approximation algorithms with a 63% performance guarantee, our work focuses on solving the problem optimally. To this end, we introduce a new class of problems that we refer to as two-stage stochastic submodular optimization models. We propose a delayed constraint generation algorithm to find the optimal solution to this class of problems with a finite number of samples. The influence maximization problems of interest are special cases of this general problem class. We show that the submodularity of the influence function can be exploited to develop strong optimality cuts that are more effective than the standard optimality cuts available in the literature. Finally, we report our computational experiments with large-scale real-world datasets for two fundamental influence maximization problems, independent cascade and linear threshold, and show that our proposed algorithm outperforms the basic greedy algorithm of Kempe et al. (Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, KDD’03, New York, NY, USA, ACM, pp 137-146, 2003). [ABSTRACT FROM AUTHOR]

Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of an objective function being the sum of a data fidelity term and a penalization (e.g., a sparsity promoting function), Majorize-Minimize (MM) methods have recently attracted much interest since they are fast, highly flexible, and effective in ensuring convergence. The goal of this paper is to show how these methods can be successfully extended to the case when the data fidelity term corresponds to a least squares criterion and the cost function is replaced by a sequence of stochastic approximations of it. In this context, we propose an online version of an MM subspace algorithm and we study its convergence by using suitable probabilistic tools. Simulation results illustrate the good practical performance of the proposed algorithm associated with a memory gradient subspace, when applied to both nonadaptive and adaptive filter identification problems. [ABSTRACT FROM PUBLISHER]

In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle (SFO). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case iteration complexity. When a randomly chosen iterate is returned as the output of such an algorithm, we prove that in the worst case, the SFO-calls complexity is O(ε-2) to ensure that the expectation of the squared norm of the gradient is smaller than the given accuracy tolerance ε. We also propose a specific algorithm, namely, a stochastic damped limited-memory BFGS (SdLBFGS) method, that falls under the proposed framework. Moreover, we incorporate the stochastic variance reduced gradient variance reduction technique into the proposed SdLBFGS method and analyze its SFO-calls complexity. Numerical results on a nonconvex binary classification problem using a support vector machine and a multiclass classification problem using neural networks are reported. [ABSTRACT FROM AUTHOR]

To alleviate the excessive computational burden involved in topology optimizations, an efficient methodology for topology optimization is proposed. In the proposed methodology, a multi-scale on/off method is designed to avoid using infinite number of decision parameters; and a stochastic approximation method is employed to minimize the computational costs when computing the sensitivity information. Numerical results are reported to showcase the merits of the proposed methodology. [ABSTRACT FROM AUTHOR]

A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown n-dimensional real-/complex-valued signal \boldsymbol {x} from m “phaseless” quadratic equations of the form \psi _i=|\langle \boldsymbol a_i,\boldsymbol x\rangle | . This problem, also known as phase retrieval from magnitude-only information, is NP-hard in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that are useful when n is large. When \lbrace \boldsymbol a_i\rbrace i=1^m are independent Gaussian, STAF provably recovers exactly any \boldsymbol x\in \mathbbR^n exponentially fast based on order of n quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian \lbrace \boldsymbol {a}_i\rbrace vectors demonstrate that STAF empirically reconstructs any \boldsymbol x\in \mathbbR^n exactly from about 2.3n$ magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations $m=2n-1$ . Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives. [ABSTRACT FROM PUBLISHER]

We present a scalable computing framework for the solution stochastic multiobjective optimization problems. The proposed framework uses a nested conditional value-at-risk (nCVaR) metric to find compromise solutions among conflicting random objectives. We prove that the associated nCVaR minimization problem can be cast as a standard stochastic programming problem with expected value (linking) constraints. We also show that these problems can be implemented in a modular and compact manner using PLASMO (a Julia -based structured modeling framework) and can be solved efficiently using PIPS-NLP (a parallel nonlinear solver). We apply the framework to a CHP design study in which we seek to find compromise solutions that trade-off cost, water, and emissions in the face of uncertainty in electricity and water demands. [ABSTRACT FROM AUTHOR]

This paper introduces an optimization model of a multi-terminal, multi-modal maritime container port, such as the ones in the European northern range. The decisions concern the scheduling of ships, trains and trucks on terminals, while limiting inter-terminal transport of containers and minimizing weighted turnaround time. Heuristics based on the decomposition of the resulting mixed-integer program are proposed and tested on realistic generated instances with up to four terminals. The efficiency of the restrict-and-fix heuristic allows to investigate the impact of a global management on port’s performance: an average improvement of 5% was observed. [ABSTRACT FROM AUTHOR]

This paper presents a d -minimal cut based algorithm to evaluate the performance index R d +1 of a distribution network, defined as the probability that a specified demand d + 1 can be successfully distributed through stochastic arc capacities from the source to the destination. To improve the efficiency of solving d -minimal cuts, a novel technique is developed to determine the minimal capacities of arcs. Also, two new judging criteria are proposed to detect duplicate d -minimal cuts. Both theoretical and computational results indicate that our algorithm outperforms the existing methods. Furthermore, a real case study is provided to illustrate the application of the algorithm. [ABSTRACT FROM AUTHOR]

Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., the problem $$\min _x \mathbf{E}_v\left[ f_v\big (\mathbf{E}_w [g_w(x)]\big ) \right] .$$ In order to solve this stochastic composition problem, we propose a class of stochastic compositional gradient descent (SCGD) algorithms that can be viewed as stochastic versions of quasi-gradient method. SCGD update the solutions based on noisy sample gradients of $$f_v,g_{w}$$ and use an auxiliary variable to track the unknown quantity $$\mathbf{E}_w\left[ g_w(x)\right] $$ . We prove that the SCGD converge almost surely to an optimal solution for convex optimization problems, as long as such a solution exists. The convergence involves the interplay of two iterations with different time scales. For nonsmooth convex problems, the SCGD achieves a convergence rate of $$\mathcal {O}(k^{-1/4})$$ in the general case and $$\mathcal {O}(k^{-2/3})$$ in the strongly convex case, after taking k samples. For smooth convex problems, the SCGD can be accelerated to converge at a rate of $$\mathcal {O}(k^{-2/7})$$ in the general case and $$\mathcal {O}(k^{-4/5})$$ in the strongly convex case. For nonconvex problems, we prove that any limit point generated by SCGD is a stationary point, for which we also provide the convergence rate analysis. Indeed, the stochastic setting where one wants to optimize compositions of expected-value functions is very common in practice. The proposed SCGD methods find wide applications in learning, estimation, dynamic programming, etc. [ABSTRACT FROM AUTHOR]

We consider the minimization of a convex expectation-valued objective E[ƒ(x;ø*, ξ)] over a closed and convex set X in a regime where ø* is unavailable and ξ is a suitably deffened random variable. Instead, ø* may be obtained through the solution of a learning problem that requires minimizing a metric E[g(ø;η)] in ø over a closed and convex set ø. To resolve the absence of convergent efficient schemes, we present a coupled stochastic approximation scheme which simultaneously solves both the computational and the learning problems. The obtained schemes are shown to be equipped with almost sure convergence properties in regimes when the function ƒ is either strongly convex or merely convex. Importantly, the scheme displays the optimal rate for both strongly convex and convex problems where the rate statement in the latter regime necessitates the use of averaging. In the second part of the paper, we extend these statements to a class of stochastic variational inequality problems, an object that unifles stochastic convex optimization problems and a range of stochastic equilibrium problems. Analogous almost-sure convergence statements are provided in strongly monotone and merely monotone regimes, the latter facilitated by using an iterative Tikhonov regularization. Again, we note that the schemes admit the optimal rate in strongly monotone and monotone settings, where the latter result requires the additional assumption of weak sharpness. Preliminary numerics demonstrate the performance of the prescribed schemes. [ABSTRACT FROM AUTHOR]