Minimum-Time Trajectory Optimization With
Data-Based Models: A Linear Programming Approach

Minimum-time trajectory optimization (also known as “time-optimal control”) is frequently involved in robot path planning and tracking (Lepetič et al., 2003; Verscheure et al., 2009), space mission design and operation (Shirazi et al., 2018), and other disciplines wherever a task is desired to be accomplished in a least amount of time, typically subject to limited resources. Due to its significant relevance, the investigation into this topic has been extensive over decades (Kalman and Bertram, 1959; LaSalle, 1959; O’Reilly, 1981).

The formulation of a minimum-time trajectory optimization problem can be either in continuous time or in discrete time. In continuous time, solution techniques are usually based on indirect methods (also known as “variational methods”): One first applies Pontryagin’s maximum principle to reduce the trajectory optimization problem to a two-point boundary value problem (TPBVP), and then solves the TPBVP using a shooting method (Trélat, 2012; Taheri et al., 2017). In discrete time, in contrast, direct methods are more often considered. Various direct methods for minimum-time trajectory optimization in discrete time have been proposed in the literature: In the approach of Carvallo et al. (1990), a minimum-time problem is reformulated into a mixed-integer program, where a set of Boolean variables are used to indicate if a given target condition is reached at each time step over the planning horizon. In the approaches of Van den Broeck et al. (2011) and Zhang et al. (2014), a minimum-time problem is solved using a bi-level algorithm, where the lower level solves a fixed-horizon trajectory planning problem treating the target condition as a terminal constraint and the upper level adjusts the planning horizon of the lower-level problem to find the minimum horizon length such that the lower-level problem admits a feasible solution. In the approaches of Rösmann et al. (2015) and Wang et al. (2017), the time is scaled and the scaling factor is treated as an optimization variable. This way, minimizing the final time of the original free-final-time problem is achieved through minimizing the scaling factor in a related fixed-final-time problem. However, in such an approach based on time scaling, the optimization problem is necessarily nonlinear and nonconvex, even for linear systems. In the approach of Verschueren et al. (2017), the deviation from the target condition is penalized with a weight that increases exponentially with time. It is shown that a minimum-time trajectory solution can be obtained if the weight parameter is chosen to be sufficiently high. The approaches reviewed above typically use a state-space model of the considered dynamic system to predict the trajectories. A common approach to obtaining a state-space model, to be used for trajectory optimization, is to first derive the model from first principles and then calibrate its parameters according to prior knowledge and/or data of the system.

Recently, a non-parametric modeling approach based on behavioral systems theory is gaining attention due to its unique applicability to emerging data-driven paradigms (Markovsky and Dörfler, 2021). This approach uses input-output time-series data of a given system to build up a (non-parametric) predictive model, which is referred to as a data-based model in this paper, rather than using the data to identify/calibrate a (parametric) state-space model. The integration of such data-based models into predictive control algorithms has been investigated by various researchers, e.g., Coulson et al. (2019, 2021); Berberich et al. (2020); Baros et al. (2022); Huang et al. (2023), and has demonstrated superior performance than conventional control methods in a number of applications (Elokda et al., 2021; Huang et al., 2021; Chinde et al., 2022). Along with bypassing the step of state-space model identification/calibration, such a predictive control algorithm using an input-output data-based model determines control input values directly based on output measurements and does not require state estimation using an observer. Therefore, it provides an “end-to-end” data-to-control solution, which may be simpler to implement from the point of view of practitioners and may facilitate fully autonomous operation of future intelligent systems.

In the above context, the goal of this paper is to develop an approach to minimum-time trajectory optimization based on input-output data-based models, to produce an end-to-end data-to-control solution to many time-optimal planning and control problems in robotics, aerospace, and other disciplines. To the best of our knowledge, there has been no previous work addressing this topic. We focus on linear time-invariant systems, for which we adopt the approach based on behavioral systems theory to build up a non-parametric data-based model for trajectory prediction. We then exploit an exponential weighting scheme extended from the one of Verschueren et al. (2017) to solve for minimum-time trajectories. We show that the optimization problem in its final form is a linear program and hence is easy to solve. Main contributions of this paper are as follows:

