Selecting preferred solutions in the minimax approach to dynamic programming problems under flexible constraints

Dynamic Programming is a powerful approach to the optimization of sequential or multistage decision processes, e.g., in planning or in system control. In this paper, we consider both theoretical and algorithmic issues in sequential decision processes under flexible constraints. Such processes must attain a given goal within some tolerance. Tolerances or preferences also apply to the values the decision variables may take or on the action chosen at each step. Such problems boil down to maximin optimization. Unfortunately, this approach suffers from the so-called “drowning effect” (lack of discrimination) and the optimality principle of dynamic programming is not always verified. In this context, we introduce a general framework for refined minimax optimization procedures in order to compare and select preferred alternatives. This framework encompasses already introduced methods such as LexiMin and DiscriMin, but it allows their extension to the comparison of vectors of unequal lengths. We show that these refined comparisons restore compatibility with the optimality principle, and that classical algorithms can be adapted to compute such preferred solutions, by exploiting existing results on idempotent semirings.     

Solving a general discounted dynamic program by linear programming

Summary As is well known (cf. Derman (1970) and references cited there), dynamic programming problems with finite state and action spaces can be solved by linear programming techniques. In the present paper it will be shown that this statement can be generalized to the case of general state and action spaces.By this approach, the underlying sequential structure is completely neglected. Instead, vectore space structures and linear programming results (such as existence and duality theorems, complementary slackness) are used to obtain optimality statements.     

Sequential Quadratic Programming Method for Volatility Estimation in Option Pricing

Our goal is to identify the volatility function in Dupire’s equation from given option prices. Following an optimal control approach in a Lagrangian framework, a globalized sequential quadratic programming (SQP) algorithm combined with a primal-dual active set strategy is proposed. Existence of local optimal solutions and of Lagrange multipliers is shown. Furthermore, a sufficient second-order optimality condition is proved. Finally, some numerical results are presented underlining the good properties of the numerical scheme.     

Viscosity Solutions of HJB Equations with Unbounded Data and Characteristic Points

We study a class of infinite horizon and exit-time control problems for nonlinear systems with unbounded data using the dynamic programming approach. We prove local optimality principles for viscosity super- and subsolutions of degenerate Hamilton–Jacobi equations in a very general setting. We apply these results to characterize the (possibly multiple) discontinuous solutions of Dirichlet and free boundary value problems as suitable value functions for the above-mentioned control problems.     

Viscosity Solutions of HJB Equations with Unbounded Data and Characteristic Points

We study a class of infinite horizon and exit-time control problems for nonlinear systems with unbounded data using the dynamic programming approach. We prove local optimality principles for viscosity super- and subsolutions of degenerate Hamilton–Jacobi equations in a very general setting. We apply these results to characterize the (possibly multiple) discontinuous solutions of Dirichlet and free boundary value problems as suitable value functions for the above-mentioned control problems.     

Second-order sequence-based necessary optimality conditions in constrained nonsmooth vector optimization and applications

Several notions of sequential directional derivatives and sequential local approximations are introduced. Under (first-order) Hadamard differentiability assumptions of the data at the point of study, these concepts are utilized to analyze second-order necessary optimality conditions, which rely on given sequences, for local weak solutions in nonsmooth vector optimization problems with constraints. Some applications to minimax programming problems are also derived.     

On duality with generalized convexity

A multi-stage stochastic decision model with general reward functional is considered. We get statements with respect to criteria of optimality and to the existence of optimal strategies which generalize well-known theorems of classical theory of dynamic programming.     

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.     

Disaggregation under uncertainty in hierarchical production planning

This study deals with a hierarchical planning system that is used for planning of a single-stage manufacturing system. We consider two decision levels, aggregate and detailed planning, and formulate a model for evaluation of aggregate plans and optimal disaggregation in case of independent stochastic demand. It is shown how the optimal solution can be obtained with the aid of a dynamic programming algorithm. Furthermore, we give conditions that will guarantee optimality of a simple intuitive disaggregation rule.     

Discrete dynamic programming with outcomes in random variable structures

Multiobjective approach is the common way of generalization single-criterion dynamic programming models. Another way is to consider partially ordered criteria structures. That approach is rather rare. The aim of the paper is to present such a model. Generalization of Bellman’s principle of optimality is employed to create a forward procedure to find the set of all maximal elements. As this set is usual large, the second problem under consideration is to find its subsets. To reduce the number of solutions presented to decision maker we propose to apply a family of narrowing relations. That approach is similar to scalarization in multiobjective programming. Ordered structures of random variables based on mean–variance, stochastic dominance and inverse stochastic dominance are considered. Numerical illustration is given at the end of the paper.     

Compactness of the space of non-randomized policies in countable-state sequential decision processes

For sequential decision processes with countable state spaces, we prove compactness of the set of strategic measures corresponding to nonrandomized policies. For the Borel state case, this set may not be compact (Piunovskiy, Optimal control of random sequences in problems with constraints. Kluwer, Boston, p. 170, 1997) in spite of compactness of the set of strategic measures corresponding to all policies (Schäl, On dynamic programming: compactness of the space of policies. Stoch Processes Appl 3(4):345–364, 1975b; Balder, On compactness of the space of policies in stochastic dynamic programming. Stoch Processes Appl 32(1):141–150, 1989). We use the compactness result from this paper to show the existence of optimal policies for countable-state constrained optimization of expected discounted and nonpositive rewards, when the optimality is considered within the class of nonrandomized policies. This paper also studies the convergence of a value-iteration algorithm for such constrained problems.     

