二次半定规划的增广拉格朗日算法

基于变换X=VV~T,本文将半定规划问题转换为非线性规划问题,提出了解决此问题的增广拉格朗日算法,并证明了算法的线性收敛性.在此算法中,每一次迭代计算的子问题利用最速下降搜索方向和满足wolf条件的线性搜索法求最优解.数值实验表明,此算法是行之有效的,且优于内点算法.     

KLee和Minty例的性质

本文证明了:用单纯形法迭代求解Kell和Minty例（式（1）的线性规划问题）时，如果用最大增量法确定入基变量，则从其任一顶点出发，迭代次数不超过n次．     

基于信赖域技术的处理带线性约束优化的内点算法

基于信赖域技术,本文提出了一个求解带线性等式和非负约束优化问题的内点算法,其特点是:为了求得搜索方向,算法在每一步迭代时仅需要求解一线性方程组系统,从而避免了求解带信赖域界的子问题,然后利用非精确的Armijo线搜索法来得到下一个迭代内点. 从数值计算的观点来看,这种技巧可减少计算量.在适当的条件下,文中还证明了该算法所产生的迭代序列的每一个聚点都是原问题的KKT点.     

一类新的多步曲线搜索下的超记忆梯度法

研究一类新的求解无约束优化问题的超记忆梯度法,分析了算法的全局收敛性和线性收敛速率.算法利用一种多步曲线搜索准则产生新的迭代点,在每步迭代时同时确定下降方向和步长,并且不用计算和存储矩阵,适于求解大规模优化问题.数值试验表明算法是有效的.     

基于核函数求解线性互补问题的不可行内点算法

本文研究了线性互补问题内点算法.利用全牛顿步长求解迭代方向,获得了算法迭代复杂性为O(nlogn/ε),推广了Roos等关于线性规划问题不可行内点算法,其复杂性与目前最好的不可行内点算法复杂性一致.     

非单调线性互补问题的高阶宽领域内点算法

本文研究了P(K)-阵线性互补问题宽邻域高阶内点算法.利用线性规划的原始-对偶仿射尺度算法来确定迭代方向,得到了算法的收敛性及迭代复杂性,其算法是有效可行的.     

一种新的记忆梯度法及其收敛性

本文提出一种新的无约束优化记忆梯度算法,算法在每步迭代时利用了前面迭代点的信息,增加了参数选择的自由度,适于求解大规模无约束优化问题.分析了算法的全局收敛性.数值试验表明算法是有效的.     

求解P_*(κ)-阵线性互补问题的高阶仿射尺度内点算法

对P*(k)-阵线性互补问题提出了一种高阶内点算法.算法的每步迭代是基于线性规划原始-对偶仿射尺度算法的思想来确定迭代方向,再通过适当选取步长,得到算法的多项式复杂性.     

半定规划的近似中心投影法

1．引言半定规划问题标准形的数学形式是这里C，AIEIR”””及变量XEIRn“”为对称矩阵，Tr（·）表示矩阵的迹，用符号＞0和三0分别表示矩阵正定和半正定．由于半定规划在控制论，结构优化，组合优化方面有重要应用［1，3，16，17］以及线性规划内点法取得的巨大成就［7］，将线性规划的内点法推广到半定规划上，是数学规划领域内近年来受到重视的一个研究课题．线性规划内点法中的势函数下降法［10，16］原始对偶中心路径跟踪法［2，4，8，9，11。15］已经先后被推广到半定规划上．ROOS－Visl近似中心法则是求解线性规划的另一类内…     

无约束优化问题的一个下降方法

本文研究了无约束优化问题.利用当前和前面迭代点的信息以及曲线搜索技巧产生新的迭代点,得到了一个新的求解无约束优化问题的下降方法.在较弱条件下证明了算法具有全局收敛性.当目标函数为一致凸函数时,证明了算法具有线性收敛速率.初步的数值试验表明算法是有效的.     

优化方法解决无上层约束的线性双层规划问题

In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

A Constrained Optimization Approach for LCP

In this paper, LCP is converted to an equivalent nonsmooth nonlinear equation system H(x,y) = 0 by using the famous NCP function-Fischer-Burmeister function. Note that some equations in H(x, y) = 0 are nonsmooth and nonlinear hence difficult to solve while the others are linear hence easy to solve. Then we further convert the nonlinear equation system H(x, y) = 0 to an optimization problem with linear equality constraints. After that we study the conditions under which the K-T points of the optimization problem are the solutions of the original LCP and propose a method to solve the optimization problem. In this algorithm, the search direction is obtained by solving a strict convex programming at each iterative point, However, our algorithm is essentially different from traditional SQP method. The global convergence of the method is proved under mild conditions. In addition, we can prove that the algorithm is convergent superlinearly under the conditions: M is P0 matrix and the limit point is a strict complementarity solution of LCP. Preliminary numerical experiments are reported with this method.     

