线性权互补问题的改进全牛顿步不可行内点算法

权互补问题是指在一个流形与一个锥的交集上找到一向量对,使得这对向量的某代数积等于一个给定的权向量。当权向量为零时,权互补问题退化为互补问题。作为互补问题的非平凡推广,权互补问题可用于求解科学、经济和工程中的诸多均衡问题,且在某些情况下可以产生更高效的算法。考虑非负象限上的一类线性权互补问题,提出了一种改进的全牛顿步不可行内点算法来求其数值解。通过推广线性优化的全牛顿步不可行内点算法,给出了线性权互补问题的扰动问题、中心路径及其诱导的牛顿方向。算法构造了线性权互补问题的一系列扰动问题的严格可行点;每一步主迭代由一个可行步和若干个中心步组成,且都采用全牛顿步,因而无需计算步长;在每一步迭代,算法的可行性残差和权向量残差都以相同比率减少;运用中心步的二次收敛结果,为可行步提供了一个稍宽的邻域。通过分析算法的可行步,中心步和收敛性,得到了算法的全局收敛性和多项式时间复杂度。最后,数值算例验证了算法求解线性权互补问题的有效性。     

线性互补问题的内点算法

互补问题分为线性互补和非线性互补,而线性互补问题是线性规划和二次规划的推广,求解线性互补问题的常用算法有内点算法和外点算法。本文主要研究了线性互补问的一种内点算法：中心路径算法,并给出了基于此算法的最优解的判定算法和收敛性分析。     

求解对称锥互补问题的一种非精确光滑牛顿方法(英文)

本文给出了一种求解对称锥互补问题的非精确光滑牛顿方法,所采用的互补函数是含一个参数且以FB和CHKS为特例的光滑函数.新方法的每步迭代中,都采用非精确牛顿方法求解由原问题产生的子问题.在一定条件下,新算法具有全局收敛和局部超线性收敛的性质.数值试验表明算法对于求解大规模对称锥互补问题是非常有效的.     

复合不可微最优化问题的非单调信赖域方法

对复合不可微最优化问题提出了一种新的非单调信赖域方法。算法在每个迭代点处构造带信赖域约束的二次规划子问题,新的迭代点采用非单调策略产生,在一般的假设条件下证明了算法的全局收敛性。数值试验表明：该算法能在一定程度上克服由非光滑性引起的Ｍａｒａｔｏｓ效应     

复合不可微最优化问题的非单调依赖域方法

对复合不可微最优化问题提出了一种新的非单调信赖域方法,算法在每个迭代点处构造带信域约束的二次规划子问题,新的迭代点采用了非单调策略产生,在一般的假设下证明了算法的全局收敛性,数值试验表明;该算法能在一定程度上克服由非光滑性引起的Ｍａｒａｔｏｓ效应。     

二阶锥规划的非精确不可行内点法

二阶锥规划在工程、控制、金融等领域具有广泛的应用.本文研究一种求解二阶锥规划的非精确不可行内点法.该算法的基本思想是首先定义不可行中心路径及其邻域,然后通过求解一个非线性方程组得到非精确的搜索方向,再取一个合适的步长,使得新的迭代点落在不可行中心路径的邻域内.该算法不要求初始点和迭代点位于严格可行解集内.在适当的假设条件下证明了算法只需迭代O(√n ln(1ε))次就可以找到问题的ε-近似解.     

稳固非扩张映射不动点集处均衡问题的一种不精确次梯度算法（英文）

本文提出了稳固非扩张映射不动点集处均衡问题的一种新算法.该算法要求双函数是连续的,但不一定是单调的.首先,通过事先引入的参数确定一个闭凸集;其次,根据双函数的不精确次梯度在闭凸集上的投影构造中间迭代点;最后,下一个迭代点由当前迭代点和中间迭代点的凸组合在稳固非扩张算子的映射得到.在适当条件下,本文给出了该算法的全局收敛性证明.     

带有线搜索的新的非单调自适应信赖域算法

