Conditions for the discovery of solution horizons

We present necessary and sufficient conditions for discrete infinite horizon optimization problems with unique solutions to be solvable. These problems can be equivalently viewed as the task of finding a shortest path in an infinite directed network. We provide general forward algorithms with stopping rules for their solution. The key condition required is that of weak reachability, which roughly requires that for any sequence of nodes or states, it must be possible from optimal states to reach states close in cost to states along this sequence. Moreover the costs to reach these states must converge to zero. Applications are considered in optimal search, undiscounted Markov decision processes, and deterministic infinite horizon optimization.This work was supported in part by NSF Grant ECS-8700836 to The University of Michigan.     

Nondominated decisions and cone convexity in dynamic multicriteria decision problems

The concepts of domination structures and non-dominated decisions are extended to dynamic decision problems. Previously derived results are utilized in conjunction with optimal control theory to deduce necessary as well as sufficient conditions for nondominated controls. Cone convexity for dynamic problems is discussed, and sufficient conditions are given for a class of linear systems.     

Dynamic decision making for graphical models applied to oil exploration

We present a framework for sequential decision making in problems described by graphical models. The setting is given by dependent discrete random variables with associated costs or revenues. In our examples, the dependent variables are the potential outcomes (oil, gas or dry) when drilling a petroleum well. The goal is to develop an optimal selection strategy of wells that incorporates a chosen utility function within an approximated dynamic programming scheme. We propose and compare different approximations, from naive and myopic heuristics to more complex look-ahead schemes, and we discuss their computational properties. We apply these strategies to oil exploration over multiple prospects modeled by a directed acyclic graph, and to a reservoir drilling decision problem modeled by a Markov random field. The results show that the suggested strategies clearly improve the naive or myopic constructions used in petroleum industry today. This is useful for decision makers planning petroleum exploration policies.     

On Regularization Methods for Inverse Problems of Dynamic Type

In this paper, we consider new regularization methods for linear inverse problems of dynamic type. These methods are based on dynamic programming techniques for linear quadratic optimal control problems. Two different approaches are followed: a continuous and a discrete one. We prove regularization properties and also obtain rates of convergence for the methods derived from both approaches. A numerical example concerning the dynamic EIT problem is used to illustrate the theoretical results.     

Existence of optimal policy for time non-homogeneous discounted Markovian decision programming

In this paper we discuss the discrete time non-homogeneous discounted Markovian decision programming, where the state space and all action sets are countable. Suppose that the optimum value function is finite. We give the necessary and sufficient conditions for the existence of an optimal policy. Suppose that the absolute mean of rewards is relatively bounded. We also give the necessary and sufficient conditions for the existence of an optimal policy.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

Maximin share and minimax envy in fair-division problems

For fair-division or cake-cutting problems with value functions which are normalized positive measures (i.e., the values are probability measures) maximin-share and minimax-envy inequalities are derived for both continuous and discrete measures. The tools used include classical and recent basic convexity results, as well as ad hoc constructions. Examples are given to show that the envy-minimizing criterion is not Pareto optimal, even if the values are mutually absolutely continuous. In the discrete measure case, sufficient conditions are obtained to guarantee the existence of envy-free partitions.     

Optimality in transient markov chains and linear programming

It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.This research was supported by the National Research Council of Canada, Grant A7751.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

Continuous time markov decision processes with interventions

We study Markov jump decision processes with both continuously and instantaneouslyacting decisions and with deterministic drift between jumps. Such decision processes were recentlyintroduced and studied from discrete time approximations point of view by Van der Duyn Schouten.Weobtain necessary and sufficient optimality conditions for these decision processes in terms of equations and inequalities of quasi-variational type. By means of the latter we find simple necessaryand sufficient conditions for the existence of stationary optimal policies in such processes with finite state and action spaces, both in the discounted and average per unit time reward cases.     

A Posteriori Verification of Optimality Conditions for Control Problems with Finite-Dimensional Control Space

In this article, we investigate non-convex optimal control problems. We are concerned with a posteriori verification of sufficient optimality conditions. If the proposed verification method confirms the fulfillment of the sufficient condition then a posteriori error estimates can be computed. A special ingredient of our method is an error analysis for the Hessian of the underlying optimization problem. We derive conditions under which positive definiteness of the Hessian of the discrete problem implies positive definiteness of the Hessian of the continuous problem. The article is complemented with numerical experiments.     

Optimization of Mayer Problem with Sturm–Liouville-Type Differential Inclusions

