A Parallel Linear Active Set Method

E. Dov Neimand () and Şerban Sabău ()
Additional contact information
E. Dov Neimand: Stevens Institute of Technology
Şerban Sabău: Stevens Institute of Technology

A chapter in Data Analysis and Optimization, 2023, pp 237-255 from Springer

Abstract: Abstract Given a linear-inequality-constrained convex minimization problem in a Hilbert space, we develop a novel binary test that examines sets of constraints and passes only active-constraint sets. The test employs a black-box, linear-equality-constrained convex minimization method but can often fast fail, without calling the black-box method, by considering information from previous applications of the test on subsets of the current constraint set. This fast fail, as a function of the number of dimensions, has quadratic complexity, and can be completely multi-threaded down to near-constant complexity. Only when the test is unable to fast fail, does it use the black-box method. In both cases the test generates the optimal point over the subject inequalities. Iterative and largely parallel applications of the test over growing subsets of inequality constraints yields a minimization algorithm. We also include an adaptation of the algorithm for a non-convex polyhedron in Euclidean space. Outside of calling the black-box method, complexity is not a function of accuracy. The algorithm does not require the feasible space to have a non-empty interior, or even be nonempty. With ample threads, the multi-threaded complexity of the algorithm is constant as a function of the number of inequalities.

Keywords: Convex optimization; Non-convex polyhedron; Hilbert space; Strict convexity; Parallel optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-31654-8_16

Ordering information: This item can be ordered from
http://www.springer.com/9783031316548

DOI: 10.1007/978-3-031-31654-8_16

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().