# Reformulation of optimization problem using kkt and lagrange conditions

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?

• Minimization of a quadratic form subject to linear constraints (a subspace) gives either zero, if the quadratic form is non-negative on the subspace, or $-\infty$ otherwise. I guess already your reformulation might be wrong then if you need negative $y^T\bar Hy$ as an answer. However, $y^T\bar Hy=0$ does not mean necessarily $y=0$ if the matrix is not positive definite on the subspace.
– A.Γ.
Jul 26, 2018 at 10:10
• Thank you for your comment. The reformulation from $V_k-V_{k+1}$ to $y^T\bar{H}y$ is likely correct. As stated, I am able to find, for a specific $A,B,N$, a $y$ with $y^T\bar{H}y<0$. That is for the second optimization problem, I can find a $y$ which satisfies $y^T\bar{H}y<0$ under constraint $\bar{E}y=0$. As from there, I use neccesary but not sufficient conditions, shouldn't I, with what you said in mind, then get $-\infty$ instead of $0$? From my understanding, the final conditions should give me values of $y$ which contain the optimum, which should be $\leq$ the value i guessed.
– VGD
Jul 26, 2018 at 11:24
• Yes, then you get $-\infty$ and the necessary conditions (Lagrange or KKT) is not applicable. If $y_0^T\bar Hy_0<0$ with $\bar Ey_0=0$ then just set $y=ty_0$ and let $t\to\infty$ to see that the function is unbounded on the subspace ($\inf=-\infty$). You need more constraints on your control variable to make the problem reasonable (i.e. to ensure existence of min).
– A.Γ.
Jul 26, 2018 at 11:41
• Can you elaborate on why I then cannot apply lagrange/KKT to the second optimization problem? Checking wikipedia for the KKT, it says that they are applicable as long as e.g. my constraints are affine functions, which they are.
– VGD
Jul 26, 2018 at 11:55

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).