Minimize a non-convex function subject to linear dynamics constraint

Question

I want to solve the following problem: $$\min\limits_{\bf u} \frac{\bf c^T {\bf x} (T_f)}{\| \bf c\|\|{\bf x} (T_f)\|}$$

subject to

$$\dot{\bf x} (t) = A {\bf x}(t) + B {\bf u}(t)$$

$$x(0) = x_0$$

where ${\bf c} =(1, 1, \cdots, 1)^T \in \mathbb{R}^n$, ${\bf x} \in \mathbb{R}^n$, $A \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n\times q}$ and ${\bf u} \in \mathbb{R}^q$. The $x_0 \in \mathbb{R}^n $ denotes the initial state of the system and $T_f \in \mathbb{R}$ is the ternimal time which could be $\infty$. We choose Euclidean norm for $\|\cdot\|$.

Is there a standard solution for such a formulation and any solvers can help? thanks.

Answer 1

As answered on the YALMIP forum, what you want to do is to drive the state to a configuration where $x(T_f) = -\gamma c$ for some non-negative $\gamma$, as this will yield the minimal objective $-1$. If the system is controllable, this can be done for any choice of $T_f$ (and $\gamma$). By working with the Gramians, you should be able to derive an explicit control law using standard controllability arguments (see, e.g., Linear systems theory by Rugh)

Answer 2

Your criterion can be restated as $$\frac{c^Tx(T_f)}{\|c\|\|x(T_f)\|}=\frac{\|c\|\|x(T_f)\|\cos(\theta)}{\|c\|\|x(T_f)\|}=\cos(\theta)$$ where $\theta$ is the angle between vectors $c$ and $x(T_f)$. So its minimum value is $-1$ and can be achieved if $x(T_f)=-\lambda c$ for every positive real $\lambda>0$.

If the system $(A,B)$ is controllable then the controllability Grammian $$W_c(t)=\int_0^t{e^{As}BB^Te^{A^Ts}ds}$$ is positive definite for every $t > 0$ and the control input $$u(t)=-B^Te^{A^T(T_f-t)}W_c^{-1}(T_f)\left(\lambda c+e^{AT_f}x_0\right)\:,\qquad t\in[0,T_f]$$ yields the desired minimum value.

As you can see there is no unique input $u$ but an infinite number of inputs parameterized by $\lambda$.

The minimum value of $-1$ can be achieved even if the system is not controllable under the extra assumption that $$x_0,c\in Im \left[\matrix{B & AB & \cdots & A^{n-1}B}\right]$$

This follows from the decomposition of the system through suitable transformation to a controllable and uncontrollable part. Specifically if there are $k$ controllable modes and $n-k$ uncontrollable modes ($rank\left[\matrix{B & AB & \cdots & A^{n-1}B}\right]=k$) then there exists some nonsingular $T$ such that $$\bar{x}=Tx=\left[\matrix{T_1\\T_2}\right]x=\left[\matrix{\bar{x}_1\\\bar{x}_2}\right]$$ with $\bar{x}_1\in\mathbb{R}^{k}$ and $\bar{x}_2\in\mathbb{R}^{n-k}$ and $$\left[\matrix{\dot{\bar{x}}_1\\\dot{\bar{x}}_2}\right]=\left[\matrix{A_{c} & A_{12}\\ 0 & A_{\bar{c}}}\right]\left[\matrix{\bar{x}_1\\\bar{x}_2}\right]+\left[\matrix{B_c\\0}\right]u$$ with $(A_c,B_c)$ controllable.

The transformation $T$ is constructed as follows $$T^{-1}:=\left[\matrix{q_1 & \cdots & q_k & q_{k+1} & \cdots & q_n}\right]$$ with $q_1,\cdots, q_k$ $k$-linearly independent columns of the controllability matrix $$ \mathcal{C}:=\left[\matrix{B & AB & \cdots & A^{n-1}B}\right]$$ and $q_{k+1},\ldots,q_n$ extra columns to ensure the non-singularity of $T$ .

Note that $$\dot{\bar{x}}_2=A_{\bar{c}}\bar{x}_2$$ and therefore $$\bar{x}_2(T_f)=e^{A_{\bar{c}}T_f}\bar{x}_2(0)$$ Thus we want $$\bar{x}(T_f)=\left[\matrix{\bar{x}_1(T_f)\\e^{A_{\bar{c}}T_f}T_2x_0}\right]=Tx(T_f)=-\lambda Tc=-\lambda\left[\matrix{T_1 c\\ T_2c}\right]$$ So if we select the control input $$u(t)=-B_c^Te^{A_c^T(T_f-t)}\bar{W}_c^{-1}(T_f)\left\{e^{A_cT_f}T_1x_0 +\int_0^{T_f}{e^{A_c(T_f-s)}A_{12}e^{A_{\bar{c}}s}ds}T_2x_0+\lambda T_1c\right\}$$ with $$\bar{W}_c(t):=\int_0^t{e^{A_c s}B_c B_c^Te^{A_c^Ts}ds}$$ we ensure that $$\bar{x}_1(T_f)=-\lambda T_1c$$ Additionally the following condition must hold $$e^{A_{\bar{c}}T_f}T_2x_0+\lambda T_2c=0$$

Since $TT^{-1}=\mathbb{I}$ we have that $$T_2q_i=0\qquad \forall i=1,2,\cdots,k$$ If $$x_0,c\in Im \mathcal{C}$$ then there exist some $v_1,v_2\in\mathbb{R}^k$ such that $$x_0=\left[\matrix{q_1 & q_2 & \cdots & q_k}\right]v_1$$ $$c=\left[\matrix{q_1 & q_2 & \cdots & q_k}\right]v_2$$ and therefore $$T_2x_0=T_2\left[\matrix{q_1 & q_2 & \cdots & q_k}\right]v_1=\left[\matrix{T_2q_1 & T_2q_2 & \cdots & T_2q_k}\right]v_1=0$$ $$T_2c =T_2\left[\matrix{q_1 & q_2 & \cdots & q_k}\right]v_2=\left[\matrix{T_2q_1 & T_2q_2 & \cdots & T_2q_k}\right]v_2=0$$ that concludes the proof for the second part.