7
$\begingroup$

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!

$\endgroup$
8
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tim Nov 24 '11 at 14:41
  • $\begingroup$ Strict inequalities aren't covered by the KKT conditions, so you might say that they won't have Lagrange multipliers associated to them. If there rightfully are strict inequalities, I'd suggest treating them with an interior-point method. $\endgroup$ – Dominique Aug 13 '15 at 16:02
  • $\begingroup$ So in other words, we just solve the optimization problem without the strict inequality constraints, then explicitly check if the solutions satisfy those constraints to accept/reject, I assume? For implicit constraints, optimizing cost function will never break them (b/c we actually just traverse on the domain of the function), so we could just ignore them, I assume? $\endgroup$ – THN Feb 13 '18 at 5:55
  • $\begingroup$ If all other problem functions are well defined outside of the strict inequality constraints, you could ignore them and check them after the fact. Otherwise, you need a dedicated method that enforces those strict inequalities (and an initial point that satisfies them). $\endgroup$ – Dominique Feb 13 '18 at 10:22

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.