sci.op-research

On Feb 12, 12:38 am, 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.

This is false. There are very many books that give good examples. It
is a fact, however, that most "non-trivial" problems tend to need a
good computer code to obtain a solution.

> 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.

What do you mean by "always" here? Do you mean that g(x) = 0 for ALL
x? The only function like that is the identically-zero function, and
in that case the constraint is meaningless.

>
> I define the Laplacian to be:

That should be the Lagrangian, not Laplacian.

>
> 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; in some problems, it could be zero
also, even though the constraint is binding.

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

No. We could have L1 = 0 and x1 = a. The correct way to do it is: (1)
if x > a then L1 = 0; and (2) if L1 > 0 then x1 = a (as you said).

> I solve for x1, x2, x3.

What do you solve? What are the equations? You also need @V/@x1 <= 0,
@V/@x2 = 0 and @V/@x3 = 0; in the case x1 > a the first condition
becomes @V/@x1 = 0.

> 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.

It does matter. You need x1 >= a (> a in Case 1), so if your solution
does not satisfy that, you know you have the "wrong case".

> For
> any value of "a", I get the same expressions for x1, x2, x3. "a"
> probably even doesn't appear in the expressions;
>
> (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?

It is OK to have x1 = a, but not x1 < a. If you get x1 < a for some
parameters, they you know that you have the "wrong case".

>
> (3) After discussing the two cases, how do I combine them together?

Why do you want to combine them? The solution is either in Case (1) or
in Case (2) (although, in problems with multiple local extrema, you
could have one or more solutions that satisfy Case (1) and one or more
that satisfy Case (2)).

>
> I think I should pick one of these two that gives the largest
> objective function value.

Exactly. And that is why global optimization is difficult. In some
problems there can be millions of local maxima, all satisfying the KT
conditions, and the only way to tell the actual max is to compute the
objective for all of them.

>
> Do I plug in these two solutions into the objective function and then
> compare?

Of course, why wouldn't you? You /know/ the answer already, you just
seem to lack confidence in your own understanding.

>
> 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?

That all depends on why you know that x2 and x3 are never binding. If
you did not know that, there would be additional cases.


>
> (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.

Yes, if you usage of terms allow a boundary point that is not a corner
point. Also, if some of the constraint functions are nonlinear, there
may be no "extreme" points in the technical sense, since the
constraint region may be non-convex.

> Am I correct? In general, shall I just
> compare the objective function values for all these "candidate"
> interior points and the boundary points? 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.

That is correct. However, there are also second-order necessary
conditions and related (but slightly different) second-order
sufficient conditions. These can sometimes be successful in
eliminating some of the candidate points. Some sophisticated solution
algorithms use second-order conditions as part of their workings, so
they would not give you false candidates (such as a minimum when your
problem is a max, or a saddle-point instead of an optimum). However,
in difficult global optimization problems you would still need other
methods to find the one, best candidate.


> And then comparing these objective functions to choose the
> largest one is very tedious, any better approaches?

Google "global optimization" to learn about some of the approaches.
However, in the worst case you might need to perform tedious
enumeration. Here is a little example:
min sum[cj*xj;j=1..n] + M*sum[xj*(1-xj):j=1..n], subject to
sum[a(i,j)*xj:j=1..n] <= bi for i = 1,..., m and 0 <= xj <= 1 for all
j. This has a simple quadratic objective and linear constraints.
However, for M > 0 the objective is concave, which means that the
solution occurs at an extreme point of the feasible region. For large
M > 0 it is equivalent to the 0-1 programming problem min
sum[cj*xj;j=1..n], subject to sum[a(i,j)*xj:j=1..n] <= bi for all i
and xj = 0 or 1 for all j. This problem is NP-hard, with no know good
algorithm to solve it. As far as we know, in the worst case we could
need to enumerate all the 2^n vertices of the unit parallelogram
[0,1]^n. Google NP-complete and NP-hard to get a better understanding
of what this all means.

R.G. Vickson

su