Numerical study of regularity in semidefinite programming and applications

Abstract

This 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.

Esta 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.