Differentiability Conditions for Stochastic Hybrid Systems with Application to the Optimal Design of Microgrids

This article considers the regularity of expected value minimization problems subject to discrete-time stochastic hybrid systems. A primary motivation is the optimal design of microgrids subject to detailed operational simulations with renewable resources and discrete dispatching. For such problems, hybrid behavior can make the cost function discontinuous for any fixed realization of uncertainty, which has led to the widespread use of derivative-free optimizers with well-known limitations. In contrast, we provide sufficient conditions under which the expected value of the cost is continuously differentiable. We verify these conditions for a simple example and show promising preliminary optimization results using a stochastic gradient-descent method.     

Global optimization of bounded factorable functions with discontinuities

A deterministic global optimization method is developed for a class of discontinuous functions. McCormick’s method to obtain relaxations of nonconvex functions is extended to discontinuous factorable functions by representing a discontinuity with a step function. The properties of the relaxations are analyzed in detail; in particular, convergence of the relaxations to the function is established given some assumptions on the bounds derived from interval arithmetic. The obtained convex relaxations are used in a branch-and-bound scheme to formulate lower bounding problems. Furthermore, convergence of the branch-and-bound algorithm for discontinuous functions is analyzed and assumptions are derived to guarantee convergence. A key advantage of the proposed method over reformulating the discontinuous problem as a MINLP or MPEC is avoiding the increase in problem size that slows global optimization. Several numerical examples for the global optimization of functions with discontinuities are presented, including ones taken from process design and equipment sizing as well as discrete-time hybrid systems.     

Optimization of Nonlinear Mechanical Systems under Constraints with the Particle Swarm Method

In recent years, stochastic optimization methods have gained increasing attention in parameter optimization of mechanical systems. Most popular techniques are Evolutionary Computation and the Simulating Annealing algorithm, which are applied more frequently to mechanical problems due to the increasing computing resources available now. Since theses methods do not require any gradient information, they are well suited for non‐smooth or discontinuous optimization tasks occurring in nonlinear multibody systems. In addition to these techniques, Kennedy and Eberhart [5] introduced the Particle Swarm Optimization method (PSO) based on the simulation of bird flocking. In this work, the efficiency of an extended PSO algorithm has been compared with an Evolutionary Strategy (ES) [6] and an Adapted Simulated Annealing method (ASA) [4]. In order to solve optimization tasks with both equality and inequality constraints the PSO algorithm has been extended by the Augmented Lagrangian Multiplier Method [2]. The proposed method shows often superior results and is quite simple to implement. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A self-organizing state space model and simplex initial distribution search

This paper proposes a method to seek initial distributions of parameters for a self-organizing state space model proposed by Kitagawa (J Am Stat Assoc 93:1203–1215, 1998). Our method is based on the simplex Nelder–Mead algorithm for solving nonlinear and discontinuous optimization problems. We show the effectiveness of our method by applying it to a linear Gaussian model, a linear non-Gaussian model, a nonlinear Gaussian model, and a stochastic volatility model.     

Finite-time dissipative control for singular discrete-time Markovian jump systems with actuator saturation and partly unknown transition rates

In this work, the finite-time dissipative control problem is considered for singular discrete-time Markovian jumping systems with actuator saturation and partly unknown transition rates. By constructing a proper Lyapunov–Krasonski functional and the method of linear matrix inequalities (LMIs), sufficient conditions that ensure the systems singular stochastic finite-time stability and singular stochastic finite-time dissipative are obtained. Then, the state feedback controllers are designed, and in order to get the optimal values of the dissipative level, the results are extended to LMI convex optimization problems. Finally, numerical examples are given to illustrate the validity of the proposed methods.     

Connective Stability of Discontinuous Dynamic Systems

Connective stability is defined for interconnected systems under discontinuous structural perturbations. Stability conditions are established using Lipschitz and C¹-type Lyapunov functions. A considerable flexibility of the conditions is achieved by assuming the functions to be parameter dependent. For efficient testing, the obtained stability conditions are converted to convex optimization problems via the theory of M-matrices.     

The Million-Variable “March” for Stochastic Combinatorial Optimization

Combinatorial optimization problems have applications in a variety of sciences and engineering. In the presence of data uncertainty, these problems lead to stochastic combinatorial optimization problems which result in very large scale combinatorial optimization problems. In this paper, we report on the solution of some of the largest stochastic combinatorial optimization problems consisting of over a million binary variables. While the methodology is quite general, the specific application with which we conduct our experiments arises in stochastic server location problems. The main observation is that stochastic combinatorial optimization problems are comprised of loosely coupled subsystems. By taking advantage of the loosely coupled structure, we show that decomposition-coordination methods provide highly effective algorithms, and surpass the scalability of even the most efficiently implemented backtracking search algorithms.     