• •

  We develop an approach to minimum-time trajectory optimization based on input-output data-based models, which is the first such approach in the literature.

• •

  We extend the trajectory prediction method in previous predictive control algorithms using data-based models (e.g., the ones in Coulson et al. (2019, 2021); Berberich et al. (2020); Baros et al. (2022); Huang et al. (2023)) to enable predicting trajectories over an extended planning horizon without relying on a high-dimensional model. This extension is especially relevant to trajectory optimization because a long planning horizon is not rare in a trajectory optimization setting. Our method is inspired by the multiple shooting method (Trélat, 2012).

• •

  Using an exponential weighting scheme extended from that of Verschueren et al. (2017), we formulate the minimum-time trajectory optimization problem into a linear program, which is easy to solve. We prove that minimum-time trajectories can be obtained with the linear program if a weight parameter is chosen to be sufficiently high. In particular, we make the following extensions to the exponential weighting scheme: 1) The scheme was used in Verschueren et al. (2017) for minimum-time trajectory planning based on a state-space model; we extend the scheme to apply it to minimum-time trajectory planning based on an input-output data-based model. 2) The scheme was used in Verschueren et al. (2017) for point-to-point trajectory planning; we extend the scheme to more general point-to-set trajectory planning. To enable these extensions, different assumptions are made, and, correspondingly, new proofs are developed to show the ability of this exponential weighting scheme to produce minimum-time trajectory solutions.

• •

  We validate the developed approach to minimum-time trajectory optimization and illustrate its application with an aerospace example.

Organization: The minimum-time trajectory optimization problem addressed in this paper is described in Section 2. We introduce the method using a non-parametric input-output data-based model to predict trajectories over an extended planning horizon in Section 3. We reformulate the minimum-time trajectory optimization problem into a linear program based on an exponential weighting scheme and prove its theoretical properties in Section 4. A spacecraft relative motion planning problem is considered in Section 5 to illustrate the approach. The paper is concluded in Section 6.

Notations: The symbol $\mathbb{R}$ denotes the set of real numbers and $\mathbb{Z}$ the set of integers; $\mathbb{R}^{n}$ denotes the set of $n$-dimensional real vectors, $\mathbb{R}^{n\times m}$ the set of $n$-by-$m$ real matrices, and $\mathbb{Z}_{\geq a}$ the set of integers that are greater than or equal to $a$; $I_{n}$ denotes the $n$-dimensional identity matrix, $0_{n,m}$ the $n$-by-$m$ zero matrix, and $1_{n}$ the $n$-dimensional column vector of ones. Given multiple vectors $v_{k}\in\mathbb{R}^{n_{k}}$ or matrices with the same number of columns $M_{k}\in\mathbb{R}^{n_{k}\times m}$, $k=1,...,K$, the operator $\text{col}(\cdot)$ stack them on top of one another, i.e., $\text{col}(v_{1},...,v_{K})=[v_{1}^{\top},...,v_{K}^{\top}]^{\top}$ and $\text{col}(M_{1},...,M_{K})=[M_{1}^{\top},...,M_{K}^{\top}]^{\top}$. For a discrete-time signal $z(\cdot):\mathbb{Z}\to\mathbb{R}^{n}$, we use ${\bf z}_{[a:b]}$, with $a,b\in\mathbb{Z}$ and $a\leq b$, to denote $\text{col}(z(a),...,z(b))$. We call both the sequence $z(a),...,z(b)$ and the column vector ${\bf z}_{[a:b]}=\text{col}(z(a),...,z(b))$ a trajectory (of length $l=b-a+1$).

We study trajectory optimization problems associated with finite-dimensional linear time-invariant systems which can be represented in state-space form as

