Exploiting special structure in Karmarkar's linear programming algorithm (Q1106098)

Karmarkar's projective algorithm for solving linear programming problems is polynomial though the computational requirement at each iteration is very complicated. This article proposes a variant to Karmarkar's projective algorithm for solving a certain special class of linear programming problems, when linear constraints have a special structure. This variant is also polynomial. The special structure of the linear constraints permits to generate improved bounds and hence a better direction ande constrained cases are examined by the rejection, reduction and penalty methods. The relationship between our approach and the standard cases is explored. We then describe the mean value-level set method and prove its convergence (which does not depend on the choice of initial data) and the limited influence of the error propagation. The corresponding rejection, reduction and penalty algorithms are dicussed for constrained minimization problems. The optimality conditions and algorithms for integral global optimization can be implemented by the use of a proper designed Monte Carlo technique. Numerical tests have been done covering the examples of unconstrained and constrained problems and minimization of discontinuous functions and nonlinear integer programming problems, and problems with multiple global minimizers. The algorithms have been utilized to solve problems with variables up to 50 on the IBM PC. Integral global optimization algorithms have been successfully applied to many industrial and control problems such as automatic design of optical thin-film systems and prototype tenses, computer aided design of equalizers, optimal design of microwave filters, turbine wheels and speed reducers and nonlinear observation of dynamic systems.