The present paper studies a new class of problems of optimal control theory with Sturm–Liouville-type differential inclusions involving second-order linear self-adjoint differential operators. Our main goal is to derive the optimality conditions of Mayer problem for differential inclusions with initial point constraints. By using the discretization method guaranteeing transition to continuous problem, the discrete and discrete-approximation inclusions are investigated. Necessary and sufficient conditions, containing both the Euler–Lagrange and Hamiltonian-type inclusions and “transversality” conditions are derived. The idea for obtaining optimality conditions of Mayer problem is based on applying locally adjoint mappings. This approach provides several important equivalence results concerning locally adjoint mappings to Sturm–Liouville-type set-valued mappings. The result strengthens and generalizes to the problem with a second-order non-self-adjoint differential operator; a suitable choice of coefficients then transforms this operator to the desired Sturm–Liouville-type problem. In particular, if a positive-valued, scalar function specific to Sturm–Liouville differential inclusions is identically equal to one, we have immediately the optimality conditions for the second-order discrete and differential inclusions. Furthermore, practical applications of these results are demonstrated by optimization of some “linear” optimal control problems for which the Weierstrass–Pontryagin maximum condition is obtained.     

Extremum principles for optimal control in normed linear spaces

Extremum principles intended for use in optimal control are derived in the form of necessary conditions and sufficient conditions, formulated in general normed linear spaces. The method of application is illustrated by several examples involving optimal control problems, mathematical programming problems, lumped-parameter systems, and distributed-parameter systems. The basic theorems provide a unified approach which is applicable to a wide variety of problems in open-loop optimal control.     

Increasing Lipschitz continuous maximizers of some dynamic programs

Conditions are presented for the existence of increasing and Lipschitz continuous maximizers in a general one-stage optimization problem. This property results in substantial numerical savings in case of a discrete parameter space. The one-stage result and properties of concave functions lead to simple conditions for the existence of optimal policies, composed of increasing and Lipschitz continuous decision rules, for several dynamic programs with discrete state and action space, in which case discrete concavity plays a dominant role. One of the examples, a general multi-stage allocation problem, is considered in detail. Finally, some known results in the case of a continuous state and action space are generalized.     

Discrete Optimal Control: Second Order Optimality Conditions

In this paper, we present a survey and refinement of our recent results in the discrete optimal control theory. For a general nonlinear discrete optimal control problem (P) , second order necessary and sufficient optimality conditions are derived via the nonnegativity ( I S 0) and positivity ( I >0) of the discrete quadratic functional I corresponding to its second variation. Thus, we fill the gap in the discrete-time theory by connecting the discrete control problems with the theory of conjugate intervals, Hamiltonian systems, and Riccati equations. Necessary conditions for I S 0 are formulated in terms of the positivity of certain partial discrete quadratic functionals, the nonexistence of conjugate intervals, the existence of conjoined bases of the associated linear Hamiltonian system, and the existence of solutions to Riccati matrix equations. Natural strengthening of each of these conditions yields a characterization of the positivity of I and hence, sufficiency criteria for the original problem (P) . Finally, open problems and perspectives are also discussed.     

Discrete time-variant interpolation as classical interpolation with an operator argument

Necessary and sufficient conditions are derived for the existence of solutions to discrete time-variant interpolation problems of Nevanlinna-Pick and Nudelman type. The proofs are based on a reduction scheme which allows one to treat these time-variant interpolation problems as classical interpolation problems for operator-valued functions with operator arguments. The latter ones are solved by using the commutant lifting theorem.     

On the No-Gap Second-Order Optimality Conditions for a Discrete Optimal Control Problem with Mixed Constraints

Motivated by our recent works on optimality conditions in discrete optimal control problems under a nonconvex cost function, in this paper, we study second-order necessary and sufficient optimality conditions for a discrete optimal control problem with a nonconvex cost function and state-control constraints. By establishing an abstract result on second-order optimality conditions for a mathematical programming problem, we derive second-order necessary and sufficient optimality conditions for a discrete optimal control problem. Using a common critical cone for both the second-order necessary and sufficient optimality conditions, we obtain “no-gap” between second-order optimality conditions.     

The inverse eigenvalue problem of generalized reflexive matrices and its approximation

This paper studies inverse eigenvalue problems of generalized reflexive matrices and their optimal approximations. Necessary and sufficient conditions for the solvability of the problems are derived, the solutions and their optimal approximations are provided.     

Stability and periodic investigations of linear planar difference systems

This paper discusses the problem of stability and periodic behaviour of linear planar difference systems appearing in modelling of discrete problems of population biology and Hopfield neural networks. We concentrate especially on procedures, which enable to formulate optimal (i.e. necessary and sufficient) conditions guaranteing such a behaviour. As a main tool, we analyse in detail location of zeros of characteristic polynomials with respect to the unit circle. From this viewpoint, derived results contribute also to the polynomial theory. Copyright © 2016 John Wiley & Sons, Ltd.     

Arbitrary side observations in bandit problems

A bandit problem with side observations is an extension of the traditional two-armed bandit problem, in which the decision maker has access to side information before deciding which arm to pull. In this paper, essential properties of the side observations that allow achievability results with respect to optimal regret are extracted and formalized. The sufficient conditions for good side information obtained here admit various types of random processes as special cases, including i.i.d. sequences, Markov chains, deterministic periodic sequences, etc. A simple necessary condition for optimal regret is given, providing further insight into the nature of bandit problems with side observations. A game-theoretic approach simplifies the analysis and justifies the viewpoint that the side observation serves as an index specifying different sub-bandit machines.