检索结果-内蒙古大学图书馆

Bi-affine scaling iterative method for convex quadratic programming with bound constraints

MATHEMATICS AND COMPUTERS IN SIMULATION 2024年 226卷 373-382页

作者： Yue, Hongwei Shen, Peiping North China Univ Water Resources & Elect Power Sch Math & Stat Zhengzhou Peoples R China

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.

关键词： convex quadratic programming Bound constraints Interior-point algorithm Affine scaling

来源：评论

学校读者我要写书评

暂无评论

A new full-Newton step feasible interior point method for convex quadratic programming

引用

OPTIMIZATION 2024年第5期73卷 1571-1588页

作者： Boudjellal, Nawel Benterki, Djamel Univ Ferhat Abbas Setif 1 Fac Sci Dept Math Lab Fundamental & Numer Math Setif Algeria Univ Akli Mohand Oulhadj Bouira Bouira Algeria

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.

关键词： convex quadratic programming feasible interior point method full-Newton step variable weight vector

来源：评论

学校读者我要写书评

暂无评论

IPRQP: a primal-dual interior-point relaxation algorithm for convex quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第2-4期87卷 1027-1053页

作者： Zhang, Rui-Jin Liu, Xin-Wei Dai, Yu-Hong Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Hebei Univ Technol Inst Math Tianjin Peoples R China

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.

关键词： convex quadratic programming Interior-point relaxation method Smoothing barrier augmented Lagrangian Infeasibility detection

来源：评论

学校读者我要写书评

暂无评论

QPPAL: A Two-phase Proximal Augmented Lagrangian Method for High-dimensional convex quadratic programming Problems

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第3期48卷 1-27页

作者： Liang, Ling Li, Xudong Sun, Defeng Toh, Kim-Chuan Natl Univ Singapore Dept Math 10 Lower Kent Ridge Rd Singapore 119076 Singapore Fudan Univ Sch Data Sci Shanghai Peoples R China Hong Kong Polytech Univ Dept Appl Math Hung Hom Hong Kong Peoples R China Natl Univ Singapore Inst Operat Res & Analyt 10 Lower Kent Ridge Rd Singapore 119076 Singapore

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/.

关键词： convex quadratic programming restricted-Wolfe dual symmetric Gauss-Seidel augmented Lagrangian method

来源：评论

学校读者我要写书评

暂无评论

An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints

引用

NUMERICAL ALGORITHMS 2022年第2期91卷 711-748页

作者： Yang, Yaguang US NRC Off Res 11555 Rockville Pike Rockville MD 20852 USA

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.

关键词： Arc-search Interior-point method convex quadratic programming Polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An interior point-proximal method of multipliers for convex quadratic programming

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2021年第2期78卷 307-351页

作者： Pougkakiotis, Spyridon Gondzio, Jacek Univ Edinburgh Edinburgh Midlothian Scotland

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.

关键词： Interior point methods Proximal point methods Regularized primal-dual methods convex quadratic programming

来源：评论

学校读者我要写书评

暂无评论

A primal-dual interior point algorithm for convex quadratic programming based on a new parametric kernel function

引用

OPTIMIZATION 2021年第8期70卷 1703-1724页

作者： Boudjellal, N. Roumili, H. Benterki, D. J. Univ Ferhat Abbas Setif 1 Fac Sci Lab Fundamental & Numer Math Dept Math Setif Algeria

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.

关键词： convex quadratic programming interior point methods kernel function

来源：评论

学校读者我要写书评

暂无评论

Towards an efficient augmented Lagrangian method for convex quadratic programming

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2020年第3期76卷 767-800页

作者： Bueno, Luis Felipe Haeser, Gabriel Santos, Luiz-Rafael Univ Fed Sao Paulo Inst Sci & Technol Sao Jose Dos Campos SP Brazil Univ Sao Paulo Dept Appl Math Sao Paulo SP Brazil Univ Fed Santa Catarina Dept Math Blumenau SC Brazil

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 quadratic programming, 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 convex quadratic 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.

关键词： Linear programming convex quadratic programming Augmented Lagrangian Interior point methods

来源：评论

学校读者我要写书评

暂无评论

Extension of Eaves Theorem for Determining the Boundedness of convex quadratic programming Problems

引用

TAIWANESE JOURNAL OF MATHEMATICS 2020年第6期24卷 1551-1563页

作者： Huu-Quang Nguyen Van-Bong Nguyen Ruey-Lin Sheu Vinh Univ Sch Nat Sci Educ Dept Math Vinh Nghe An Vietnam Natl Cheng Kung Univ Dept Math Tainan Taiwan Tay Nguyen Univ Dept Math Istanbul Vietnam

It is known that the boundedness of a convex quadratic function over a convex quadratic 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 convex quadratic constraint (not just a polyhedron) can be bounded from below, with a new insight that it can only be unbounded within an affine subspace.

关键词： convex quadratic programming l(p) programming Eaves theorem recession cone

来源：评论

学校读者我要写书评

暂无评论

A constraint-reduced MPC algorithm for convex quadratic programming, with a modified active set identification scheme

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2019年第3期72卷 727-768页

作者： Laiu, M. Paul Tits, Andre L. Oak Ridge Natl Lab Comp Sci & Math Div Computat & Appl Math Grp Oak Ridge TN 37831 USA Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA

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.

关键词： convex quadratic programming Constraint reduction Primal-dual interior-point method Mehrotra's predictor-corrector Regularization Active constraints identification

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：