where $t\in\mathbb{Z}$ denotes the discrete time step, $x(t)\in\mathbb{R}^{n}$ represents the system state at time $t$, $u(t)\in\mathbb{R}^{m}$ is the control input, $y(t)\in\mathbb{R}^{p}$ is the output, and $A$, $B$, $C$ and $D$ are matrices of appropriate dimensions. We make the following assumption about the system:

Assumption 1: The system is controllable and observable.

Given a state-space model (1) of the system, we can write the following equation that relates an input trajectory of length $l$, $l\in\mathbb{Z}_{\geq 1}$, to its corresponding output trajectory:

where $x(0)$ is the system state at the initial time of the trajectory, and $\mathcal{O}_{l}$ and $\mathcal{C}_{l}$ are matrices defined as follows:

The smallest integer $l$ such that the matrix $\mathcal{O}_{l}$ defined above has full rank is called the lag of the system and denoted as $l_{\min}$. Under Assumption 1, $l_{\min}$ exists and satisfies $1\leq l_{\min}\leq n$.

Given an arbitrary pair of input trajectory ${\bf u}_{[0:l-1]}$ and output trajectory ${\bf y}_{[0:l-1]}$, both of length $l$, if (2) holds for some $x(0)\in\mathbb{R}^{n}$, then the pair $({\bf u}_{[0:l-1]},{\bf y}_{[0:l-1]})$ is called admissible by the system. In particular, an admissible pair of input-output trajectories of length $l$, $({\bf u}_{[0:l-1]},{\bf y}_{[0:l-1]})$, with $l\geq l_{\min}$, corresponds to a unique initial state $x(0)$, which can be determined according to (2) as follows:

where $(\cdot)^{\dagger}$ denotes the Moore-Penrose pseudoinverse.

In this paper, we focus on minimum-time trajectory optimization problems given in the following form:

where $K_{i}\geq l_{\min}$; ${\bf u}_{i}\in\mathbb{R}^{mK_{i}}$ and ${\bf y}_{i}\in\mathbb{R}^{pK_{i}}$ represent given initial conditions for the input and output trajectories; $K_{f}\geq 1$; $Y_{f}\subset\mathbb{R}^{pK_{f}}$ represents a target set for the output trajectory; and $c(u(t),y(t))\leq 0$ represents prescribed path constraints for the trajectory to satisfy. The goal represented by the cost function in (5a) and the constraint in (5c) is to drive the output trajectory to reach the target set $Y_{f}$ in the minimum time, starting with the initial condition in (5b), while satisfying the path constraints in (5d). We first make the following assumption about the initial condition $({\bf u}_{i},{\bf y}_{i})$:

Assumption 2: The pair $({\bf u}_{i},{\bf y}_{i})$ represents an admissible pair of input-output trajectories (of length $K_{i}$) that satisfies the path constraints $c(u(t),y(t))\leq 0$ at all times.

Assumption 2 is reasonable because ${\bf u}_{i}$ and ${\bf y}_{i}$, according to (5b), represent the input and output trajectories of the system over the past $K_{i}$ time steps, and hence, the pair $({\bf u}_{i},{\bf y}_{i})$ is supposed to be admissible and satisfies any path constraints. Under Assumption 2, given a state-space model (1) of the system, (5b) corresponds to the following initial condition for the state:

where $\mathcal{O}_{K_{i}}$ and $\mathcal{C}_{K_{i}}$ are the matrices defined in (3) with $l=K_{i}$.

We consider polyhedral target set $Y_{f}\subset\mathbb{R}^{pK_{f}}$ and linear-inequality path constraints $c(u(t),y(t))\leq 0$, i.e., they can be written as:

where $G,H,S_{u},S_{y}$ and $g,h,s$ are matrices and vectors of compatible dimensions. Furthermore, we make the following “controlled invariance” assumption about $Y_{f}$:

