3
$\begingroup$

I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$.

Then to use it in my problem analysis, I am trying to build the KKT conditions. After multiplying each of them by lagrange multipliers ($\lambda,\mu$), I get $\lambda x \ge 0$ and $\mu x \le 1 $. After differentiating and equating to zero I get these:

\begin{equation} \frac{d}{d\lambda} = x = 0 \end{equation}

and \begin{equation} \frac{d}{d\mu} = x -1 = 0 \end{equation}

The equations can't be solved as a system of linear equations. How these can be solved?

$\endgroup$
0
1
$\begingroup$

Minimize $x^2$ where $1 \le x \le 2$.

\begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & h_{1}(x) \le 0\\ &h_{2}(x) \le 0 \\ \end{aligned} where \begin{align} f(x) &= x^2 \\ h_{1}(x) &= 1 - x \\ h_{2}(x) &= x - 2 \end{align}

KKT conditions: \begin{align} 0 &= \nabla f(x) + \mu_{1}\nabla h_{1}(x) + \mu_{2} \nabla h_{2}(x) \\ &= 2x - \mu_{1} + \mu_{2} \\ 0 &= \mu_{1} h_{1}(x) = \mu_{1}(1-x) \\ 0 &= \mu_{2} h_{2}(x) = \mu_{2}(x-2) \\ \mu_{1} &\ge 0 \\ \mu_{2} &\ge 0 \end{align}

if $\mu_{1} = 0$, the $h_{1}(x)$ constraint is inactive. Otherwise, the constraint is active. Active means the solution is at the boundary of the constraint.

I think the KKT conditions mean there are three cases:

  • The $h_{1}$ constraint is active and the $h_2$ constraint is inactive. That means the minima is at the boundary of the feasible region and $x = 1$.
  • The $h_{1}$ constraint is inactive and the $h_2$ constraint is active. That means the minima is at the boundary of the feasible region and $x = 2$.
  • Both constraints are inactive. That means the minima is in the interior of the feasible region and $0 = \nabla f(x)$.
$\endgroup$
2
  • $\begingroup$ I googled the kkt conditions. This is nearly my 1st impression. $\endgroup$ Jun 26 at 6:51
  • $\begingroup$ Erh. The solution is either in the interior of the feasible region or at the boundary of the feasible region. It can't be outside of the feasible region. Besides that, what is so special about the KKT conditions? $\endgroup$ Jun 26 at 7:03

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.