Online stochastic reservation systems

This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overbooking are examples of such online stochastic reservations. The paper studies how to adapt the online stochastic framework and the consensus and regret algorithms proposed earlier to online stochastic reservation systems. On the theoretical side, it presents a constant sub-optimality approximation of multi-knapsack problems, leading to a regret algorithm that evaluates each scenario with a single mathematical programming optimization followed by a small number of dynamic programs for one-dimensional knapsacks. It also proposes several integer programming models for handling cancellations and proves their equivalence. On the experimental side, the paper demonstrates the effectiveness of the regret algorithm on multi-knapsack problems (with and without overbooking) based on the benchmarks proposed earlier.     

Tractable stochastic analysis in high dimensions via robust optimization

Modern probability theory, whose foundation is based on the axioms set forth by Kolmogorov, is currently the major tool for performance analysis in stochastic systems. While it offers insights in understanding such systems, probability theory, in contrast to optimization, has not been developed with computational tractability as an objective when the dimension increases. Correspondingly, some of its major areas of application remain unsolved when the underlying systems become multidimensional: Queueing networks, auction design in multi-item, multi-bidder auctions, network information theory, pricing multi-dimensional options, among others. We propose a new approach to analyze stochastic systems based on robust optimization. The key idea is to replace the Kolmogorov axioms and the concept of random variables as primitives of probability theory, with uncertainty sets that are derived from some of the asymptotic implications of probability theory like the central limit theorem. In addition, we observe that several desired system properties such as incentive compatibility and individual rationality in auction design are naturally expressed in the language of robust optimization. In this way, the performance analysis questions become highly structured optimization problems (linear, semidefinite, mixed integer) for which there exist efficient, practical algorithms that are capable of solving problems in high dimensions. We demonstrate that the proposed approach achieves computationally tractable methods for (a) analyzing queueing networks, (b) designing multi-item, multi-bidder auctions with budget constraints, and (c) pricing multi-dimensional options.     

Implementable Algorithm for Stochastic Optimization Using Sample Average Approximations

We develop an implementable algorithm for stochastic optimization problems involving probability functions. Such problems arise in the design of structural and mechanical systems. The algorithm consists of a nonlinear optimization algorithm applied to sample average approximations and a precision-adjustment rule. The sample average approximations are constructed using Monte Carlo simulations or importance sampling techniques. We prove that the algorithm converges to a solution with probability one and illustrate its use by an example involving a reliability-based optimal design.     

Optimization with multivariate stochastic dominance constraints

We consider stochastic optimization problems where risk-aversion is expressed by a stochastic ordering constraint. The constraint requires that a random vector depending on our decisions stochastically dominates a given benchmark random vector. We identify a suitable multivariate stochastic order and describe its generator in terms of von Neumann–Morgenstern utility functions. We develop necessary and sufficient conditions of optimality and duality relations for optimization problems with this constraint. Assuming convexity we show that the Lagrange multipliers corresponding to dominance constraints are elements of the generator of this order, thus refining and generalizing earlier results for optimization under univariate stochastic dominance constraints. Furthermore, we obtain necessary conditions of optimality for non-convex problems under additional smoothness assumptions.     

Stochastic design optimization of asynchronous flexible assembly systems

This paper presents the application of the stochastic quasigradient method (SQG) of Ermoliev and Gaivaronski to the performance optimization of asynchronous flexible assembly systems (AFAS). These systems are subject to blocking and starvation effects that make complete analytic performance modeling difficult. A hybrid algorithm is presented in this paper which uses a queueing network model to set the number of pallets in the system and then an SQG algorithm is used to set the buffer spacings to obtain optimal system throughput. Different forms of the SQG algorithm are examined and the specification of optimal buffer sizes and pallet numbers for a variety of assembly systems with ten stations are discussed. The combined Network-SQG method appears to perform well in obtaining a near optimal solution in this discrete optimization example, even though the SQG method was primarily designed for application to differentiable performance functionals. While a number of both theoretical and practical problems remain to be resolved, a heuristic version of the SQG method appears to be a reasonable technique for analyzing optimization problems for certain complex manufacturing systems.     

Stochastic intermediate gradient method for convex optimization problems

