Dijkstra’s algorithm and L-concave function maximization

Dijkstra’s algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra’s algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the steepest ascent algorithm for L-concave function maximization, when applied to the LP dual of the shortest path problem and implemented with some auxiliary variables, coincides exactly with Dijkstra’s algorithm.     

Hamilton–Jacobi–Bellman equations on time scales

In this paper, we consider a class of optimal control problems on time scales without state constraints, target conditions or the fixed terminal time. We first present and show a time scale version of the Bellman optimality principle. On this basis, using a chain rule of multivariables on time scales, we will derive Hamilton–Jacobi–Bellman equations on a time scale for these kind of optimal control problems. Finally, the quantum time scale is considered as an example to illustrate our results.     

Solving a Hamilton–Jacobi–Bellman equation with constraints

Optimal investment strategies for an insurer with state-dependent constraints are computed via a recursive finite difference solution to the corresponding discretized Hamilton–Jacobi–Belman equation. Convergence is derived from viscosity solution arguments. For this, a comparison result is given which is similar to the result given by Azcue and Muler [Ann. Appl. Probab. 20 (2010), pp. 1253–1302].     

Bellman不等式和Bellman猜想

在复数域Ｃ上讨论了矩阵迹的不等式，得到了广义几何算术平均不等式、几何算术平均不等式，给出了等号成立的充要条件，解决了Ｂｅｌｌａｍｎ的一个猜想。     

Nonlinear Potentials for Hamilton–Jacobi–Bellman Equations. II

A formal method of constructing the viscosity solutions for abstract nonlinear equations of Hamilton–Jacobi–Bellman (HJB) type was developed in the previous work of the author. A new advantage of this method (which was called an nonlinear potentials method) is that it gives a possibility to choose at the first step an expected regularity of the solution and then – to construct this solution. This makes the whole procedure more simple because an analysis of regularity of viscosity solutions is usually the most complicated step.Nonlinear potentials method is a generalization of Krylov's approach to study HJB equations.In this article nonlinear potentials method is applied to elliptic degenerate HJB equations in R^d with variable coefficients.     

Transmission conditions on interfaces for Hamilton–Jacobi–Bellman equations

We establish a comparison principle for a Hamilton–Jacobi–Bellman equation, more appropriately a system, related to an infinite horizon problem in presence of an interface. Namely a low dimensional subset of the state variable space where discontinuities in controlled dynamics and costs take place. Since corresponding Hamiltonians, at least for the subsolution part, do not enjoy any semicontinuity property, the comparison argument is rather based on a separation principle of the controlled dynamics across the interface. For this, we essentially use the notion of ε-partition and minimal ε-partition for intervals of definition of an integral trajectory.     

A recursive algorithm for multivariate risk measures and a set-valued Bellman’s principle

A method for calculating multi-portfolio time consistent multivariate risk measures in discrete time is presented. Market models for d assets with transaction costs or illiquidity and possible trading constraints are considered on a finite probability space. The set of capital requirements at each time and state is calculated recursively backwards in time along the event tree. We motivate why the proposed procedure can be seen as a set-valued Bellman’s principle, that might be of independent interest within the growing field of set optimization. We give conditions under which the backwards calculation of the sets reduces to solving a sequence of linear, respectively convex vector optimization problems. Numerical examples are given and include superhedging under illiquidity, the set-valued entropic risk measure, and the multi-portfolio time consistent version of the relaxed worst case risk measure and of the set-valued average value at risk.     

Application of variational iteration method for Hamilton–Jacobi–Bellman equations

In this paper, we use the variational iteration method (VIM) for optimal control problems. First, optimal control problems are transferred to Hamilton–Jacobi–Bellman (HJB) equation as a nonlinear first order hyperbolic partial differential equation. Then, the basic VIM is applied to construct a nonlinear optimal feedback control law. By this method, the control and state variables can be approximated as a function of time. Also, the numerical value of the performance index is obtained readily. In view of the convergence of the method, some illustrative examples are presented to show the efficiency and reliability of the presented method.     

Second order Hamilton–Jacobi–Bellman equations with an unbounded operator

This work is devoted to the study of a class of Hamilton–Jacobi–Bellman equations associated to an optimal control problem where the state equation is a stochastic differential inclusion with a maximal monotone operator. We show that the value function minimizing a Bolza-type cost functional is a viscosity solution of the HJB equation. The proof is based on the perturbation of the initial problem by approximating the unbounded operator. Finally, by providing a comparison principle we are able to show that the solution of the equation is unique.     

