Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We study the preconditioning of symmetric indefinite linear systems of equations that arise in interior point solution of linear optimization problems. The preconditioning method that we study exploits the block structure of the augmented matrix to design a similar block structure preconditioner to improve the spectral properties of the resulting preconditioned matrix so as to improve the convergence rate of the iterative solution of the system. We also propose a two-phase algorithm that takes advantage of the spectral properties of the transformed matrix to solve for the Newton directions in the interior-point method. Numerical experiments have been performed on some LP test problems in the NETLIB suite to demonstrate the potential of the preconditioning method discussed.

Short term hydroelectric scheduling combining network flow and interior point approaches

In this paper, short term hydroelectric scheduling is formulated as a network flow optimization model and solved by interior point methods. The primal-dual and predictor-corrector versions of such interior point methods are developed and the resulting matrix structure is explored. This structure leads to very fast iterations since it avoids computation and factorization of impedance matrices. For each time interval, the linear algebra reduces to the solution of two linear systems, either to the number of buses or to the number of independent loops. Either matrix is invariant and can be factored off-line. As a consequence of such matrix manipulations, a linear system which changes at each iteration has to be solved, although its size is reduced to the number of generating units and is not a function of time intervals. These methods were applied to IEEE and Brazilian power systems, and numerical results were obtained using a MATLAB implementation. Both interior point methods proved to be robust and achieved fast convergence for all instances tested. (C) 2004 Elsevier Ltd. All rights reserved.

An adaptation of the dual-affine interior point method for the surface flatness problem

This paper presents an adaptation of the dual-affine interior point method for the surface flatness problem. In order to determine how flat a surface is, one should find two parallel planes so that the surface is between them and they are as close together as possible. This problem is equivalent to the problem of solving inconsistent linear systems in terms of Tchebyshev's norm. An algorithm is proposed and results are presented and compared with others published in the literature. (C) 2006 Elsevier B.V. All rights reserved.

Using interior point algorithms for the solution of linear programs with special structural features

Linear Programming (LP) is a powerful decision making tool extensively used in various economic and engineering activities. In the early stages the success of LP was mainly due to the efficiency of the simplex method. After the appearance of Karmarkar's paper, the focus of most research was shifted to the field of interior point methods. The present work is concerned with investigating and efficiently implementing the latest techniques in this field taking sparsity into account. The performance of these implementations on different classes of LP problems is reported here. The preconditional conjugate gradient method is one of the most powerful tools for the solution of the least square problem, present in every iteration of all interior point methods. The effect of using different preconditioners on a range of problems with various condition numbers is presented. Decomposition algorithms has been one of the main fields of research in linear programming over the last few years. After reviewing the latest decomposition techniques, three promising methods were chosen the implemented. Sparsity is again a consideration and suggestions have been included to allow improvements when solving problems with these methods. Finally, experimental results on randomly generated data are reported and compared with an interior point method. The efficient implementation of the decomposition methods considered in this study requires the solution of quadratic subproblems. A review of recent work on algorithms for convex quadratic was performed. The most promising algorithms are discussed and implemented taking sparsity into account. The related performance of these algorithms on randomly generated separable and non-separable problems is also reported.

Implementation of an interior point source in the ultra weak variational formulation through source extraction

The Ultra Weak Variational Formulation (UWVF) is a powerful numerical method for the approximation of acoustic, elastic and electromagnetic waves in the time-harmonic regime. The use of Trefftz-type basis functions incorporates the known wave-like behaviour of the solution in the discrete space, allowing large reductions in the required number of degrees of freedom for a given accuracy, when compared to standard finite element methods. However, the UWVF is not well disposed to the accurate approximation of singular sources in the interior of the computational domain. We propose an adjustment to the UWVF for seismic imaging applications, which we call the Source Extraction UWVF. Differing fields are solved for in subdomains around the source, and matched on the inter-domain boundaries. Numerical results are presented for a domain of constant wavenumber and for a domain of varying sound speed in a model used for seismic imaging.

Predictor-Corrector Primal-Dual Interior Point Method for Solving Economic Dispatch Problems: A Postoptimization Analysis

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Interior-exterior point method with global convergence strategy for solving the reactive optimal power flow problem

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Re-examination of one-point methods of liquid limit determination

