No description available.

We study the zeroth-, first-, and second-order algorithms proposed by Tuncel. The zeroth-order algorithms are the generalization of the classic primal-dual affine-scaling methods, and have a strong connection with the quasi-Newton method. Although the zeroth-order algorithms have the property of strict monotone decrease in both primal and dual objective values, they may not converge. We give an illustrative example as well as an algebraic proof to show that the zeroth-order algorithms do not converge to an optimal solution in some cases. The second-order algorithms use the gradients and Hessians of the barrier functions. Tuncel has shown that all second-order algorithms have a polynomial iteration bound. The second-order algorithms have a range of primal-dual scaling matrices to be chosen. We give a method to construct such a primal-dual scaling matrix. We then analyze a new centrality measure. This centrality measure appeared in both first- and second-order algorithms. We compare the neighbourhood defined by this centrality measure with other known neighbourhoods. We then analyze how this centrality measure changes in the next iteration in terms of the step length and some other information of the current iteration.

We study the zeroth-, first-, and second-order algorithms proposed by Tuncel. The zeroth-order algorithms are the generalization of the classic primal-dual affine-scaling methods, and have a strong connection with the quasi-Newton method. Although the zeroth-order algorithms have the property of strict monotone decrease in both primal and dual objective values, they may not converge. We give an illustrative example as well as an algebraic proof to show that the zeroth-order algorithms do not converge to an optimal solution in some cases. The second-order algorithms use the gradients and Hessians of the barrier functions. Tuncel has shown that all second-order algorithms have a polynomial iteration bound. The second-order algorithms have a range of primal-dual scaling matrices to be chosen. We give a method to construct such a primal-dual scaling matrix. We then analyze a new centrality measure. This centrality measure appeared in both first- and second-order algorithms. We compare the neighbourhood defined by this centrality measure with other known neighbourhoods. We then analyze how this centrality measure changes in the next iteration in terms of the step length and some other information of the current iteration.

The thesis formulates and proves a witnessing theorem for SPV -provable formulas in the form ∀x∃yA(x, y) where A corresponds to a polynomial time decidable relation. By SPV we understand an extension of the theory TPV (the universal theory of N in the language representing polynomial algorithms) by additional axioms ensuring the existence of a minimum of a linear ordering defined by a polynomial time decidable relation on an initial segment. As these additional axioms are not universal sentences, the theory SPV requires nontrivial use of witnessing Herbrand's and KPT theorems which have direct application only for universal theories. Based on the proven witnessing theorem, we derive a NP search problem characterizing complexity of finding y for a given x such that A(x, y). A part of the thesis is dedicated to arguments supporting the conjecture that SPV is strictly stronger than TPV . 1

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-12T16:55:40Z No. of bitstreams: 2 Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:31:42Z (GMT) No. of bitstreams: 2 Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-12-13T19:31:42Z (GMT). No. of bitstreams: 2 Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-18 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Quadratic forms are algebraic expressions that have important role in different areas of computer science, mathematics, physics, statistics and others. We deal with rational quadratic forms and integral quadratic forms, with rational and integer coefficients respectively. Existing methods for recognition of rational quadratic forms have exponential time complexity or use approximation that weaken the result reliability. We develop a polinomial algorithm that improves the best-case of rational quadratic forms recognition in constant time. In addition, new strategies were used to guarantee the results reliability, by representing rational numbers as a fraction of integers, and to identify linear combinations that are linearly independent, using Gauss reduction. About the recognition of integral quadratic forms, we identified that the existing algorithms have exponential time complexity for weakly nonnegative type and are polynomial for weakly positive type, however the degree of the polynomial depends on the algebra dimension and can be very large. We have introduced a polynomial algorithm for the recognition of weakly nonnegative quadratic forms. The related algorithm identify hypercritical restrictions testing every subgraph of 9 vertices of the quadratic form associated graph. By adding Depth First Search approach, a similar strategy was used in the recognition of weakly positive type. We have also shown that the recognition of integral quadratic forms can be done by mutations in the related exchange matrix. / Formas quadráticas são expressões algébricas que têm papel importante em diferentes áreas da ciência da computação, matemática, física, estatística e outras. Abordamos nesta tese formas quadráticas racionais e formas inteiras, com coeficientes racionais e inteiros respectivamente. Os métodos existentes para reconhecimento de formas quadráticas racionais têm complexidade de tempo exponencial ou usam aproximações que deixam o resultado menos confiável. Apresentamos um algoritmo polinomial que aprimora o melhorcaso do reconhecimento de formas quadráticas para tempo constante. Ainda mais, novas estratégias foram usadas para garantir a confiabilidade dos resultados, representando nú- meros racionais como frações de inteiros, e para identificar combinações lineares que são linearmente independentes, usando a redução de Gauss. Sobre o reconhecimento de formas inteiras, identificamos que os algoritmos existentes têm complexidade de tempo exponencial para o tipo fracamente não-negativa e polinomial para o tipo fracamente positiva. No entanto, o grau do polinômio depende da dimensão da álgebra e pode ser muito grande. Apresentamos um algoritmo polinomial para o reconhecimento de formas inteiras fracamente positivas. Este algoritmo identifica restrições hipercríticas avaliando todo subgrafo com 9 vértices do grafo associado à forma inteira. Através da busca em profundidade, uma estratégia similar pôde ser usada no reconhecimento do tipo fracamente positiva. Por fim, mostramos que o reconhecimento de formas inteiras pode ser feito através de mutações na matriz de troca relacionada.