Assumption 3: Let $\bar{K}_{f}=\max(K_{f},l_{\min})$. For any admissible pair of input-output trajectories of length $\bar{K}_{f}$, $({\bf u}_{[0:\bar{K}_{f}-1]},{\bf y}_{[0:\bar{K}_{f}-1]})$, that satisfies the path constraints $c(u(t),y(t))\leq 0$ for $t=0,...,\bar{K}_{f}-1$ and the target condition ${\bf y}_{[\bar{K}_{f}-K_{f}:\bar{K}_{f}-1]}\in Y_{f}$, there exist an input $u(\bar{K}_{f})$ and its corresponding output $y(\bar{K}_{f})$ such that they satisfy $c(u(\bar{K}_{f}),y(\bar{K}_{f}))\leq 0$ and ${\bf y}_{[\bar{K}_{f}-K_{f}+1:\bar{K}_{f}]}\in Y_{f}$.

In Assumption 3, because $\bar{K}_{f}\geq l_{\min}$, an admissible pair of input-output trajectories $({\bf u}_{[0:\bar{K}_{f}-1]},{\bf y}_{[0:\bar{K}_{f}-1]})$ corresponds to a unique initial state $x(0)$ and a unique state trajectory $x(0),x(1),...,x(\bar{K}_{f})$. Hence, for an input $u(\bar{K}_{f})$, the corresponding output $y(\bar{K}_{f})$ is also unique. Assumption 3 means that for any pair of input-state trajectories the output trajectory of which enters the target set $Y_{f}$ while satisfying the path constraints, there exists a control to maintain the output trajectory in $Y_{f}$ while satisfying the path constraints. Hence, it specifies a “controlled invariance” property of $Y_{f}$ with respect to the system dynamics and the path constraints.

Remark 1: While in many conventional trajectory optimization problem formulations the initial condition is a given value $x_{i}$ for the state at the initial time $t=0$, a given value for the output or a given pair of input-output at a single time is not sufficient for uniquely determining the trajectory. Therefore, we consider a pair of input-output trajectories of length $K_{i}$ that satisfies $K_{i}\geq l_{\min}$ as the initial condition which uniquely determines the initial state according to (6) and hence the trajectory. For the terminal condition, we consider a target set $Y_{f}$ instead of a single point to represent a larger class of problems which includes a single target point as a special case.

Lastly, we assume that a state-space model of the considered system (i.e., the matrices $(A,B,C,D)$ in (1)) is not given and only input-output trajectory data of the system are available. For instance, we may deal with a real system that has uncertain parameters while can generate input-output data (see the example in Section 5). The goal of this paper is to develop a computationally-efficient approach to the minimum-time trajectory optimization problem (5) for such a setting. We note that although it is possible to first identify the matrices $(A,B,C,D)$ using input-output data and system identification techniques and then solve the problem (5) based on the identified state-space model, this two-step approach may be cumbersome from the point of view of practitioners and $(A,B,C,D)$ that is compatible with given data is in general not unique. Therefore, we pursue an end-to-end solution – directly from input-output data to a solution to (5).

Assume that we have input-output trajectory data of length $M$:

where the superscript $d$ indicates “data.” Note that these input-output pairs $(u^{d}(t),y^{d}(t))$, $t=0,...,M-1$, should be sampled from a single trajectory¹¹1If the data are from multiple trajectories, then the inputs shall satisfy a collectively persistently exciting condition (van Waarde et al., 2020).. Construct the following Hankel data matrices:

where $L$ indicates the number of stacks of the signal $u^{d}$ or $y^{d}$ in each column. The control input trajectory $u^{d}(0),u^{d}(1),...,u^{d}(M-1)$ is said to be persistently exciting of order $L$ if $\mathcal{H}_{L}(u^{d})$ has full rank.

Our approach uses a result known as the fundamental lemma of Willems et al. (2005). The following lemma is an equivalent statement of Willems’ fundamental lemma in a state-space context (van Waarde et al., 2020):

Lemma 1: If the system (1) is controllable and the control input trajectory $u^{d}(0),u^{d}(1),...,u^{d}(M-1)$ is persistently exciting of order $L+n$, then a pair of input-output trajectories of length $L$, $({\bf u}_{[t:t+L-1]},{\bf y}_{[t:t+L-1]})$, is admissible by the system (1) if and only if

