Este trabalho propõe uma abordagem que utiliza uma associação dos métodos de barreira modificada e de pontos interiores primal-dual para a resolução do problema de fluxo de potência ótimo (FPO) reativo. Para isso, foi realizado um levantamento bibliográfico que explicitou os conceitos de otimização aplicados ao sistema estático de energia elétrica e os métodos dual-Lagrangiano, Newton-Lagrangiano, primal-dual barreira logarítmica e de barreira modificada. Na abordagem proposta, as restrições canalizadas são desmembradas em duas desigualdades. Estas são transformadas em igualdades a partir do acréscimo de variáveis de folga ou de excesso, as quais são relaxadas e tratadas pela função barreira modificada. Associa-se a esse problema uma função Lagrangiana. O sistema de equações resultantes das condições de estacionaridade da função Lagrangiana foi resolvido pelo método de Newton. Na implementação computacional foram usadas técnicas de esparsidade. Os sistemas elétricos de potência utilizados para verificar a eficiência da abordagem proposta na solução do problema de FPO reativo em três tipos de testes foram o de 3 barras, os do IEEE 14, 30, 118, 162 e 300 barras, o equivalente CESP 440 kV com 53 barras e o equivalente brasileiro sul-sudeste com 787 barras / This work proposes an approach that uses an association of the methods of modified barrier and primal-dual interior points for the resolution of the reactive optimal power flow (OPF) problem. On this purpose, a bibliographical review was accomplished, which enlightened the optimization concepts applied to the static system of electrical energy and the methods dual-Lagrangian, Newton-Lagrangian, primal-dual logarithmic barrier and modified barrier. In this approach, the bounded constraints are transformed in equalities by adding the non-negative slack variables. Those slack variables are relaxed and handled by the modified barrier function. A Lagrangian function is associated to this problem. The equation sets generated by the first-order necessary conditions of the Lagrangian function, were solved by Newton's method. In the computational implementation, sparsity techniques were used. The electric systems used to verify the efficiency of the approach proposed in the solution of the reative OPF problem in three types of tests were of the 3, IEEE 14, 30, 118, 162 and 300 buses, equivalent CESP 440 kV with 53 buses and the equivalent brazilian south-southeast with 787 buses

Este trabalho descreve uma abordagem do método primal-dual barreira logarítmica (MPDBL) associado ao método de Newton modificado para a resolução do problema de fluxo de potência para sistemas de distribuição radial. Também foi realizado um estudo comparativo com duas técnicas clássicas de solução do problema de fluxo potência para redes de distribuição radial. São os métodos: Backward/Forward Sweep e o método proposto por M. Baran e F. Wu, que é baseado na técnica de Newton-Raphson. Este método utiliza uma matriz Jacobiana modificada que atende a característica radial dos sistemas de distribuição. Nos testes comparativos serão considerados todos os parâmetros do sistema. Os algoritmos de solução serão analisados em suas propriedades de convergência e será realizado um teste de robustez. Os resultados dos testes realizados em 4 sistemas (4, 10, 34 e 70 barras) e o teste comparativo entre os métodos evidenciam a melhor metodologia na solução do problema de fluxo de potência para sistemas radiais / This work describes an approach on primal-dual logarithmic barrier method (PDLBM) associate to the method of Newton modified for the resolution of the problem of power flow for radial distribution systems. Also a comparative study with two classic techniques of solution of the flow problem was carried through power for nets of radial distribution. They are the methods: Backward/Forward Sweep and the method considered for M. Baran and F. Wu, that is based on the technique of Newton-Raphson. This method uses modified Jacobiana matrix that takes care of the radial characteristic of the distribution systems. In the comparative tests all will be considered the parameters of the system. The solution algorithms will be analyzed in its properties of convergence and will be carried through a robustness test. The results of the tests carried through in 4 systems (4, 10, 34 and 70 bus) and the comparative test between the methods evidence the best methodology in the solution of the problem of power flow for radial systems

