Maximization problems - Using implicit function to avoid KKT

Question

I am wondering if the following procedure to solve a maximization problem in - let's say - two variables with inequality and non-negative constraints works.

More specifically, let's assume something like the following concrete example:
$ \text{max } F(x,y)=x^{\frac{2}{3}} y^{\frac{1}{3}}$
$ \text{sub } G(x,y)=x^2 + y^2 \leq 2 \hspace{0.5cm}\text{and } x,y\geq 0$

I thought that, instead of using Kuhn-Tucker conditions, which would bring me to a real nightmare, it would be better to go for the following steps:

I realize that the objective function is increasing in $\mathbb{R}^3_{+}$.
For this reason the constraint has to work as an equality constraint and it is binding.
I take the implicit function of $F(x,y)$ of $y$ in terms of $x$ and I put it equal to the same thing, for the inequality constraint.
I create a system with the previous equation and the inequality constraint expressed as an equality constraint.
I focus on the positive value of $x$ and $y$ and that's it.

Does it sound reasonable?
Any feedback is welcome!

How general a technique are you trying to make here? Because you could cube that objective function without changing the optimal point, as well. Then you simply have $x^2y=(2-y^2)y$ to maximize over $y\in[0,\sqrt{2}]$. But again, it's not clear how particular this example is. I agree with your work so far though. — Michael Grant, May 24 '13 at 19:27
Actually, I was interested in Cobb-Douglas functions in general: namely, any objective function of the form $x^{\alpha} y^{1-\alpha}$. — Kolmin, May 24 '13 at 19:31
Actually, any strictly increasing function in $\mathbb{R}^3$ should work in this setting. — Kolmin, May 24 '13 at 19:40
Given the general setting of the objective function (which could be considered specific), I would say that the constraint should be pretty general, but no idea how to prove it. — Kolmin, May 24 '13 at 19:42
$x^\alpha y^{1-\alpha}$ is not just increasing but concave in the nonnegative orthant. So as stated you have a convex optimization problem, and you can consider a variety of general convex constraints on $x$ and $y$ without sacrificing tractability. The solution will indeed satisfy $x,y>0$ unless the interior of the feasible region is empty. — Michael Grant, May 24 '13 at 20:30

gerw · Answer 1 · 2013-05-25T06:46:53.293

1

This sound reasonable. The precise justification for your step 1 could go along the following lines: Assume that $(x,y)$ is a (feasible) minimizer of $F$. Obviously, $F(x,y) > 0$.

Assume $r^2 := x^2 + y^2 < 2$. Then, take $(\sqrt2 \, x/r,\sqrt 2\,y/r)$. Obviously, this point is still feasible and $F(\sqrt 2 \, x/r,\sqrt 2\,y/r) = F(x,y) \, \sqrt 2/r > F(x,y)$. Contradiction.

Hence, $x^2 + y^2 = 2$ holds for the minimizer.

edited May 25 '13 at 06:46

answered May 24 '13 at 19:17

gerw

31,359

Two questions: 1) you write minimizer cause you set the problem as a minimization one, right?; 2) I don't want to look naive but exactly how do $(2x/r,2y/r)$ come from? – Kolmin May 24 '13 at 19:33
Yes, I usually minimize functionals ;) 2) Oh, I should replace $2$ by $\sqrt 2$. And then, $(\sqrt 2x/r)^2 + (\sqrt 2y/r)^2 = 2$.

gerw

May 25 '13 at 06:46

score 1 · Accepted Answer · answered May 24 '13 at 19:29

1

Your assumptions of (1) and (2) are correct and then you can use a more formal way. To maximize $F(x,y)$ the first differential must be zero $$dF=\frac{\partial F}{\partial x}dx+\frac{\partial F}{\partial y}dy=\frac 23 \frac{y^{1/3}}{x^{1/3}}dx+\frac 13 \frac{x^{2/3}}{y^{2/3}}dy=0$$ Due to constraint $dx$ and $dy$ are related in a way that $x$ and $y$ must always be on the curve $G(x,y)=2$. To find the relation we use the first differential $$dG=\frac{\partial G}{\partial x}dx+\frac{\partial G}{\partial y}dy=2x\,dx+2y\,dy=0\Rightarrow dy=-\frac xy dx$$ Now we can use this relation to eliminate $dy$ in $dF$ $$dF=\frac 23 \frac{y^{1/3}}{x^{1/3}}dx-\frac 13 \frac{x^{2/3}}{y^{2/3}}\frac xy dx=0$$ $$dF=\bigg(\frac 23 \frac{y^{1/3}}{x^{1/3}}-\frac 13 \frac{x^{2/3}}{y^{2/3}}\frac xy\bigg) dx=0$$ The above equation can be satisfied for any $dx$ (or in any directions) if $$\frac 23 \frac{y^{1/3}}{x^{1/3}}-\frac 13 \frac{x^{2/3}}{y^{2/3}}\frac xy=0$$ $$2 \frac{y^{1/3}}{x^{1/3}}=\frac{x^{5/3}}{y^{5/3}}$$ $$2 y^2=x^2\Rightarrow y=\frac x{\sqrt 2}$$ Now we satisfied that objective $F(x,y)$ is maximized along the curve $G(x,y)$. We need to satisfy one more condition that $G(x,y)=2$ by using the relation between $y$ and $x$ $$x^2+y^2=x^2+\frac{x^2}2=2\Rightarrow x=\frac 2{\sqrt 3}$$ and $$y=\frac x{\sqrt 2}=\frac {\sqrt 2}{\sqrt 3}$$ So you neither used Lagrange multipliers nor KKT.

answered May 24 '13 at 19:29

AnilB

4,202

Just wondering, would you accept my steps, even if formally a bit sloppy? [Actually, now I realize my step (3) could look a bit cryptic - I simply meant that we use the implicit function on the constraint as well, and then we make it equal to the result of the implicit function applied to the objective function] – Kolmin May 24 '13 at 19:47
You can only take the implicit of $F(x,y)$ if it is in the form of $F(x,y)=a$ where $a$ is any constant. Can you give more details on this step? – AnilB May 24 '13 at 19:52
Basically I set a system of equations and the equations are: (1) $- \frac{x}{y} = - \frac{2y}{x}$ and (2) $x^{2} + y^{2} = 2$. Equation (1) is indeed the result of putting the result of the application of the implicit function theorem to the objective function equal to the result of the application of the same theorem to the constraint (obviously in terms of the same variable); equation (2) is the inequality constraint expressed as an equality constraint for the theoretical reasons previously pointed. – Kolmin May 24 '13 at 20:01
Yes it seems OK. You are able to do it. – AnilB May 24 '13 at 20:04
Actually, it seems this procedure work (given the assumptions I put in my previous answer to your question on the constraint). Namely, as far as the objective function is strictly increasing, it seems to me that we can take whatever inequality constraint and the procedure gives us the desire result. Is it sound? Is it always the case? As I wrote before, I don't know. – Kolmin May 24 '13 at 20:07
Sorry, I didn't read your last comment while I was writing. Ok, great. Thanks. – Kolmin May 24 '13 at 20:07
No problem. It is great that you are not stuck with usual methods and looking for your own ways. Keep on going... – AnilB May 24 '13 at 20:09
I would say it's a natural reaction to the pure fear I have every time I need to come up with the "computationally easy" KKT... truly a nightmare. Again, thanks! – Kolmin May 24 '13 at 20:13

Maximization problems - Using implicit function to avoid KKT

2 Answers2