Nonlinear programming is a very important tool for optimizing many systems in science and engineering. The interior point solver IPOPT has become one of the most popular solvers for NLP because of its high performance. However, certain types of problems are still challenging for IPOPT. This dissertation considers three improvements or extensions to IPOPT to improve performance on several practical classes of problems. Compared to active set solvers that treat inequalities by identifying active constraints and transforming to equalities, the interior point method is less robust in the presence of degenerate constraints. Interior point methods require certain regularity conditions on the constraint set for the solution path to exist. Dependent constraints commonly appear in applications such as chemical process models and violate the regularity conditions. The interior point solver IPOPT introduces regularization terms to attempt to correct this, but in some cases the required regularization terms either too large or too small and the solver will fail. To deal with these challenges, we present a new structured regularization algorithm, which is able to numerically delete dependent equalities in the KKT matrix. Numerical experiments on hundreds of modified example problems show the effectiveness of this approach with average reduction of more than 50% of the iterations. In some contexts such as online optimization, very fast solutions of an NLP are very important. To improve the performance of IPOPT, it is best to take advantage of problem structure. Dynamic optimization problems are often called online in a control or stateestimation. These problems are very large and have a particular sparse structure. This work investigates the use of parallelization to speed up the NLP solution. Because the KKT factorization is the most expensive step in IPOPT, this is the most important step to parallelize. Several cyclic reduction algorithms are compared for their performance on generic test matrices as well as matrices of the form found in dynamic optimization. The results show that for very large problems, the KKT matrix factorization time can be improved by a factor of four when using eight processors. Mathematical programs with complementarity constraints (MPCCs) are another challenging class of problems for IPOPT. Several algorithmic modifications are examined to specially handle the difficult complementarity constraints. First, two automatic penalty adjustment approaches are implemented and compared. Next, the use of our structured regularization is tested in combination with the equality reformulation of MPCCs. Then, we propose an altered equality reformulation of MPCCs which effectively removes the degenerate equality or inequality constraints. Using the MacMPEC test library and two applications, we compare the efficiency of our approaches to previous NLP reformulation strategies.

The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and analysis. Our computational results indicate that 72% of the NETLIB suite problem instances are ill-conditioned. However, after pre-processing heuristics are applied, only 19% of the post-processed problem instances are ill-conditioned, and log C(d) of the finitely-conditioned post-processed problems is fairly nicely distributed. We also show that the number of IPM iterations needed to solve the problems in the NETLIB suite varies roughly linearly (and monotonically) with log C(d) of the post-processed problem instances. Empirical evidence yields a positive linear relationship between IPM iterations and log C(d) for the post-processed problem instances, significant at the 95% confidence level. Furthermore, 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the problem instances after pre-processin

In each iteration of the interior point method (IPM) at least one linear system has to be solved. The main computational effort of IPMs consists in the computation of these linear systems. Solving the corresponding linear systems with a direct method becomes very expensive for large scale problems. In this thesis, we have been concerned with using an iterative method for solving the reduced KKT systems arising in IPMs for linear programming. The augmented system form of this linear system has a number of advantages, notably a higher degree of sparsity than the normal equations form. We design a block triangular preconditioner for this system which is constructed by using a nonsingular basis matrix identified from an estimate of the optimal partition in the linear program. We use the preconditioned conjugate gradients (PCG) method to solve the augmented system. Although the augmented system is indefinite, short recurrence iterative methods such as PCG can be applied to indefinite system in certain situations. This approach has been implemented within the HOPDM interior point solver. The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of IPM for this inexact case. We present the convergence analysis of the inexact infeasible path-following algorithm, prove the global convergence of this method and provide complexity analysis.

In the present work we study Interior Point Algorithm used for solving linear problems

We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points al,...,am C Rn . This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it has been the subject of much theoretical complexity analysis. Here we focus on computation. We present a combined interior-point and active-set method for solving this problem. Our computational results demonstrate that our method solves very large problem instances (m = 30, 000 and n = 30) to a high degree of accuracy in under 30 seconds on a personal computer.

We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the correlation between these measures and IPM iteration counts (solved using the software SDPT3) when the measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.896), and is a very good predictor of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations.

Optimal design problems aim at selecting design points optimally with respect to certain statistical criteria. The research of this thesis focuses on optimal design problems with respect to A-, D- and E-optimal criteria, which minimize the trace, determinant and largest eigenvalue of the information matrix, respectively. Semide nite programming (SDP) is concerned with optimizing a linear objective function subject to a linear matrix being positive semide nite. Two powerful MATLAB add-ons, SeDuMi and CVX, have been developed to solve SDP problems e ciently. In this paper, we show in detail how to formulate A- and E-optimal design problems as SDP problems and solve them by SeDuMi and CVX. This technique can be used to construct approximate A-optimal and E-optimal designs for all linear and non-linear models with discrete design spaces. The results can also provide guidance to nd optimal designs on continuous design spaces. For one variable polynomial regression models, we solve the A- and E- optimal designs on the continuous design space by using a two-stage procedure. In the rst stage we nd the optimal moments by casting it as an SDP problem and in the second stage we extract the optimal designs from the optimal moments obtained from the rst stage. Unlike E- and A-optimal design problems, the objective function of D-optimal design problem is nonlinear. So D-optimal design problems cannot be reformulated as an SDP. However, it can be cast as a convex problem and solved by an interior point method. In this thesis we give details on how to use the interior point method to solve D-optimal design problems. Finally several numerical examples for A-, D-, and E-optimal designs along with the MATLAB codes are presented. / Graduate