New first-order methods are introduced for solving convex optimization problems from a fairly broad class. For composite optimization problems with an inexact stochastic oracle, a stochastic intermediate gradient method is proposed that allows using an arbitrary norm in the space of variables and a prox-function. The mean rate of convergence of this method and the probability of large deviations from this rate are estimated. For problems with a strongly convex objective function, a modification of this method is proposed and its rate of convergence is estimated. The resulting estimates coincide, up to a multiplicative constant, with lower complexity bounds for the class of composite optimization problems with an inexact stochastic oracle and for all usually considered subclasses of this class.     

Scenario reduction for stochastic programs with Conditional Value-at-Risk

In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem easier to solve. The majority of works for scenario reduction are designed for classical risk-neutral stochastic optimization problems; however, it is intuitive that in the risk-averse case one is more concerned with scenarios that correspond to high cost. By building upon the notion of effective scenarios recently introduced in the literature, we formalize that intuitive idea and propose a scenario reduction technique for stochastic optimization problems where the objective function is a Conditional Value-at-Risk. Numerical results presented with problems from the literature illustrate the performance of the method and indicate the cases where we expect it to perform well.     

Finite difference approximations of optimal control problems for semilinear elliptic equations with discontinuous coefficients and solutions

Mathematical formulation of nonlinear optimal control problems for semilinear elliptic equations with discontinuous coefficients and discontinuous solutions are examined. Finite difference approximations of optimization problems are constructed, and the approximation error is estimated with respect to the state and the cost functional. Weak convergence of the approximations with respect to the control is proved. The approximations are regularized using Tikhonov regularization.     

Optimal consumption problems in discontinuous markets

We study an extension of Merton’s classical portfolio investment – consumption optimization problem (1969–1970) to a particular case of complete discontinuous market, with a single jump. The market consists of a non-risky asset, a ‘standard risky’ asset and a risky asset with discontinuous price dynamics (e.g. a defaultable bond or a mortality linked security). We consider three different problems of maximization of the expected utility from consumption: in the case when the investment horizon is fixed and finite, when it is finite, but possibly uncertain and when it is infinite. The innovative setting is the second one. In a general stochastic coefficients’ model, we solve the problems and we compare the three optimal consumption rates, finding quite interesting results. In the logarithmic and power utility cases, explicit solutions are provided. Furthermore, the benchmark – constant coefficients’ case is deeply investigated and a partial information setting is also studied in the uncertain time horizon case.     

Random-Direction Optimization Algorithms with Applications to Threshold Controls

This work develops a class of stochastic optimization algorithms. It aims to provide numerical procedures for solving threshold-type optimal control problems. The main motivation stems from applications involving optimal or suboptimal hedging policies, for example, production planning of manufacturing systems including random demand and stochastic machine capacity. The proposed algorithm is a constrained stochastic approximation procedure that uses random-direction finite-difference gradient estimates. Under fairly general conditions, the convergence of the algorithm is established and the rate of convergence is also derived. A numerical example is reported to demonstrate the performance of the algorithm.     

Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models

This paper proposes a new method that extends the efficient global optimization to address stochastic black-box systems. The method is based on a kriging meta-model that provides a global prediction of the objective values and a measure of prediction uncertainty at every point. The criterion for the infill sample selection is an augmented expected improvement function with desirable properties for stochastic responses. The method is empirically compared with the revised simplex search, the simultaneous perturbation stochastic approximation, and the DIRECT methods using six test problems from the literature. An application case study on an inventory system is also documented. The results suggest that the proposed method has excellent consistency and efficiency in finding global optimal solutions, and is particularly useful for expensive systems.     

Variational problems in the theory of optimum processes

This paper presents a review of the optimization problems for control processes described by ordinary differential equations and of the variational methods for solving these problems. The following cases are studied: problems with constraints on the controls or the coordinates, problems described by equations with discontinuous right-hand sides, problems with functionals depending on intermediate coordinates, and problems with given discontinuities in the coordinates. Variational problems of synthesis of optimal systems are also discussed. The method of solution is based on the multiplier rule and the Weierstrass necessary condition for the strong minimum of a functional. In some cases, the Legendre-Clebsch necessary condition for the weak minimum of a functional is used.     

Collective behavior models with vision geometrical constraints: Truncated noises and propagation of chaos

We consider large systems of stochastic interacting particles through discontinuous kernels which has vision geometrical constrains. We rigorously derive a Vlasov–Fokker–Planck type of kinetic mean-field equation from the corresponding stochastic integral inclusion system. More specifically, we construct a global-in-time weak solution to the stochastic integral inclusion system and derive the kinetic equation with the discontinuous kernels and the inhomogeneous noise strength by employing the 1-Wasserstein distance.