The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are Ax b, x > 0 ), then there are two mathematically equivalent forms of the search direction, involving different matrices. One form necessitates factoring a matrix whose sparsity pattern has the same form as that of (A AT). The other form necessitates factoring a matrix whose sparsity pattern has the same form as that of (ATA). Depending on the structure of the matrix A, one of these two forms may produce significantly less fill-in than the other. Furthermore, by analyzing the fill-in of both forms prior to starting the iterative phase of the algorithm, the form with the least fill-in can be computed and used throughout the algorithm. Finally, this methodology can be applied to linear programs that are not in symmetric form, that contain both equality and inequality constraints.

This paper develops a potential reduction algorithm for solving a linear-programming problem directly from a "warm start" initial point that is neither feasible nor optimal. The algorithm is of an "interior point" variety that seeks to reduce a single potential function which simultaneously coerces feasibility improvement (Phase I) and objective value improvement (Phase II). The key feature of the algorithm is the ability to specify beforehand the desired balance between infeasibility and nonoptimality in the following sense. Given a prespecified balancing parameter /3 > 0, the algorithm maintains the following Phase I - Phase II "/3-balancing constraint" throughout: (cTx- Z*) < /3TX, where cTx is the objective function, z* is the (unknown) optimal objective value of the linear program, and Tx measures the infeasibility of the current iterate x. This balancing constraint can be used to either emphasize rapid attainment of feasibility (set large) at the possible expense of good objective function values or to emphasize rapid attainment of good objective values (set /3 small) at the possible expense of a lower infeasibility gap. The algorithm exhibits the following advantageous features: (i) the iterate solutions monotonically decrease the infeasibility measure, (ii) the iterate solutions satisy the /3-balancing constraint, (iii) the iterate solutions achieve constant improvement in both Phase I and Phase II in O(n) iterations, (iv) there is always a possibility of finite termination of the Phase I problem, and (v) the algorithm is amenable to acceleration via linesearch of the potential function.

We propose a family of search directions based on primal-dual entropy in the context of interior point methods for linear programming. This new family contains previously proposed search directions in the context of primal-dual entropy. We analyze the new family of search directions by studying their primal-dual affine-scaling and constant-gap centering components. We then design primal-dual interior-point algorithms by utilizing our search directions in a homogeneous and self-dual framework. We present iteration complexity analysis of our algorithms and provide the results of computational experiments on NETLIB problems.

We propose a family of search directions based on primal-dual entropy in the context of interior point methods for linear programming. This new family contains previously proposed search directions in the context of primal-dual entropy. We analyze the new family of search directions by studying their primal-dual affine-scaling and constant-gap centering components. We then design primal-dual interior-point algorithms by utilizing our search directions in a homogeneous and self-dual framework. We present iteration complexity analysis of our algorithms and provide the results of computational experiments on NETLIB problems.

The ¡§Congestion Management¡¨ (CM) always has been an outstanding and major problem in power system operation. To solve this problem, experts compose solutions in a wide variety. This thesis, based on the equivalent current, applies the Equivalent Current Injection (ECI) concept and circuit parameters to derive the Power Flow Tracing Method (PFTM) . By means of this method we can get a Sensitive Matrix (SM), which is also called the Contribution Matrix (CM), to show the linear relationship between the input power and tidal current discharge of each generator set, with the linear relationship we can derive the mathematic model of treating the congestion problem discussed in this thesis. Combining the Predictor-Corrector Interior Point Algorithm (PCIPA), we can manipulate the change of each generator set in the prospective of solving the congestion problem resulting from the system contingency (SC). The thesis performed various simulations for the IEEE 30 Bus system. Regarding the power contingencies, the solutions of the power-congestion problems can be resulted from the following incidents: heavy load addition, transmission line tripped, generator malfunction as well as the multi-contingencies, etc., which can all be solved with solutions within reasonably restricted domains. We can thus verify the effectiveness of the method .

With the deregulation of power industry and the market competition, low cost, reliable power supply, and secured system operations are major concerns of the advanced deregulation markets. Power system protection is important for service reliability and quality assurance. To reduce the outage duration and promptly restore power services, fault section estimate has to be done effectively and accurately with fault alarms. First, an operational strategy for secondary power system restoration using Modified Grey Relational Analysis (MGRA) is proposed. The Restoration Scheme (RS) can be divided into three steps involving fault section determination, recovering process, and voltage correction process. Three GRAs are incorporated to design the overall restoration scheme. The first GRA uses network switching status to identify the fault. The second GRA combines switching states and load levels for network recovery. The third GRA uses capacitor bank control to support bus voltages. For security operation of restoration scheme, an Equivalent Current Injection (ECI) based hybrid current-power Optimal Power Flow (OPF) model with Predictor-Corrector Interior Point Algorithm (PCIPA) is used to verify the proposed scheme by off-line analysis to confirm a secure overall network operation including load-power balance, power generation limits, voltage limits, and power flow limits. The proposed method can further decompose into two sub-problems. Computer simulations were conducted with an IEEE 30-bus power system to show the effectiveness of the proposed restoration scheme and the PCIPA technique is very accurate, robust, and efficient for the modified OPF solution.