To solve general convex quadratic programming problems with bound constraints, this paper proposes a new interior point iterative method that is easy to be implemented. The method exhibits a simple and sufficiently sm...
详细信息
To solve general convex quadratic programming problems with bound constraints, this paper proposes a new interior point iterative method that is easy to be implemented. The method exhibits a simple and sufficiently smooth search direction, and possesses the characteristics of affine scaling. Under the limited optimal stepsize rule, starting from an arbitrary interior point, any accumulation point of the generated sequence is an optimal solution of the corresponding problem. Furthermore, due to the absence of introducing dual variables and solving equations, the proposed method is more suitable for solving large-scale problems. Preliminary numerical results indicate that the new method has advantages in terms of both efficiency and accuracy.
In this paper, we propose and analyse a new full-Newton step feasible interior point method for convex quadratic programming. The basic idea of this method is to replace a complementarity condition by a non-negative v...
详细信息
In this paper, we propose and analyse a new full-Newton step feasible interior point method for convex quadratic programming. The basic idea of this method is to replace a complementarity condition by a non-negative variable weight vector. With a zero of weight vector, the limit of the weighted path exists and satisfies the complementarity condition, the limit yields an optimal solution of problem. In each main iteration of the new algorithm consisted of only full-Newton steps with a quadratic rate of convergence. The advantage of this method is the use of a full-Newton step, that is no calculation of the step size is required. Finally, some numerical results are reported to show the practical performance of the proposed algorithm with different parameters.
We propose IPRQP, an enhanced primal-dual interior-point relaxation method (IPRM), for solving convex quadratic programming. This method is based on a smoothing barrier augmented Lagrangian function for convex quadrat...
详细信息
We propose IPRQP, an enhanced primal-dual interior-point relaxation method (IPRM), for solving convex quadratic programming. This method is based on a smoothing barrier augmented Lagrangian function for convex quadratic programming. IPRQP inherits the advantages of IPRM, including not requiring iterative points to be interior points, which makes IPRQP suitable for the warm-starting of combinatorial optimization problems. Compared to IPRM, the customized starting points allow the line search of IPRQP to contain only vector operations. In addition, IPRQP improves the updating scheme of the barrier parameter and provides a certificate of infeasibility. Some results on global convergence are presented. We implement the algorithm on convex quadratic programming problems from Maros-Meszaros and the benchmark problem sets NETLIB and Kennington, which contain feasible and infeasible linear programming problems. The numerical results show that our algorithm is reliable for feasible problems and efficient for detecting the infeasibility of infeasible problems.
In this article, we aim to solve high-dimensional convex quadratic programming (QP) problems with a large number of quadratic terms, linear equality, and inequality constraints. To solve the targeted QP problem to a d...
详细信息
In this article, we aim to solve high-dimensional convex quadratic programming (QP) problems with a large number of quadratic terms, linear equality, and inequality constraints. To solve the targeted QP problem to a desired accuracy efficiently, we consider the restricted-Wolfe dual problem and develop a two-phase Proximal Augmented Lagrangian method (QPPAL), with Phase I to generate a reasonably good initial point to warm start Phase II to obtain an accurate solution efficiently. More specifically, in Phase I, based on the recently developed symmetric Gauss-Seidel (sGS) decomposition technique, we design a novel sGS-based semi-proximal augmented Lagrangian method for the purpose of finding a solution of low to medium accuracy. Then, in Phase II, a proximal augmented Lagrangian algorithm is proposed to obtain a more accurate solution efficiently. Extensive numerical results evaluating the performance of QPPAL against existing state-of-the-art solvers Gurobi, OSQP, and QPALM are presented to demonstrate the high efficiency and robustness of our proposed algorithm for solving various classes of large-scale convex QP problems. The MATLAB implementation of the software package QPPAL is available at https://***/mattohkc/softwares/qppal/.
This paper proposes an arc-search interior-point algorithm for convex quadratic programming with box constraints. The problem has many applications, such as optimal control with actuator saturation. It is shown that a...
详细信息
This paper proposes an arc-search interior-point algorithm for convex quadratic programming with box constraints. The problem has many applications, such as optimal control with actuator saturation. It is shown that an explicit feasible starting point exists for this problem. Therefore, an efficient feasible interior-point algorithm is proposed to tackle the problem. It is proved that the proposed algorithm is polynomial and has the best known complexity bound O (root nlog(1/is an element of). Moreover, the search neighborhood for this special problem is wider than an algorithm for general convex quadratic programming problems, which implies that longer steps and faster convergence are expected. Finally, an engineering design problem is considered and the algorithm is applied to solve the engineering problem.
In this paper we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM). The resulting algorithm (IP-PMM) is interpreted as a primal-dual regularized IPM, suitable for solving ...
详细信息
In this paper we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM). The resulting algorithm (IP-PMM) is interpreted as a primal-dual regularized IPM, suitable for solving linearly constrained convex quadratic programming problems. We apply few iterations of the interior point method to each sub-problem of the proximal method of multipliers. Once a satisfactory solution of the PMM sub-problem is found, we update the PMM parameters, form a new IPM neighbourhood and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under standard assumptions. To our knowledge, this is the first polynomial complexity result for a primal-dual regularized IPM. The algorithm is guided by the use of a single penalty parameter;that of the logarithmic barrier. In other words, we show that IP-PMM inherits the polynomial complexity of IPMs, as well as the strict convexity of the PMM sub-problems. The updates of the penalty parameter are controlled by IPM, and hence are well-tuned, and do not depend on the problem solved. Furthermore, we study the behavior of the method when it is applied to an infeasible problem, and identify a necessary condition for infeasibility. The latter is used to construct an infeasibility detection mechanism. Subsequently, we provide a robust implementation of the presented algorithm and test it over a set of small to large scale linear and convex quadratic programming problems. The numerical results demonstrate the benefits of using regularization in IPMs as well as the reliability of the method.
In this paper, we deal with a polynomial primal-dual interior-point algorithm for solving convex quadratic programming based on a new parametric kernel function with an exponential barrier term. The proposed kernel fu...
详细信息
In this paper, we deal with a polynomial primal-dual interior-point algorithm for solving convex quadratic programming based on a new parametric kernel function with an exponential barrier term. The proposed kernel function is not logarithmic and not self-regular. We analyze a class of large and small-update versions which are based on our new kernel function. The complexity obtained generalizes the result given by Bai et al. This result is the first to reach this goal. Finally, some numerical results are provided to show the efficiency of the proposed algorithm and to compare it with an available method.
Interior point methods have attracted most of the attention in the recent decades for solving large scale convex quadratic programming problems. In this paper we take a different route as we present an augmented Lagra...
详细信息
Interior point methods have attracted most of the attention in the recent decades for solving large scale convex quadratic programming problems. In this paper we take a different route as we present an augmented Lagrangian method for convex quadratic programming based on recent developments for nonlinear programming. In our approach, box constraints are penalized while equality constraints are kept within the subproblems. The motivation for this approach is that Newton's method can be efficient for minimizing a piecewise quadratic function. Moreover, since augmented Lagrangian methods do not rely on proximity to the central path, some of the inherent difficulties in interior point methods can be avoided. In addition, a good starting point can be easily exploited, which can be relevant for solving subproblems arising from sequential quadraticprogramming, in sensitivity analysis and in branch and bound techniques. We prove well-definedness and finite convergence of the method proposed. Numerical experiments on separable strictly convexquadratic problems formulated from the Netlib collection show that our method can be competitive with interior point methods, in particular when a good initial point is available and a second-order Lagrange multiplier update is used.
It is known that the boundedness of a convexquadratic function over a convexquadratic constraint (c-QP) can be determined by algorithms. In 1985, Terlaky transformed the said boundedness problem into an l(p) program...
详细信息
It is known that the boundedness of a convexquadratic function over a convexquadratic constraint (c-QP) can be determined by algorithms. In 1985, Terlaky transformed the said boundedness problem into an l(p) programming problem and then apply linear programming, while Caron and Obuchowska in 1995 proposed another iterative procedure that checks, repeatedly, the existence of the implicit equality constraints. Theoretical characterization about the boundedness of (c-QP), however, does not have a complete result so far, except for Eaves' theorem, first by Eaves and later by Dostal, which answered the boundedness question only partially for a polyhedraltype of constraints. In this paper, Eaves' theorem is generalized to answer, necessarily and sufficiently, when the general (c-QP) with a convexquadratic constraint (not just a polyhedron) can be bounded from below, with a new insight that it can only be unbounded within an affine subspace.
A constraint-reduced Mehrotra-predictor-corrector algorithm for convex quadratic programming is proposed. (At each iteration, such algorithms use only a subset of the inequality constraints in constructing the search ...
详细信息
A constraint-reduced Mehrotra-predictor-corrector algorithm for convex quadratic programming is proposed. (At each iteration, such algorithms use only a subset of the inequality constraints in constructing the search direction, resulting in CPU savings.) The proposed algorithm makes use of a regularization scheme to cater to cases where the reduced constraint matrix is rank deficient. Global and local convergence properties are established under arbitrary working-set selection rules subject to satisfaction of a general condition. A modified active-set identification scheme that fulfills this condition is introduced. Numerical tests show great promise for the proposed algorithm, in particular for its active-set identification scheme. While the focus of the present paper is on dense systems, application of the main ideas to large sparse systems is briefly discussed.
暂无评论