I've a question on optimization (it is a general question). I have a problem $P$ where basically i have the analytic expression of the objective function, which is a multivariate polynomial (positive), but i don't know all the constraints on the decision variables. There's a part where it is a linear system, while instead there is one constraints which is highly non linear and i can't derive neither the expression, however it is computable (i mean i can compute if such constraint hold's or not for a given decision variables).
Basically it is something like
$$\begin{equation}\left\{ \begin{array}{l} \vec{x} = \text{argmin}_{\vec{x}} p_n(\vec{x}) \\ A\vec{x} \leq \vec{b} \\ \psi(\vec{x}) \leq \epsilon \\ \vec{x} \in U \subset \mathbb{Z}^n \end{array} \right.\end{equation} $$
It is of course a problem of integer programming, the set $U$ isn't that large (i.e. go through all the values of the variables is not that expensive) and the function $\psi(\cdot)$ is computationally expensive to compute. Just to clarify it is something of the form $\psi(\vec{x}) = \text{max}_{q \in V} g(\vec{x} ; q)$ where $V$ is a discrete but very large set.
My question is since basically the problem it is partially known (in terms of formula to be briefly) is there a specific way to study this kind of problem?
I basically need to find the max of $\psi(\cdot)$ in a fast way. What kind of properties could i look for? What kind of mathematical optimizations approach are there for this kind of problem?