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?
Best Answer
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).