5
$\begingroup$

I have a following type of problem:

$Maximize\,\, F(s,x,y,z)$
$s,x,y,z$

s.t. (i) $g(x,y,z) \le I$
(ii) $x \ge 0$
(iii) $y \ge 0$
(iv) $s > 0$

That is there is no non negativity constraint on variable $z$. I have read about the Kuhn-Tucker method in the books but in all those cases the problem is fourmulated such that the non-negativity constraints apply to all the choice variables. How would my K-T optimality conditions change if I have no non-negativity constraint on $z$?

My sense is that other than the regular K-T conditions for $x$ and $y$ and Lagrange multiplier, $\lambda$, we would have (a) $\frac{\partial \Large{L}}{\partial z} = 0$ (i.e. no inequality here) and NO such condition as (b) $z\,.\frac{\partial \Large{L}}{\partial z} = 0$ (which is obviously true given (a)). My entire confusion is because I have not seen such a formulation in books where K-T conditions are discussed and just want to be sure about my steps.

What would the conditions be in case of $s$, where the inequality is strict?

Here I would think that with strict inequality the problem is not well defined. The constraint set is not compact (not closed).

Thanks a lot in advance.

$\endgroup$
4
$\begingroup$

Non-negativity constraints have nothing special and are not critical for the general validity of the Karush-Kuhn-Tucker approach. First, realize that we could have $x \geq a >0$ and then we could write $x-a \geq 0$ and view this "non-negativity" constraint as just one more inequality constraint on the solution.

When a decision variable is weakly bounded, the new phenomenon that emerges is that we may have the partial derivative non-zero (strictly negative, for the maximization case), if at the solution this decision variable lies on the boundary.

If it is unbounded, than we must have the first-order derivative equal to zero. As another question pointed out, this may create issues in certain contexts, but it does not invalidate the approach.

As for your second question, indeed strict inequalities may create problems, but don't jump immediately to a "not well-defined" heavy statement. The problem will arise only if (stars denote the optimal solution)

$$\frac {\partial F(s^*,x^*,y^*,z^*)}{\partial s^*} <0$$

which would "push" the solution vector towards the unreachable zero-lower boundary for $s$. To avoid that, we require that at the solution the first-order derivative w.r.t to $s$ equals zero, and see whether we can indeed obtain a solution vector. If we can, it means that the $s>0$ constraint does not even "tend to" be binding, so you can ignore it.

$\endgroup$
3
$\begingroup$

My gut feeling is that:

(1) Existence of extremum may not be guaranteed. If one of the choice variables can be negative, say in consumer theory one of the goods, I suspect the budget set no longer would be compact. For example in the case of $L=2$, suppose you allow quantity for good 2 to be negative. What would this mean. Maybe it is garbage or pollution, so at the extreme, you wouldn't want it in any possible way. So a possible budget set would look like a quasiconcave function (e.g. bell curve with cusp) on vertical axis where there is no guarantee of closedness or boundedness.
(2) Constraint qualification will be violated so solving KT method bears no meaning. When checking the constraint qualification, we use the fact that price vectors are strictly positive to investigate the matrix has full rank of not at the point of interest. Say, this time you allow it to be negative or zero, constraint qualification would be violated, and maybe solving the usual KT would give you something ,but it wouldn't probably something you desired.

Just my 2 cent.

$\endgroup$
1
$\begingroup$

Generally speaking, even having nonnegativity constraints on all your variables will not guarantee that your constraint space is compact. To make any statements about your constraint space, you need to take into account constraint (i). Usually, $g$ will be such that $\lim_{\|x, y, z\| \to \infty} g(x,y,z) = \infty$, and you can have a guarantee that your constraint space is compact as long as all of the variables are constrained to be nonnegative. Without a constraint on $z$, you would have to look at the form of $g$ to be able to guarantee your constraint space is compact. For instance, if $g(x,y,z)= z^2 + h(x,y)$, the lack of a constraint $z \ge 0$ does not pose an issue for solving the problem (the constraint space is still compact.)

However, the strict inequality constraint on $s$ (iv) makes it likely that your constraint space is not compact, since it is not closed. From my (relatively limited) experience with constraint programming, you would just solve your problem as usual, ignoring constraint (iv), and throw out any solutions for which $s \le 0$. (Other users can correct me if this is not correct.) Depending on the specific form of your problem, you may obtain a solution that satisfies $s > 0$, or you may find the only maximum has $s \le 0$, in which case a maximum does not exist for your problem.

To summarize, yes, just solve the K-T conditions for the inequality constraints (i-iii). Your problem is not guaranteed to have a solution (because of the lack of an inequality constraint on $z$, and the strict inequality on $s$), but if a solution exists, K-T will give it to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.