For the following problem:

$\text{min:}\ f(x)\\ s.t. \ g(x)\leq t$

Is the above problem equivalent to the following problem?

$\text{min:}\ f(x) + \lambda g(x) \\ s.t. \ \lambda\geq0$

where $t$ and $\lambda$ are variables. It seems equivalent, because if we increase $\lambda$, $t$ will tend to decrease, if we decrease $\lambda$, then $t$ will tend to increase.


This question is not clear, as you don't define what you're minimizing over, among other things. If you are minimizing with respect to $(x, \lambda)$, the answer is "no", because the minimum (for $g(x) \geq 0$) will occur at $\lambda = 0$ and $x = \arg \min f(x)$, i.e., at the solution to the unconstrained problem $\min_x f(x)$.

However, it is true that, under a broad range of conditions, there exists a $\lambda$ such that the solution to $\min_x:f(x) + \lambda g(x)$ equals the solution to the constrained problem as initially stated. It is not sufficient to constrain $\lambda \geq 0$ to find that solution; instead, you must solve the root-finding problem:

$$\min_\lambda \text{s.t.} \, g(x(\lambda)) - t \leq 0$$

where $x(\lambda) = \arg \min_x f(x) + \lambda g(x)$. ($\text{s.t.}$ means "such that" or "subject to".) The reason for choosing the minimum $\lambda$ from the set of $\lambda$s that cause the constraint to be satisfied is that, writing heuristicaly, as you increase $\lambda$ past the minimum, in "most" problems you'll also move $g(x(\lambda))$ farther and farther below $t$ while increasing $f(x(\lambda))$, i.e., you won't be minimizing $f(x)$ subject to the constraint, but subject to some other constraint $g(x) \leq t'$ with $t' < t$.


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.