Optimization Online


An Infeasible Active Set Method with Combinatorial Line Search for Convex Quadratic Problems with Bound Constraints

Hungerlaender Philipp (philipp.hungerlaender***at***aau.at)
Franz Rendl (franz.rendl***at***aau.at)

Abstract: The minimization of a convex quadratic function under bound constraints is a fundamental building block for more complicated optimization problems. The active-set method introduced by [M. Bergounioux, K. Ito, and K. Kunisch. Primal-Dual Strategy for Constrained Optimal Control Problems. SIAM Journal on Control and Optimization, 37:1176–1194, 1999.] and [M. Bergounioux, M. Haddou, M. Hintermüller, and K. Kunisch. A comparison of interior point methods and a Moreau-Yosida based active set strategy for constrained optimal control problems. SIAM Journal on Optimization, 11(2):495–521, 2000.] has turned out to be a powerful, fast and competitive approach for this problem. [M. Hintermüller, K. Ito, and K. Kunisch. The primal-dual active set strategy as a semi-smooth newton method. SIAM Journal on Optimization, 13(3):865–888, 2003.] provide a theoretical explanation of its efficiency by interpreting it as a semismooth Newton method. One major drawback of this method lies in the fact that it is not globally convergent. Several modifications were introduced recently, that ensure global convergence. In this paper we introduce yet another modified version of this active set method, which aims at maintaining the combinatorial flavour of the original semismooth Newton method. We prove global convergence for our modified version and show it to be competitive on a variety of difficult classes of test problems.

Keywords: primal-dual active set methods, semismooth Newton method, quadratic programming, box-constraints, convex programming

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical report, Alpen-Adria Universität Kla- genfurt, Mathematics, Optimization Group, TR-AAUK-M-O-16-08-03, 2016.

Download: [PDF]

Entry Submitted: 09/21/2016
Entry Accepted: 09/21/2016
Entry Last Modified: 03/10/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society