本文给出了一种新的信赖域算法。该算法以变化的速率来调整信赖域半径的大小。在由信赖域子问题产生的试探步不被接受的情况下,新算法采用线搜索的方法得到下一个迭代点。同时算法采用非单调的技术来加速算法的收敛效果。文中给出了新算法的全局收敛性分析和数值试验的结果。     

一类非光滑最优化问题的非单调Bundle型算法

本文对满足弱半光滑或正则条件的局部Ｌｉｐｓｃｈｉｔｚ函数给出了一种非单调Ｂｕｎｄｌｅ型算法。该算法允许迭代点列对应的函数值序列是非单调下降的。     

一类新的基于信赖域技术的非单调共轭梯度算法

为有效求解大规模无约束优化问题,本文基于信赖域技术和修正拟牛顿方程,同时结合Zhang H. C.策略和Gu N. Z.策略,设计了一种新的非单调共轭梯度算法,应用信赖域技术保证了算法的稳健性和收敛性,并给出了算法的全局收敛性分析．在适当条件下,证明了该算法具有线性收敛性．数值实验表明新算法能够有效求解病态和大规模问题．与单独结合其中一种非单调策略的算法相比,新算法需要较少的迭代次数和运行时间,利用其得到的函数值与最优值更接近．     

A Primal-Dual Interior-Point Method to Solve the Optimal Power Flow Dispatching Problem

This paper presents a primal-dual path-following interior-point method for the solution of the optimal power flow dispatching (OPFD) problem. The underlying idea of most path-following algorithms is relatively similar: starting from the Fiacco-McCormick barrier function, define the central path and loosely follow it to the optimum solution. Several primal-dual methods for OPF have been suggested, all of which are essentially direct extensions of primal-dual methods for linear programming. Nevertheless, there are substantial variations in some crucial details which include the formulation of the non-linear problem, the associated linear system, the linear algebraic procedure to solve this system, the line search, strategies for adjusting the centring parameter, estimating higher order correction terms for the homotopy path, and the treatment of indefiniteness. This paper discusses some of the approaches that were undertaken in implementing a specific primal-dual method for OPFD. A comparison is carried out with previous research on interior-point methods for OPF. Numerical tests on standard IEEE systems and on a realistic network are very encouraging and show that the new algorithm converges where other algorithms fail.     

Second-order cone programming with warm start for elastoplastic analysis with von Mises yield criterion

The incremental problem for quasistatic elastoplastic analysis with the von?Mises yield criterion is discussed within the framework of the second-order cone programming (SOCP). We show that the associated flow rule under the von?Mises yield criterion with the linear isotropic/kinematic hardening is equivalently rewritten as a second-order cone complementarity problem. The minimization problems of the potential energy and the complementary energy for incremental analysis are then formulated as the primal-dual pair of SOCP problems, which can be solved with a primal-dual interior-point method. To enhance numerical performance of tracing an equilibrium path, we propose a warm-start strategy for a primal-dual interior-point method based on the primal-dual penalty method. In this warm-start strategy, we solve a penalized SOCP problem to find the equilibrium solution at the current loading step. An advanced initial point for solving this penalized SOCP problem is defined by using information of the solution at the previous loading step.     

一种新型线性化迭代算法及其在结构优化准则方程组求解中的应用

求解一元非线性方程的埃特金算法是一种线性化自动迭代算法,其每次迭代需要计算两次函数值。将其推广到结构优化非线性准则方程组的迭代求解,可实现结构优化迭代求解的完全自动化。为克服其每次迭代需要两次结构分析的缺点,构造了一种新型线性化迭代解法,称为Atiken Chen算法,该算法利用前次结构分析信息,每次迭代只需一次结构分析,从而大大提高了结构优化迭代计算的效率与自动化程度。算例验证了该算法的可行性和优越性。     

An efficient method for large-scale slack allocation