for some vector $\zeta\in\mathbb{R}^{M-L+1}$.

Assume $L>K_{i}$ and let $t=-K_{i}$. Then, (10) can be written as

Given $({\bf u}_{[-K_{i}:-1]},{\bf y}_{[-K_{i}:-1]})=({\bf u}_{i},{\bf y}_{i})$, (11) is a linear equation of variables $({\bf u}_{[0:L-K_{i}-1]},{\bf y}_{[0:L-K_{i}-1]},\zeta)\in\mathbb{R}^{m(L-K_{i})}\times\mathbb{R}^{p(L-K_{i})}\times\mathbb{R}^{M-L+1}$. In Coulson et al. (2019), (11) is used as a model for predicting the outputs $y(t)$ over the entire planning horizon $t=0,...,N-1$. This requires $L=N+K_{i}$. When the planning horizon $N$ is large, which is not rare in a trajectory optimization setting, such a strategy requires high-dimensional data matrices $(\mathcal{H}_{L}(u^{d}),\mathcal{H}_{L}(y^{d}))$ and requires the control input trajectory $u^{d}(0),u^{d}(1),...,u^{d}(M-1)$ to be persistently exciting of an order of $L+n=N+K_{i}+n$. Inspired by the multiple shooting method for trajectory optimization over an extended planning horizon (Trélat, 2012), we consider partitioning the entire trajectory of length $N=K(L-K_{i})$ into $K$ segments:

For each segment $k$, $k=1,...,K$, we stack its previous $K_{i}$ points on top to get the following vectors:

According to Lemma 1, for each $k=1,...,K$, the pair $({\sf u}_{k},{\sf y}_{k})$ is an admissible pair of input-output trajectories if and only if

for some $\zeta_{k}\in\mathbb{R}^{M-L+1}$. We refer to (14) for $k=1,...,K$ as equality dynamic constraints with $\zeta_{k}$ as auxiliary variables. Then, we impose the following equality matching conditions for $k=1,...,K-1$ to piece together the segments and form a long admissible trajectory:

i.e., we enforce the first $K_{i}$ points of ${\sf u}_{k+1}$ (resp. ${\sf y}_{k+1}$) to be equal to the last $K_{i}$ points of ${\sf u}_{k}$ (resp. ${\sf y}_{k}$). Note that because $K_{i}\geq l_{\min}$, an admissible pair of input-output trajectories of length $K_{i}$ corresponds to a unique state trajectory of length $K_{i}+1$. Specifically, given a state-space model (1) of the system, for an admissible pair of input-output trajectories of length $K_{i}$, with $K_{i}\geq l_{\min}$, the unique corresponding initial state can be determined by (4) with $l=K_{i}$, and then the states over the next $K_{i}$ steps are uniquely determined by this initial state and the given input trajectory. Therefore, matching the first $K_{i}$ points of $({\sf u}_{k+1},{\sf y}_{k+1})$ to the last $K_{i}$ points of $({\sf u}_{k},{\sf y}_{k})$ creates a continuous state trajectory $x((k-1)(L-K_{i})-K_{i}),...,x((k+1)(L-K_{i}))$.

The initial condition for the input-output trajectories in (5b) can be imposed through the following equality constraints on $({\sf u}_{1},{\sf y}_{1})$:

Also, the path constraints in (5d) can be imposed through the following inequality constraints for $k=1,...,K$ and $l=K_{i}+1,...,L$:

The input-output trajectories over the entire planning horizon $t=-K_{i},...,N-1$ can be constructed from the vectors ${\sf u}_{k}$ and ${\sf y}_{k}$, $k=1,...,K$, through the equations in (18). And we arrive at the following result:

