Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

Analyzing securitization processes using simulation methods

The aim of this paper is to present an analysis of securitization processes using simulation and optimization methods. We discuss the main risk factors that may affect profitability of the process. These risk factors are interest rates and mortgage prepayments. We combine latest risk factor models to create a consistent framework to analyze and improve securitization processes. We then show that making ad hoc securitization decisions may be far less efficient than by solving optimization problems. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Lipschitzianity of optimal trajectories for the Bolza optimal control problem

In this paper we investigate Lipschitz continuity of optimal solutions for the Bolza optimal control problem under Tonelli’s type growth condition. Such regularity being a consequence of normal necessary conditions for optimality, we propose new sufficient conditions for normality of state-constrained nonsmooth maximum principles for absolutely continuous optimal trajectories. Furthermore we show that for unconstrained problems any minimizing sequence of controls can be slightly modified to get a new minimizing sequence with nice boundedness properties. Finally, we provide a sufficient condition for Lipschitzianity of optimal trajectories for Bolza optimal control problems with end point constraints and extend a result from (J. Math. Anal. Appl. 143, 301–316, 1989) on Lipschitzianity of minimizers for a classical problem of the calculus of variations with discontinuous Lagrangian to the nonautonomous case.     

Optimal control of Markovian jump processes with partial information and applications to a parallel queueing model

