In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam características que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cíclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais. / Real world problemas in areas such as machine learning are known for the huge number of decision variables (> 10^6) and data volume. For such problems working with second order derivatives is prohibitive. These problems have properties that benefits the application of coordinate descent/minimization methods. These kind of methods are defined by the change of a single, or small number of, decision variable at each iteration. In the literature, the commonly found description of this type of method is based on the cyclic change of variables. Recent papers have shown that randomized versions of this method have better convergence properties. This version is based on the change of a single variable chosen randomly at each iteration, based on a fixed, but not necessarily uniform, distribution. In this work we present some theoretical aspects of such methods, but we focus on practical aspects.

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam características que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cíclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais. / Real world problemas in areas such as machine learning are known for the huge number of decision variables (> 10^6) and data volume. For such problems working with second order derivatives is prohibitive. These problems have properties that benefits the application of coordinate descent/minimization methods. These kind of methods are defined by the change of a single, or small number of, decision variable at each iteration. In the literature, the commonly found description of this type of method is based on the cyclic change of variables. Recent papers have shown that randomized versions of this method have better convergence properties. This version is based on the change of a single variable chosen randomly at each iteration, based on a fixed, but not necessarily uniform, distribution. In this work we present some theoretical aspects of such methods, but we focus on practical aspects.

Submitted by Guilherme Atem (guiatem@gmail.com) on 2013-03-19T16:02:06Z No. of bitstreams: 1 Dissertação - Guilherme Atem.pdf: 2045602 bytes, checksum: 3d2427a0fdd1376baf5c274252a390a2 (MD5) / Approved for entry into archive by Suzinei Teles Garcia Garcia (suzinei.garcia@fgv.br) on 2013-03-19T16:04:40Z (GMT) No. of bitstreams: 1 Dissertação - Guilherme Atem.pdf: 2045602 bytes, checksum: 3d2427a0fdd1376baf5c274252a390a2 (MD5) / Made available in DSpace on 2013-03-19T16:24:11Z (GMT). No. of bitstreams: 1 Dissertação - Guilherme Atem.pdf: 2045602 bytes, checksum: 3d2427a0fdd1376baf5c274252a390a2 (MD5) Previous issue date: 2013-02-05 / Neste trabalho, comparamos algumas aplicações obtidas ao se utilizar os conhecimentos subjetivos do investidor para a obtenção de alocações de portfólio ótimas, de acordo com o modelo bayesiano de Black-Litterman e sua generalização feita por Pezier e Meucci. Utilizamos como medida de satisfação do investidor as funções utilidade correspondentes a um investidor disciplinado, isto é, que é puramente averso a risco, e outro que procura risco quando os resultados são favoráveis. Aplicamos o modelo a duas carteiras de ações que compõem o índice Ibovespa, uma que replica a composição do índice e outra composta por pares de posições long&short de ações ordinárias e preferenciais. Para efeito de validação, utilizamos uma análise com dados fora da amostra, dividindo os dados em períodos iguais e revezando o conjunto de treinamento. Como resultado, foi possível concluir que: i) o modelo de Black-Litterman não é suficiente para contornar as soluções de canto quando o investidor não é disciplinado, ao menos para o modelo utilizado; ii) para um investidor disciplinado, o P&L médio obtido pelos modelos de média-variância e de Black-Litterman é consideravelmente superior ao do benchmark para as duas carteiras; iii) o modelo de Black Litterman somente foi superior ao de média-variância quando a visão do investidor previu bem os resultados do mercado. / On this work, we compare results obtained when the investor chooses to use his subjective views on the market to calculate the allocation optimization of a given portfolio, according to the bayesian model of Black-Litterman (BLACK; LITTERMAN, 1992) and the generelization provided by Pezier (PEZIER, 2007) and Meucci (MEUCCI, 2008). As a measure of satisfaction of the investor, we use utility functions describing an investor with discipline that is always risk-averse and other function for an investor who seeks risk when the results are favourable. The model is applied to two portfolios consisting of stock from the Ibovespa index: one of them consists of all stocks from the index, with time horizon of half an year, and the other presents four long short positions betwen ordinary and preferential stocks and time horizon of one month. The results are validated with out of sample data, according to a 10-fold cross validation. As a result, we conclude that: i) the Black-Litterman model may not be enougth to avoid corner solutions when the investor has no discipline, according to our model; ii) both the Black-Litterman and the Mean-Variance models perform better then the benchmarks; iii) but the winner model depends on the forecast power of the investor views.