Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper

1 Introduction

AI systems that interact with the real world often have to solve continuous optimization problems. For convex problems, which have no local optima, many sophisticated algorithms exist. However, most continuous optimization problems in AI and related fields are nonconvex, and often have an exponential number of local optima. For these problems, the standard solution is to apply convex optimizers with multistart and other randomization techniques [Schoen, 1991], but in problems with an exponential number of optima these typically fail to find the global optimum in a reasonable amount of time. Branch and bound methods can also be used, but scale poorly due to the curse of dimensionality [Neumaier et al., 2005].

In this paper we propose that such problems can instead be approached using problem decomposition techniques, which have a long and successful history in AI for solving discrete problems (e.g, [Davis et al., 1962; Darwiche, 2001; Bayardo Jr. and Pehoushek, 2000; Sang et al., 2004; 2005; Bacchus et al., 2009]). By repeatedly decomposing a problem into independently solvable subproblems, these algorithms can often solve in polynomial time problems that would otherwise take exponential time. The main difficulty in nonconvex optimization is the combinatorial structure of the modes, which convex optimization and randomization are illequipped to deal with, but problem decomposition techniques are well suited to. We thus propose a novel nonconvex optimization algorithm, which uses recursive decomposition to handle the hard combinatorial core of the problem, leaving a set of simpler subproblems that can be solved using standard continuous optimizers.

The main challenges in applying problem decomposition to continuous problems are extending them to handle continuous values and defining an appropriate notion of local structure. We do the former by embedding continuous optimizers within the problem decomposition search, in a manner reminiscent of satisfiability modulo theory solvers [De Moura and Bjørner, 2011], but for continuous optimization, not decision problems. We do the latter by observing that many continuous objective functions are approximately locally decomposable, in the sense that setting a subset of the variables causes the rest to break up into subsets that can be optimized nearly independently. This is particularly true when the objective function is a sum of terms over subsets of the variables, as is typically the case. A number of continuous optimization techniques employ a static, global decomposition (e.g., block coordinate descent [Nocedal and Wright, 2006] and partially separable methods [Griewank and Toint, 1981]), but many problems only decompose locally and dynamically, which our algorithm accomplishes.

For example, consider protein folding [Anfinsen, 1973; Baker, 2000], the process by which a protein, consisting of a chain of amino acids, assumes its functional shape. The computational problem is to predict this final conformation by minimizing a highly nonconvex energy function consisting mainly of a sum of pairwise distance-based terms representing chemical bonds, electrostatic forces, etc. Physically, in any conformation, an atom can only be near a small number of other atoms and must be far from the rest; thus, many terms are negligible in any specific conformation, but each term is non-negligible in some conformation. This suggests that sections of the protein could be optimized independently if the terms connecting them were negligible but that, at a global level, this is never true. However, if the positions of a few key atoms are set appropriately then certain amino acids will never interact, making it possible to decompose the problem into multiple independent subproblems and solve each separately. A local recursive decomposition algorithm for continuous problems can do exactly this.

We first define local structure and then present our algorithm, RDIS, which (asymptotically) finds the global optimum of a nonconvex function by (R)ecursively (D)ecomposing the function into locally (I)ndependent (S)ubspaces. In our analysis, we show that RDIS achieves an exponential speedup versus traditional techniques for nonconvex optimization such as gradient descent with restarts and grid search (although the complexity remains exponential, in general). This result is supported empirically, as RDIS significantly outperforms standard nonconvex optimization algorithms on three challenging domains: structure frommotion, highly multimodal test functions, and protein folding.

2 Recursive Decomposition for Continuous Optimization

This section presents our nonconvex optimization algorithm, RDIS. We first present our notation and then define local structure and a method for realizing it. We then describe RDIS and provide pseudocode.

