Reformulation of optimization problem using kkt and lagrange conditions

Question

Following setup:

$$ \begin{align} \min_{y} &\frac{1}{2} y^T \bar{H} y \left(=V_k-V_{k+1}\right) \\ \text{s.t. } &x_{k+1}=Ax_k+Bu_k^*\\ &U_k^* = \underset{U_k}{\arg \min} V_k,\\ &U_{k+1}^* = \underset{U_{k+1}}{\arg \min} V_{k+1}, \end{align}$$ where I assume that $y = \begin{bmatrix}U_k^T, x_k^T, U_{k+1}^T,x_{k+1}^T\end{bmatrix}^T$, the Lyapunov function candidate $$V_k = U_k^T H U_k + U_k^T G x_k + x_k^T \bar{Q}x_k$$ $\bar{H}$ is an indefinite matrix of appropriate dimension, $H$ is a positive semidefinite matrix of appropriate dimension ($H,G,\bar{Q}$ depend on $N$, not important here) and the two last equality constraints/min problems are convex, that is I can replace them with the sufficient and necessary KKT-conditions. I also assume that the two last min problems do not have any constraints. Lastly, $U_k = \begin{bmatrix}u_k^T, ...,u_{k+N-1}^T\end{bmatrix}^T$ with $x_k,u_k$ denoting the state and input of a discrete system at time $k$ and $N\in \mathbb{N}^+$ (for more detail, also regarding the other matrices, the problem is from here.

If I replace the two last constraints with the (in this case lagrange) conditions, I can write the problem as $$ \begin{align} \min_{y} &\frac{1}{2} y^T \bar{H} y\\ \text{s.t. } &\bar{E}y=0, \end{align}$$ where $\bar{E}$ collects $$ \begin{align} x_{k+1}=Ax_k+Bu_k,\\ HU_k + Gx_k = 0,\\ HU_{k+1}+Gx_{k+1}=0. \end{align} $$ Now with $\bar{H}$ being indefinite, the kkt (in this case lagrange since no inequality constraints) conditions are only necessary if I wanted to replace the optimization problem. I end up with $$\begin{align} \bar{H}y + \bar{E}^T \lambda = 0\\ \bar{E} y =0\\ \end{align}$$ as neccessary conditions. This means that if there is a configuration such that $V_k-V_{k+1}$ is $<0$, I should be able to find it using those conditions.

Now by inspection, for a given $A,B,N$, I can find such a $y$. However, solving the system of conditions, I only find $y=0$ since if I reformulate to a homogenous matrix equation, the corresponding kernel of the matrix contains only the null vector. Furthermore I notice that in the optimum, $y$ satifies $$ \bar{H} y = -\bar{E}^T\lambda$$ and thus $$ \frac{1}{2} y^T \bar{H} y = -\frac{1}{2} y^T \bar{E}^T\lambda =-\frac{1}{2} \left(\bar{E} y\right) \lambda = 0.$$ Hence, I cannot ever get a solution from these conditions such that $\frac{1}{2} y^T \bar{H} y<0$?

Question

Obviously, something doesn't add up here. Is there a mistake in the derivation of those conditions?

Answer 1

Example: take $$ \bar H=\begin{bmatrix}1 & 0\\0 & -2\end{bmatrix},\qquad \bar E=\begin{bmatrix}1 & -1\end{bmatrix}. $$ Then you are minimizing $y_1^2-2y_2^2$ subject to $y_1=y_2$.

The necessary condition gives $$ \begin{cases} y_1+\lambda&=&0,\\ -2y_2-\lambda&=&0 \end{cases}\quad\implies\quad y_1=2y_2. $$ Together with $y_1=y_2$ it makes $y_1=y_2=0$, with the objective function being zero.

However, if you take a feasible point $y_1=y_2=1$ you get the smaller objective function value $-1<0$. What's wrong?

The wrong part is the application of the necessary condition, which is applicable only if the minimum exists. In our case, the minimum does not exist: take $y_1=y_2=t$ and let $t\to+\infty$, you get $-t^2\to-\infty$.

One can compare the phenomenon with an unconstrained minimization: $$\min x^3.$$ The necessary condition $3x^2=0$ gives the saddle point $x=0$ that has nothing to do with the solution (which does not exist).