3
$\begingroup$

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 Answers 1

2

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}$

  • 0
    Actually, I just read the errata: http://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.2012-08-17