Minimizing sum of functions with pairwise dependence

Question

I have formulated a problem where I need to minimize the sum of $N$ functions, with only pairwise dependence between the functions (any single constraint involves only two functions having adjacent indices). \begin{align} [\hat{x}_{1}~\hat{x}_{2}~\cdots~\hat{x}_{N}] &= \text{min}~\sum\limits_{n=1}^{N} f_{n}(x_{n}) \\ g(f_{1}(x_{1}),f_{2}(x_{2})) &\leq k \\ g(f_{2}(x_{2}),f_{3}(x_{3})) &\leq k \\ &\vdots \\ g(f_{N-1}(x_{N-1}),f_{N}(x_{N})) &\leq k \\ \end{align}

The functions $f(x)$ and $g(x)$ are highly non-linear and non-convex, in addition to the decision variables being integer-valued. I am wondering if there is a method for decomposing this problem into smaller sub-problems and iteratively solving them, using a divide-and-conquer approach? Essentially, my question is whether this 'pairwise dependence' can somehow be exploited to make this problem easier to solve? Fortunately, the sample space for the decision variables is small (about 5000 values), and I can actually apply a brute-force search for the minimum, provided the sub-problems are small enough.

I am aware of non-convex solvers such as Baron etc. but I'd like to know whether I can instead reduce the overall objective to a sum of 'smaller' objectives that can each be solved by a brute-force approach and where I am certain that the global minimum has been found.

Answer 1

I can suggest a shortest path approach, but you'll have to decide if it's computationally feasible (which depends on how hard $g()$ is to compute and how large $N$ is, among other things) and better than brute force.

First, let $X$ be the domain of $x$ and let $y_n=f(x_n)$. We can rewrite the problem as minimizing $\sum_{n=1}^N y_n$ subject to $g(y_n, y_{n+1})\le k$ for all $n$. Compute $Y=f(X)$ (which involves something like 5,000 evaluations of $f()$). The cardinality of $Y$ is at worst that of $X$, smaller if you are lucky.

Next, compute $Y_2=\lbrace (y,y')\in Y\times Y : g(y, y') \le k\rbrace$. This involves potentially 25 million or so evaluations of $g()$, so you might want to bring some reading material.

Now picture a layered digraph with $N+2$ layers, indexed $0,\dots,N+1$. Layer 0 contains just the root node and layer $N+1$ contains just the terminus. Layers $1,\dots,N$ each contain one node for every $y\in Y$. Arcs $(i,j)$ cost $j$ (except that arcs to the terminus have no cost). There is an arc from the root to every node in layer 1 and from every node in layer $N$ to the terminus. Otherwise, arc $(y_i, y_{i+1})$ exists if and only if $(y_i, y_{i+1})\in Y_2$. If $N$ is small, you can solve this directly.

If the network is too big, consider breaking it up based on powers of 2. We start with $N=1$ and find the shortest path from root to each node in layer 1 (trivial). Next, we set $N=2$ and find the shortest path (if any) from each node of layer 1 to each node of layer 2, which will just be the arc between them (if any). For $N=4$, we consider it as two copies of $N=2$ and find the shortest path from each node of the first layer of the first copy to each node of the second layer of the second copy, using what we know about $N=2$ and $Y_2$ (which is the set of possible connections between the two copies). Now repeat for $N=8, 16, \dots$, and eventually for the original value of $N$ by writing it as a binary expansion and stitching together previous results.

(Edit: I corrected something misleading in the preceding paragraph. I originally talked about shortest path source to end layer and start layer to sink, but you really need the shortest path from each node in the front layer of one copy to each node in the back layer of the other copy, which is more work.)

There's a lot of comparisons and record keeping in this approach, but the upsides are that it is all just adding and comparing (once the function evaluations are out of the way) and it is amenable to parallel operations.