We consider a stochastic control problem over an infinite horizon where the state process is influenced by an unobservable environment process. In particular, the Hidden-Markov-model and the Bayesian model are included. This model under partial information is transformed into an equivalent one with complete information by using the well-known filter technique. In particular, the optimal controls and the value functions of the original and the transformed problem are the same. An explicit representation of the filter process which is a piecewise-deterministic process, is also given. Then we propose two solution techniques for the transformed model. First, a generalized verification technique (with a generalized Hamilton–Jacobi–Bellman equation) is formulated where the strict differentiability of the value function is weaken to local Lipschitz continuity. Second, we present a discrete-time Markovian decision model by which we are able to compute an optimal control of our given problem. In this context we are also able to state a general existence result for optimal controls. The power of both solution techniques is finally demonstrated for a parallel queueing model with unknown service rates. In particular, the filter process is discussed in detail, the value function is explicitly computed and the optimal control is completely characterized in the symmetric case.     

Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme (Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for solving a set of randomly generated SDP instances.     

Optimal securitization of credit portfolios via impulse control

We study the optimal loan securitization policy of a commercial bank which is mainly engaged in lending activities. For this we propose a stylized dynamic model which contains the main features affecting the securitization decision. In line with reality we assume that there are non-negligible fixed and variable transaction costs associated with each securitization. The fixed transaction costs lead to a formulation of the optimization problem in an impulse control framework. We prove viscosity solution existence and uniqueness for the quasi-variational inequality associated with this impulse control problem. Iterated optimal stopping is used to find a numerical solution of this PDE, and numerical examples are discussed.     

Dynamic mean-variance problem with constrained risk control for the insurers

In this paper, we study optimal reinsurance/new business and investment (no-shorting) strategy for the mean-variance problem in two risk models: a classical risk model and a diffusion model. The problem is firstly reduced to a stochastic linear-quadratic (LQ) control problem with constraints. Then, the efficient frontiers and efficient strategies are derived explicitly by a verification theorem with the viscosity solutions of Hamilton–Jacobi–Bellman (HJB) equations, which is different from that given in Zhou et al. (SIAM J Control Optim 35:243–253, 1997). Furthermore, by comparisons, we find that they are identical under the two risk models. This work was supported by National Basic Research Program of China (973 Program) 2007CB814905 and National Natural Science Foundation of China (10571092).     

Continuous Reformulations for Zero–One Programming Problems

In this work, we study continuous reformulations of zero–one programming problems. We prove that, under suitable conditions, the optimal solutions of a zero–one programming problem can be obtained by solving a specific continuous problem.     

Numerical analysis of the Navier–Stokes/Darcy coupling

We consider a differential system based on the coupling of the Navier–Stokes and Darcy equations for modeling the interaction between surface and porous-media flows. We formulate the problem as an interface equation, we analyze the associated (nonlinear) Steklov–Poincaré operators, and we prove its well-posedness. We propose and analyze iterative methods to solve a conforming finite element approximation of the coupled problem.     

Scenario reduction in stochastic programming

 Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario tree the optimal reduced tree still has about 90% relative accuracy. Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem – electrical load scenario tree Mathematics Subject Classification (1991): 90C15, 90C31     

The Sturm-Liouville problem with a nonlocal boundary condition

In this paper, we consider the Sturm-Liouville problem with one classical and another nonlocal boundary condition. We investigate general properties of the characteristic function and spectrum for such a problem in the complex case. In the second part, we investigate the case of real eigenvalues, analyze the dependence of the spectrum on parameters of the boundary condition, and describe the qualitative behavior of all eigenvalues subject to of the nonlocal boundary condition. Dedicated to N. S. Bakhvalov (1934–2005) Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 410–428, July–September, 2007.     

Transversality condition for singular infinite horizon calculus of variations

We consider an optimal infinite horizon calculus of variations problem linear with respect to the velocities. In this framework the Euler–Lagrange equation are known to be algebraic and thus no informative for the general optimal solutions. We prove that the value of the objective along the MRAPs, the curves that connect as quickly as possible the solutions of the Euler–Lagrange equation, is Lipschitz continuous and satisfies a Hamilton–Jacobi equation in some generalised sense. We derive then a sufficient condition for a MRAP to be optimal by using a transversality condition at infinity that we generalize to our non regular context.     

Conditioning of convex piecewise linear stochastic programs

 In this paper we consider stochastic programming problems where the objective function is given as an expected value of a convex piecewise linear random function. With an optimal solution of such a problem we associate a condition number which characterizes well or ill conditioning of the problem. Using theory of Large Deviations we show that the sample size needed to calculate the optimal solution of such problem with a given probability is approximately proportional to the condition number. Received: May 2000 / Accepted: May 2002-07-16 Published online: September 5, 2002 RID="★" The research of this author was supported, in part, by grant DMS-0073770 from the National Science Foundation Key Words. stochastic programming – Monte Carlo simulation – large deviations theory – ill-conditioned problems     

Numerical solution to the optimal feedback control of continuous casting process

Using a semi-discrete model that describes the heat transfer of a continuous casting process of steel, this paper is addressed to an optimal control problem of the continuous casting process in the secondary cooling zone with water spray control. The approach is based on the Hamilton–Jacobi–Bellman equation satisfied by the value function. It is shown that the value function is the viscosity solution of the Hamilton–Jacobi–Bellman equation. The optimal feedback control is found numerically by solving the associated Hamilton–Jacobi–Bellman equation through a designed finite difference scheme. The validity of the optimality of the obtained control is experimented numerically through comparisons with different admissible controls. Detailed study of a low-carbon billet caster is presented.     

A multidimensional knapsack model for asset-backed securitization

Securitization is a financial operation which allows a financial institution to transform financial assets, for instance mortgage assets or lease contracts, into marketable securities. We focus the analysis on a real case of a bank for the leasing. Once the securitization characteristics, such as size and times of the operation, have been defined, the profit for the financial institution—Italease Bank for the Leasing in our case—depends on how the financial assets to use in the securitization are selected. We show that the selection problem can be modelled as a multidimensional knapsack problem (MDKP). Some formal arguments suggest that there may exist a prevailing constraint in the MDKP. Such an idea is used in the design of some simple heuristics which turn out to be very effective.     

Error estimates for abstract linear–quadratic optimal control problems using proper orthogonal decomposition

In this paper we investigate POD discretizations of abstract linear–quadratic optimal control problems with control constraints. We apply the discrete technique developed by Hinze (Comput. Optim. Appl. 30:45–61, 2005) and prove error estimates for the corresponding discrete controls, where we combine error estimates for the state and the adjoint system from Kunisch and Volkwein (Numer. Math. 90:117–148, 2001; SIAM J. Numer. Anal. 40:492–515, 2002). Finally, we present numerical examples that illustrate the theoretical results.     

A priori error estimates for space–time finite element discretization of semilinear parabolic optimal control problems

In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008; SIAM Control Optim 47(3):1301–1329, 2008) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and R?sch (SIAM J Control Optim 43:970–985, 2004), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls.     

A fully discrete numerical scheme for weighted mean curvature flow

Summary. We analyze a fully discrete numerical scheme approximating the evolution of n–dimensional graphs under anisotropic mean curvature. The highly nonlinear problem is discretized by piecewise linear finite elements in space and semi–implicitly in time. The scheme is unconditionally stable und we obtain optimal error estimates in natural norms. We also present numerical examples which confirm our theoretical results. Received October 2, 2000 / Published online July 25, 2001     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.