An iterative approach to solve multiobjective linear fractional programming problems

This paper suggests an iterative parametric approach for solving multiobjective linear fractional programming (MOLFP) problems which only uses linear programming to obtain efficient solutions and always converges to an efficient solution. A numerical example shows that this approach performs better than some existing algorithms. Randomly generated MOLFP problems are also solved to demonstrate the performance of new introduced algorithm.     

A least-distance programming procedure for minimization problems under linear constraints

In this paper, an algorithm is developed for solving a nonlinear programming problem with linear contraints. The algorithm performs two major computations. First, the search vector is determined by projecting the negative gradient of the objective function on a polyhedral set defined in terms of the gradients of the equality constraints and the near binding inequality constraints. This least-distance program is solved by Lemke's complementary pivoting algorithm after eliminating the equality constraints using Cholesky's factorization. The second major calculation determines a stepsize by first computing an estimate based on quadratic approximation of the function and then finalizing the stepsize using Armijo's inexact line search. It is shown that any accumulation point of the algorithm is a Kuhn-Tucker point. Furthermore, it is shown that, if an accumulation point satisfies the second-order sufficiency optimality conditions, then the whole sequence of iterates converges to that point. Computational testing of the algorithm is presented.     

对称线性互补问题的并行Schwarz算法

1引言考虑对称线性互补问题:求x∈R~N使得(1) Ax 6≥0,x≥0,x~T(Ax b)=0其中,A是给定的N×N实对称矩阵,b是N×1向量.目前求解该互补问题的迭代算法有很多(如Mangasarian(1977),Mangasarian,Leone (1987),Cottle(1992),曾金平,李董辉(1994)等).区域分解法以其将大问题化为若干子问     

Viable set computation for hybrid systems

In this paper, we revisit the problem of computing viability sets for hybrid systems with nonlinear continuous dynamics and competing inputs. As usual in the literature, an iterative algorithm, based on the alternating application of a continuous and a discrete operator, is employed. Different cases, depending on whether the continuous evolution and the number of discrete transitions are finite or infinite, are considered. A complete characterization of the reach-avoid computation (involved in the continuous time calculation) is provided based on dynamic programming. Moreover, for a certain class of automata, we show convergence of the iterative process by using a constructive version of Tarski’s fixed point theorem, to determine the maximal fixed point of a monotone operator on a complete lattice of closed sets. The viability algorithm is applied to a benchmark example and to the problem of voltage stability for a single machine-load system in case of a line fault.     

On an enumerative algorithm for solving eigenvalue complementarity problems

In this paper, we discuss the solution of linear and quadratic eigenvalue complementarity problems (EiCPs) using an enumerative algorithm of the type introduced by Júdice et al. (Optim. Methods Softw. 24:549–586, 2009). Procedures for computing the interval that contains all the eigenvalues of the linear EiCP are first presented. A nonlinear programming (NLP) model for the quadratic EiCP is formulated next, and a necessary and sufficient condition for a stationary point of the NLP to be a solution of the quadratic EiCP is established. An extension of the enumerative algorithm for the quadratic EiCP is also developed, which solves this problem by computing a global minimum for the NLP formulation. Some computational experience is presented to highlight the efficiency and efficacy of the proposed enumerative algorithm for solving linear and quadratic EiCPs.     

Further Developments in an Iterative Projection and Contraction Method for Linear Programming

A linear programming problem can be translated into an equivalent general linear complementarity problem, which can be solved by an iterative projection and contraction (PC) method [6]. The PC method requires only two matrix-vector multiplications at each iteration and the efficiency in practice usually depends on the sparsity of the constraint-matrix. The prime PC algorithm in [6] is globally convergent; however, no statement can be made about the rate of convergence. Although a variant of the PC algorithm with constant step-size for linear programming [7] has a linear speed of convergence, it converges much slower in practice than the prime method [6]. In this paper, we develop a new step-size rule for the PC algorithm for linear programming such that the resulting algorithm is globally linearly convergent. We present some numerical experiments to indicate that it also works better in practice than the prime algorithm.