Lossless divide and conquer principle for massively parallel optimizations

A lossless divide-and-conquer strategy is discovered for solving a global optimization on massively parallel and distributed processors. The lossless principle which is analogous to the incoherent phenomenon in physics is expressed in terms of a vector velocity V derived from the least mean square kinetic energy E=|V|²/2. We illustrate the nonlinearity that the sum of the best traveling salesman problem (TSP) solutions in subregions is not necessarily globally the best because of the boundary resultant vectors: V=A+B have a cross interaction terms (A,B)≠0. In fact, a nearest neighbor connection at the boundary cities represents a longer overall distance than the next nearest neighbor connection between boundary cities. Then, a theorem of orthogonal division error for lossless divide-and-conquer is proved, and the orthogonal projection is constructed for solving TSP explicitly.