# Minimisation problem turned into Maximisation

My course always converts minimisation problems into maximisation. They give the following reason as outlined in the problem below.

$$Min\; P_xx + P_yy \; s.t. \; u(x,y) \le x^{\frac{1}{2}} + y$$

• "In order to apply the Kuhn-Tucker theorem we can rewrite this problem as"

They would write it as:

$$Max\; -(P_xx + P_yy) \; s.t. \; -u(x,y) \ge -(x^{\frac{1}{2}} + y)$$

1. As far as i'm aware it's not strictly necessary to do this, so long as our constraint and objective function are both convex (i.e. our Lagrangian is convex), then the KKT / Lagrange technique will find a minimum, just as it would find a maximum, and through duality, these will be the same value. So why the emphasis? I have suspicion that it could be to do with a subtle point regarding non-negativity constraints that they haven't elaborated.

Non negativity constraints: Assuming the possibility of $$y = 0$$ I have written the problem below both as a maximisation and a minimisation:

Max: $$L(,x,t,λ) = -(P_xx + P_yy) - λ[(\bar{u} -(x^{\frac{1}{2}} + y)] + μy$$
Min: $$L(,x,t,λ) = (P_xx + P_yy) + λ[(\bar{u} -(x^{\frac{1}{2}} + y)] - μy$$

Taking the FOC with respect to y from the Maximisation problem we get:

$$\frac{\partial L}{\partial y} = -P_yy + λ + m \le 0$$ Which as $$μ \ge 0$$ implies $$\frac{\partial L}{\partial y} = -P_yy + λ \le 0$$

• $$P_yy \ge λ$$

And now here is my problem, taking the FOC with a respect to the Minimisation problem we get.

$$\frac{\partial L}{\partial y} = P_yy - λ - μ \le 0$$

Question: I believe that when we have a minimisation problem, and are testing a binding non-negativity constraint i.e. boundary solution on the axis, then the inequality in the FOC becomes $$\ge 0$$ Is this correct?

I.e. It should be: $$\frac{\partial L}{\partial y} = P_yy - λ - μ \ge 0$$ Which as $$μ \ge 0$$ implies $$\frac{\partial L}{\partial y} = P_yy - λ \ge 0$$

• $$P_yy \ge λ$$

This is the only way i can get it to make sense otherwise the two versions are giving different results. This problem goes unnoticed when it's equality contained. And because my course has never written the problem formally as a minimisation problem i haven't been able to see what happens in this boundary case.

if i am correct can someone explain some economic / mathematical intuition behind the $$\ge 0$$.

Thanks!

Update 23/04/2024

To try and make clear what version of KKT (i think) i'm following as suggested by Michael, i have outlined the nuances in the comments of two different courses i have taken. For context the degree is self taught so i have very little outside help apart from the kindness of fellow enthusiasts like yourselves! It also means differences in methods are hard to distinguish between expedience of a particular module vs fundamental difference.

The images i am attaching here are screenshots from this youtube lecture series by Mark Walker, which is the Econ PHD maths prep programme. It's been the most useful reference for me!

• There are several versions of the KKM-Theorem. It would be helpful if you would state which one you are using. Commented Apr 22 at 23:14
• That is it self really helpful. I’ve never been taught that there are several versions (I’ve just learnt what I felt was the same thing in some times different ways). Could you tell me their names or a reference and I will try and identify which I’m using, thank you! Commented Apr 23 at 7:13
• Also I am referring to the KKT conditions for inequality constrained optimisation. Karush–Kuhn–Tucker. You mentioned KKM, I’m not sure if that’s a typo, or related concept, or perhaps alternate name? Commented Apr 23 at 7:15
• Sorry, that was a misspelling. The various versions differ in the form of the constraint qualifications used, whether differentiabikity assumptions are made, what the domain is etc. Commented Apr 23 at 7:19
• I don't have an answer to your question but maybe look at a well respected textbook ? Back in the pre-historic times, Bazarra and Shetty was quite popular. I'm not sure if it's still used in OR departments ? Nowadays there is a book by Bertsimas and also a book by Boyd that are both quite popular but I can't comment on their exposition of KKT. Nocedal and Wright is another one that just came into my mind. Commented Apr 23 at 9:39

You have the function $$f:\mathbb{R}^n\to\mathbb{R}$$ you want to maximize, subject to the constraint (written using vector notation) that $$G(x)\leq b$$ for a function $$G:\mathbb{R}^n\to\mathbb{R}^m$$ and some $$b\in\mathbb{R}^m$$. The Lagrangian $$L:\mathbb{R}^n\times\mathbb{R}^m_+\to\mathbb{R}$$ is given by $$L(x,\lambda)=f(x)+\lambda\cdot (b-G(x)).$$ You can view the Lagrangian as the payoff-function of a zero-sum game. One player, the one controlling $$x$$, wants to maximize the Lagrangian, and the other player, the one controlling $$\lambda$$, wants to minimize the Lagrangian. The sufficiency conditions tell you that if you have an equilibrium of this game, then the payoff of the maximizer is the maximum of the optimization problem. The necessary conditions guarantee that an equilibrium exists and that a minimax theorem holds for this game: $$\sup_{x\in\mathbb{R}^n}\inf_{\lambda\in\mathbb{R}^m_+}L(x,\lambda)=\inf_{\lambda\in\mathbb{R}^m_+}\sup_{x\in\mathbb{R}^n} L(x,\lambda).$$ The sup becomes a max, the inf becomes a min, and the solutions are given by first-order conditions. Here is the idea of why this works: If the maximizer maximizes $$f$$ under the constraint, we get $$b-G(x)\geq 0$$, and thus, for every $$\lambda\geq 0,$$ one has $$\lambda\cdot (b-G(x))\geq 0$$. Since $$\lambda=0$$ is always possible for the minimizer, we must have $$\lambda\cdot (b-G(x))= 0$$. However, if the maximizer would violate the constraint, there must be some coordinate $$i=1,\ldots,m$$ such that $$b_i-G_i(x)<0$$. Let $$e_i\in\mathbb{R}^m$$ be the vector with a $$1$$ in the $$i$$th place, and all other coordinates $$0$$. For $$\lambda=C e_i$$ with $$C$$ a large positive number, the Lagragian can be made arbitrarily small (negative). So the maximizer has to satisfy the constraint in order for the minimizer not to "win." Duality tells you that it doesn't matter which player would move first, but it doesn't change the asymmetry between maximizing and minimizing. Of course you can rewrite the result to be one for minimization problems, which is exactly what you get by maximizing $$-f$$.