1
$\begingroup$

I am working on implementing the interior point method, and the barrier function always gives me a complex number. B(x) = f(x) - t * sum(ln(hi(x))). I have changed the value of 't' to see the B(x) behavior, but it's not responding. My hi(x) has small values of {10^-14}. Is there any way to deal with the issue?

$\endgroup$
2
  • $\begingroup$ You may need to truncate those small numbers to zero. Can you give more information on your specific algorithm? Which paper/book are you following? $\endgroup$
    – Brannon
    Mar 3, 2023 at 16:23
  • $\begingroup$ I am following the book numerical optimization by Jorge Nocedal. I have added a small number inside the ln(hi(x)+eps)) where eps 10^-3 and it's working. $\endgroup$
    – Muhammad
    Mar 3, 2023 at 17:02

2 Answers 2

2
$\begingroup$

The issue of obtaining complex values when evaluating the barrier function in an interior point method can be caused by taking the natural logarithm of a negative number. This can happen when the values of the inequality constraints $h_i(x)$ are very small, as you have observed. In this case, the logarithm of $h_i(x)$ may be negative, resulting in a complex value when multiplied by $t$.

One way to address this issue is to add a small positive constant to the values of $h_i(x)$ before taking the natural logarithm. This is known as a "logarithmic barrier with a small constant" and is a common technique used in interior point methods to avoid taking the logarithm of a negative number.

For example, you can modify the barrier function as follows:

$$B(x) = f(x) - t \sum_{i=1}^m \ln(h_i(x) + \epsilon)$$

where $\epsilon$ is a small positive constant, such as $10^{-8}$. By adding this constant, you ensure that the logarithm is always taken of a positive number, avoiding the issue of obtaining complex values.

However, keep in mind that adding a small constant can also affect the convergence properties of the interior point method. It can make the barrier function less steep, which can slow down the convergence of the method. Therefore, it is important to choose a value of $\epsilon$ that is small enough to avoid the issue of complex values, but not so large that it significantly affects the convergence of the method.

Another approach is to use a truncated logarithmic barrier, which involves setting a lower bound on the value of $h_i(x)$ before taking the logarithm. This can also avoid the issue of obtaining complex values, but may require more careful tuning of the parameter values.

Overall, adding a small positive constant to the values of $h_i(x)$ before taking the logarithm is a common technique used to avoid the issue of complex values in the barrier function. However, it is important to choose an appropriate value of the constant to balance convergence and numerical stability.

$\endgroup$
0
$\begingroup$

It sounds like you're running into numerical issues due to very small or very large values. A few things to try:

Use logged variables instead of raw values in the barrier term. So instead of ln(hi(x)), use ln(max(hi(x), ε)), where ε is a small positive constant (like 10^-14). This avoids taking the log of a very small number.

Scale your problem to avoid very large/small raw values. If hi(x) is on the order of 10^-14, scale x and hi(x) by a large constant to bring the values into a more reasonable range. Use higher precision floating point, like quad precision if available. This can help with stability for problems with a wide range of scales.

Check for other potential numerical issues - are there divisions by very small numbers, exponential growth/decay, etc.

In general, interior point methods can be numerically sensitive, so it's important to be careful with scaling, avoiding extremes, and using stable algorithms/precision.

$\endgroup$
2
  • $\begingroup$ Can you explain this point in detail ? Adding a small number inside the log function is not helping as line search is computed using the difference between B(x)_k - B(x)_k-1, which is failing. And if I scale my input variable, 'x,' the output changes. $\endgroup$
    – Muhammad
    Mar 7, 2023 at 13:06
  • $\begingroup$ Try using relative difference instead of absolute; (B(x)_k - B(x)_k-1) / B(x)_k-1. Stable even if B(x)_k-1 is very small. Scale the input x, and scale the outputs B(x) via same amount. the relative difference will be preserved, and it may help the values to more stable range. The line search method that is more robust to small/large function values, like a Wolfe line search. In general, when taking differences or ratios of computed values, it's important to think about relative changes. Line search methods have a number of strategies to handle difficult functions - may be worth exploring. $\endgroup$ Mar 7, 2023 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.