Consider a convex optimisation problem in the form

$$ \begin{align} f_0(x_1, \ldots, x_n) &\to min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align} $$ where $f_0$ and $f_i$ are convex functions. Without loss of generality we can assume that $f_0$ is linear.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln(n/\varepsilon))$ computations of the values and  $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that $p(n,m) = n^3 (m+ n)$, $q(n,m) = n^2$. At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(.)$ expressions are somehow dependent on the functions $f_i$, e.g. on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. the discussion here https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(.)$ indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.

Interior point methods that have been developed later, seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.

Consider a convex optimisation problem in the form

$$\begin{align} f_0(x_1, \ldots, x_n) &\to \min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align}$$

where $f_0, f_1, \dots, f_m$ are convex functions. Without loss of generality, we can assume that $f_0$ is linear.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln (n/\varepsilon))$ computations of the values and  $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that

$$p(n,m) = n^3 (m+ n), \qquad q(n,m) = n^2$$

At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(\cdot)$ expressions are somehow dependent on the functions $f_i$, e.g., on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. this discussion on MathOverflow.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(\cdot)$ indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.

Interior point methods that have been developed later seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.

Consider a convex optimisation problem in the form

$$ \begin{align} f_0(x_1, \ldots, x_n) &\to min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align} $$ where $f_0$ and $f_i$ are convex functions.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln(n/\varepsilon))$ computations of the values and $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that $p(n,m) = n^3 (m+ n)$, $q(n,m) = n^2$. At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(.)$ expressions are somehow dependent on the functions $f_i$, e.g. on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. the discussion here https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(.)$ indeed depends on the problem, but could not find any clear confirmation of this guess.

Interior point methods that have been developed later, seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.

Consider a convex optimisation problem in the form

$$ \begin{align} f_0(x_1, \ldots, x_n) &\to min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align} $$ where $f_0$ and $f_i$ are convex functions. Without loss of generality we can assume that $f_0$ is linear.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln(n/\varepsilon))$ computations of the values and $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that $p(n,m) = n^3 (m+ n)$, $q(n,m) = n^2$. At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(.)$ expressions are somehow dependent on the functions $f_i$, e.g. on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. the discussion here https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(.)$ indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.

Interior point methods that have been developed later, seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.