I have got an optimization problem with a function to minimize and an equailty constraint. $$ min ~~f(x) \\ s.t. ~~~~~ h(x) = 1 $$ Now I am adding a penalty function $g(x)$ (which should be minimized, too) to $f(x)$ leading to $$ min ~~f(x) + µ g(x) \\ s.t. ~~~~~ h(x) = 1 $$which makes the problem non convex and solvebale for $x$. Becaus I do not care wheather $h(x)$ is excatly 1, I would like to ask, if there is a method to relax this constraint, eg. $0.2< h(x) < 1.8$, to make it easier to solve? Maybe a numeric one or a way to linearize it?

  • $\begingroup$ why don't you replace the constraint by another penalty $R(h(x)-1)$ where $R(z)$ is some non-negative function with $R(z)=0$ only at $z=0$ (so for example an l2 norm but you could have more or less aggressive penalty depending on your problem, maybe a barrier function) $\endgroup$
    – tibL
    Sep 23 '16 at 7:42
  • $\begingroup$ If I add $\vert R(h(x)-1) \vert^2$ (l2-norm) as a penalty function to the problem, it is not possible to find the minimum, because the expression is too complex. Finding the solution to $f(x)+µg(x)$ is not a problem. Therefore I am looking for a way to handle the constraint somehow different $\endgroup$
    – N8_Coder
    Sep 23 '16 at 9:49
  • $\begingroup$ you mean analytically? because numerically it shouldn't really make your problem much harder $\endgroup$
    – tibL
    Sep 23 '16 at 13:01
  • 1
    $\begingroup$ Unless $h$ is affine, most algorithms won't deal with the bounds directly since computing the distance to the bound is really only easy with affine functions. Likely, you'll end up adding a slack variable, $h(x)=y$ and then bounding the variable $y$, $0.2\leq y\leq 1.8$. Alternatively, at this point, you could just penalize $y$ as well like @tibL suggested by adding a term like $\rho (y-1)^2$ for some value of $\rho$ that you choose. $\endgroup$
    – wyer33
    Sep 24 '16 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.