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

Cecilia Orellana Castro; Manolo Rodriguez Heredia; Aurelio Ribeiro Leite Oliveira

doi:10.34179/revisem.v9i1.19557

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

Auteurs

Cecilia Orellana Castro Universidade Federal do Sul e Sudeste do Pará
Manolo Rodriguez Heredia Universidade Federal do Sul e Sudeste do Pará
Aurelio Ribeiro Leite Oliveira Universidade Estadual de Campinas

DOI :

https://doi.org/10.34179/revisem.v9i1.19557

Résumé

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

Téléchargements

Bibliographies de l'auteur

Manolo Rodriguez Heredia, Universidade Federal do Sul e Sudeste do Pará

Possui graduação em Engenharia Matemática pela Universidad Mayor de San Simon (2010), título revalidado na Universidade Estadual de Campinas como Bacharel em Matemática. Mestrado em Matemática pela Universidade Federal Fluminense (2013). Doutor em Matemática Aplicada pela Universidade Estadual de Campinas (2017). Pós-doutorado em Matemática Aplicada pela Universidade Estadual de Campinas (2020). Trabalha na área de Pesquisa Operacional, Otimização Linear e Tecnologias Digitais aplicadas ao ensino de Matemática. Atualmente é Professor Adjunto do Curso de Licenciatura em Matemática na área de Álgebra/Geometria, atuando também como professor no curso de Pós-graduação Lato-Sensu "Tecnologias Digitais aplicadas ao ensino de Ciências e Matemática" da Faculdade de Ciências Exatas do Instituto de Engenharia do Araguaia da Universidade do Sul e Sudeste do Pará. Coordenador Local do Polo Olímpico de Treinamento Intensivo (POTI) organizado pelo Instituto de Matemática Pura e Aplicada (IMPA) que prepara discentes da educação básica para a Olimpíada Brasileira de Matemática das Escolas Públicas (OBMEP).

Aurelio Ribeiro Leite Oliveira, Universidade Estadual de Campinas

Possui graduação em Bacharelado em Física e graduação em Bacharelado em Ciências da Computação pela Universidade Estadual de Campinas (1986), mestrado em Engenharia Elétrica pela Universidade Estadual de Campinas (1989), mestrado em Computational and Applied Mathematics - Rice University (1994) e doutorado em Computational and Applied Mathematics - Rice University (1997). Foi pós doutorando da Fapesp na Faculdade de Engenharia Eétrica e de Computação da Unicamp. Atualmente é professor titular da Universidade Estadual de Campinas tendo sido professor na USP São Carlos por um ano e meio. Tem experiência na área de Engenharia de Produção, Pesquisa Operacional, com ênfase em Programação Linear e Quadrática atuando principalmente nos seguintes temas: métodos de pontos interiores, programação linear, sistemas de potência, resolução de sistemas lineares de grande porte, precondicionadores, planejamento por radioterapia e fluxo em redes.

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

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

Auteurs

DOI :

Résumé

Téléchargements

Bibliographies de l'auteur

Manolo Rodriguez Heredia, Universidade Federal do Sul e Sudeste do Pará

Aurelio Ribeiro Leite Oliveira, Universidade Estadual de Campinas

Téléchargements

Publiée

Comment citer

Numéro

Rubrique

Licence