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?

  • $\begingroup$ 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 $\endgroup$ Dec 3, 2023 at 22:09
  • $\begingroup$ @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? $\endgroup$ Dec 4, 2023 at 4:17
  • $\begingroup$ 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" $\endgroup$ Dec 4, 2023 at 12:58
  • $\begingroup$ @MarkL.Stone OK. So the question is: how can I detect if constructing an efficiently-computable self-concordant barrier is possible? $\endgroup$ Dec 4, 2023 at 13:03
  • $\begingroup$ 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. $\endgroup$ Dec 4, 2023 at 13:38


Your Answer

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