I'm trying to understand an example given by Nocedal & Wright (1999), pg 329, Example 12.4. According to a definition given earlier in this book:

At a feasible point x, the inequality constraint $i\in I$ is said to be active if $c_i(x)=0$ and inactive if the strict inequality $c_i(x)>0$ is satisfied.

So, in Example 12.4 of the same book, a constrained minimization problem is given as:

$argmin$ $(x_1-\frac{3}{2})^2 + (x_2-\frac{1}{2})^4$
such that
$c_1 \equiv 1-x_1-x_2\ge0$
$c_2 \equiv 1-x_1+x_2\ge0$
$c_3 \equiv1+x_1-x_2\ge0$
$c_4 \equiv1+x_1+x_2\ge0$

The authors provide a picture which clearly show that the solution is $x^*=(1,0)$ and state that constraints $c_1$ & $c_2$ are active at this point.

I have two questions regarding this problem:

First Question
Since complementarity implies that the lagrange multipliers associated with constraints $c_3$ and $c_4$ are zero (i.e. inactive), can I state the Karush-Kuhn-Tucker Conditions , as follows:

$\nabla f(x^*)=\lambda_1\nabla c_1(x^*) + \lambda_2\nabla c_2(x^*)$
$\Rightarrow \left( \begin{array}{c} -1\\ -\frac{1}{2}\\ \end{array} \right) = \left( \begin{array}{c} -\lambda_1-\lambda_2\\ -\lambda_1+\lambda_2\\ \end{array} \right) $

Second Question

If the optimal solution were not provided, would I consider all constraints as active?

My concern is how to state the KKT conditions, in general. That is, do I need to discern the set of active constraints ahead of time to setup the KKT conditions? If so, how would I without knowing the optimal solution apriori? Obviously, because of complementarity I know that the lagrange multipliers of inactive constraints will inevitably become zero, but is there a way to know which will be inactive ahead of time? If the inactive constraints were known, would it simplify the process of obtaining the active lagrange multipliers in general?


1) Yes, since $c_3$ and $c_4$ are inactive at this particular $x^*$ the KKT conditions will require $\lambda_3 = \lambda_4 = 0$.

2) If you don't know $x^*$, you have to consider all possibilities for which constraints are active. You would write the KKT conditions as $$ \eqalign{\nabla f(x^*) &= \lambda_1 \nabla c_1(x^*) + \lambda_2 \nabla c_2(x^*) + \lambda_3 \nabla c_3(x^*) + \lambda_4 \nabla c_4(x^*) \cr c_i(x^*) &\ge 0,\ i=1\ldots 4\cr \lambda_i &\ge 0,\ i=1\ldots 4\cr \lambda_i c_i(x^*) &= 0,\ i=1\ldots 4\cr}$$

  • $\begingroup$ You're right... I copied it from the text, so I guess there's a slight mistake there. $\endgroup$ – Paul Aug 17 '12 at 18:30
  • $\begingroup$ Actually, I just read the errata: users.eecs.northwestern.edu/~nocedal/book/2ndprint.pdf It says that $\frac{1}{8}$ should be replaced by $\frac{1}{2}$ in the objective function. I'll make the edit. $\endgroup$ – Paul Aug 17 '12 at 18:36

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.