Average Point Pursuit using the Greedy Algorithm: Theory and Applications

MaRDI QIDQ6309938zbMATH OpenFDO

Authors Andrey Bernstein, Niek Bouman

Publication date 16 November 2018

Abstract: This paper considers a discrete-time decision problem wherein a decision maker has to track, on average, a sequence of inputs selected from a convex set $mathcalXsubsetmathbb{R}^d$ by choosing actions from a possibly non-convex feasible set $mathcalYsubsetmathbb{R}^d$, where $mathcalX$ is in fact the convex hull of $mathcalY$. We study some generalized variants of this problem, in which: (i) $mathcalX$ and $mathcalY$ vary with time, and (ii) there might be a delay between them, in the sense that $mathcalX$ is the convex hull of the previous $mathcalY$. We investigate the conditions under which the greedy algorithm that minimizes, in an online fashion, the accumulated error between the sequence of inputs and decisions, is able to track the average input asymptotically. Essentially, this comes down to proving that the accumulated error, whose evolution is governed by a non-linear dynamical system, remains within a bounded invariant set. Applications include control of discrete devices using continuous setpoints; control of highly uncertain devices with some information delay; and digital printing, scheduling, and assignment problems.

This page was built for publication: Average Point Pursuit using the Greedy Algorithm: Theory and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309938)