On a stochastic control problem with exit constraints

In this paper the logarithmic transformation of Fleming [1] is used to discuss a specific problem of controlled diffusions. The problem is to minimize a certain quadratic functional of the applied drift while satisfying the requirement that the place where the process exits a domain is not in a specified subset of its boundary. The main result is that the solution of this problem is given by the logarithm of a related exit probability.This research was supported in part by the Air Force Office of Scientific Research under AF-AFOSR 76-3063.     

Subregular recourse in nonlinear multistage stochastic optimization

We consider nonlinear multistage stochastic optimization problems in the spaces of integrable functions. We allow for nonlinear dynamics and general objective functionals, including dynamic risk measures. We study causal operators describing the dynamics of the system and derive the Clarke subdifferential for a penalty function involving such operators. Then we introduce the concept of subregular recourse in nonlinear multistage stochastic optimization and establish subregularity of the resulting systems in two formulations: with built-in nonanticipativity and with explicit nonanticipativity constraints. Finally, we derive optimality conditions for both formulations and study their relations.

     

On the stochastic uncapacitated dynamic single-item lotsizing problem with service level constraints

In this paper, we consider the uncapacitated single-item dynamic lotsizing problem with stochastic period demands and backordering. We present a model formulation that minimizes the setup and holding costs with respect to a constraint on the probability that the inventory at the end of any period does not become negative (α service level) and, alternatively, to a fill rate constraint (β service level). In contrast to earlier model formulations which consider the cycle α service level (α_c) and which approximate the on hand inventory by the net inventory, we include the exact on hand inventory into the model formulation. Therefore, the models are also applicable in situations with very low service levels.     

An infinite-horizon multistage dynamic optimization problem

Multiprocess problems are dynamic optimization problems in which there is a collection of control systems coupled through constraints in the endpoints of the constituent trajectories and through the cost function. Optimality conditions for such problems posed over a finite interval have already been derived. However, multiprocess problems arise, for example in the mathematical economics literature, in which one of the component processes operates over an infinite horizon. We give a proof of the relevant necessary conditions in the form of a maximum principle under mild and verifiable hypotheses and apply the theory to a two-stage problem in which an explicit dependence on the intermediate time (taken as a choice variable) is incorporated in the integrands of the cost functional.This research was carried out while the author was a Graduate Student at the Department of Electrical Engineering, Imperial College of Science, Technology, and Medicine, London, England. The author is grateful to Professor R. B. Vinter for his advice and helpful discussions.     

Solution of a tropical optimization problem with linear constraints

An optimization problem is considered that is formulated in terms of tropical (idempotent) mathematics and consists in the minimization of a nonlinear function in the presence of linear constraints on the domain of admissible values. The objective function is defined on the set of vectors over an idempotent semifield by a matrix with the use of the operation of multiplicative conjugate transposition. The problem considered is a further generalization of several known problems in which the solution involves the calculation of the spectral radius of the matrix. This generalization implies the use of a more complicated objective function compared with that in the above-mentioned problems, and the imposition of additional constraints. To solve the new problem, an auxiliary variable is introduced that describes the minimum value of the objective function. Then the problem reduces to solving an inequality in which the auxiliary variable plays the role of a parameter. Necessary and sufficient conditions for the existence of solutions to the inequality are used to calculate the parameter, and then the general solution of the inequality is taken as a solution to the original optimization problem. Numerical examples of the solution of problems on the set of two-dimensional vectors are presented.     

Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse

We consider two-stage risk-averse stochastic optimization problems with a stochastic ordering constraint on the recourse function. Two new characterizations of the increasing convex order relation are provided. They are based on conditional expectations and on integrated quantile functions: a counterpart of the Lorenz function. We propose two decomposition methods to solve the problems and prove their convergence. Our methods exploit the decomposition structure of the risk-neutral two-stage problems and construct successive approximations of the stochastic ordering constraints. Numerical results confirm the efficiency of the methods.     

On a variational problem with non-differentiable constraints

We study the regularity of minimizers and critical points of the Dirichlet energy under an integral constraint given by a non-differentiable function. We obtain existence of a Lipschitz continuous minimizer for a relaxed problem. In two dimensions, some regularity can also be proved for critical points.     

Confidence sets for discrete stochastic optimization

Consider the problem of finding the points of maximum of an expectation functional over a finite setS. Based on statistical estimates at each point ofS, confidence sets for theargmax-set are constructed which guarantee a prespecified probability of correct selection. We review known selection methods and propose a new two-stage procedure that works well for largeS and few global maxima. The performance is compared in a simulation study.     

Online stochastic optimization under time constraints

This paper considers online stochastic combinatorial optimization problems where uncertainties, i.e., which requests come and when, are characterized by distributions that can be sampled and where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. It proposes online stochastic algorithms that combine the frameworks of online and stochastic optimization. Online stochastic algorithms differ from traditional a priori methods such as stochastic programming and Markov Decision Processes by focusing on the instance data that is revealed over time. The paper proposes three main algorithms: expectation E, consensus C, and regret R. They all make online decisions by approximating, for each decision, the solution to a multi-stage stochastic program using an exterior sampling method and a polynomial number of samples. The algorithms were evaluated experimentally and theoretically. The experimental results were obtained on three applications of different nature: packet scheduling, multiple vehicle routing with time windows, and multiple vehicle dispatching. The theoretical results show that, under assumptions which seem to hold on these, and other, applications, algorithm E has an expected constant loss compared to the offline optimal solution. Algorithm R reduces the number of optimizations by a factor |R|, where R is the number of requests, and has an expected ρ(1+o(1)) loss when the regret gives a ρ-approximation to the offline problem.     

