(476a) On the Use of Data Analytics Technology to Replace Dual Problems and Improve Decomposition Algorithms for Global Optimization Using Cutting Plane Approximations

The work explores data analytics in the development of optimization methodology for global optimization as applied through decomposition methods and cutting plane algorithms. The basic idea would be to treat cutting planes as data populations generated during the implementation of the method and at each separate iteration of the algorithm; the elements of the population are renewed based on the incumbent (local) solution. Data intelligence is subsequently applied to measure, fathom, and screen planes, also to represent data spaces of the dual problem. Data technology is applied to explore metrics, the geometry of the space and aims to evaluate correlations in the solution space.

The data approach has been tested against a library of optimization problems formulated as quadratic and box constrained programs that feature varying sparsity and density in their symmetric matrix Q. The work capitalizes and builds on innovations by Baltean-Lugojan et al. (2019) who recently presented a generic and effective outer approximation method suitable for semidefinite relaxations. The key element of their work is to decompose high-dimensional cutting planes into their low-dimensional counterparts. Such a decomposition results in an combinatorial explosion in available cutting planes for the separation problem, and thus they have introduced novel selection measures based on feasibility violation and improvement of the objective function. Their separation problem has been researched using clustering techniques. New metrics are explored by means of geometrical interpretation of the similarities cutting planes are expected to be baring depending on the solution of the Primal problem. Apart from the Euclidean metric, an affinity metric is presented to efficiently evaluate and screen cutting planes generated from different subspaces. The cosine similarity is tested to evaluate cutting planes based on the direction they are driving the objective function.

Data analytics are explored with the application of a range of clustering techniques while spectral clustering is applied with a twofold objective: visualize the solution space and represent the data in the dual space. Analytics are found to dramatically improve the duality gap and the quality of the solution. Computational overheads in the use have been tested with accelerated versions of clustering and a combined use of short-cut methods towards a number of hybrid variants that are compared using the set of test problems.

The work identifies a lot of promising ground in the use of data analytics. Other than replacing the dual problem by a data-driven approach, advances include significant improvements in closing the duality gap in the optimization. This is a consistent result in all the problems tested as depicted in Figure 1. Overall, as the complexity of the problems increases, high dimensionality and high density, the gap closure is widened; in problems of Set 3 and Set 4, QPs with 100 variables and 50 and 75 density respectively, the proposed clustering techniques outperform the Reference algorithm derived from Baltean-Lugojan et al. (2019). The best performance is observed by the use of the affinity metric algorithm followed by Hybrid1. In the cases of lower complexity the both the reference algorithm and the proposed algorithms have closed the duality gap.

Figure 2 illustrates the convergence of the various examined algorithms for a fixed problem with 100 variables and 50% density. It is apparent that neither of the algorithms have reached the global optimum, however the new clustering approaches are converging faster in terms of optimization rounds and reach a lower final solution.

To further investigate the improvement of the new algorithms, the ratio of the deference of % gap closure between reference and new algorithm (%Δf) to %gap closure of reference (f*) is computed. In Figure 3 the % improvement in the solution quality scales with the complexity of the set problem, in Set 3 the novel methods propose no improvements in the final solution, in Set 4 the are up to 40% for the new metric clustering and in Set 5 they spike at almost 90% of the reference algorithm which is consistent with Figure 2 as well.

We can summarize that the geometry of space and the metrics hold a very significant impact on the performance. In other words, the geometrical interpretation of the dual space holds the most promising lines for future work.

References:

Radu Baltean-Lugojan, Ruth Misener, Pierre Bonami and Andrea Tramontani. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. 2019