A superlinearly convergent method to linearly constrained optimization problems under degeneracy

Most papers concerning nonlinear programming problems with linear constraints assume linear independence of the gradients of the active constraints at any feasible point. In this paper we remove this assumption and give an algorithm and prove its convergency. Also, under appropriate assumptions on the objective function, including one which could be viewed as an extension of the strict complementary slackness condition at the optimal solution, we prove the rate of convergence of the algorithm to be superlinear.     

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

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

A superlinearly convergent method of quasi-strongly sub-feasible directions with active set identifying for constrained optimization

Combining the norm-relaxed sequential quadratic programming (SQP) method and the idea of method of quasi-strongly sub-feasible directions (MQSSFD) with active set identification technique, a new SQP algorithm for solving nonlinear inequality constrained optimization is proposed. Unlike the previous work, at each iteration of the proposed algorithm, the norm-relaxed quadratic programming (QP) subproblem only consists of the constraints corresponding to an active identification set. Moreover, the high-order correction direction (used to avoid the Maratos effect) is yielded by solving a system of linear equations (SLE) which also includes only the constraints and their gradients corresponding to the active identification set, therefore, the scale and the computation cost of the high-order correction directions are further decreased. The arc search in our algorithm can effectively combine the initialization processes with the optimization processes, and the iteration points can get into the feasible set after a finite number of iterations. Furthermore, the arc search conditions are weaker than the previous work, and the computation cost is further reduced. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ). If the strong second-order sufficient conditions are satisfied, then the active constraints are exactly identified by the identification set. Without the strict complementarity, superlinear convergence can be obtained. Finally, some elementary numerical results are reported.     

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 method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

Parallel algorithms for large-scale linearly constrained minimization problem

In this paper, two PVD-type algorithms are proposed for solving inseparable linear constraint optimization. Instead of computing the residual gradient function, the new algorithm uses the reduced gradients to construct the PVD directions in parallel computation, which can greatly reduce the computation amount each iteration and is closer to practical applications for solve large-scale nonlinear programming. Moreover, based on an active set computed by the coordinate rotation at each iteration, a feasible descent direction can be easily obtained by the extended reduced gradient method. The direction is then used as the PVD direction and a new PVD algorithm is proposed for the general linearly constrained optimization. And the global convergence is also proved.     

基于有效约束识别技术的一个SSLE算法及其收敛性分析

基于一个有效约束识别技术, 给出了具有不等式约束的非线性最优化问题的一个可行SSLE算法. 为获得搜索方向算法的每步迭代只需解两个或三个具有相同系数矩阵的线性方程组. 在一定的条件下, 算法全局收敛到问题的一个KKT点. 没有严格互补条件, 在比强二阶充分条件弱的条件下算法具有超线性收敛速度.     

Relaxed Cutting Plane Method for Solving Linear Semi-Infinite Programming Problems

One of the major computational tasks of using the traditional cutting plane approach to solve linear semi-infinite programming problems lies in finding a global optimizer of a nonlinear and nonconvex program. This paper generalizes the Gustafson and Kortanek scheme to relax this requirement. In each iteration, the proposed method chooses a point at which the infinite constraints are violated to a degree, rather than a point at which the violations are maximized. A convergence proof of the proposed scheme is provided. Some computational results are included. An explicit algorithm which allows the unnecessary constraints to be dropped in each iteration is also introduced to reduce the size of computed programs.     

A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS

In this paper, we propose a feasible QP-free method for solving nonlinear inequality constrained optimization problems. A new working set is proposed to estimate the active set. Specially, to determine the working set, the new method makes use of the multiplier information from the previous iteration, eliminating the need to compute a multiplier function. At each iteration, two or three reduced symmetric systems of linear equations with a common coefficient matrix involving only constraints in the working set are solved, and when the iterate is sufficiently close to a KKT point, only two of them are involved. Moreover, the new algorithm is proved to be globally convergent to a KKT point under mild conditions. Without assuming the strict complementarity, the convergence rate is superlinear under a condition weaker than the strong second-order sufficiency condition. Numerical experiments illustrate the efficiency of the algorithm.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

Smoothing SQP algorithm for semismooth equations with box constraints

