2
$\begingroup$

This question may be too basic, but I was wondering if it is possible to implement simple methods such as gradient descent or its variations to find the minimum of barrier functions in constrained optimization problems.

If possible, what would be the problems with this approach and is it recommended?

For example:

$$\text{minimize}\;f(x_1,x_2,...,x_n)$$

$$\text{subject to:}\; h(x_1,x_2,...,x_n) \geq C $$

Applying the log barrier function, the objective function becomes:

$$P(x_1,x_2,...,x_n)=f(x_1,x_2,...,x_n)-\log(-h(x_1,x_2,...,x_n))$$

$\endgroup$
  • $\begingroup$ Welcome to Computational Science SE! It would be helpful if you provide a slightly more mathematical statement of your question. $\endgroup$ – Anton Menshov Nov 17 '19 at 18:00
  • $\begingroup$ Hello, I added an example, if it is still unclear, I can try to improve a little or maybe make a picture of the objective function. $\endgroup$ – Marcus Nov 17 '19 at 19:20
2
$\begingroup$

Non-mathematical view:

The underlying problem with gradient descent in this context is, that your gradient often has a discontinuity at your barrier. Let's pick up your example with this case:

minimize:$$f(x)=x$$ subject to :$$ h(x) = x, h(x) >= 0$$

In this case, your gradient descent will walk towards zero from the positive range $x>0$ and will likely overstep the minimum at $x=0$. To prevent this from happening, you might introduce additional terms wherever $x<0$, but you still have a discontinuity at $x=0$. Then you can do a line search, which basically means that when your gradient descent algorithm tries to make a step downslope and finds that its error (residuum) has not improved (i.e. the penalty kicking in for $x<0$), it will decrease its stepsize and try again. That way it can inch towards your minimum with smaller and smaller stepsizes until some criterion is met. It's like running with your head into the wall, but halving your speed at every step you make:-) You will reach the wall...slowly.

The solution you proposed is a viable option to overcome the problem of the discontinuity, but be aware that the term, as you introduced it shifts the minimum slightly.

Plot of $x - \log(x)$ from 0 to 5:

Plot of x - log(x) from 0 to 5

You can control, how far your new minimum is off by a parameter in front of the log-term, but you will never reach the true minimum. (And in many cases thats perfectly fine!)

$\endgroup$

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.