sci.op-research

I see you're a believer in cross-posting. sci.physics??

LunaMoon wrote:
> 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.

No, you only know that l4 >= 0. l4 = 0 and g(x) = 0 can happen
simultaneously.
>
> Now I have one lambda remaining, which is l1.
>
> I divide into two cases:
>
> case 1: If l1=0, then x1>a, I solve for x1, x2, x3. And these involve
> the additional parameters such as p and q.

Almost. If l1 = 0, then x1 >= 0. It's possible that they are both zero.
>
> 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;

It matters in that the lower bound x1 >= a is still enforced. See the
next answer.
>
> (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 discard the solution and conclude that case 1 does not happen for
those parameter values.
>
> (3) After discussing the two cases, how do I combine them together?

Several possibilities occur. First, you need to verify that what you
ended up with are constrained maxima. Remember you're only working with
first order conditions here. (If certain conditions are met, including
f being concave, then this is a given.)

Now you conclude that for certain parameter ranges, the maximum occurs
at x = ... based on case 1, and for other parameter ranges the maximum
occurs at x = ... based on case 2. If both cases yield solutions for a
particular range of parameter values (or if one case yields multiple
solutions), then either you have multiple optima or the KKT conditions
are coughing up local optima that are not global (which can happen if,
for instance, f is not unimodal).
>
> I think I should pick one of these two that gives the largest
> objective function value.

Assuming that both cases yield solutions (not necessarily true) and
their objective values are unequal (implying at least one is a local max
but not global), that would be correct. If there are multiple optima,
they will by definition have equal objective values.
>
> 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?

The first part of this is oversimplified; see above. Yes, the two cases
are exhaustive.
>
> (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?

Or both. Or all of the above. Again, you may have multiple optima.

> In general, shall I just
> compare the objective function values for all these "candidate"
> interior points and the boundary points?

That works, assuming that you only have a finite number of them.

> I understand that since the
> first order conditions are really necessary conditions, so there could
> be multiple candidate interior points and multiple candidate boundary
> points. And then comparing these objective functions to choose the
> largest one is very tedious, any better approaches?

Assuming some smoothness, second derivative information may let you rule
some of them out.

/Paul