Lemma 2: Suppose the system (1) is controllable and the control input trajectory $u^{d}(0),u^{d}(1),...,u^{d}(M-1)$ is persistently exciting of order $L+n$. Then, a pair of input-output trajectories $({\bf u}_{[-K_{i}:N-1]},{\bf y}_{[-K_{i}:N-1]})$, where $N$ can be written as $N=K(L-K_{i})$ for some $K\in\mathbb{Z}_{\geq 1}$, is admissible by the system (1) and satisfies the initial condition in (5b) and the path constraints in (5d) if and only if there exist vectors $({\sf u}_{k},{\sf y}_{k},\zeta_{k})\in\mathbb{R}^{mL}\times\mathbb{R}^{pL}\times\mathbb{R}^{M-L+1}$, $k=1,...,K$, that satisfy the constraints in (14), (15), (16) and (17) and $({\bf u}_{[-K_{i}:N-1]},{\bf y}_{[-K_{i}:N-1]})$ relate to the vectors $({\sf u}_{k},{\sf y}_{k})$, $k=1,...,K$, according to (18).

Proof: This result follows from Lemma 1 and the constructions of the vectors $({\sf u}_{k},{\sf y}_{k})$, $k=1,...,K$, in (12)–(13) and the constraints in (14)–(17). $\blacksquare$

Now we deal with the target condition ${\bf y}_{[T:T+K_{f}-1]}\in Y_{f}$. Recall that the goal is to minimize the time $T$ at which the output trajectory reaches the target set $Y_{f}=\{{\bf y}_{f}\in\mathbb{R}^{pK_{f}}:G{\bf y}_{f}\leq g,H{\bf y}_{f}=h\}$.

Assume that the minimum time $T^{*}$ is in the range of $[T_{0},T_{1}]$. For a given problem, such a range may be estimated based on prior knowledge or set to be sufficiently large (e.g., $T_{0}=0$ and $T_{1}$ being a large number). It will become clear soon that a smaller range (i.e., a closer estimate of $T^{*}$) makes the formulated problem simpler in terms of having less decision variables and constraints. For each $t\in[T_{0},T_{1}]$, define a slack variable $\varepsilon_{t}\in\mathbb{R}^{q_{g}+q_{h}}$, where $q_{g}$ is the dimension of $g$ and $q_{h}$ is that of $h$. Impose the following constraints for $\varepsilon_{t}$:

where $\varepsilon_{t,1:q_{g}}$ denotes the first $q_{g}$ rows of $\varepsilon_{t}$ and $\varepsilon_{t,q_{g}+1:q_{g}+q_{h}}$ denotes the remaining rows of $\varepsilon_{t}$. Then, ${\bf y}_{[t:t+K_{f}-1]}\in Y_{f}$ if and only if $0$ is a feasible value for $\varepsilon_{t}$.

Consider the following function:

where $\theta>1$ is a sufficiently large constant and $\|\cdot\|_{1}$ denotes the $1$-norm. The analysis in what follows shows that minimizing (20) can lead to a minimum-time trajectory solution:

Assume $T^{*}\in[T_{0},T_{1}]$ is known and consider the following problem parameterized by $\eta=\{\eta_{t}\}_{t=T^{*},...,T_{1}}$:

where $N$ represents a planning horizon that satisfies $N\geq T_{1}+K_{f}$, and $\eta_{t}\in\mathbb{R}^{q_{g}+q_{h}}$, $t=T^{*},...,T_{1}$, are parameters with the nominal value $\eta_{t}^{*}=0$. The following result clarifies the relation between the minimum-time problem of interest, (5), and the above problem (21):

