1

This excercise has been taken from an exam. In the following problem: opt:x+y^2-2 subject to y^2<=x and x<=2-y and y>=0

I've found the green area to be the feasible region. feasible region (Sorry for the poorly drawn graph).

I determined, by Weierstrass' theorem, that the problem has global solutions (the objective function is continuous and the feasible region is bounded and closed). Then I proceeded by applying Kuhn-Tucker's method. I analyzed the values that x and y take when a different combination of values for the lagrange multipliers is made. I found the following critical points: (1;1) when both multipliers are greater than 0, (3/2;1/2) when the first multiplier is equal to 0 and the second multiplier is greater than 0. The other combinations of values for the multipliers are contradictory. The excercise asks you to explain why the solution can't be an interior point and to find the solution. The only frontier point that I find is (3/2;1/2), which you can get by examining the frontier where y=-x+2 (the red curve of the graph). I can't prove that the solution is an interior point, and I can´t classify the critical points that I found either because the 2 sufficient conditions that I know of don't apply. I'd appreciate if someone showed me all the steps to solve this.

Werther
  • 85
  • 1
    $f_x=1$ is never zero, so no internal point is an extremum. – Empy2 Jul 07 '14 at 23:27
  • If the maximum/minimum is attained in an interior point, the gradient of the function must vanish. But you have found that the gradient never vanish in an interior point. So? – mfl Jul 07 '14 at 23:28
  • The extremal points on the edges are either points like $(3/2,1/2)$ that you found by substituting $x=2-y$ then differentiating; or at the ends of the edges - that is, the vertices. – Empy2 Jul 07 '14 at 23:31
  • @Michael, the point (1;1) isn't interior, but I did find it by deriving the lagrangian function and making it equal to 0. Also, how do I know if these critical points are either maxima or minima? – Werther Jul 08 '14 at 00:05
  • You have a finite list of possible max/min. The highest is the maximum, the lowest is the minimum. – Empy2 Jul 08 '14 at 00:08
  • The Lagrangian multipliers are for the edges, when an extra condition is true $(x=2-y)$. In the interior, you simply look at the gradient of $x+y^2-2$. The gradient there is $(1,2y)$ which is never $(0,0)$. – Empy2 Jul 08 '14 at 00:11

1 Answers1

1

The problem is simpler than it may look to you. Note that the objective function is, for any fixed $x$, a monotonic increasing function of $y$, so the optimum must lie either on $y^2 = x$ with $0 \leq x \leq 1$ or on $y = 2x$ with $1 \leq x \leq 2$.

On the former curve, the objective function is $2x-2$ and the optimum is found at $x = 1$, with value $0$.

On the latter curve, the objective function is $$ x + (2-x)^2 - 2 = x^2 - 3x + 2$ $$ and this has a zero derivative extremum at $x = \frac{3}{2}$ but that is a minimum (with value $-\frac{1}{4}$) not a maximum. So the optimal point must either be at $(1,1)$ or at $(2,0)$. At both these points, the objective function has value $0$.

Mark Fischler
  • 41,743
  • Actually, at least as I've been taught, "optimum" is not a synonym of "maximum"; optimum is any point where the gradient equals 0 that is not a saddle point. Also, I see you inmediately went for the frontier points, not the interior points, and it seems that you discarded the existence of interior points because of the monotonic nature of the objective function; please, explain the relevance of the fact that the function is an increasing monotonic one. – Werther Jul 08 '14 at 02:12
  • I was using the term "optimum" as the point that makes the objective function as large as it can be, subject to the constraints.Since the function is monotone increasing – Mark Fischler Jul 08 '14 at 16:03
  • Since the function $f$ is monotone increasing in $y$ for any fixed $x$, if you conjecture that the greatest value of $f$ lies on a point $p_1 = (x,y)$ in the allowed region such that there is another point $p_2=(x,y+|\delta|$ also in the allowed region, then $f(P_2)> f(p_1)$ so $p_1$ was not actually the optimum. Thus the optimum must lie somewhere on the maximum-$y$ boundary of the feasible region. – Mark Fischler Jul 08 '14 at 16:07