The continuous growth in power system electric grid by adding new substations lead to construct many new transmission lines, transformers, control devices, and circuit breakers to connect the capacity (generators) to the demand (loads). These components will have a very heavy influence on the performance of the electric grid. The renewable technical solutions for these issues can be found by robust algorithms which can give us a full picture of the current state of the electrical network by monitoring the behavior of phase and voltage magnitude. In this thesis, the major idea is to implement several algorithms including weighted least square, extend kalman filter, and interior point method in three different electrical networks including IEEE 14, 30, and 118 to compare the performance of these algorithms which is represented by the behavior of phases and magnitude voltages as well as minimize the residual of the balance load flow real time measurements to distinguish which one is more robust. Also to have a particular understanding of the comparison between unconstraint and constraint algorithms.

Optimization methods nowadays play a very important role in financial decisions such as portfolio managements, construction of index funds and pension funds.  This Master Thesis is devoted to the problem of an index fund construction. The problem is represented as a linear optimization problem of re-balancing the portfolio at minimum cost and solved using the Primal-Dual interior point method. The index fund is constructed using ten companies from the Dow Jones Industrial Average Index (DJIA). The Primal-Dual interior point method was first implemented in Matlab and later on in Java.

Orientador: Antonio Roberto Balbo / Banca: Aparecido Nilceu Marana / Banca: Helenice de Oliveira F. Silva / Resumo: O Brasil é o maior produtor de cana-de-açúcar do mundo. Mas, existe uma grande preocupação com o sistema de colheita utilizado nesta cultura, pois é prática comum a colheita manual com a pré-queima do palhiço. Autoridades brasileiras têm aprovado leis proibindo a queimada nos canaviais. Entretanto, a colheita mecanizada, com cana-de-açúcar crua, cria novos problemas com a permanência do resíduo no solo. Assim, muitos estudos têm sido propostos para o uso deste resíduo para geração de energia. A maior dificuldade no uso desta biomassa está no custo de coletar e transferir o resíduo, do campo para o centro de processamento. Para análise da viabilidade deste sistema há a necessidade de um estudo do balanço de energia envolvido, devido ao grande número de maquinário utilizado no processo. O objetivo deste trabalho é investigar modelos matemáticos que auxiliem na escolha das variedades de cana-de-açúcar a serem implantadas, de forma a minimizar o custo de coleta da biomassa residual e avaliar o balanço de energia gerado, adicionado restrições sobre a produção de sacarose e limitações da área para plantio e considerando as distâncias entre os talhões e o centro de processamento. Para isto, técnicas de programação linear e inteira 0-1 foram utilizadas. A busca de soluções para problemas de programação inteira com grande número de variáveis e restrições é de difícil resolução, mas os resultados apresentados mostram que a utilização d eum procedimento híbrido envolvendo o método Primal-Dual de Pontos Interiores e o método Branch and Bound promove uma boa performance computacional, apresentando soluções confiáveis. Assim, o uso deste procedimento é viável para o auxílio na seleção de variedades, otimizando o custo do uso da biomassa residual de colheita ou o balanço de geração de energia / Abstract: It is that Brazil is the world's largest sugar cane producer. But there is great concern about the harvesting system used in this culture, because it is a common practice to burn the straw before the barvest. Brazilian authorities have approved laws prohibiting the burning in the sugar cane fields. However, with mechanized harvesting of sugar cane raw creates new problems with the accumulation of the waste biomass in the ground. Many studies have been proposed to use this waste for energy generation. The greatest difficulty to use this biomass is in the cost of collect and transfer the residues from the field to the the processing center. To analyze the feasibility of this system, it is necessary a study of the involved energy balance, because of the large number of machines in the process. The aim of this study is to investigate mathematical models that help on choosing varieties of sugar cane to be planted, to minimize the cost of collect of residual biomass and to analyze the balance of power generated, adding restrictions on the production on the production of sucrose and limitations on the area for planting and considering the distances among the plots the processing center. To this, techniques of 0-1 integer linear programming were used. The search for solutions to integer programming problems with many variables and constraints its very hard, but the results show that the use of a hybrid procedure involving the Primal-Dual Interior Point method and Branch and Bound method promotes good performance computing, with reliable solutions. Thus, the use of this procedure is feasible to help on select of varieties, optimizing the cost of collect of the waste biomass or the the balance of power generation / Mestre