1

We all know that if we have an optimization problem of the general form:

$$ \min f(x) $$

subject to: $$\begin{align} h(x) &= 0 \\ g(x) &\le 0. \end{align}$$

Then, we have a vector of multipliers, let's call it $s$, associated with the equality constraints and a vector of multipliers associated with the inequality constraints, let's call it $d$.

The KKT conditions require (apart from many other things) that the components of d satisfy the non-negativity condition: $d\ge 0$

My question is: does this condition depend on the problem structure? whether I have a min or max problem? And if so how does it depend?

Thank you,

Mari

muaddib
  • 8,267
user254769
  • 27
  • 5

2 Answers2

2

It does depend on the structure of the problem. Lets see what we are trying to achieve here. In your example, we want to minimize a function $f(x)$ subject to the constraints $h(x) = 0$ and $g(x) \le 0$.

When we introduce the multipliers, we form the expression $$ L(x, s, d) = f(x) + s\cdot h(x) + d \cdot g(x). $$ I think of the optimization as a game with an opponent: I control the original variable $x$ and I want to minimize this expression (In fact I want to minimize function $f(x)$ subject to the constraints, but the game guarantees that this is equivalent). The opponent controls the introduced multipliers $s$ and $d$ and is trying to maximize the expression.

The way we design this game is so that every time I violate the constraints, the opponent can win by making his objective infinite! In particular, if I select $x$ for which $g(x) >0$, then the opponent can select $d \rightarrow \infty$ and drive $L(x,s,d)$ to $\infty$. On the contrary, when I choose $x$ that does not violate the constraint, the opponent should not be able to drive $L(x,s,d)$ to $\infty$. That's why we restrict the opponent to only use $d \ge 0$. Note that if we violate $h(x)=0$, then the opponent should be able to win irrespectively of whether $h(x) >0$ or $h(x)<0$ and that's why we put no restriction on multiplier $s$.

If the original constraint was $g(x) \ge 0$, then we could form a different expression: $L(x, s, d) = f(x) + s\cdot h(x) - d \cdot g(x)$, or we could keep it as it was requiring that $d \le 0$. Finally note that if the original problem was to maximize $f(x)$, then you can always think of it as minimizing $-f(x)$.

megas
  • 2,276
1

Yes, you can think of the term $ d_i g_i ( x) $ in the Lagrangian as penalizing violations of the inequality constraint. That will help you remember if you should have $ d \geq 0$ or $d \leq 0$.

littleO
  • 51,938