In unconstrained optimization, the goal is to minimize an objective function f(x) over the variables x ∈ Rn . We focus on functions f : Rn →R that are continuously differentiable and have a nonempty optimal set x∗ with optimal value f ∗ = f(x∗ ) > -∞. Let I = {1, . . . , n} be the indices of x, let C ⊆ I, let xC ∈ R|C| be the restriction of x to the indices in C, and let ρC ∈ domain(xC) be a partial assignment where only the variables corresponding to the indices in C are assigned values. We define x|ρC ∈ Rn-|C| to be the subspace where those variables with indices in C are set to the values in ρC (i.e., for some ρC and for all i ∈ C we have x|ρC,i = ρC,i). Given U = I\C and partial assignment ρC, then, with a slight abuse of notation, we define the restriction of the function to the domain x|ρC as f|ρC (xU). In the following, we directly partition x instead of discussing the partition of I that induces it.

2.1 Local structure

A function is fully decomposable (separable) if it can be expressed as f(x) = ∑ni=1 gi(xi). Such functions are easy to optimize, since they decompose with respect to minimization; i.e., minx f(x) = ∑ni=1 minxi gi(xi). Conversely, decomposable nonconvex functions that are optimized without first decomposing them require exponentially more exploration to find the global optimum than the decomposed version. For example, let Mf be the set of modes of f and let Mi be the modes of each gi. Knowing that f is decomposable allows us to optimize each gi independently, giving |Mf | = ∑ni=1 |Mi|

modes to explore. However, if we instead optimized f directly, we would have to explore ∏ni=1 |Mi| modes, which is exponential in n. Unfortunately, fully decomposable functions like f are rare, as variables generally appear in multiple terms with many different variables and thus the minimization does not trivially distribute. However, decomposition can still be achieved if the function exhibits global or local structure, which we define here.

Definition 1.

• (a) f(x) is globally decomposable if there exists a partition {xC, xU1 , xU2 } of x such that, for every partial assignment ρC , f |ρC (xU1 , xU2 ) = f1|ρC (xU1 ) + f2|ρC (xU2 ).
• (b) f(x) is locally decomposable in the subspace x|ρC if there exists a partition {xC, xU1 , xU2 } of x and a partial assignment ρC such that f |ρC (xU1 , xU2 ) = f1|ρC (xU1 ) + f2|ρC (xU2 ).
• (c) f(x) is approximately locally decomposable in a neighbourhood of the subspace x|ρC if there exists a partition {xC, xU1 , xU2 } of x, partial assignments ρC, σC, and δ, ϵ ≥ 0 such that if ||σC -ρC|| ≤ δ then |f |σC (xU1 , xU2 ) - [f1|σC (xU1 ) + f2|σC (xU2 )]| ≤ ϵ.

Global structure (Definition 1a), while the easiest to exploit, is also the least prevalent. Local structure, which may initially appear limited, subsumes global structure while also allowing different decompositions throughout the space, making it strictly more general. Similarly, approximate local structure subsumes local structure. In protein folding, for example, two amino acids may be pushed either close together or far apart for different configurations of other amino acids. In the latter case, they can be optimized independently because the terms connecting them are negligible. Thus, for different partial configurations of the protein, different approximate decompositions are possible. The independent subspaces that result from local decomposition can themselves exhibit local structure, allowing them to be decomposed in turn. If an algorithm exploits local structure effectively, it never has to perform the full combinatorial optimization. Local structure does not need to exist everywhere in the space, just in the regions being explored. For convenience, we only refer to local structure below, unless the distinction between global or (approximate) local decomposition is relevant.

