VERIFICATION OF EMPIRICAL MODELS OF SIMPLEX METHOD COMPLEXITY USING THE MODIFIED GMDH

Abstract

This paper presents the results of constructing an empirical dependence of the number of arithmetic operations of the standard simplex method as a function of the problem dimensionality defined in canonical form. To address this problem, the principle of model self-organization based on a modified combinatorial algorithm of the Group Method of Data Handling is applied. The modification of Group Method of Data Handling consists in forming a residual representation that is assumed to contain the sought empirical complexity function, as well as in applying a preliminary partitioning algorithm for the basis functions, which are additively included in the residual representation, into two non-overlapping classes: the class of main dominant components and the class of refining residual components. This approach significantly reduces the combinatorial search procedure. Based on theoretical complexity estimates available in the literature, a redundant set of basis functions was constructed. Five fundamental models were considered: Borgwardt’s polynomial estimate, the Adler – Megiddo quadratic bound, a basic polynomial form, the smoothed analysis model of Spielman – Teng, and a general mixed model previously proposed by the authors. To expand the search space, a logarithmic component was added to the basis functions. Thus, the residual representation includes six basis components, along with all their squares and pairwise products. The optimal structure was selected using a symmetric regularity criterion by evaluating more than 134 million alternative models, the number of which is uniquely determined by the cardinality of the set of refining residual components. To ensure the correct application of the least squares method for strongly nonlinear regressors of different scales (whose absolute values differ by several orders of magnitude), the necessity of scaling input data by their standard deviation, with optional centering, was experimentally justified. The efficiency of this approach was confirmed through a specially designed experiment with a known ideal solution, including a constant term (bias) at the order of 100000 and normally distributed noise with an amplitude of 1 % of the mean value of the ideal regression on the values of the input variables of the experiment. The results of simulation modeling on a dataset of 13690 randomly generated linear programming problems demonstrate the clear superiority of the mixed polynomial-logarithmic structure within the extended class of candidate functions.