Theorem 1: (i) Suppose Assumptions 2 and 3 hold. Let $({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},{\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},T^{*})$ be an optimal solution to the minimum-time problem (5) with $T^{*}\in[T_{0},T_{1}]$. Then, (21) with $\eta=0$ has a feasible solution $({\bf u}_{[-K_{i}:N-1]}^{\prime},{\bf y}_{[-K_{i}:N-1]}^{\prime},\{\varepsilon_{t}^{\prime}\}_{t=T_{0},...,T_{1}})$ that satisfies $({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{\prime},{\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{\prime})=({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},{\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{*})$ and $\varepsilon_{t}^{\prime}=0$ for $t=T^{*},...,T_{1}$.

(ii) Suppose (5) is feasible and has a minimum time $T^{*}\in[T_{0},T_{1}]$. Let $({\bf u}_{[-K_{i}:N-1]}^{\prime},{\bf y}_{[-K_{i}:N-1]}^{\prime},\{\varepsilon_{t}^{\prime}\}_{t=T_{0},...,T_{1}})$ be an arbitrary feasible solution to (21) with $\eta=0$. Then, the triple $({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{\prime},{\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{\prime},T^{*})$ is an optimal solution to (5).

Proof: For (i), let $({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},{\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},T^{*})$ be an optimal solution to (5). Because $K_{i}\geq l_{\min}$ and $T^{*}\geq 0$, $\bar{K}_{f}=\max(K_{f},l_{\min})$ must satisfy $-K_{i}\leq T^{*}+K_{f}-\bar{K}_{f}\leq T^{*}+K_{f}-1$. Then, under Assumption 2, $({\bf u}_{[T^{*}+K_{f}-\bar{K}_{f}:T^{*}+K_{f}-1]}^{*},{\bf y}_{[T^{*}+K_{f}-\bar{K}_{f}:T^{*}+K_{f}-1]}^{*})$ is an admissible pair of input-output trajectories of length $\bar{K}_{f}$ that satisfies $c(u(t),y(t))\leq 0$ for $t=T^{*}+K_{f}-\bar{K}_{f},...,T^{*}+K_{f}-1$ and ${\bf y}_{[T^{*}:T^{*}+K_{f}-1]}\in Y_{f}$. In this case, under Assumption 3, there exist inputs $u^{\prime}(T^{*}+K_{f}),...,u^{\prime}(N-1)$ and the corresponding outputs $y^{\prime}(T^{*}+K_{f}),...,y^{\prime}(N-1)$ such that $c(u(t),y(t))\leq 0$ for $t=T^{*}+K_{f},...,N-1$ and ${\bf y}_{[t:t+K_{f}-1]}\in Y_{f}$ for $t=T^{*}+1,...,T_{1}$. Now let ${\bf u}_{[-K_{i}:N-1]}^{\prime}=\text{col}({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},u^{\prime}(T^{*}+K_{f}),...,u^{\prime}(N-1))$ and ${\bf y}_{[-K_{i}:N-1]}^{\prime}=\text{col}({\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{*},y^{\prime}(T^{*}+K_{f}),...,y^{\prime}(N-1))$, and let $\varepsilon_{t}^{\prime}$ be defined according to $\varepsilon_{t,1:q_{g}}^{\prime}=G{\bf y}_{[t:t+K_{f}-1]}^{\prime}-g$ and $\varepsilon_{t,q_{g}+1:q_{g}+q_{h}}^{\prime}=H{\bf y}_{[t:t+K_{f}-1]}^{\prime}-h$ for $t=T_{0},...,T^{*}-1$ and $\varepsilon_{t}^{\prime}=0$ for $t=T^{*},...,T_{1}$. Then, the triple $({\bf u}_{[-K_{i}:N-1]}^{\prime},{\bf y}_{[-K_{i}:N-1]}^{\prime},\{\varepsilon_{t}^{\prime}\}_{t=T_{0},...,T_{1}})$ is a feasible solution to (21) with $\eta=0$. This proves part (i).

For part (ii), let $({\bf u}_{[-K_{i}:N-1]}^{\prime},{\bf y}_{[-K_{i}:N-1]}^{\prime},\{\varepsilon_{t}^{\prime}\}_{t=T_{0},...,T_{1}})$ be a feasible solution to (21) with $\eta=0$. Due to the constraints in (21d)–(21f), this solution satisfies ${\bf y}_{[T^{*}:T^{*}+K_{f}-1]}^{\prime}\in Y_{f}$. Therefore, the triple $({\bf u}_{[-K_{i}:T^{*}+K_{f}-1]}^{\prime},{\bf y}_{[-K_{i}:T^{*}+K_{f}-1]}^{\prime},T^{*})$ is an optimal solution to the minimum-time problem (5). $\blacksquare$