One method for achieving local decomposition is via (local) simplification. We say that fi(xC, xU) is (approximately locally) simplifiable in the subspace x|ρC defined by partial assignment ρC if, for a given ϵ ≥ 0, fi|ρC (xU) - fi|ρC (xU) ≤ 2ϵ, where h(x) and h(x) refer to the upper and lower bounds of h(x), respectively. Similarly, f(x) is (approximately locally) simplified in the subspace x|ρC defined by partial assignment ρC if, for a given ϵ ≥ 0, all simplifiable terms fi|ρC (xU) are replaced by the constant ki = 12 [fi|ρC (xU ) + fi|ρC (xU )]. For a function that is a sum of terms, local decomposition occurs when some of these terms simplify in such a way that the minimization can distribute over independent groups of terms and variables (like component decomposition in Relsat [Bayardo Jr. and Pehoushek, 2000] or in the protein folding example above). Given that there are m terms in the function, the maximum possible error in the simplified function versus the true function is m · ϵ. However, this would require all terms to be simplified and their true values to be at one of their bounds, which is extremely unlikely; rather, errors in different terms often cancel, and the simplified function tends to remain accurate. Note that ϵ induces a tradeoff between acceptable error in the function evaluation and the computational cost of optimization, since a simplified function has fewer terms and thus evaluating it and computing its gradient are both cheaper. While the above definition is for sums of terms, the same mechanism applies to functions that are products of (nonnegative) factors, although error grows multiplicatively here.

2.2 The RDIS Algorithm

RDIS is an optimization method that explicitly finds and exploits local decomposition. Pseudocode is shown in Algorithm 1, with subroutines explained in the text. At each level of recursion, RDIS chooses a subset of the variables xC ⊆ x (inducing a partition {xC, xU} of x) and assigns them values ρC such that the simplified objective function f|ρC (xU) decomposes into multiple (approximately) independent subfunctions fi|ρC (xUi ), where {xU1 , . . . , xUk } is a partition of xU and 1 ≤ k ≤ n. RDIS then recurses on each subfunction, globally optimizing it conditioned on the assignment xC = ρC. When the recursion completes, RDIS uses the returned optimal values (conditioned on ρC) of xU to choose new values for xC and then simplifies, decomposes, and optimizes the function again. This repeats until a heuristic stopping criterion is satisfied.

Algorithm 1 Recursive Decomposition into locally Independent Subspaces (RDIS).

Input: Function f, variables x, initial state x0 , subspace optimizer S, and approximation error ϵ.

Output: (Approximate) global minimum f ∗ at state x∗ .

1: function RDIS(f, x, x0 , S, ϵ) 2: xC ← CHOOSEVARS(x) // variable selection 3: xU ←x\xC, f ∗ ←∞, x∗ ←x0 4: repeat 5: partition x∗ into {σ∗C , σ∗U } 6: ρC ← S( f |σ∗U (xC), σ∗C ) // value selection 7: ˆ f |ρC (xU ) ← SIMPLIFY(f |ρC (xU ), ϵ) 8: { ˆ fi(xUi )} ← DECOMPOSE( ˆ f |ρC (xU )) 9: for i = 1, . . . , k do // recurse on the components 10: 〈f ∗ i , ρUi 〉 ←RDIS( ˆ fi, xUi , σ∗Ui , S, ϵ) 11: f ∗ ρ ← ∑ki=1 f ∗ i , ρU ←∪ki=1ρUi 12: if f ∗ ρ < f ∗ then // record new minimum 13: f ∗ ← f ∗ ρ , x∗ ← ρC ∪ ρU 14: until stopping criterion is satisfied 15: return 〈f ∗ , x∗ 〉

RDIS selects variables (line 2) heuristically, with the goal of choosing a set of variables that enables the largest amount of decomposition, as this provides the largest computational gains. Specifically, RDIS uses a hypergraph partitioning algorithm to determine a small cutset that will decompose the graph; this cutset becomes the selected variables, xC. Values for xC are determined (line 6) by calling a nonconvex subspace optimizer with the remaining variables (xU) fixed to their current values. The subspace optimizer S is specified by the user and is customizable to the problem being solved. In our experiments we used multi-start versions of conjugate gradient descent and Levenberg-Marquardt [Nocedal and Wright, 2006]. Restarts occur within line 6: if S converges without making progress then it restarts to a new point in xC and runs until it reaches a local minimum.

