[pt] Otimização Robusta é uma das formas mais comuns de considerar in- certeza nos parâmetros de um problema de otimização. A forma tradicional de achar soluções robustas consiste em resolver a contraparte robusta de um problema, o que em muitos casos, na prática, pode ter um custo computacional proibitivo. Neste trabalho, estudamos métodos iterativos para resolver problemas de Otimização Convexa Robusta de forma aproximada, que não exigem a formulação da contraparte robusta. Utilizamos conceitos de Online Learning para propor um novo algoritmo que utiliza agregação de restrições, demonstrando garantias teóricas de convergência. Desenvolvemos ainda uma modificação deste algoritmo que, apesar de não possuir tais garantias, obtém melhor performance prática. Por fim, implementamos outros métodos iterativos conhecidos da literatura de Otimização Robusta e fazemos uma análise computacional de seus desempenhos. / [en] Robust Optimization is a common paradigm to consider uncertainty in the parameters of an optimization problem. The traditional way to find robust solutions requires solving the robust counterpart of an optimiza- tion problem, which, in practice, can often be prohibitively costly. In this work, we study iterative methods to approximately solve Robust Convex Optimization problems, which do not require solving the robust counter- part. We use concepts from the Online Learning framework to propose a new algorithm that performs constraint aggregation, and we demonstrate theoretical convergence guarantees. We then develop a modification of this algorithm that, although without such guarantees, obtains better practical performance. Finally, we implement other classical iterative methods from the Robust Optimization literature and present a computational study of their performances.

[pt] Diversos problemas em engenharia, aprendizado de máquina e economia podem ser resolvidos através de Programação Semidefinida (SDP). Potenciais aplicações podem ser encontradas em telecomunicações, fluxo de potência e teoria dos jogos. Além disso, como SDP é uma subclasse de otimização convexa, temos uma série de propriedades e garantias que fazem da SDP uma tecnologia muito poderosa. Entretanto, dentre as diferentes subclasses de otimização convexa, SDP ainda permanece como uma das mais desafiadoras. Instancias de larga escala ainda não podem ser resolvidas pelos atuais softwares disponíveis. Nesse sentido, esta tese porpõe um novo algoritmo para resolver problemas de SDP. A principal contribuição deste novo algoritmo é explorar a propriedade de posto baixo presente em diversas instancias. A convergência desta nova metodologia é provada ao mostrar que o algoritmo proposto é um caso particular do Approximate Proximal Point Algorithm. Adicionalmente, as variáveis ótimas duais são disponibilizadas como uma consequência do algoritmo proposto. Além disso, disponibilizamos um software para resolver problemas de SDP, chamado ProxSDP. Três estudos de caso são utilizados para avaliar a performance do algoritmo proposto. / [en] Many problems of interest can be solved by means of Semidefinite Programming (SDP). The potential applications range from telecommunications, electrical power systems, game theory and many more fields. Additionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not efficiently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribution of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[pt] A geração de malhas geomecânicas de reservatórios ainda é uma tarefa tediosa que consome muito tempo. Para acelerar este processo, soluções que reconstroem analiticamente a geometria do reservatório têm sido propostas, mas essas soluções não são as mais adequadas para modelagem de objetos naturais. Este trabalho propõe uma modelagem discreta para a geometria do reservatório, onde os vértices da malha são posicionados por meio da solução de um problema de otimização quadrático e convexo. O problema de otimização é modelado de forma a garantir que as malhas geomecânicas de saída sejam suaves e que ao mesmo tempo respeitem as restrições do reservatório e dos horizontes presentes. Além disso, a metodologia proposta permite uma implementação eficiente, paralelizável e de baixo consumo de memória. Casos de teste com milhões de variáveis são apresentados para validar essa abordagem. Finalmente, a metodologia proposta neste trabalho para malhas de geomecânica pode ser naturalmente estendida para a modelagem estrutural de sub-superfícies na interpretação sísmica e de restauração geológica. / [en] Geomechanical mesh generation of complex reservoirs remains a tedious task prone to errors. Recently proposed solutions based on analytical reconstruction of the sub-surfaces are not capable to represent all the geometric details of natural objects. This work proposes a discrete model where the mesh vertices are positioned based on a convex quadratic optimization process. The optimization problem seeks to guarantee smooth meshes that conform with prescribed constraints. The resulting mesh therefore respects, as far as possible, the finite volume mesh of the reservoir pay zone and the existing horizons. Finally, the proposed methodology for Geomechanical meshes can be easily extend to model sub-surfaces present in the structural interpretation and geological restauration.