Multiobjective optimization problem with variational inequality constraints

 We study a general multiobjective optimization problem with variational inequality, equality, inequality and abstract constraints. Fritz John type necessary optimality conditions involving Mordukhovich coderivatives are derived. They lead to Kuhn-Tucker type necessary optimality conditions under additional constraint qualifications including the calmness condition, the error bound constraint qualification, the no nonzero abnormal multiplier constraint qualification, the generalized Mangasarian-Fromovitz constraint qualification, the strong regularity constraint qualification and the linear constraint qualification. We then apply these results to the multiobjective optimization problem with complementarity constraints and the multiobjective bilevel programming problem. Received: November 2000 / Accepted: October 2001 Published online: December 19, 2002 Key Words. Multiobjective optimization – Variational inequality – Complementarity constraint – Constraint qualification – Bilevel programming problem – Preference – Utility function – Subdifferential calculus – Variational principle Research of this paper was supported by NSERC and a University of Victoria Internal Research Grant Research was supported by the National Science Foundation under grants DMS-9704203 and DMS-0102496 Mathematics Subject Classification (2000): Sub49K24, 90C29     

On complexity of multistage stochastic programs

In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramér's Large Deviations Theorem.     

Necessary conditions for a domain optimization problem with various constraints

In this paper, a scheme for obtaining the necessary conditions in a wide class of domain optimization problems is given. In the case of a linear boundary-value problem of the Dirichlet type, necessary conditions are given.     

Interactive procedure for a multiobjective stochastic discrete dynamic problem

Multiple objectives and dynamics characterize many sequential decision problems. In the paper we consider returns in partially ordered criteria space as a way of generalization of single criterion dynamic programming models to multiobjective case. In our problem evaluations of alternatives with respect to criteria are represented by distribution functions. Thus, the overall comparison of two alternatives is equivalent to the comparison of two vectors of probability distributions. We assume that the decision maker tries to find a solution preferred to all other solutions (the most preferred solution). In the paper a new interactive procedure for stochastic, dynamic multiple criteria decision making problem is proposed. The procedure consists of two steps. First, the Bellman principle is used to identify the set of efficient solutions. Next interactive approach is employed to find the most preferred solution. A numerical example and a real-world application are presented to illustrate the applicability of the proposed technique.     

On discrete optimization with ordering

This paper studies discrete optimization problems with ordering requirements. These problems are formulated on general discrete sets in which there exists an ordering on their elements together with a cost function that evaluates each element of a given subset depending on its ordering relative to the remaining elements in the set. It is proven that ordered sequences over the original ground set define an independence system. The simplest such ordering problem, that consists of finding the ordered sequence of maximum weight, and its restriction to sets of a fixed cardinality are studied. In both cases, the polyhedral structure of the corresponding feasible sets is analyzed.     

Multi-stage portfolio selection problem with dynamic stochastic dominance constraints

We study the multi-stage portfolio selection problem where the utility function of an investor is ambiguous. The ambiguity is characterized by dynamic stochastic dominance constraints, which are able to capture the dynamics of the random return sequence during the investment process. We propose a multi-stage dynamic stochastic dominance constrained portfolio selection model, and use a mixed normal distribution with time-varying weights and the K-means clustering technique to generate a scenario tree for the transformation of the proposed model. Based on the scenario tree representation, we derive two linear programming approximation problems, using the sampling approach or the duality theory, which provide an upper bound approximation and a lower bound approximation for the original nonconvex problem. The upper bound is asymptotically tight with infinitely many samples. Numerical results illustrate the practicality and efficiency of the proposed new model and solution techniques.

     

Approximating infinite horizon stochastic optimal control in discrete time with constraints

Traditional approaches to solving stochastic optimal control problems involve dynamic programming, and solving certain optimality equations. When recast as stochastic programming problems, structural aspects such as convexity are retained, and numerical solution procedures based on decomposition and duality may be exploited. This paper explores a class of stationary, infinite-horizon stochastic optimization problems with discounted cost criterion. Constraints on both states and controls are permitted, and modeled in the objective function by allowing it to take infinite values. Approximating techniques are developed using variational analysis, and intuitive lower bounds are obtained via averaging the future. These bounds could be used in a finite-time horizon stochastic programming setting to find solutions numerically. Research supported in part by a grant of the National Science Foundation. AMS Classification 46N10, 49N15, 65K10, 90C15, 90C46     

Risk exposure and Lagrange multipliers of nonanticipativity constraints in multistage stochastic problems

We take advantage of the interpretation of stochastic capacity expansion problems as stochastic equilibrium models for assessing the risk exposure of new equipment in a competitive electricity economy. We develop our analysis on a standard multistage generation capacity expansion problem. We focus on the formulation with nonanticipativity constraints and show that their dual variables can be interpreted as the net margin accruing to plants in the different states of the world. We then propose a procedure to estimate the distribution of the Lagrange multipliers of the nonanticipativity constraints associated with first stage decisions; this gives us the distribution of the discounted cash flow of profitable plants in that stage.     

A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs

Multistage stochastic linear programs can represent a variety of practical decision problems. Solving a multistage stochastic program can be viewed as solving a large tree of linear programs. A common approach for solving these problems is the nested decomposition algorithm, which moves up down the tree by solving nodes and passing information among nodes. The natural independence of subtrees suggests that much of the computational effort of the nested decomposition algorithm can run in parallel across small numbers of fast processors. This paper explores the advantages of such parallel implementations over serial implementations and compares alternative sequencing protocols for parallel processors. Computational experience on a large test set of practical problems with up to 1.5 million constraints and almost 5 million variables suggests that parallel implementations may indeed work well, but they require careful attention to processor load balancing. Supported in part by the National Science Foundation under Grants DDM-9215921 and SES-9211937.