To simplify the objective function (line 7), RDIS determines which terms are simplifiable (i.e., have sufficiently small bounds) and then simplifies (approximates) these by replacing them with a constant. These terms are not passed to the recursive calls. After variables have been assigned and the function simplified, RDIS locally decomposes (line 8) the simplified function into independent sub-functions (components) that have no overlapping terms or variables and thus can be optimized independently, which is done by recursively calling RDIS on each. See Figure 1 for a visualization of this process. The recursion halts when CHOOSEVARS selects all of x (i.e., xC = x and xU = ∅), which occurs when x is small enough that the subspace optimizer can optimize f(x) directly. At this point, RDIS repeatedly calls the subspace optimizer until the stopping criterion is met, which (ideally) finds the global optimum of f |σ∗U (xC) = f (x) since S is a nonconvex optimizer. The stopping criterion is userspecified, and depends on the subspace optimizer. If a multistart descent method is used, termination occurs after a specified number of restarts, corresponding to a certain probability that the global optimum has been found. If the subspace optimizer is grid search, then the loop terminates after all values of xC have been assigned. More subroutine details are provided in Section 4.

3 Analysis

We now present analytical results demonstrating the benefits of RDIS versus standard algorithms for nonconvex optimization. Formally, we show that RDIS explores the state space in exponentially less time than the same subspace optimizer for a class of functions that are locally decomposable, and that it will (asymptotically) converge to the global optimum. Due to space limitations, proofs are presented in the supplementary material. 1 Let the number of variables be n and the number of values assigned by RDIS to xC be ξ(d), where d is the size of xC. The form of ξ(d) depends on the subspace optimizer, but can be roughly interpreted as the number of modes of the sub-function f|σ∗U (xC) to explore times a constant factor.

Proposition 1. If, at each level, RDIS chooses xC ⊆ x of size |xC| = d such that, for each selected value ρC, the simplified function ˆ f|ρC (xU) locally decomposes into k > 1 independent sub-functions { ˆ fi(xUi )} with equal-sized domains xUi , then the time complexity of RDIS is O( nd ξ(d)logk (n/d) ).

Note that since RDIS uses hypergraph partitioning to choose variables, it will always decompose the remaining variables xU. This is also supported by our experimental results; if there were no decomposition, RDIS would not perform any better than the baselines.

From Proposition 1, we can compute the time complexity of RDIS for different subspace optimizers. Let the subspace optimizer be grid search (GS) over a bounded domain of width w with spacing δ in each dimension. Then the complexity of grid search is simply O((w/δ)n ) = O(sn ).

Proposition 2. If the subspace optimizer is grid search, then ξ(d) = (w/δ)d = sd , and the complexity of RDISGS is O( nd sd logk (n/d) ).

Rewriting the complexity of grid search as O(sn ) = O(sd(n/d) ), we see that it is exponentially worse than the complexity of RDISGS when decomposition occurs.

Now consider a descent method with random restarts (DR) as the subspace optimizer. Let the volume of the basin of attraction of the global minimum (the global basin) be ln and the volume of the space be Ln . Then the probability of randomly restarting in the global basin is (l/L)n = pn . Since the restart behavior of DR is a Bernoulli process, the expected number of restarts to reach the global basin is r = p-n , from the shifted geometric distribution. If the number of iterations needed to reach the stationary point of the current basin is τ then the expected complexity of DR is O(τp-n ). If DR is used within RDIS, then we obtain the following result.

Proposition 3. If the subspace optimizer is DR, then the expected value of ξ(d) is τp-d , and the expected complexity of RDISDR is O( nd (τp-d )logk (n/d) ).

Rewriting the expected complexity of DR as O(τ(p-d )n/d ) shows that RDISDR is exponentially more efficient than DR.

