Lagrangian formulation of an optimization problem

41 Views Asked by At

I am a bit puzzled on how the constraints of a given optimization problem pass through the Lagrangian. Given, say, the following problem: \begin{align} (P) \qquad \inf_x \,\,\, f(x) \quad \text{such that} \quad g_1\geq0,\ldots,g_m\geq 0, \end{align} with $x \in \mathbb{R}^n$ and $g_i : x \mapsto g_i(x)$ are polynomials defining a semialgebraic set.

My first confusion is whether the Lagrangian problem (under certain assumptions) can be written as (maybe with plus sign?) \begin{align} (L1) \qquad \inf_x \sup_t \,\,\, f(x) - t\sum_{i=1}^mg_i, \end{align} where $t$ is the Lagrange multiplier, or as (maybe with plus sign?) \begin{align} (L2) \qquad \inf_x \sup_{t_i} \,\,\, f(x) - \sum_{i=1}^mt_ig_i, \quad \forall i, \end{align} where now one has many Lagrange multipliers (one for each constraint).

My relevant second confusion is how exactly taking the sup of $t$ or of all $t_i$s guarantees that the constraints are satisfied. In (P) the requirement is clear. However, in (L1) and (L2) it is not clear to me why the constraints are satisfied. If, for example, a certain $g_j <0$, then taking the sup w.r.t. $t_j$ can yield negative infinity.

Can you provide me some intuition on how exactly the Lagrangian enforces the constraints? Or what I understand wrongfully?