Linear decision rules for cash-balancing and inventory problems

Optimal dynamic programming solutions for cash-balancing problems are compared with suboptimal linear decision rule solutions. It can be shown that cost deviations are not larger than 10% for small set-up costs. The comparison is extended to the pure inventory case for which similar results are obtained.     

Optimal myopic policies and index policies for stochastic scheduling problems

Stochastic scheduling problems are considered by using discounted dynamic programming. Both, maximizing pure rewards and minimizing linear holding costs are treated in one common Markov decision problem. A sufficient condition for the optimality of the myopic policy for finite and infinite horizon is given. For the infinite horizon case we show the optimality of an index policy and give a sufficient condition for the index policy to be myopic. Moreover, the relation between the two sufficient conditions is discussed.     

Robust optimization analysis for multiple attribute decision making problems with imprecise information

This paper considers ranking decision alternatives under multiple attributes with imprecise information on both attribute weights and alternative ratings. It is demonstrated that regret results from the decision maker??s inadequate knowledge about the true scenario to occur. Potential optimality analysis is a traditional method to evaluate alternatives with imprecise information. The essence of this approach is to identify any alternative that outperforms the others in its best-case scenario. Our analysis shows that potential optimality analysis is optimistic in nature and may lead to a significant loss if an unfavorable scenario occurs. We suggest a robust optimization analysis approach that ranks alternatives in terms of their worst-case absolute or relative regret. A robust optimal alternative performs reasonably well in all scenarios and is shown to be desirable for a risk-concerned decision maker. Linear programming models are developed to check robust optimality.     

Checking weak optimality of the solution to linear programming with interval right-hand side

The interval linear programming (IvLP) is a method for decision making under uncertainty. A weak feasible solution to IvLP is called weakly optimal if it is optimal for some scenario of the IvLP. One of the basic and difficult tasks in IvLP is to check whether a given point is weak optimal. In this paper, we investigate linear programming problems with interval right-hand side. Some necessary and sufficient conditions for checking weak optimality of given feasible solutions are established, based on the KKT conditions of linear programming. The proposed methods are simple, easy to implement yet very effective, since they run in polynomial time.     

An enumerative algorithm for computing all possibly optimal solutions to an interval LP

Interval programming techniques are a valuable approach for tackling uncertainty in mathematical programming models, because they only require the knowledge of the feasible range of variation of the model coefficients. Nevertheless, the use of these techniques has some limitations, namely when the number of decision variables with interval coefficients is high since the number of objective functions at stake in the sub-problem for testing the (weak) efficiency of each non-basic variable may be easily out of an acceptable computational effort. A similar problem may arise with the number of sub-problems for testing the multi-parametric optimality of each solution obtained (that is, to check whether the solution is possibly optimal or not) and the multi-parametric optimality of each edge by using the all emanating edges algorithm. An alternative algorithm is suggested that allows obtaining all possibly optimal solutions, which fulfill the formal criteria of optimality in a feasible bounded region.     

Inverse DEA under inter-temporal dependence using multiple-objective programming

This paper deals with the inverse Data Envelopment Analysis (DEA) under inter-temporal dependence assumption. Both problems, input-estimation and output-estimation, are investigated. Necessary and sufficient conditions for input/output estimation are established utilizing Pareto and weak Pareto solutions of linear multiple-objective programming problems. Furthermore, in this paper we introduce a new optimality notion for multiple-objective programming problems, periodic weak Pareto optimality. These solutions are used in inverse DEA, and it is shown that these can be characterized by a simple modification in weighted sum scalarization tool.     

Vehicle Scheduling: Proximity Priority Searching

In this paper a new basis for the allocation of customers to routes is discussed. The technique commences at peripheral locations and branches sequentially to nearest customers. A sequential assignment technique provides a simple programming approach which incorporates restrictions, such as distance, weight, quantity and time. Several test problems are analysed and results compared with solutions produced by the more familiar scheduling techniques. It is concluded, on the basis of optimality and calculation time, that the proposed method is as good as any other technique.     

Stability and accuracy functions for a multicriteria Boolean linear programming problem with parameterized principle of optimality “from Condorcet to Pareto”

A multicriteria Boolean programming problem with linear cost functions in which initial coefficients of the cost functions are subject to perturbations is considered. For any optimal alternative, with respect to parameterized principle of optimality “from Condorcet to Pareto”, appropriate measures of the quality are introduced. These measures correspond to the so-called stability and accuracy functions defined earlier for optimal solutions of a generic multicriteria combinatorial optimization problem with Pareto and lexicographic optimality principles. Various properties of such functions are studied and maximum norms of perturbations for which an optimal alternative preserves its optimality are calculated. To illustrate the way how the stability and accuracy functions can be used as efficient tools for post-optimal analysis, an application from the voting theory is considered.     

Preference Order Stochastic Knapsack Problems: Methodological Issues

A preference order dynamic programming model proposed in the literature for solving stochastic knapsack problems is shown to be somewhat limited from both the methodological and computational points of view. A counterexample is presented contradicting the optimality of a procedure designed for normal variates.