Regarding convergence, RDIS with ϵ = 0 converges to the global minimum given certain conditions on the subspace optimizer. For grid search, RDISGS returns the global minimum if the grid is finite and has sufficiently fine spacing. For gradient descent with restarts, RDISDR will converge to stationary points of f(x) as long as steps by the subspace optimizer satisfy two technical conditions. The first is an Armijo rule guaranteeing sufficient decrease in f and the second guarantees a sufficient decrease in the norm of the gradient (see (C1) and (C2) in the supplementary material). These conditions are necessary to show that RDISDR behaves like an inexact Gauss-Seidel method [Bonettini, 2011], and thus each limit point of the generated sequence is a stationary point of f(x). Given this, we can state the probability with which RDISDR will converge to the global minimum.

1 http://cs.uw.edu/homes/pedrod/papers/ijcai15sp.pdf

Proposition 4. If the non-restart steps of RDIS satisfy (C1) and (C2), ϵ = 0, the number of variables is n, the volume of the global basin is v = ln , and the volume of the entire space is V = Ln , then RDISDR returns the global minimum after t restarts, with probability 1 - (1 - (v/V ))t .

For ϵ > 0, we do not yet have a proof of convergence, even in the convex case, since preliminary analysis indicates that there are rare corner cases in which the alternating aspect of RDIS, combined with the simplification error, can potentially result in a non-converging sequence of values; however, we have not experienced this in practice. Furthermore, our experiments clearly show ϵ > 0 to be extremely beneficial, especially for large, highly-connected problems.

Beyond its discrete counterparts, RDIS is related to many well-known continuous optimization algorithms. If all variables are chosen at the top level of recursion, then RDIS simply reduces to executing the subspace optimizer. If one level of recursion occurs, then RDIS behaves similarly to alternating minimization algorithms (which also have global convergence results [Grippo and Sciandrone, 1999]). For multiple levels of recursion, RDIS has similarities to block coordinate (gradient) descent algorithms (see Tseng and Yun [2009] and references therein). However, what sets RDIS apart is that decomposition in RDIS is determined locally, dynamically, and recursively. Our analysis and experiments show that exploiting this can lead to substantial performance improvements.

4 RDIS Subroutines

In this section, we present the specific choices we've made for the subroutines in RDIS, but note that others are possible and we intend to investigate them in future work.

Variable Selection. Many possible methods exist for choosing variables. For example, heuristics from satisfiability may be applicable (e.g., VSIDS [Moskewicz et al., 2001]). However, RDIS uses hypergraph partitioning in order to ensure decomposition whenever possible. Hypergraph partitioning splits a graph into k components of approximately equal size while minimizing the number of hyperedges cut. To maximize decomposition, RDIS should choose the smallest block of variables that, when assigned, decomposes the remaining variables. This corresponds exactly to the set of edges cut by hypergraph partitioning on a hypergraph that has a vertex for each term and a hyperedge for each variable that connects the terms that variable is in (note that this is the inverse of Figure 1). RDIS maintains such a hypergraph and uses the PaToH hypergraph partitioning library [C¸ ataly¨urek and Aykanat, 2011] to quickly find good, approximate partitions. A similar idea was used in Darwiche and Hopkins 2001 to construct d-trees for recursive conditioning; however, they only apply hypergraph partitioning once at the beginning, whereas RDIS performs it at each level of the recursion.

While variable selection could be placed inside the loop, it would repeatedly choose the same variables because hypergraph partitioning is based on the graph structure. However, RDIS still exploits local decomposition because the variables and terms at each level of recursion vary based on local structure. In addition, edge and vertex weights could be set based on current bounds or other local information.

