SFU Operations Research Seminars: Tanmaya Karmarkar

First example of applying tensor optimization to combinatorial problems was shown in IPCO 1992: pages 406-420. We improve and strengthen those results in several ways and obtain computational results on three problems – graph partitioning, satisfiability and analysis of counterexamples related to Hilbert’s 17th problem. For this we created a mixed symbolic-numeric model formulation package which facilitates definition of objective function, equality and inequality constraints and definition of new dependent variables. For discrete problems certain inequalities valid at candidate solutions are dynamically incorporated in the iterations of the continuous optimization algorithm based on underlying non-Newtonian geometry of the interior-point space. For graph partitioning we obtain optimal solutions including proof of optimality. For satisfiability problem we either find the satisfiable assignment or construct and output proof of unsatisfiability. For Hilbert’s 17th problem we analyse concrete examples whose non-negativity has been stablished to be not provable using sums of the squares expressions valid in RN. However, for these counterexamples, we construct non-negativity proofs by computationally constructing sums of squares expressions valid on certain sub-varieties of RN The same modeling package mentioned above is used to post process the solver output into symbolic proofs of optimality or infeasibility.