Solving a max-min convex optimization problem with interior-point methods

I would like to solve the following problem:

\begin{align} \text{ minimize } && t \\ \text{ subject to } && f_i(x) - t \leq 0 \text{ for all i\in 1,\ldots,n,} \\ && 0\leq x_j \leq 1 \text{ for all j\in 1,\ldots,m.} \end{align}

The functions $$f_i$$ are convex, so the entire problem is convex. I would like to solve it using interior point methods. From what I know, the first thing I need to do for this is to find an efficiently-computable self-concordant barrier for the domain:

$$G := \{(x,t): f_i(x) - t \leq 0 \text{ for all } i\in 1,\ldots m, \text{ and } 0\leq x_j \leq 1 \text{ for all } j\in 1,\ldots,m$$ }.

I know that, for linear functions $$f_i$$, I can use the logarithmic barrier. But here the functions $$f_i$$ are convex.

Does there always exist a self-concordant barrier for $$G$$ (for any convex functions $$f_i$$)? If so, how can I find it? If no, what other conditions on $$f_i$$ are needed?

• Start by reading section 9.2.3 of Ben-Tal and Nemirovski "LECTURE NOTES OPTIMIZATION III CONVEX ANALYSIS NONLINEAR PROGRAMMING THEORY NONLINEAR PROGRAMMING ALGORITHMS ISYE 6663 Spring Semester 2023" www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf Dec 3, 2023 at 22:09
• @MarkL.Stone I have just read it.. there are examples and combination rules, but I do not see the general pattern - how can I detect if constsructing a self-concordant barrier is possible? Dec 4, 2023 at 4:17
• en.wikipedia.org/wiki/… "it can be proved that every closed convex domain in Rn has a self-concordant barrier with parameter O(n). But this “universal barrier” is given by some multivariate integrals, and it is too complicated for actual computations" Dec 4, 2023 at 12:58
• @MarkL.Stone OK. So the question is: how can I detect if constructing an efficiently-computable self-concordant barrier is possible? Dec 4, 2023 at 13:03
• If you manage to construct one and prove it is so, then you know it's possible. Otherwise, I'm not sure anyone knows how to make that determination. But I invite anyone to post to the contrary if they do know how. Dec 4, 2023 at 13:38