Value Selection. RDIS can use any nonconvex optimization subroutine to choose values, allowing the user to pick an optimizer appropriate to their domain. In our experiments, we use multi-start versions of both conjugate gradient descent and Levenberg-Marquardt, but other possibilities include Monte Carlo search, quasi-Newton methods, and simulated annealing. We experimented with both grid search and branch and bound, but found them practical only for easy problems. In our experiments, we have found it helpful to stop the subspace optimizer early, because values are likely to change again in the next iteration, making quick, approximate improvement more effective than slow, exact improvement.

Simplification and Decomposition. Simplification is performed by checking whether each term (or factor) is simplifiable and, if it is, setting it to a constant and removing it from the function. RDIS knows the analytical form of the function and uses interval arithmetic [Hansen and Walster, 2003] as a general method for computing and maintaining bounds on terms to determine simplifiability. RDIS maintains the connected components of a dynamic graph [Holm et al., 2001] over the variables and terms (equivalent in structure to a factor or co-occurrence graph). Components in RDIS correspond exactly to the connected components in this graph. Assigned variables and simplified terms are removed from this graph, potentially inducing local decomposition.

Caching and Branch & Bound. RDIS' similarity to model counting algorithms suggests the use of component caching and branch and bound (BnB). We experimented with these and found them effective when used with grid search; however, they were not beneficial when used with descentbased subspace optimizers, which dominate grid-searchbased RDIS on non-trivial problems. For caching, this is because components are almost never seen again, due to not reencountering variable values, even approximately. For BnB, interval arithmetic bounds tended to be overly loose and no bounding occurred. Our experience suggests that this is because the descent-based optimizer effectively focuses exploration on the minima of the space, which are typically close in value to the current optimum. However, we believe that future work on caching and better bounds would be beneficial.

5 Experimental Results

We evaluated RDIS on three difficult nonconvex optimization problems with hundreds to thousands of variables: structure from motion, a high-dimensional sinusoid, and protein folding. Structure from motion is an important problem in vision, while protein folding is a core problem in computational biology. We ran RDIS with a fixed number of restarts at each level, thus not guaranteeing that we found the global minimum. For structure from motion, we compared RDIS to that domain's standard technique of LevenbergMarquardt (LM) [Nocedal and Wright, 2006] using the levmar library [Lourakis, 2004], as well as to a block-coordinate descent version (BCD-LM). In protein folding, gradientbased methods are commonly used to determine the lowest energy configuration of a protein, so we compared RDIS to conjugate gradient descent (CGD) and a block-coordinate descent version (BCD-CGD). CGD and BCD-CGD were also used for the high-dimensional sinusoid. Blocks were formed by grouping contextually-relevant variables together (e.g., in protein folding, we never split up an amino acid). We also compared to ablated versions of RDIS. RDIS-RND uses a random variable selection heuristic and RDIS-NRR does not use any internal random restarts (i.e., it functions as a convex optimizer) but does have top-level restarts. In each domain, the optimizer we compare to was also used as the subspace optimizer in RDIS. All experiments were run on the same cluster. Each computer in the cluster was identical, with two 2.33GHz quad core Intel Xeon E5345 processors and 16GB of RAM. Each algorithm was limited to a single thread. Further details can be found in the supplementary material.

Structure fromMotion. Structure from motion is the problem of reconstructing the geometry of a 3-D scene from a set of 2-D images of that scene. It consists of first determining an initial estimate of the parameters and then performing nonlinear optimization to minimize the squared error between a set of 2-D image points and a projection of the 3-D points onto camera models [Triggs et al., 2000]. The latter, known as bundle adjustment, is the task we focus on here. Global structure exists, since cameras interact explicitly with points, creating a bipartite graph structure that RDIS can decompose, but (nontrivial) local structure does not exist because the bounds on each term are too wide and tend to include ∞. The dataset used is the 49-camera, 7776-point data file from the Ladybug dataset [Agarwal et al., 2010]

