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

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?

## 1 Answer

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.

• Ah, thank you! In case my feasible set is connected, as you mention, and if I can get a decent starting point, can you point me towards any standard algorithms or ways to go about solving the problem? – air Nov 16 '14 at 2:48
• I don't know. Thinking about it some more, the connectnedness of the feasible set isn't worth much because you are maximize a function that you know is growing. I can't quite convince myself that every local optimum is in fact a global optimum. If that were the case, you could relax the problem and first apply a continuous optimization scheme, as is often done in integer programming. I'm not an expert in this, and others will be able to help you more. – Wolfgang Bangerth Nov 17 '14 at 5:42
• Thank you again! I thought I had done progress on my previous question by reparametrizing it and seeing that the maximum can only occur at certain discrete points, but I suppose this does not help a lot. Playing around with relaxing the discrete problem to a continuous one seems to help a bit though! – air Nov 18 '14 at 0:01
• "If $g$ is also increasing in each component, then you know that the feasible set is connected and, I believe, in fact convex." It's connected, but not necessarily convex: consider $g(x,y)=\sqrt x+\sqrt y$. – user3883 Nov 21 '14 at 9:52
• Yes, good example. – Wolfgang Bangerth Nov 21 '14 at 12:29