טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentLenger Benjamin
SubjectAdditive Decomposition of Matrices and Optimization
Problems on an Infinite Horizon
DepartmentDepartment of Applied Mathematics
Supervisor Mr. Arie Leizarowitz (Deceased)


Abstract

We discuss control systems over finite and countable spaces defined on an infinite horizon, where, typically, all the associated costs become unbounded as the time grows infinitely. We consider the limit behavior, as n→∞, of the expression ∑v(zi ,zi+1), as i goes from 0 to n-1  for programs z={zi} in a finite state space X={xi} with N states, V is a real N×N matrix whose (i,j) entry, Vij, is equal to the transition cost, v(xi,xj), from state xi to state xj.          We will also establish an additive decomposition of a matrix of the form V=μJ+pηT-ηpT where μ is a scalar, J is a matrix that satisfies Jij=1 for every 1≤i,j≤N, p and η are N-dimensional column vectors where η satisfies ηi=1 for all 1iN and Θ is a matrix with the following property:  min1≤j≤N Θij= 0 for every 1≤i≤N. We will show how to compute μ, p and Θ in a polynomial time. Also, we will discuss optimality of nonautonomous control systems.