Figure 2 shows performance on bundle adjustment as a function of the size of the problem, with a log scale y-axis. Each point is the minimum error found after running each algorithm for 5 hours. Each algorithm is given the same set of restart states, but algorithms that converge faster may use more of these. Since no local structure is exploited, Figure 2 effectively demonstrates the benefits of using recursive decomposition with intelligent variable selection for nonconvex optimization. Decomposing the optimization across independent subspaces allows the subspace optimizer to move faster, further, and more consistently, allowing RDIS to dominate the other algorithms. Missing points are due to algorithms not returning any results in the allotted time.

High-dimensional Sinusoid. The second domain is a highlymultimodal test function defined as a multidimensional sinusoid placed in the basin of a quadratic, with a small slope to make the global minimum unique. The arity of this function (i.e., the number of variables contained in each term) is controlled parametrically. Functions with larger arities contain more terms and dependencies, and thus are more challenging. A small amount of local structure exists in this problem.

In Figure 3, we show the current best value found versus time. Each datapoint is from a single run of an algorithm using the same set of top-level restarts, although, again, algorithms that converge faster use more of these. RDIS outperforms all other algorithms, including RDIS-NRR. This is due to the nested restart behavior afforded by recursive decomposition, which allows RDIS to effectively explore each subspace and escape local minima. The poor initial performance of RDIS for arities 8 and 12 is due to it being trapped in a local minimum for an early variable assignment while performing optimizations lower in the recursion. However, once the lowlevel recursions finish it escapes and finds the best minimum without ever performing a top level restart (Figure 2 in the supplementary material contains the full trajectories).

Protein Folding. The final domain is sidechain placement for protein folding with continuous angles between atoms. Amino acids are composed of a backbone segment and a sidechain. Sidechain placement requires setting the sidechain angles with the backbone atoms fixed. It is equivalent to finding the MAP assignment of a continuous pairwise Markov random field (cf., Yanover et al. [2006]). Significant local structure is present in this domain. Test proteins were selected from the Protein Data Bank [Berman et al., 2000] with sequence length 300-600 such that the sequences of any two did not overlap by more than 30%.

Figure 4 shows the results of combining all aspects of RDIS, including recursive decomposition, intelligent variable selection, internal restarts, and local structure on a difficult problem with significant local structure. Each algorithm is run for 48 hours on each of 21 proteins of varying sizes. RDIS is run with both ϵ = 1.0 and ϵ = 2.0 and both results are shown on the figure. RDIS outperforms CGD and BCD-CGD on all proteins, often by a very large amount.

Figure 5 demonstrates the effect of ϵ on RDIS for protein folding. It shows the performance of RDIS-NRR as a function of ϵ, where performance is measured both by minimum energy found and time taken. RDIS-NRR is used in order to remove the randomness associated with the internal restarts of RDIS, resulting in a more accurate comparison across multiple runs. Each point on the energy curve is the minimum energy found over the same 20 restarts. Each point on the time curve is the total time taken for all 20 restarts. As ϵ increases, time decreases because more local structure is being exploited. In addition, minimum energy actually decreases initially. We attribute this to the smoothing caused by increased simplification, allowing RDIS to avoid minor local minima in the objective function.

6 Conclusion

This paper proposed a new approach to solving hard nonconvex optimization problems based on recursive decomposition. RDIS decomposes the function into approximately locally independent sub-functions and then optimizes these separately by recursing on them. This results in an exponential reduction in the time required to find the global optimum. In our experiments, we show that problem decomposition enables RDIS to systematically outperform comparable methods.

Directions for future research include applying RDIS to a wide variety of nonconvex optimization problems, further analyzing its theoretical properties, developing new variable and value selection methods, extending RDIS to handle hard constraints, incorporating discrete variables, and using similar ideas for high-dimensional integration.

Acknowledgments

This research was partly funded by ARO grant W911NF-081-0242, ONR grants N00014-13-1-0720 and N00014-12-10312, and AFRL contract FA8750-13-2-0019. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of ARO, ONR, AFRL, or the United States Government.