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.

We know that $f(x) \to \min$ subject to $g(x) = t$ and $h(x) \leq m$ can be written as $f(x) + \lambda g(x)\to\min$ subject to $h(x) \leq m$.

How do we get value of lambda so that the two problems are equivalent.

share|improve this question
    
first of all, if $t\neq 0$ you have to solve $f(x)+\lambda (t-g(x))\to \min$. Second, the value of the multiplier $\lambda$ you find solving the new optimization problem, you don't know it in advance. –  Ilya Sep 28 '11 at 14:53
    
@Gortaur When you do not have inequality constraint, I understand what you wrote is correct. With the presence of the inequality constraint, we will have to use KKT and I do not know if they will yield the same solution. How can I prove that there exists such a lambda. Also, if all functions are convex, does is mean that inequality can be converted to equality in both problem formulations? Thanks a ton. –  Pratik Poddar Sep 29 '11 at 3:37
    
@PratikPoddar: Don't you mean that you minimize $f(x) + \lambda \|g(x)\|$ or $f(x) + \lambda \|g(x)\|^2$ as in penalty methods. You'll find how to determine the optimal value of $\lambda$ for regular problems in any good optimization book. –  Dominique Oct 28 '11 at 20:53

1 Answer 1

You may formulate the inequality constraint using a log-barrier, as it does not allow $m-h(x)$ to be less than or equal to zero. This is the formulation of the minimization problem :$f(x)+\lambda_{1}(g(x)-t)-\lambda_{2}log(m-h(x))$

Now to find the lambda's first solve a closed form for x by setting the gradient w.r.t x as zero. You will have a closed form for x, containing the lambda's.

Now consider this to be $x^{*}=c(x)$. Now substitute the closed form for $x^{*}$ in the constraint as, $g(x^{*})-t=0$ and solve for $\lambda_{1}$ . Similarly solve for $\lambda_{2}$ by substituting $x^{*}$ in the second constraint.

For your further-reading, reference: you may look up log-barrier methods for inequality constraints.

In a statistical modeling scenario, the $\lambda's$ are estimated by cross-validation. But I am not sure about the domain of your work.

share|improve this answer

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.