Is convex program with exponential constraints NP-Hard

74 Views Asked by At

Convex optimization is widely known to be solvable in polynomial time, but is it still true when a convex program has an exponential number of constraints? For example, I have a convex program as follows, where $x_i \in \mathbb{R}^d$ and $x \in \mathbb{R}^{N \times d}$ (suppose $N$ is a super large number that is exponential to the input size), $f(x):\mathbb{R}^{N \times d} \rightarrow \mathbb{R}$ is a convex function (e.g. cross-entropy of $N$ distributions), $a \in \mathbb{R}^{N \times d}$ is constants:

$$ \text{min}_x \sum_i a_i x_i + f(x) $$

$$ \text{subject to} \quad a_i x_i \ge a_i x_j \quad \forall i, j \in \{1, \cdots, N\} $$

Obviously, the above program is a convex program but has exponential constraints. Can it still be efficiently solved, or is it actually NP-Hard?