In this paper, in order to solve semismooth equations with box constraints, we present a class of smoothing SQP algorithms using the regularized-smooth techniques. The main difference of our algorithm from some related literature is that the correspondent objective function arising from the equation system is not required to be continuously differentiable. Under the appropriate conditions, we prove the global convergence theorem, in other words, any accumulation point of the iteration point sequence generated by the proposed algorithm is a KKT point of the corresponding optimization problem with box constraints. Particularly, if an accumulation point of the iteration sequence is a vertex of box constraints and additionally, its corresponding KKT multipliers satisfy strictly complementary conditions, the gradient projection of the iteration sequence finitely terminates at this vertex. Furthermore, under local error bound conditions which are weaker than BD-regular conditions, we show that the proposed algorithm converges superlinearly. Finally, the promising numerical results demonstrate that the proposed smoothing SQP algorithm is an effective method.     

An Affine Scaling Interior Trust-Region Algorithm Combining Backtracking Line Search with Filter Technique for Nonlinear Constrained Optimization

In this article, an affine scaling interior trust-region algorithm which employs backtracking line search with filter technique is presented for solving nonlinear equality constrained programming with nonnegative constraints on variables. At current iteration, the general full affine scaling trust-region subproblem is decomposed into a pair of trust-region subproblems in vertical and horizontal subspaces, respectively. The trial step is given by the solutions of the pair of trust-region subproblems. Then, the step size is decided by backtracking line search together with filter technique. This is different from traditional trust-region methods and has the advantage of decreasing the number of times that a trust-region subproblem must be resolved in order to determine a new iteration point. Meanwhile, using filter technique instead of merit function to determine a new iteration point can avoid the difficult decisions regarding the choice of penalty parameters. Under some reasonable assumptions, the new method possesses the property of global convergence to the first-order critical point. Preliminary numerical results show the effectiveness of the proposed algorithm.     

An application of homotopy to solving linear programs

Consider a linear program inm inequality constraints andn nonnegative variables. An application of homotopy to the problem gives an algorithm similar to Dantzig's self-dual method. Howeve, the homotopy approach allows one to recognize several previously undescribed and potentially interesting properties. For example, the algorithm can be initiated in such a way as to produce a path which is primal-dual feasible. Moreover, one can theoretically identify an orthant with the property that if one initiates the algorithm at any point in that orthant then, after a ‘phase I’ requiring at most min{m, n} pivots, convergence is obtained in one step.     

Generalized monotone line search SQP algorithm for constrained minimax problems

In this article, non-linear minimax problems with general constraints are discussed. By means of solving one quadratic programming an improved direction is yielded and a second-order correction direction can also be at hand via one system of linear equations. So a new algorithm for solving the discussed problems is presented. In connection with a special merit function, the generalized monotone line search is used to yield the step size at each iteration. Under mild conditions, we can ensure global and superlinear convergence. Finally, some numerical experiments are operated to test our algorithm, and the results demonstrate that it is promising.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

A trust region method for solving semidefinite programs

When using interior point methods for solving semidefinite programs (SDP), one needs to solve a system of linear equations at each iteration. For problems of large size, solving the system of linear equations can be very expensive. In this paper, we propose a trust region algorithm for solving SDP problems. At each iteration we perform a number of conjugate gradient iterations, but do not need to solve a system of linear equations. Under mild assumptions, the convergence of this algorithm is established. Numerical examples are given to illustrate the convergence results obtained.     

A Proportioning Based Algorithm with Rate of Convergence for Bound Constrained Quadratic Programming

The proportioning algorithm with projections turned out to be an efficient algorithm for iterative solution of large quadratic programming problems with simple bounds and box constraints. Important features of this active set based algorithm are the adaptive precision control in the solution of auxiliary linear problems and capability to add or remove many indices from the active set in one step. In this paper a modification of the algorithm is presented that enables to find its rate of convergence in terms of the spectral condition number of the Hessian matrix and avoid any backtracking. The modified algorithm is shown to preserve the finite termination property of the original algorithm for problems that are not dual degenerate.     

A feasible SQP method for nonlinear programming

In this paper, a new SQP algorithm is presented to solve the general nonlinear programs with mixed equality and inequality constraints. Quoted from P. Spellucci (see [9]), this method maybe be named sequential equality constrained quadratic programming (SECQP) algorithm. Per single iteration, based on an active set strategy ( see [9]), this SECQP algorithm requires only to solve equality constrained quadratic programming subproblems or system of linear equations. The theoretical analysis shows that global and superlinear convergence can be induced under some suitable conditions.     

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.