Este trabalho apresenta uma abordagem do método da função barreira logarítmica (MFBL) para a resolução do problema de fluxo de potência ótimo (FPO). A pesquisa fundamenta-se metodologicamente na função barreira logarítmica e nas condições de primeira ordem de Karush-Kuhn-Tucker (KKT). Para a solução do sistema de equações resultantes das condições de estacionaridade, da função Lagrangiana, utiliza-se o método de Newton. Na implementação computacional utiliza-se técnicas de esparsidade. Através dos resultados numéricos dos testes realizados em 5 sistemas (3, 8, 14, 30 e 118 barras) evidencia-se o potencial desta metodologia na solução do problema de FPO. / This work describes an approach on logarithmic barrier function method to solving the optimal power flow (OPF) problem. Search was based on the logarithmic barrier function and first order conditions of Karush-Kuhn-Tucker (KKT). To solve the equation system, obtained from the stationary conditions of the Lagrangian function, is used the Newton method. Implementation is performed using sparsity techniques. The numerical results, carried out in five systems (3, 8, 14, 30 and 118 bus), demonstrate the reliability of this approach in the solution OPF problem.

Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.

We report a Hessian-implicit optimization method to quickly solve the charge optimization problem over protein molecules: given a ligand and its complex with a receptor, determine the ligand charge distribution that minimizes the electrostatic free energy of binding. The new optimization couples boundary element method (BEM) and primal-dual interior point method (PDIPM); initial results suggest that the method scales much better than the previous methods. The quadratic objective function is the electrostatic free energy of binding where the Hessian matrix serves as an operator that maps the charge to the potential. The unknowns are the charge values at the charge points, and they are limited by equality and inequality constraints that model physical considerations, i.e. conservation of charge. In the previous approaches, finite-difference method is used to model the Hessian matrix, which requires significant computational effort to remove grid-based inaccuracies. In the novel approach, BEM is used instead, with precorrected FFT (pFFT) acceleration to compute the potential induced by the charges. This part will be explained in detail by Shihhsien Kuo in another talk. Even though the Hessian matrix can be calculated an order faster than the previous approaches, still it is quite expensive to find it explicitly. Instead, the KKT condition is solved by a PDIPM, and a Krylov based iterative solver is used to find the Newton direction at each step. Hence, only Hessian times a vector is necessary, which can be evaluated quickly using pFFT. The new method with proper preconditioning solves a 500 variable problem nearly 10 times faster than the techniques that must find a Hessian matrix explicitly. Furthermore, the algorithm scales nicely due to the robustness in number of IPM iterations to the size of the problem. The significant reduction in cost allows the analysis of much larger molecular system than those could be solved in a reasonable time using the previous methods. / Singapore-MIT Alliance (SMA)

This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments. The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct. In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints. The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case. The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming. <b>Keywords:</b>Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path. <b>Mathematics Subject Classification (2000):</b>Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.

After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems.

In this document, we study the nonnegative least squares primal-dual method for solving linear programming problems. In particular, we investigate connections between this primal-dual method and the classical Hungarian method for the assignment problem. Firstly, we devise a fast procedure for computing the unrestricted least squares solution of a bipartite matching problem by exploiting the special structure of the incidence matrix of a bipartite graph. Moreover, we explain how to extract a solution for the cardinality matching problem from the nonnegative least squares solution. We also give an efficient procedure for solving the cardinality matching problem on general graphs using the nonnegative least squares approach. Next we look into some theoretical results concerning the minimization of p-norms, and separable differentiable convex functions, subject to linear constraints described by node-arc incidence matrices for graphs. Our main result is the reduction of the assignment problem to a single nonnegative least squares problem. This means that the primal-dual approach can be made to converge in one step for the assignment problem. This method does not reduce the primal-dual approach to one step for general linear programming problems, but it appears to give a good starting dual feasible point for the general problem.

<p>This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments.</p><p>The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct.</p><p>In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints.</p><p>The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case.</p><p>The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming.</p><p><b>Keywords:</b>Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path.</p><p><b>Mathematics Subject Classification (2000):</b>Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.</p>

After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems.