Logarithms in Karush-Kuhn-Tucker conditions

Question

I have the following optimization (and standarised) problem:

$$minimize\ -(x\ ln(x)\ +\ y\ ln(y))$$ $$subject\ to\ \ \ \ \ \ \ \ \ \ \ \ \ x+y-1<=0$$ $$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -x,\ -y <= 0$$

I have calculated the Lagrange's equation as:

$$L(x,y,\lambda_1,\lambda_2,\lambda_3)=-(x\ ln(x)+y\ ln(y))+\lambda_1(x+y-1)-\lambda_2 x-\lambda_3 y$$

And I have the following Karush–Kuhn–Tucker conditions:

$$\delta_xL=-ln(x)-1+\lambda_1-\lambda_2=0$$ $$\delta_yL=-ln(y)-1+\lambda_1-\lambda_3=0$$ $$\lambda_1(x+y-1)=0$$ $$\lambda_2x=0$$ $$\lambda_3y=0$$ $$x, y>=0$$ $$\lambda_1,\lambda_2,\lambda_3>=0$$

The question is the following: When I suppose, for example, that $\lambda_1=0,\ \lambda_2>0$ and $\lambda_3>0$, then by the above equations, we can assum that $x=0$ and $y=0$. So the point to be evaluated will be the $(0, 0)$. Is this point a local minimum of the given problem? I mean, when $x=0$ (or $y=0$), the first (or second) condition can't be calculated because the $ln(0)$ does not exist, so, in consequence, the point $(0,0)$ is not an candidate one, even if we see that it fixes the current optimization problem, becase $x\ ln(x)$ is 0.

Is this reasoning correct? Could you help me to solve this issue?

The same reasoning could be applied for the points $(0,1)$ and $(1,0)$?

Thanks!

Answer 1

Maybe this graphic helps

So you see intuitively the minima in the points (0,0), (0,1) and (1,0).

But indeed, the functions $\log(x)$ and $\log(y)$ are not defined in those points. The problem is a bit ill-defined and maybe we should say that there is no solution because the function has no solution for $x=0$ or $y=0$.

But we do have the limit $\lim_{x \to 0} -x \log(x) = 0$, and if you allow those then the function is defined everywhere.

---

I would say that the points (0,0), (1,0) and (0,1) are valid. But it is just that the method with Lagrange multipliers does not work well.

The solutions (0,0), (1,0) and (0,1) are then to be found by showing that the function $-x*log(x) - y*log(y)$ has no zero gradient on the interior of the domain defined by the constraints (there is a point around 0.3,0.3 but it is a maximum). Because of that we can conclude that the minimum must be at the borders, and we can find it with a line search (redefine/parameterize the problem as three single-dimensional problems).

---

To investigate this further:

We could if we want compute those contour lines by making $y$ a function of $x$ and solve it computationally

$$y \log(y) = c-x \log(y)$$

### function to find y as function of x using uniroot
invert_xy <- function(x) {
  uniroot(function(y) y*log(y)+x*log(x), interval = c(1,2), tol = 10^-100)$root
}
invert_xy <- Vectorize(invert_xy)  

xs <- seq(0.001,1,0.001)
plot(xs,invert_xy(xs), 
     xlab="x", ylab = "y", type = "l", xaxs="i", yaxs="i",
     ylim = c(0,2), xlim = c(0,2),
     main = "contour for \n-x*log(x) -y*log(y) = 0", cex.main = 1)
lines(invert_xy(xs),xs)


f = 100
xs <- seq(0.001/f,1/f,0.001/f)
plot(xs,invert_xy(xs), 
     xlab="x", ylab = "y", type = "l", xaxs="i", yaxs="i",
     ylim = 1+c(-1,1)/f, xlim = c(0,2/f),
     main = "closeup of contour \n near the border x=0", cex.main = 1)

The intuition behind the Lagrange multipliers is in comparing the gradient vector along the borders of the constraints. These gradients become infinite for $x=0$ or $y=0$, but the 'direction' can actually still be computed.

When we zoom in to the point (1,0) and look at the iso-line then we see the direction of the gradient approaches a horizontal direction.

This makes the very weird situation that the direction of the gradient is perpendicular to the line $x=0$, but you do not get a minimum because of it. The function does change along the line $x=0$.