A Globally and Superlinearly Convergent Primal-Dual Interior Point Method for General Constrained Optimization

In this paper, a primal-dual interior point method is proposed for general constrained optimization, which incorporated a penalty function and a kind of new identification technique of the active set. At each iteration, the proposed algorithm only needs to solve two or three reduced systems of linear equations with the same coefficient matrix. The size of systems of linear equations can be decreased due to the introduction of the working set, which is an estimate of the active set. The penalty parameter is automatically updated and the uniformly positive definiteness condition on the Hessian approximation of the Lagrangian is relaxed. The proposed algorithm possesses global and superlinear convergence under some mild conditions. Finally, some preliminary numerical results are reported.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point

For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence. To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above. Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China.     

A Superlinearly Convergent SSLE Algorithm for Optimization Problems with Linear Complementarity Constraints

In this paper we study a special kind of optimization problems with linear complementarity constraints. First, by a generalized complementarity function and perturbed technique, the discussed problem is transformed into a family of general nonlinear optimization problems containing parameters. And then, using a special penalty function as a merit function, we establish a sequential systems of linear equations (SSLE) algorithm. Three systems of equations solved at each iteration have the same coefficients. Under some suitable conditions, the algorithm is proved to possess not only global convergence, but also strong and superlinear convergence. At the end of the paper, some preliminary numerical experiments are reported.     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations （SSLE） algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.     

A penalty continuation method for the ∓∞ solution of overdetermined linear systems

A new algorithm for the ∓_∞ solution of overdetermined linear systems is given. The algorithm is based on the application of quadratic penalty functions to a primal linear programming formulation of the ∓_∞ problem. The minimizers of the quadratic penalty function generate piecewise-linear non-interior paths to the set of ∓_∞ solutions. It is shown that the entire set of ∓_∞ solutions is obtained from the paths for sufficiently small values of a scalar parameter. This leads to a finite penalty/continuation algorithm for ∓_∞ problems. The algorithm is implemented and extensively tested using random and function approximation problems. Comparisons with the Barrodale-Phillips simplex based algorithm and the more recent predictor-corrector primal-dual interior point algorithm are given. The results indicate that the new algorithm shows a promising performance on random (non-function approximation) problems.     

SEQUENTIAL SYSTEMS OF LINEAR EQUATIONS ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS-INEQUALITY CONSTRAINED PROBLEMS

AbstractIn this paper, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints is proposed. Since the new algorithm only needs to solve several systems of linear equations having a same coefficient matrix per iteration, the computation amount of the algorithm is much less than that of the existing SQP algorithms per iteration. Moreover, for the SQP type algorithms, there exist so-called inconsistent problems, i.e., quadratic programming subproblems of the SQP algorithms may not have a solution at some iterations, but this phenomenon will not occur with the SSLE algorithms because the related systems of linear equations always have solutions. Some numerical results are reported.     

无严格互补松驰条件的序列线性方程组新算法

该文通过构造特殊形式的有效集来逼近KKT点处的有效集，给出了一个任意初始点下的序列线性方程组新算法，并证明了该算法在没有严格互补松驰条件的情况下具有全局收敛性和一步超线性收敛性。      

Globally and Superlinearly Convergent QP-Free Algorithm for Nonlinear Constrained Optimization

A new, infeasible QP-free algorithm for nonlinear constrained optimization problems is proposed. The algorithm is based on a continuously differentiable exact penalty function and on active-set strategy. After a finite number of iterations, the algorithm requires only the solution of two linear systems at each iteration. We prove that the algorithm is globally convergent toward the KKT points and that, if the second-order sufficiency condition and the strict complementarity condition hold, then the rate of convergence is superlinear or even quadratic. Moreover, we incorporate two automatic adjustment rules for the choice of the penalty parameter and make use of an approximated direction as derivative of the merit function so that only first-order derivatives of the objective and constraint functions are used.     

PARALLEL STABILIZATION

1.IntroductionLetusconsideranevolutionsystemwhosestateisgivenbythesolutionofaPartialDifferentialEquation(PDE)whichiswritten(formallyforthetimebeing)asIn(1.1),(1.2),whichmaybealinearoranonlinearPDE,ydenotesthestate,andvdenotesthecontrol.TheoperatorA,w...     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

求解定常不可压Stokes方程的两层罚函数方法

借助于两套有限元网格空间提出了一种求解定常不可压Stokes方程的两层罚函数方法.该方法只需要求解粗网格空间上的Stokes方程和细网格空间上的两个易于求解的罚参数方程（离散后的线性方程组具有相同的对称正定系数矩阵）.收敛性分析表明粗网格空间相对于细网格空间可以选择很小，并且罚参数的选取只与粗网格步长和问题的正则性有关.因此罚参数不必选择很小仍能够得到最优解.最后通过数值算例验证了上述理论结果，并且数值对比可知两层罚函数方法对于求解定常不可压Stokes方程具有很好的效果.     

An efficient algorithm for solving rank one perturbed linear Diophantine systems using Rosser��s approach

Recently, we described a generalization of Rosser’s algorithm for a single linear Diophantine equation to an algorithm for solving systems of linear Diophantine equations. Here, we make use of the new formulation to present a new algorithm for solving rank one perturbed linear Diophantine systems, based on using Rosser’s approach. Finally, we compare the efficiency and effectiveness of our proposed algorithm with the algorithm proposed by Amini and Mahdavi-Amiri (Optim Methods Softw 21:819–831, 2006).     

二阶锥线性互补问题的低阶罚函数算法

本文研究了二阶锥线性互补问题的低阶罚函数算法.利用低阶罚函数算法将二阶锥线性互补问题转化为低阶罚函数方程组,获得了低阶罚函数方程组的解序列在特定条件下以指数速度收敛于二阶锥线性互补问题解的结果,推广了二阶锥线性互补问题的幂罚函数算法.数值实验结果验证了算法的有效性.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

A SSLE-Type Algorithm of Quasi-Strongly Sub-Feasible Directions for Inequality Constrained Minimax Problems

In this paper, we discuss the nonlinear minimax problems with inequality constraints. Based on the stationary conditions of the discussed problems, we propose a sequential systems of linear equations (SSLE)-type algorithm of quasi-strongly sub-feasible directions with an arbitrary initial iteration point. By means of the new working set, we develop a new technique for constructing the sub-matrix in the lower right corner of the coefficient matrix of the system of linear equations (SLE). At each iteration, two systems of linear equations (SLEs) with the same uniformly nonsingular coefficient matrix are solved. Under mild conditions, the proposed algorithm possesses global and strong convergence. Finally, some preliminary numerical experiments are reported.     

A penalty function approach for solving bi-level linear programs

The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.     

线性规划椭球算法若干改进结果

本文给出线性规划哈奇杨椭球算法的两个改进形式,推广了哈奇杨文的结果,给出了对解线性代数方程组的应用和若干数值算例。     

超线性与二次收敛序列线性方程组算法

本文,在无严格互补条件下,对非线性不等式约束最优化问题提出了一个新的序列线性方程组(简称SSLE)算法．算法有两个重要特征:首先,每次迭代,只须求解一个线性方程组或一个广义梯度投影阵,且线性方程组可以无解．其次,初始点可以任意选取．在无严格互补条件下,算法仍有全局收敛性、强收敛性、超线性收敛性及二次收敛性．文章的最后,还对算法进行了初步的数值实验．