0

How to use the barrier method for equality (or positive) constraints?

https://optimization.mccormick.northwestern.edu/index.php/Interior-point_method_for_LP#Barrier_Method

My initial reasoning was that since the example there starts with constraints $f_i(x) \leq 0$ and then takes

$$\phi(x)=-\sum_{i=1}^m \log(-f_i(x))$$

Then if one'd start with $f_i(x)=0$, then reasonably one doesn't need to flip the sign so could one then simply do

$$\phi(x)=-\sum_{i=1}^m \log(f_i(x))$$

for constraints of the form $f_i(x)=0$ or $f_i(x) \geq 0$.

However, without being entirely familiar with the barrier method, is this enough?

mavavilj
  • 7,270

1 Answers1

1

A constraint $f(x) \geq 0$ is equivalent to $-f(x) \leq 0$. Of course $f$ should be concave if you expect globally optimal solutions.

An equality constraint does not fit in the barrier method, since the feasible set for such a constraint has a nonempty interior.

The page you link to also has a description of the primal-dual method. That method can cope with equality constraints (in fact, all inequality constraints are first reformulated as equality constraints).

LinAlg
  • 19,822
  • Would I need to convert the equality into inequality then? And how should I do that? – mavavilj Jan 30 '19 at 21:54
  • @mavavilj no, if you transform it into two inequalities, the feasible set is still not full dimensional – LinAlg Jan 30 '19 at 21:54
  • Good, but this doesn't answer my question. Since I'm not switching $-f(x)$ to $f(x)$, but $g(-f(x))$ to $g(f(x))$. – mavavilj Feb 25 '19 at 16:56
  • @mavavilj the barrier term is $-\sum_i \log(f_i(x))$ for constraints of the type $f_i(x)\geq 0$ (this is obvious from the first line in my answer). However, you need to use a different method for equality constraints, because the logarithmic function forces a strict inequality which you cannot have for an equality constraint. – LinAlg Feb 25 '19 at 17:12