Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/16278
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorTchemisova, Tatianapt
dc.contributor.authorMacedo, Eloísa Catarina Monteiro de Figueiredo Amaral ept
dc.date.accessioned2016-11-14T12:51:52Z-
dc.date.available2016-11-14T12:51:52Z-
dc.date.issued2016-
dc.identifier.urihttp://hdl.handle.net/10773/16278-
dc.descriptionDoutoramento em Matemáticapt
dc.description.abstractThis thesis is devoted to the study of regularity in semidefinite programming (SDP), an important area of convex optimization with a wide range of applications. The duality theory, optimality conditions and methods for SDP rely on certain assumptions of regularity that are not always satisfied. Absence of regularity, i.e., nonregularity, may affect the characterization of optimality of solutions and SDP solvers may run into numerical difficulties, leading to unreliable results. There exist different notions associated to regularity. In this thesis, we study in particular, well-posedness, good behaviour and constraint qualifications (CQs), as well as relations among them. A widely used CQ in SDP is the Slater condition. This condition guarantees that the first order necessary optimality conditions in the Karush-Kuhn-Tucker formulation are satisfied. Current SDP solvers do not check if a problem satisfies the Slater condition, but work assuming its fulfilment. We develop and implement in MATLAB numerical procedures to verify if a given SDP problem is regular in terms of the Slater condition and to determine the irregularity degree in the case of nonregularity. Numerical experiments presented in this work show that the proposed procedures are quite effcient and confirm the obtained conclusions about the relationship between the Slater condition and other regularity notions. Other contribution of the thesis consists in the development and MATLAB implementation of an algorithm for generating nonregular SDP problems with a desired irregularity degree. The database of nonregular problems constructed using this generator is publicly available and can be used for testing new SDP methods and solvers. Another contribution of this thesis is concerned with an SDP application to data analysis. We consider a nonlinear SDP model and linear SDP relaxations for clustering problems and study their regularity. We show that the nonlinear SDP model is nonregular, while its relaxations are regular. We suggest a SDP-based algorithm for solving clustering and dimensionality reduction problems and implement it in R. Numerical tests on various real-life data sets confirm the fastness and efficiency of this numerical procedure.pt
dc.description.abstractEsta tese _e dedicada ao estudo de regularidade em programação semidefinida (SDP - semidefinite programming), uma importante área da optimização convexa com uma vasta gama de aplicações. A teoria de dualidade, condições de optimalidade e métodos para SDP assentam em certos pressupostos de regularidade que nem sempre são satisfeitos. A ausência de regularidade, isto é, não regularidade, pode afetar a caracterização da optimalidade de soluções e os solvers podem apresentar dificuldades numéricas, conduzindo a resultados pouco fiáveis. Existem diferentes noções associadas a regularidade. Nesta tese, estudamos em particular, os conceitos de problemas bem-postos, bem comportados e condições de qualificação de restrições (CQ - constraint qualifications), bem como as relações entre eles. Uma das CQs mais utilizadas em SDP é a condição de Slater. Esta condição garante que as condições de optimalidade de primeira ordem, conhecidas como condições de Karush-Kuhn-Tucker, estão satisfeitas. Os solvers atuais não verificam se um problema a resolver satisfaz a condição de Slater, mas trabalham nesse pressuposto. Desenvolvemos e implementamos em MATLAB procedimentos numéricos para verificar se um dado problema de SDP é regular em termos da condição de Slater e determinar o grau de irregularidade no caso de problemas não regulares. Os resultados das experiências numéricas apresentados neste trabalho mostram que os procedimentos propostos são eficientes e confirmam as conclusões obtidas sobre a relação entre a condição de Slater e outras noções de regularidade. Outra contribuição da tese consiste no desenvolvimento e na implementação em MATLAB de um procedimento numérico para gerar problemas de SDP não regulares com um determinado grau de irregularidade. A colecção de problemas não regulares construídos usando este gerador é de acesso livre e permite testar novos métodos e solvers para SDP. Uma outra contribuição desta tese está relacionada com uma aplicação de SDP em análise de dados. Consideramos um modelo de SDP não linear, bem como as suas relaxações lineares para problemas de clusterização, e estudamos a sua regularidade. Mostramos que o modelo não linear é não regular, enquanto que as suas relaxações são regulares. Sugerimos um algoritmo baseado em modelos de SDP para resolver problemas de clusterização e redução de dimensionalidade, e implementámo-lo em R. Os testes numéricos usando vários conjuntos de dados confirmam a rapidez e eficiência deste procedimento numérico.pt
dc.language.isoengpt
dc.publisherUniversidade de Aveiropt
dc.rightsopenAccesspor
dc.subjectMatemática aplicadapt
dc.subjectProgramação matemáticapt
dc.subjectProgramação semidefinidapt
dc.subject.otherSemidefinite programming (SDP)pt
dc.subject.otherregularitypt
dc.subject.otherconstraint qualifications (CQ)pt
dc.subject.otheroptimality conditionspt
dc.subject.otherdata analysispt
dc.subject.otherclusteringpt
dc.titleNumerical study of regularity in semidefinite programming and applicationspt
dc.title.alternativeEstudo numérico de regularidade em programação semidefinida e aplicaçõespt
dc.typedoctoralThesispt
thesis.degree.leveldoutoramentopt
thesis.degree.grantorUniversidade de Aveiropt
Appears in Collections:UA - Teses de doutoramento
DMat - Teses de doutoramento

Files in This Item:
File Description SizeFormat 
Estudo numérico de regularidade em programação semidefinida e aplicações.pdf1.39 MBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.