LiveLowGrow said:
That was superb...thank you very much for your time and effort and being so lucid in your explanation...I was only unfamiliar with term nabal "look at points where \nabal f = 0 inside that sphere"...
which I guess means I did not have that symbol in my computers font selection?
..your answer has allowed me to answer several of the other variations of max min I have...
..not to press my luck...but regarding the Type 2 question in my original post...
when I get to this stage..
1) 2x-1 = λ2x + (mu)(0)
2) 2y-1 = λ2y + (mu)(0)
3) -2z-1 = λ(0) + (mu)(2z)
and the system of equations becomes..
1) 2x-1=λ2x
2) 2y-1=λ2y
3) -2z-1=(mu)(2z)
what would you recommend in this situation or more generally what are the main techniques I would try to solve these?
1) look for a lonely variable x or y to isolate
2) divide one by another and cross multiply as we did above
3) ....??
my goal is always to get two of the three variables and plug it into my constraint?
what is the process for two constraints?
any advice if you have a moment would be much appreciated...and thank you again for your prior insight...
In general: suppose that for a vector of variables x = (x1,x2,...,xn) we have a problem such as max/min f(x) subject to g1(x) <= 0, g2(x) <= 0,..., gm(x) <= 0. The standard method is to form a Lagrangian and to set its gradient to zero. There are other conditions as well, but let's deal with them later. The main difference between an inequality-constrained problem and an equality-constrained one is that for inequalities
the signs of the Lagrange multipliers are known, provided that we form the Lagrangian in the correct manner. Here, the general rule is: form a Lagrangian so that it is better than the objective f for feasible points. Here, "better" means larger in a max problem and smaller in a min problem. So, if our problem is max f subject to g_i <= 0 for i = 1,2,...,m, then for a feasible point we want L to be larger than f; we achieve this by subtracting positive multiples of the g_i from f (because we would be subtracting negative quantities). So we let
L(x,u) = f(x) - \sum_{i=1}^m u_i g_i (x), where ##u_1, u_2, \ldots, u_m ## are the Lagrange multipliers (often denoted as ##\lambda_i##, but ##u## is just as good a symbol as ##\lambda##). The point is that the signs are known: we have ## u_1 \geq 0, u_2 \geq 0, \ldots, u_m \geq 0.##
Now we have the optimality conditions:
(1)\; \partial L/ \partial x_j = 0, \: j = 1, 2, \ldots, n \\<br />
(2)\; u_i \geq 0, i = 1, 2, \ldots, m \\<br />
(3)\; \text{either } g_i = 0 \text{ or } u_i = 0.
What is condition (3) all about? Well, the optimal solution is either in the interior of the ith constraint---where ##g_i(x) < 0##--- or it is on the boundary of the ith constraint---where ##g_i(x) = 0.## If it is in the interior we essentially ignore g_i, and this is achieved by setting u_i = 0 so that g_i does not appear in the optimality condition, and so does not affect x. If it is on the boundary, then we have, essentially, an equality constraint g_i = 0, and so do have a Lagrange multiplier (which could, nevertheless, still = 0 by accident). However, unlike a problem that had an equality constraint from the "get-go", in the present case the sign of the Lagrange multiplier is restricted.
So, let's look at the first problem in max form.
max f(x,y,z) = x^2 + y^2 + z^2 - xyz, subject to g(x,y,z) = x^2 + y^2 + z^2 -1 <= 0.
L = f - u g = x^2 + y^2 + x^2 - xyz - u (x^2+y^2+z^2-1).
The optimality conditions are:
L_x = \partial L / \partial x = 0 \Longrightarrow 2x - yz - 2u x = 0\\<br />
L_y = \partial L / \partial y = 0 \Longrightarrow 2y - xz - 2u y = 0\\<br />
L_z = \partial L / \partial z = 0 \Longrightarrow 2z - xy - 2u z = 0
and u = 0 or g = 0.
If we first try u = 0 we obtain 5 candidate points (where grad f = 0):
(x,y,z) = (0,0,0),\: (2,2,2), \: (2,-2,-2),\: (-2,-2,2), \:(-2,2,-2).
Only the first point (0,0,0) satisfies the constraint g <= 0. The Hessian matrix of f at this point is positive-definite, so (0,0,0) is a strict local
minimum. Therefore, we have solved the min problem, not the max problem!
OK, so now we know that a max must be on the boundary, so u may by > 0. Besides the previous solution (x,y,z) = (0,0,0), we get:
\begin{array}[cccc] ((x,y,z) &= & (2-2u, 2-2u, 2 - 2u) & (P1) \\<br />
(x,y,z) &=& (2 - 2u, -2 + 2u, -2 + 2u) & (P2)\\<br />
(x,y,z) &=& ( -2 + 2u, 2 - 2u, -2 + 2u) & (P3)\\<br />
(x,y,z) &=& (-2 + 2u, -2 + 2u, 2 - 2u) & (P4)<br />
\end{array}<br />
Substituting P1 into the equation g1 = 0 gives two solutions:
u_1 = 1 + \frac{1}{6}\sqrt{3} \doteq 1.288675, \;<br />
u_2 = 1 - \frac{1}{6}\sqrt{3} \doteq 0.71132,
Both u_1 and u_2 are > 0, so u = u_1 and u = u_2 give two candidate points for the max:
u = u_1 \Longrightarrow (x,y,z) = (-\sqrt{3}/3,-\sqrt{3}/3, -\sqrt{3}/3), \: g = 0, \; f = 1 + \frac{1}{9}\sqrt{3} \doteq 1.19245\\<br />
u = u_2 \Longrightarrow (x,y,z) = (\sqrt{3}/3,\sqrt{3}/3,\sqrt{3}/3), \; g = 0, \:<br />
f = 1 - \frac{2}{9}\sqrt{3} \doteq 0.80755 .
The first point above must be a local max of f; the second point may be another local max or may be a constrained saddle point. We would have to perform some second-derivative tests to tell which case applies. (However, the second-derivative tests would be tricky: they involve testing the Hessian of the Lagrangian---NOT of just f itself---projected down into the tangent space of the constraint surface.) Interestingly, we can be sure the second point is
not a constrained minimum of f, because the Lagrange multiplier u = u_2 would have the wrong sign for a min problem!
The points (P2) and (P3) can be analyzed similarly; they lead to two other "mirror images" of the above maximizing point. That makes sense, because for any (x,y,z) there are three other points with the same values of |x|, |y| and |z|, but where two of them have the opposite sign, so that the values of f and g are unchanged.
The second problem you listed above is harder because it has more inequality constraints. I will leave the fun of solving it up to you.
