Following objective is to be maximised: $\sum_{i=1}^n c_i.x + \sum_{j=1}^{300} e^{-x_j^2}$ where $x \in R^{300}, c_i \in R^{300}$ and $x_j$ is the $j^{th}$ element of the vector $x$
We need to find the vector $x$. I am solving the above in Python, and it is taking extremely long. How can I find the time complexity of this optimization problem? I need to find the bottleneck step that is making this so slow. Thanks in advance!
I assume $R$ refers to the real numbers, $\cdot$ refers to the dot product and you are trying to find the global maximum point of the objective function.
First, let's package $c_i$ into a $n \times 300$ matrix as $$C = \begin{pmatrix}c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix}$$ The objective function $f$ can then be written as $$f(x) = \sum_{i = 1}^n (Cx)_i + \sum_{j = 1}^{300} e^{-x_j^2}$$ If we choose $C$ to be a random matrix, say each $c_{ij} \sim N(0, 1)$ i.i.d., we claim
Proof
First, notice $$\sum_{i = 1}^n c_{i1} \sim N(0, n)$$ This implies $\sum_\limits{i = 1}^n c_{i1} \ne 0$ a.s.
Let $\sigma = \sum_\limits{i = 1}^n c_{i1}$. Suppose $\sigma > 0$. We then choose $x = Me_1$ and thus $$f(x) = f(Me_1) = M\sum_{i = 1}^n c_{i1} + e^{-M^2} + 299 = M\sigma + e^{-M^2} + 299 \to +\infty$$ as $M \to +\infty$.
The same argument works for $\sigma < 0$ if we choose $x = -Me_1$.
Therefore, $f$ is unbounded above a.s. if we choose $C$ randomly.
I think this is why you ran into problem when trying to solve it in Python - no algorithm can work because the global maximum point does not exist almost surely!