Primal Interior-Point Methods

Question

It is common that when one solves the nonlinear inequality constrained problem

$$ \min_{x\in\mathbb{R}^{n}}f(x) \\ \text{ such that } c_{i}(x)\geq 0,\,\,\,i=1,2,\dots,m $$

that one introduces slack variables $s_{1},s_{2},\dots,s_{m}$

$$ \min_{x\in\mathbb{R}^{n},s\in\mathbb{R}^{m}}f(x)\\ \text{ such that } c_{i}(x) - s_{i} = 0,\,\,\,i=1,2,\dots,m\\ \text{ and } s_{i}\geq 0 $$

and then solves a sequence of equality-constrained log-barrier subproblems with log-barrier parameter $\mu>0$

$$ \min_{x\in\mathbb{R}^{n},s\in\mathbb{R}^{m}}\varphi(x,s,\mu):=f(x)-\mu\sum_{i=1}^{m}\log(s_{i})\\ \text{ such that } c_{i}(x)-s_{i}=0,\,\,\,i=1,2,\dots,m $$

I have interest in not introducing this slack variable and working directly with unconstrained log-barrier subproblems of the form

$$ \min_{x\in\mathbb{R}^{n}}\mathcal{E}(x,\mu):=f(x)-\mu\sum_{i=1}^{m}\log(c_{i}(x)) $$

This seems to be unconventional, do you know any references that discuss how to numerically solve such problems? Do you have any insight into why it is so unconventional to not introduce the slack variable $s$?

Answer 1

If you go back to the original article by Fiacco & McCormick, see e.g. jstor, they do not introduce slack variables either. (Note: they work with $1/c_i(x)$ barrier instead of the logarithmic one, but this is on no consequences for your question.). So I would say "so unconventional" this approach is not. A bigger issue is that there is community wisdom and computational evidence that primal-dual IP methods are superior to primal ones, and the notation with the nonnegative slack variables and the corresponding nonnegative Lagrange multipliers is quite standard, convenient, and aesthetically pleasing owing to its symmetry.

Answer 2

You could apply a primal-dual approach or a primal approach to your problem. Both are valid. The primal approach to your problem is called the logarithmic barrier method. The primal-dual approach is usually called the interior point method. Your concern may be this confusion with the nomenclature. Why people do not prefer to use the primal approach? The penalty methods, like the logarithmic barrier method, typically solve convex problems in a linear rate of convergence, but the primal-dual approach converges almost quadratically for the same class of problems. The computational effort in primal-dual methods is also smaller in most cases. On the other hand, logarithmic barrier methods seems more stable in terms of global convergence, but it also depends on how the primal-dual approach implemented. There are primal-dual interior point methods that converges globally. To my knowledge, there are no comparisons between globally convergent primal and primal-dual methods, but I expect that primal-dual methods will perform better for problems that satisfy a strong constraint qualification, like MFCQ.