This article concerns a timing or project graph, with given delays on the edges and given arrival times at the source and sink nodes. The arrival times at the other nodes are to be chosen; these determine the timing slacks, which must be non-negative, on the edges. The set of possible timing slacks is a polyhedron; to choose one, a separable concave utility function, such as the sum of the logarithms of the slacks, is maximized. This slack allocation problem, which can be given a simple statistical interpretation, is convex, and can be solved by a variety of methods. Gradient and coordinate ascent methods are simple and scale to large problems, but can converge slowly, depending on the topology and problem data. The Newton method, in contrast, reliably computes an accurate solution, but typically cannot scale beyond problems with a few thousand nodes. This article describes a custom truncated Newton method that efficiently computes an accurate solution, and scales to large graphs (say, with a million or more nodes). The method typically requires just a few hundred iterations, with each iteration requiring a few passes over the graph; in particular, the method has approximately linear complexity in the size of the problem. The same approach can be used to solve slack allocation problems with constraints, using an interior-point method that relies on the custom truncated Newton approach.     

LFTB: An Efficient Algorithm to Bound Linear Fractional Transformations

This work presents an efficient algorithm to solve a structured semidefinite program (SDP) with important applications in the analysis of uncertain linear systems. The solution to this particular SDP gives an upper bound for the maximum singular value of a multidimensional rational matrix function, or linear fractional transformation, over a box of n real parameters. The proposed algorithm is based on a known method for solving semidefinite programs. The key features of the algorithm are low memory requirements, low cost per iteration, and efficient adaptive rules to update algorithm parameters. Proper utilization of the structure of the semidefinite program under consideration leads to an algorithm that reduced the cost per iteration and memory requirements of existing general-purpose SDP solvers by a factor of O(n). Thus, the algorithm in this paper achieves substantial savings in computing resources for problems with a large number of parameters. Additional savings are obtained when the problem data includes block-circulant matrices as is the case in the analysis of uncertain mechanical structures with spatial symmetry.     

Zonotopes and the LP-Newton method

Although linear programming problems can be solved in polynomial time by the ellipsoid method and interior-point algorithms, there still remains a long-standing open problem of devising a strongly polynomial algorithm for linear programming (or of disproving the existence of such an algorithm). The present work is motivated by an attempt toward solving this problem. Linear programming problems can be formulated in terms of a zonotope, a kind of greedy polyhedron, on which linear optimization is made easily. We propose a method, called the LP-Newton method, for linear programming that is based on the zonotope formulation and the minimum-norm-point algorithm of Philip Wolfe. The LP-Newton method is a finite algorithm even for real-number input data with exact arithmetic computations. We show some preliminary computational results to examine the behavior of the LP-Newton method. Major part of this paper was presented as a plenary talk with the same title at ICOTA7 (December 12–15, 2007, Kobe, Japan) by the first author. The fourth author’s research was carried out while visiting RIMS in August 2007.     

Bordering method for solving systems of linear equations generated by the finite element method in the plate bending problem

A combined iteration algorithm based on the bordering and conjugate gradient methods is proposed to solve systems of linear equations generated by the finite element method in the plate bending problem. The numerical results for the analysis of the convergence rate of the iterative process are presented in the solution of model problems using a classical and modified algorithm of the method of conjugate gradients. The possibility of acceleration of the iterative algorithm is shown. __________ Translated from Problemy Prochnosti, No. 4, pp. 137–145, July–August, 2007.     

A computational procedure for flexible beams with frictional contact constraints

This paper deals with the application of a parametric quadratic programming (PQP) method to the numerical solution of large-deflection beams involving frictional contact constraints. The flexibility of the structure is modelled by an intrinsic spatial beam theory which is approximated by transverse-shear deformable linear beam elements. The linear complementary problem (LCP) without the penalty function resulting from PQP is made part of a Newton-Raphson search. The tool for solving the complementary equations is Lemke's algorithm, in which frictional contact conditions are enforced and new contact surfaces are updated during iteration. Applying the resulting contact element, a more accurate approximation of the contact point can be guaranteed, and the contact force can be directly computed by the adjacent beam elements. Three numerical examples are analysed to show the effectiveness and validity of the method.