An Improved Affine-Scaling Interior Point Algorithm for Linear Programming

In this paper, an Improved Affine-Scaling Interior Point Algorithm for Linear Programming has been proposed. Computational results of selected practical problems affirming the proposed algorithm have been provided. The proposed algorithm is accurate, faster and therefore reduces the number of iterations required to obtain an optimal solution of a given Linear Programming problem as compared to the already existing Affine-Scaling Interior Point Algorithm. The algorithm can be very useful for development of faster software packages for solving linear programming problems using the interior-point methods.

A class of polynomial primal-dual interior-point algorithms for semidefinite optimization

In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.

Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.

Superlinear Convergence of Affine Scaling Interior Point Newton Method for Linear Inequality Constrained Minimization without Strict Complementarity

In this paper we extend and improve the classical affine scaling interior-point Newton method for solving nonlinear optimization subject to linear inequality constraints in the absence of the strict complementarity assumption. Introducing a computationally efficient technique and employing an identification function for the definition of the new affine scaling matrix, we propose and analyze a new affine scaling interior-point Newton method which improves the Coleman and Li affine sealing matrix in [2] for solving the linear inequlity constrained optimization. Local superlinear and quadratical convergence of the proposed algorithm is established under the strong second order sufficiency condition without assuming strict complementarity of the solution.

Nash Equilibrium of a Fixed-Sum Two-Player Game

It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems known as PPAD (Polynomial Parity Argument on Directed graphs), for which no polynomial-time solution methods are known, even for two-player games. This paper demonstrates that in fixed-sum two-player games (including zero-sum games), the Nash equilibrium forms a convex set, and has a unique expected payoff. Furthermore, these equilibria are Pareto optimal. Additionally, it is shown that the Nash equilibrium of fixed-sum two-player games can theoretically be found in polynomial time using the principal-dual interior point method, a solution method of linear programming.

Superlinearly Convergent Affine Scaling Interior Trust-Region Method for Linear Constrained LC^1 Minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.

NONMONOTONIC REDUCED PROJECTED HESSIAN METHOD VIA AN AFFINE SCALING INTERIOR MODIFIED GRADIENT PATH FOR BOUNDED-CONSTRAINED OPTIMIZATION

The authors propose an affine scaling modified gradient path method in association with reduced projective Hessian and nonmonotonic interior backtracking line search techniques for solving the linear equality constrained optimization subject to bounds on variables. By employing the QR decomposition of the constraint matrix and the eigensystem decomposition of reduced projective Hes- sian matrix in the subproblem, the authors form affine scaling modified gradient curvilinear path very easily. By using interior backtracking line search technique, each iterate switches to trial step of strict interior feasibility. The global convergence and fast local superlinear/quadratical convergence rates of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.

An Affine Scaling Interior Trust Region Method via Optimal Path for Solving Monotone Variational Inequality Problem with Linear Constraints

Based on a differentiable merit function proposed by Taji et al. in ＂Math. Prog. Stud., 58, 1993, 369-383＂, the authors propose an affine scaling interior trust region strategy via optimal path to modify Newton method for the strictly monotone variational inequality problem subject to linear equality and inequality constraints. By using the eigensystem decomposition and affine scaling mapping, the authors form an affine scaling optimal curvilinear path very easily in order to approximately solve the trust region subproblem. Theoretical analysis is given which shows that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions.

非线性方程组的仿射尺度内点信赖域算法

很多领域研究寻优问题时,所采用的寻优算法普遍存在全局搜索能力差、收敛速度慢的问题,导致求出的解无法达到最优。针对上述问题,研究了一种非线性方程组的仿射尺度内点信赖域算法。构建目标最小化或者目标最大化非线性方程组,并针对方程组设置等式或者不等式约束条件;在约束条件下,利用仿射尺度内点信赖域算法求取非线性方程组最优解;将所研究算法应用到有功优化当中,以线损最小化和电压偏差最小化构建非线性方程组,并为其设置四个约束条件,利用仿射尺度内点信赖域算法求取最优解。实验结果表明:与自适应粒子群算法、樽海鞘群算法以及改进差分灰狼算法相比,所研究算法应用下,线损以及电压偏差均要更小,说明仿射尺度内点信赖域算法的求解结果更优,算法的寻优能力更强。

A Partial First-Order Affine-Scaling Method

We present a partial first-order affine-scaling method for solving smooth optimization with linear inequality constraints. At each iteration, the algorithm considers a subset of the constraints to reduce the complexity. We prove the global convergence of the algorithm for general smooth objective functions, and show it converges at sublinear rate when the objective function is quadratic. Numerical experiments indicate that our algorithm is efficient.

A New Kernel Function Yielding the Best Known Iteration Bounds for Primal-Dual Interior-Point Algorithms

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.

基于非线性优化算法的电力系统状态估计技术研究

海上油田电网的安全运行直接影响着我国海上油气生产企业的稳定运行,通过了解状态估计的功能和研究现状,结合海洋石油生产电网的实际情况,提出了一种基于非线性优化算法的状态估计算法。基于状态估计的基本原理和流程,包括目标函数、约束条件的建立以及原-对偶内点算法的求解,采用了状态估计中不良数据检测与识别的计算方法,通过软件模块程序实现状态估计结果的求解。结合实际算例对比分析,得出了在正常情况下、不检测不良数据情况下、系统分裂运行情况下的状态估计结果与系统状态,为实现电力系统状态估计提供了高可靠性、高可信的数据,为电力系统调度中心电网运行状态分析提供参考。

