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

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

Full description

Saved in:
Bibliographic Details
Published in:Numerical algorithms 2022-10, Vol.91 (2), p.711-748
Main Author: Yang, Yaguang
Format: Article
Language:English
Subjects:
Actuators
Algebra
Algorithms
Computer Science
Design engineering
Efficiency
Linear programming
Neighborhoods
Numeric Computing
Numerical Analysis
Optimal control
Optimization
Original Paper
Polynomials
Quadratic programming
Searching
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ( n log ( 1 / ε ) ) . 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.
ISSN:1017-1398
1572-9265
DOI:10.1007/s11075-022-01279-x