This Paper deals with the analysis of liquid limit of soils, an inferential parameter of universal acceptance. It has been undertaken primarily to re-examine one-point methods of determination of liquid limit water contents. It has been shown by basic characteristics of soils and associated physico-chemical factors that critical shear strengths at liquid limit water contents arise out of force field equilibrium and are independent of soil type. This leads to the formation of a scientific base for liquid limit determination by one-point methods, which hitherto was formulated purely on statistical analysis of data. Available methods (Norman, 1959; Karlsson, 1961; Clayton & Jukes, 1978) of one-point liquid limit determination have been critically re-examined. A simple one-point cone penetrometer method of computing liquid limit has been suggested and compared with other methods. Experimental data of Sherwood & Ryley (1970) have been employed for comparison of different cone penetration methods. Results indicate that, apart from mere statistical considerations, one-point methods have a strong scientific base on the uniqueness of modified flow line irrespective of soil type. Normalized flow line is obtained by normalization of water contents by liquid limit values thereby nullifying the effects of surface areas and associated physico-chemical factors that are otherwise reflected in different responses at macrolevel.Cet article traite de l'analyse de la limite de liquidité des sols, paramètre déductif universellement accepté. Cette analyse a été entreprise en premier lieu pour ré-examiner les méthodes à un point destinées à la détermination de la teneur en eau à la limite de liquidité. Il a été démontré par les caractéristiques fondamentales de sols et par des facteurs physico-chimiques associés que les résistances critiques à la rupture au cisaillement pour des teneurs en eau à la limite de liquidité résultent de l'équilibre des champs de forces et sont indépendantes du type de sol concerné. On peut donc constituer une base scientifique pour la détermination de la limite de liquidité par des méthodes à un point lesquelles, jusqu'alors, n'avaient été formulées que sur la base d'une analyse statistique des données. Les méthodes dont on dispose (Norman, 1959; Karlsson, 1961; Clayton & Jukes, 1978) pour la détermination de la limite de liquidité à un point font l'objet d'un ré-examen critique. Une simple méthode d'analyse à un point à l'aide d'un pénétromètre à cône pour le calcul de la limite de liquidité a été suggérée et comparée à d'autres méthodes. Les données expérimentales de Sherwood & Ryley (1970) ont été utilisées en vue de comparer différentes méthodes de pénétration par cône. En plus de considérations d'ordre purement statistque, les résultats montrent que les méthodes de détermination à un point constituent une base scientifique solide en raison du caractère unique de la ligne de courant modifiée, quel que soit le type de sol La ligne de courant normalisée est obtenue par la normalisation de la teneur en eau en faisant appel à des valeurs de limite de liquidité pour, de cette manière, annuler les effets des surfaces et des facteurs physico-chimiques associés qui sans cela se manifesteraient dans les différentes réponses au niveau macro.

On the Erdos-Szekeres n-interior point problem

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n-1, every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n-3. In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

On the Erdos-Szekeres n-interior-point problem

The n-interior-point variant of the Erdos Szekeres problem is the following: for every n, n >= 1, does there exist a g(n) such that every point set in the plane with at least g(n) interior points has a convex polygon containing exactly n interior points. The existence of g(n) has been proved only for n <= 3. In this paper, we show that for any fixed r >= 2, and for every n >= 5, every point set having sufficiently large number of interior points and at most r convex layers contains a subset with exactly n interior points. We also consider a relaxation of the notion of convex polygons and show that for every n, n >= 1, any point set with at least n interior points has an almost convex polygon (a simple polygon with at most one concave vertex) that contains exactly n interior points. (C) 2013 Elsevier Ltd. All rights reserved.

Security constrained optimal active power flow via network model and interior point method

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Interior point method for long-term generation scheduling of large-scale hydrothermal systems

This paper presents an interior point method for the long-term generation scheduling of large-scale hydrothermal systems. The problem is formulated as a nonlinear programming one due to the nonlinear representation of hydropower production and thermal fuel cost functions. Sparsity exploitation techniques and an heuristic procedure for computing the interior point method search directions have been developed. Numerical tests in case studies with systems of different dimensions and inflow scenarios have been carried out in order to evaluate the proposed method. Three systems were tested, with the largest being the Brazilian hydropower system with 74 hydro plants distributed in several cascades. Results show that the proposed method is an efficient and robust tool for solving the long-term generation scheduling problem.