Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

KKT conditions from Wikipedia:

We consider the following nonlinear optimization problem: $$ \text{Minimize }\; f(x) $$ $$ \text{subject to: }\ g_i(x) \le 0 , h_j(x) = 0 $$ The number of inequality and equality constraints are denoted $m$ and $l$, respectively.

Suppose that the objective function $f : \mathbb{R}^n \rightarrow \mathbb{R} $ and the constraint functions $g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R}$ and $h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R}$ are continuously differentiable at a point $x^*$ . If $x^*$ is a local minimum that satisfies some regularity conditions, then there exist constants $\mu_i\ (i = 1,\ldots,m)$ and $\lambda_j\ (j = 1,\ldots,l)$, called KKT multipliers, such that

Stationarity $$ \nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda_j \nabla h_j(x^*) = 0, $$ Primal feasibility $$ g_i(x^*) \le 0, \mbox{ for all } i = 1, \ldots, m $$$$ h_j(x^*) = 0, \mbox{ for all } j = 1, \ldots, l $$ Dual feasibility $$
\mu_i \ge 0, \mbox{ for all } i = 1, \ldots, m $$ Complementary slackness $$ \mu_i g_i (x^*) = 0, \mbox{for all}\; i = 1,\ldots,m. $$

I was wondering:

  1. how will the KKT conditions change, if the inequality constraints $g_i(x) \le 0$ are replaced with strict inequalities i.e. $g_i(x) < 0$?
  2. if the cost function $f$ already put some implicit condition on $x$ so that it can be well-defined, will the implicit condition be considered as an explicit constraint when writing the KKT conditions? For example, $f(x)=x- \ln(x)$ requires $x>0$. Will $x>0$ be considered as a constraint when writing the KKT conditions?

Thanks and regards!

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted
  1. It does not really make sense to optimize smooth functions over open sets because then, you must replace $\min$ by $\inf$ and the optimal value is not necessarily attained. There are no KKT conditions for open sets. If you feel like strict inequalities are what you need, it is sometimes an indication that something went wrong when the problem was modeled.
  2. The short answer is no. Implicitly, since the term $(-\ln(x)) \uparrow +\infty$ when $x \downarrow 0$, a solution of your problem will not have any zero component. The $\ln(x)$ term ensures in a sense that a solution will lie interior to $x \geq 0$. This strategy is the basis of interior-point methods where inequality constraints are pushed into the objective in the form of a logarithmic term. For example, if you are minimizing $f(x)$ subject to $x \geq 0$, you can solve a sequence of unconstrained problems with the new objective $f(x) - \mu \sum_i \ln(x_i)$, where $\mu > 0$ is a parameter. For a given value of $\mu > 0$, you will identify a (approximate) solution $x_{\mu}$. Now let $\mu \to 0$. If your approximate solutions are accurate enough and if $\mu$ does not decrease too fast, you will observe that $x_{\mu} \to x_*$, a solution of the original, constrained, problem. This $x_*$ may lie on the boundary of $x \geq 0$, but you approached it by staying interior. The KKT conditions of the subproblem are simply that $\nabla f(x) - \mu x^{-1} = 0$, where $x^{-1}$ is the vector with components $1/x_i$. The constraint $x > 0$ must be enforced implicitly here, e.g., by rejecting any candidate solution to the KKT conditions that has a component $x_j \leq 0$. But it doesn't have a Lagrange multiplier.

I hope this helps a bit.

share|improve this answer
    
Thanks, Dominique! Although you said "if you feel like strict inequalities are what you need, it is sometimes an indication that something went wrong when the problem was modeled", if there is indeed some strict inequality constraint, will it be treated as you said in 2 that it will not have a Lagrange multiplier, and must be enforced implicitly on any candidate solution to the KKT conditions derived without the strict inequality? –  Tim Nov 24 '11 at 14:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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