Kuhn-Tucker's Conditions for optimization problem with non linear inequalities constraints

Question

My problem is to minimize the function \begin{align*} f(x,y,z,t)=& 3 t \left(2 x^2+4 x z\right) \left(2 t x y+t x z-2 t y^2-2 x z+4 y z\right) \\ &+\left(-t x^2+4 t x y+4 t y z+4 x z-8 y z\right)^2 \end{align*} under constraints \begin{align*} g_1(x, y, z, t) &= x\leq 0 ,\\ g_2(x, y, z, t)&= x - y\leq 0, \\ g_3(x, y, z, t)&= y - x - z\leq 0, \\ g_4(x, y, z, t)&= 1 - t\leq 0. \end{align*} The Lagrangian is $$ \mathscr{L}=f-\lambda _1g_1 -\lambda _2g_2-\lambda _3g_3 -\lambda _4g_4 $$ Then $$ \mathscr{L}=-\lambda _4 (1-t)+3 t \left(2 x^2+4 x z\right) \left(2 t x y+t x z-2 t y^2-2 x z+4 y z\right)+\left(-t x^2+4 t x y+4 t y z+4 x z-8 y z\right)^2-\lambda _1 x-\lambda _2 (x-y)-\lambda _3 (-x+y-z) $$ So the necessary conditions of KKT are: \begin{align*} \dfrac{\partial }{\partial x}\mathscr{L}& =4 t^2 x^3 + 12 t^2 x^2 y + 8 t^2 x y^2 - 60 t x^2 z + 18 t^2 x^2 z + 144 t x y z + 32 t^2 x y z - 64 t y^2 z + 8 t^2 y^2 z + 32 x z^2 - 48 t x z^2 + 24 t^2 x z^2 - 64 y z^2 + 80 t y z^2=0\\ \dfrac{\partial }{\partial y}\mathscr{L}& =4 t^2 x^3 + 8 t^2 x^2 y + 72 t x^2 z + 16 t^2 x^2 z - 128 t x y z + 16 t^2 x y z - 64 x z^2 + 80 t x z^2 + 128 y z^2 - 128 t y z^2 + 32 t^2 y z^2=0\\ \dfrac{\partial }{\partial z}\mathscr{L}& -20 t x^3 + 6 t^2 x^3 + 72 t x^2 y + 16 t^2 x^2 y - 64 t x y^2 + 8 t^2 x y^2 + 32 x^2 z - 48 t x^2 z + 24 t^2 x^2 z - 128 x y z + 160 t x y z + 128 y^2 z - 128 t y^2 z + 32 t^2 y^2 z=0\\ \dfrac{\partial }{\partial t}\mathscr{L}& =2 t x^4 + 8 t x^3 y + 8 t x^2 y^2 - 20 x^3 z + 12 t x^3 z + 72 x^2 y z + 32 t x^2 y z - 64 x y^2 z + 16 t x y^2 z - 24 x^2 z^2 + 24 t x^2 z^2 + 80 x y z^2 - 64 y^2 z^2 + 32 t y^2 z^2=0 \end{align*} Solution is given by this following: \begin{align*} (y = x/2 \wedge t= 0) & \vee\\ (z = 0 \wedge t= 0 ) & \vee \\ (x = 0 \wedge y = 0) & \vee\\ ( x = 0\wedge z = 0) & \vee \\ (y = x/2\wedge z = -(x/2)& \vee\\ (y = x/2\wedge z =-(x/2), t =-5)& \vee\\ (y= x/2\wedge z = -(x/2)\wedge t = -2)& \vee\\ (y = x\wedge z = -(x/2)\wedge t =-2)& \vee\\ ( y = x/2\wedge z = -(x/2)\wedge t = -1)& \vee\\ ( x = 0\wedge y = 0, t = 2)& \vee\\ (x = 0\wedge y = z\wedge t = 2)\vee\\ (x = 0\wedge z = 0\wedge t = 2) \end{align*} So could you give me a hint for conclude. Thank's in advance

Answer 1

Well, now that you have such a nice list, I would advice to test the value of $f$ at any solution of the KKT equations. The one whose value is the lowest is your candidate for optimality.

For examples, the first 3 cases ($y=x/2, t=0$ or $t=z=0$ or $x=y=0$) all lead to $f(x,y,z,t)=0$. I let you deal with the other cases.

Another advice: to get less candidate for optimality, you should compute the Lagrange multiplier for each of them: if their signs aren't right (see KKT theorem), then it is not a real candidate for optimality (it is your call to see if it is worth computing these Lagrange multiplier, or if it is faster to evaluate $f$ for all of them; but in many interesting cases, this remark is very helpful).

Last warning: let's say you find the best candidate for the minimization of $f$. There remains a gap in the proof that it is the minimum for your optimization problem: indeed, you need to prove the existence of a minimizer first, which is sometimes not trivial. Two easy cases are if the set of definition is compact (which isn't the case for you), or if $f$ is coercive (goes to $+\infty$ when $\|(x,y,z,t)\|\to\infty$. Another different situation is if the problem is convex (I don't think it is the case in your example, but it is worth knowing it): in that case, if you find a solution of the KKT equations, then this solution has to be a minimizer for your problem (and therefore you get existence): this it some kind of converce of KKT theorem, in the convex setting.

Answer 2

To distinguish between max and min, if you check every solution in the list, it is easy, the higher value for $f$ is the max, the lowest is the min. About my remark about signs, the Lagrange multiplier must have a sign, one for the min, the opposite for the max (check the theorem, I don't remember !) But the remark of @yhhuang seems of use, maybe your equations/solutions aren't valid, I haven't checked.

When using KKT, you should always consider two cases for each constraint: either the constraint is non saturated (for example $x<0$) and then $\lambda_1$ (corresponding to $g=x$) is 0, or the constraint is saturated: in that case $\lambda_1$ is a new unknown (though as I said, there is a sign, depending wheather you search for a max or a min), but you have another information $x=0$.

Well, double check your computations before checking all the candidates. But if there exists both a max and a min (which is always true in a compact set for example, though in your case, I don't have a clue about existence, I would be surprised if there is both a max and a min (global)), both of them are in the list of candidates (solutions to KKT): the max is the one whose energy is maximal (among the one in the list, which should all be computable), the min is... the min !