Discontinuous solutions of Hamilton–Jacobi–Bellman equation under state constraints

This article is devoted to the Hamilton–Jacobi partial differential equation $$\left\{\begin{array}{lll}\frac{\partial V}{\partial t} = H\left(t, x, - \frac{\partial V}{\partial x}\right) & \hbox{on} & [0, 1]\times {\overline{\Omega}}\\V(1, x) = g(x) & \hbox{on}& {\overline{\Omega}},\end{array}\right.$$ where the Hamiltonian ${{H:[0, 1] \times \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}}}$ is convex and positively homogeneous with respect to the last variable, ${{\Omega \subset \mathbb{R}^n}}$ is open and ${{g : \mathbb{R}^n \to \mathbb{R} \cup \{+ \infty\}}}$ is lower semicontinuous. Such Hamiltonians do arise in the optimal control theory. We apply the method of generalized characteristics to show uniqueness of lower semicontinuous solution of this first order PDE. The novelty of our setting lies in the fact that we do not ask regularity of the boundary of Ω and extend the Soner inward pointing condition in a nontraditional way to get uniqueness in the class of lower semicontinuous functions.     

On the Douglas–Rachford algorithm

Mathematical Programming - The Douglas–Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the...     

Probabilistic interpretation of a coupled system of Hamilton–Jacobi–Bellman equations

In this paper, we give a probabilistic interpretation for a coupled system of Hamilton–Jacobi–Bellman equations using the value function of a stochastic control problem. First we introduce this stochastic control problem. Then we prove that the value function of this problem is deterministic and satisfies a (strong) dynamic programming principle. And finally, the value function is shown to be the unique viscosity solution of the coupled system of Hamilton–Jacobi–Bellman equations.     

An adaptive domain decomposition method for the Hamilton–Jacobi–Bellman equation

In this paper, we propose an efficient algorithm for a Hamilton–Jacobi–Bellman equation governing a class of optimal feedback control and stochastic control problems. This algorithm is based on a non-overlapping domain decomposition method and an adaptive least-squares collocation radial basis function discretization with a novel matrix inversion technique. To demonstrate the efficiency of this method, numerical experiments on test problems with up to three states and two control variables have been performed. The numerical results show that the proposed algorithm is highly parallelizable and its computational cost decreases exponentially as the number of sub-domains increases.     

Properties of the nonsymmetric Robinson–Schensted–Knuth algorithm

We introduce a generalization of the Robinson–Schensted–Knuth insertion algorithm for semi-standard augmented fillings whose basement is an arbitrary permutation σ∈S _n . If σ is the identity, then our insertion algorithm reduces to the insertion algorithm introduced by the second author (Sémin. Lothar. Comb. 57:B57e, 2006) for semi-standard augmented fillings and if σ is the reverse of the identity, then our insertion algorithm reduces to the original Robinson–Schensted–Knuth row insertion algorithm. We use our generalized insertion algorithm to obtain new decompositions of the Schur functions into nonsymmetric elements called generalized Demazure atoms (which become Demazure atoms when σ is the identity). Other applications include Pieri rules for multiplying a generalized Demazure atom by a complete homogeneous symmetric function or an elementary symmetric function, a generalization of Knuth’s correspondence between matrices of non-negative integers and pairs of tableaux, and a version of evacuation for composition tableaux whose basement is an arbitrary permutation σ.     

Singular optimal controls of stochastic recursive systems and Hamilton–Jacobi–Bellman inequality

In this paper, we study the optimal singular controls for stochastic recursive systems, in which the control has two components: the regular control, and the singular control. Under certain assumptions, we establish the dynamic programming principle for this kind of optimal singular controls problem, and prove that the value function is a unique viscosity solution of the corresponding Hamilton–Jacobi–Bellman inequality, in a given class of bounded and continuous functions. At last, an example is given for illustration.     

Peterson–Gorenstein–Zierler algorithm for skew RS codes

We design a non-commutative version of the Peterson–Gorenstein–Zierler decoding algorithm for a class of codes that we call skew RS codes. These codes are left ideals of a quotient of a skew polynomial ring, which endow them of a sort of non-commutative cyclic structure. Since we work over an arbitrary field, our techniques may be applied both to linear block codes and convolutional codes. In particular, our decoding algorithm applies for block codes beyond the classical cyclic case.