THE GOLDMAN-TUCKER THEOREM FOR TWO-SIDE CONSTRAINTS LINEAR OPTIMIZATION PROBLEM

Abstract

The Goldman-Tucker theorem holds significant importance in linear optimization, as it ensures the existence of a strictly complementary solution. Two reasons underscore its relevance: firstly, logarithmic barrier interior point methods converge towards a strictly complementary solution, whose existence is warranted by this theorem. Secondly, the Goldman-Tucker theorem, coupled with the complementary slackness condition of the KKT (Karush–Kuhn–Tucker) system, has motived the development of efficient preconditioners for the final iterations of interior point methods, such as the Splitting preconditioner. Academic texts of linear optimization present this result as well as its consequences only for the canonical and standard form. This paper aims to accurately elucidate this theorem for the two-side constraints linear optimization problem with a detailed demonstration. Additionally, a theoretical result that uses this theorem to show that the central path converges to a strictly complementary solution and an example of application of both theoretical results are presented.

Keywords: Interior point method; Central path; Strictly