[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.

[pt] O mercado financeiro é essencial na economia, trazendo estabilidade, acesso a novos tipos de investimentos, e aumentando a capacidade das empresas no acesso ao crédito. A constante busca por reduzir o papel de especialistas humanos na tomada de decisão, visa reduzir o risco inerente as emoções intrínsecas do ser humano, do qual a máquina não compartilha. Como consequência, reduzindo efeitos especulativos no mercado, e aumentando a precisão nas decisões tomadas. Neste trabalho é discutido o problema de seleção de portfólios online, onde um vetor de alocações de ativos é requerido em cada passo. O algoritmo proposto é o multilayer perceptron with side information - MLPi. Este algoritmo utiliza redes neurais para a solução do problema quando o investidor tem acesso a informações futuras sobre o preço dos ativos. Para avaliar o uso da informação lateral na seleção de portfolio, testamos empiricamente o MLPi em contraste com dois algoritmos, um baseline e o estado-da-arte. Como baseline é utilizado o buy-and-hold. O estado-da-arte é o algoritmo online moving average mean reversion proposto por Li e Hoi (2012). Para avaliar a utilização de informação lateral no algoritmo MLPi é definido um benchmark baseado numa solução ótima simples utilizando a informação lateral, mas sem considerar a acurácia da informação futura. Para os experimentos, utilizamos informações a nível de minuto do mercado de ações brasileiro, operados na bolsa de valores B3. É simulado um preditor de preço com 7 níveis de acurácia diferentes para 200 portfólios. Os resultados apontam que tanto o benchmark quanto o MLPi superam os dois algoritmos selecionados, para níveis de acurácia de um ativo maiores que 50 por cento, e na média, o MLPi supera o benchmark em todos os níveis de acurácia simulados. / [en] The financial market is essential in the economy, bringing stability, access to new types of investments, and increasing the ability of companies to access credit. The constant search for reducing the role of human specialists in decision making aims to reduce the risk inherent in the intrinsic emotions of the human being, which the machine does not share. As a consequence, reducing speculative effects in the market, and increasing the precision in the decisions taken. In this paper, we discuss the problem of selecting portfolios online, where a vector of asset allocations is required in each step. The proposed algorithm is the multilayer perceptron with side information - MLPi. This algorithm uses neural networks to solve the problem when the investor has access to future information on the price of the assets. To evaluate the use of side information in portfolio selection, we empirically tested MLPi in contrast to two algorithms, a baseline and the state-of-the-art. As a baseline, buy-andhold is used. The state-of-the-art is the online moving average mean reversion algorithm proposed by Li and Hoi (2012). To evaluate the use of side information in the algorithm MLPi a benchmark based on a simple optimal solution using the side information is defined, but without considering the accuracy of the future information. For the experiments, we use minute-level information from the Brazilian stock market, traded on the B3 stock exchange. A price predictor is simulated with 7 different accuracy levels for 200 portfolios. The results show that both the benchmark and MLPi outperform the two algorithms selected, for asset accuracy levels greater than 50 percent, and on average, MLPi outperforms the benchmark at all levels of simulated accuracy.

[pt] Neste trabalho, quatro métodos projetados especificamente para a estimação de sistemas esparsos são originalmente elaborados e apresentados. São eles: Encolhimentos Sucessivos, Expansões Sucessivas, Minimização da Norma l1 e Ajuste Automático do fator de regularização do Custo LS. Os quatro métodos propostos baseiam-se na técnica de estimação de sistemas lineares e invariantes no tempo pelo critério dos mínimos quadrados, universalmente conhecida por sua denominação em inglês - Least Squares (LS) Estimation, e incorporam técnicas relacionadas a otimização convexa e à teoria de compressive sensing. Os resultados obtidos em simulações mostram que os métodos em questão têm desempenho superior que a estimação LS convencional e que o algoritmo Recursive Least Squares (RLS) com regularização convexa denominado l1-RLS, em muitos casos alcançando o desempenho ótimo apresentado pelo método de estimação LS Oráculo, no qual o suporte da resposta ao impulso em tempo discreto do sistema estimado é conhecido a priori. Além disso, os métodos propostos apresentam custo computacional menor que do algoritmo l1-RLS. / [en] In this thesis, four methods specifically designed for sparse systems estimation are originally developed and presented, which were called here: Relaxations method, Successive Expansions method, l1-norm Minimization method and Automatic Adjustment of the Regularization Factor method. The four proposed methods are based on the Least Squares (LS) Estimation method and incorporate techniques related to convex optimization and to the theory of compressive sensing. The simulation results show that the proposed methods herein present superior performance than the ordinary LS estimation method and the Recursive Least Squares (RLS) with convex regularization method (l1-RLS), in many cases achieving the same optimal performance presented by the LS Oracle method. Furthermore, the proposed methods demand lower computational cost than the l1-RLS method.