Discrete optimization on a cartesian product with component-wise increasing objective function

Question

The set-up is the following:

We have $K$ finite sets of real numbers,

i.e. sets $G_i, i=1 \dotsc, K$ and $|G_i| = n_i < \infty$.

Furthermore, assume that we have a function

$$ h: \mathbb R^K \to \mathbb R $$

which is monotonically increasing in each component.

Similarly, there is another function $$g: \mathbb R^K \to \mathbb R$$,which does not necessarily fullfill the monotonicity condition.

The optimization problem I want to solve is the following:

Find $$\max_{(x_1,\dotsc,x_K) \in G_1 \times \dotsc \times G_K} h(x_1,\dotsc, x_K)$$

subject to $$g(x_1,\dotsc, x_K) \leq c$$, where $c$ is a pre-specified constant. The naive approach takes $2\prod_{i=1}^{K}n_i$ function evaluations (evaluate $h$, check condition defined by $g$).

By how much can we improve this by using the componentwise monotonicity of $h$? What if we also assume that $g$ is also increasing in each component?

Answer 1

The monotonicity of $h$ doesn't help you much if you can't say anything about the shape of the feasible set defined by the constraint. Intuitively, for a monotonic objective function, you'd like to "go as far to the right as possible" in each coordinate, but if the constraint function has no properties, in each coordinate direction the feasible set may be disconnected intervals. On the other hand, if $g$ is also increasing in each component, then you know that the feasible set is connected and, I believe, in fact convex. That's a much easier problem to describe.