AN AFFINE SCALING INTERIOR ALGORITHM VIA CONJUGATE GRADIENT PATH FOR SOLVING BOUND-CONSTRAINED NONLINEAR SYSTEMS

In this paper we propose an affine scaling interior algorithm via conjugate gradient path for solving nonlinear equality systems subject to bounds on variables. By employing the affine scaling conjugate gradient path search strategy, we obtain an iterative direction by solving the linearize model. By using the line search technique, we will find an acceptable trial step length along this direction which is strictly feasible and makes the objective func- tion nonmonotonically decreasing. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. Furthermore, the numerical results of the proposed algorithm indicate to be effective.

行阶梯观测矩阵、对偶仿射尺度内点重构算法下的语音压缩感知

基于语音信号在离散余弦域上的近似稀疏性,针对采用随机高斯观测矩阵及线性规划方法进行语音压缩感知与重构时,重构零(近似零)系数定位能力差而导致重构效果不好的缺点,本文提出一种新的行阶梯矩阵做观测矩阵,用对偶仿射尺度内点重构算法对语音进行压缩感知与重构,并对该算法下的重构性能进行理论分析.语音压缩感知仿真结果表明,在离散余弦基下,压缩比(观测序列与原始序列样值数之比)为1∶4时,行阶梯观测矩阵下的平均重构信噪比比随机高斯观测矩阵下提高9.73dB,平均MOS分比随机高斯观测矩阵下提高1.22分.

基于预测-校正原对偶内点法的无功优化新模型

在有载可调变压器模型中引入虚拟节点,并通过该节点的电压来表示理想变压器对功率、电压的转换关系,由此在直角坐标系中建立了无功优化问题的二阶新模型。该新模型的海森矩阵是精确的常系数矩阵,在内点法迭代过程中只需要计算一次,从而缩短了每次迭代的计算时间。利用AMD算法对内点法修正方程的系数矩阵进行节点优化编号,减少了其LU分解所产生的注入元。通过存储海森矩阵的非零元素值、其行、列号及对应的拉格朗日乘子编号,提出了一种新的非零元素存储方式,极大地减少了海森矩阵与乘子线性组合的计算量。基于节点数从14到1338的7个测试系统进行了仿真计算,结果验证了所建模型与方法的正确性与有效性。这种建立模型的思想还可以应用到需要计算海森矩阵的动态无功优化、最优潮流以及状态估计等问题的算法中,以提高其计算速度。

一种求解机组组合问题的内点半定规划方法

提出一种基于内点半定规划(semidefinite programming,SDP)直接求解机组组合(unit commitment,UC)问题的新方法。通过引入辅助变量,该方法将原整数变量约束转化为凸二次约束,进而将UC问题转化为半定规划问题,并用现代内点法进行求解。针对计算结果中整数变量存在微小偏差的问题,采用启发式技术进行修正。100机24时段等6个系统的仿真结果表明,所提方法能有效处理机组爬坡约束,具有较快的计算时间,适合于求解大规模的UC问题,是一种有应用前景的方法。

基于内点法消除输电断面过载的实时控制算法

当切除过载线路可能引发相关输电断面连锁跳闸时,应紧急消除线路过负荷,保证输电断面的安全。文中采用原—对偶内点法求解非线性规划得到消除线路过载的控制方案。由于实时控制的快速性需要,引入反向配对技术来避免平衡机越限;为使调整量最小且严重情况下避免切负荷,依据节点对过载线路和接近极限线路的共同作用提出综合灵敏度概念,并根据综合灵敏度确定加、减出力节点;将关键线路的范围从接近极限的线路扩大到包括过载线路所在的输电断面,以最大限度地避免出现新线路过载以减少校验次数,并对参与计算的变量进行筛选和排序。针对CEPRI 36节点系统进行了大量仿真计算,表明所提出的控制算法快速、有效。

电压崩溃临界点的非线性规划模型及算法

对直接求取电压崩溃临界点的零特征根法进行扩展，将临界点计算转化为非线性规划问题，并用预测校正原对偶内点法求解。该方法能够考虑各种不等式约束条件，因而具有较强的鲁棒性。文章还证明了零特征根法事实上是非线性规划法的一个特例。最后通过对ＩＥＥＥ－３０及ＩＥＥＥ－１１８测试系统的仿真计算验证了该模型及算法的有效性。

基于原对偶仿射尺度内点法的电力系统无功优化算法

本文对潮流雅可比矩阵进行变换直接求取灵敏度系数，建立求解无功优化问题的线性规划模型，并提出采用一种有效的方法——原对偶仿射尺度内点法求解线性规划模型。该算法具有多项式时间复杂性。实际系统的计算结果表明，此算法的迭代收敛次数稳定，与系统规模关系不大，在求解大规模系统无功优化问题时，其性能优于具有指数时间复杂性的单纯性法。

基于内点法的含暂态稳定约束的最优潮流计算

建立了含暂态稳定约束的最优潮流的数学模型 ,模型中考虑了多个预想事故。提出了一种基于原—对偶内点法的含暂态稳定约束的最优潮流算法。通过充分开发修正矩阵的稀疏性 ,并在求解时采用稀疏技巧 ,开发出了高性能的计算程序。在日本 6 0 Hz电力网的 1 0机模型系统的优化计算结果表明 ,所提算法不仅具有强大的处理等式约束和不等式约束的能力 ,而且具有良好的收敛性 ,能够有效地解决考虑多个预想事故时的含暂态稳定约束的最优潮流问题。