sci.op-research

LunaMoon writes:

> Hi all,
>
> I just had a few questions in using KKT conditions to solve
> constrained optimization problems. There are not many books give
> examples about using the conditions to solve non-trivial problems.
> Here are my questions:
>
> max f(x)
>
> such that x1>=a, x2>=b, x3>=c,
> and g(x)>=0
>
> And f(x) and g(x) involve other parameters p and q.
>
> Let's say I already know that x2>=b never becomes binding, and x3>=c
> never becomes binding, and g(x) >=0 is always binding.
>
> I define the Laplacian to be:
>
> V(x, a, b, c)= f(x) - l1*(-x1+a)-l2*(-x2+b)-l3*(-x3+c)-l4*(-g(x))
>
> where we know that l2=0, l3=0, and l4>0, and g(x)=0.

Actually we don't know l4>0.

> Now I have one lambda remaining, which is l1.
>
> I divide into two cases:
>
> case 1: If l1=0, then x1>a,

No... it's possible to have l1=0 and x1=a. KKT says x1>a => l1=0,
not that l1=0 => x1>a.

>I solve for x1, x2, x3. And these involve
> the additional parameters such as p and q.
>
> case 2: If l1>0, then x1=a, I solve for x2 and x3.
>
> My questions are:
>
> (1) In case 1: here it seems that the value of "a" doesn't matter. For
> any value of "a", I get the same expressions for x1, x2, x3. "a"
> probably even doesn't appear in the expressions;

True, the expressions don't depend on "a", but...

> (2) In case 1: What if the solved expression of x1, which depends on
> the parameters, gives x1<=a, for certain range of the parameters?

You just answered question (1). If x1 = a, it's still OK, you have a
solution to the KKT conditions. But if x1 < a, it's not a solution
because it violates the constraint x1 >= a.

> (3) After discussing the two cases, how do I combine them together?
>
> I think I should pick one of these two that gives the largest
> objective function value.
>
> Do I plug in these two solutions into the objective function and then
> compare?

Yes.

> Or, in this case, since we already know that x2, and x3 should be not
> on the boundary, we just need to check the solution in case 1:
> depending on the parameters, if the solution in case 1 is indeed with
> x1>a, then that's the optimal solution; if the solution in case 1 is
> indeed with x1<=a, then we should switch to the second case with x1=a.
> Are these two cases complete?

No. In general, you could have local maxima in both cases 1 and 2, and
there's no way to tell which is better without comparing the objective
values. The only exception would be for a convex problem.

> (4) It seems that for all constrained optimization problems, either
> the optimal solution is in the interior, or it is one of the corner/
> extreme/boundary points. Am I correct?

If there is an optimal solution, it's either in the interior or a
boundary point. That's just because any member of a set that isn't
in the set's interior is a boundary point of the set. But it could be
a boundary point that is not an extreme point. The optimal solution
could be any point of the feasible set.
--
Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada