Optimal Algorithm for Optimization Problems with Special Restriction

Abstract

The present paper analyses a class of nonlinear optimization problems with special restrictions, we propose a direct method for solving the auxiliary problem, for which we calculate complexity, we also assesses the maximum number of elementary operations and describe the optimal algorithm for performing numerical calculations. The study builds an optimal algorithm for solving the auxiliary problem of PG model; the complexity of this algorithm is O(nm2, N), the number of elementary operations is minimal. Matrix inversion does not depend on the size of problem n and always has constant size - m × m and the operation complexity is O(m3). In practical situations, if m << n, then the value of m2 is much smaller than the value of n, thus can be considered as a constant, resulting the complexity is O(n2), in other words it’s almost the same as for the approximation methods. Thus, the model PG is fully functional and practically ”immune” to the size of the optimization problem.