kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Krylov Solvers for Interior Point Methods with Applications in Radiation Therapy and Support Vector Machines
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Computational Science and Technology (CST). RaySearch Laboratories, Stockholm, Sweden.ORCID iD: 0000-0001-6865-9379
RaySearch Laboratories, Stockholm, Sweden.
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Computational Science and Technology (CST).ORCID iD: 0000-0003-0639-0639
2024 (English)In: Computational Science – ICCS 2024 - 24th International Conference, 2024, Proceedings, Springer Nature , 2024, p. 63-77Conference paper, Published paper (Refereed)
Abstract [en]

Interior point methods are widely used for different types of mathematical optimization problems. Many implementations of interior point methods in use today rely on direct linear solvers to solve systems of equations in each iteration. The need to solve ever larger optimization problems more efficiently and the rise of hardware accelerators for general purpose computing has led to a large interest in using iterative linear solvers instead, with the major issue being inevitable ill-conditioning of the linear systems arising as the optimization progresses. We investigate the use of Krylov solvers for interior point methods in solving optimization problems from radiation therapy and support vector machines. We implement a prototype interior point method using a so called doubly augmented formulation of the Karush-Kuhn-Tucker linear system of equations, originally proposed by Forsgren and Gill, and evaluate its performance on real optimization problems from radiation therapy and support vector machines. Crucially, our implementation uses a preconditioned conjugate gradient method with Jacobi preconditioning internally. Our measurements of the conditioning of the linear systems indicate that the Jacobi preconditioner improves the conditioning of the systems to a degree that they can be solved iteratively, but there is room for further improvement in that regard. Furthermore, profiling of our prototype code shows that it is suitable for GPU acceleration, which may further improve its performance in practice. Overall, our results indicate that our method can find solutions of acceptable accuracy in reasonable time, even with a simple Jacobi preconditioner.

Place, publisher, year, edition, pages
Springer Nature , 2024. p. 63-77
Keywords [en]
Interior point method, Krylov solver, Radiation therapy, Support Vector Machines
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-351764DOI: 10.1007/978-3-031-63749-0_5ISI: 001279316700005Scopus ID: 2-s2.0-85199601918OAI: oai:DiVA.org:kth-351764DiVA, id: diva2:1888731
Conference
24th International Conference on Computational Science, ICCS 2024, Malaga, Spain, Jul 2 2024 - Jul 4 2024
Note

Part of ISBN [9783031637483]

QC 20240820

Available from: 2024-08-13 Created: 2024-08-13 Last updated: 2024-09-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Liu, FelixMarkidis, Stefano

Search in DiVA

By author/editor
Liu, FelixMarkidis, Stefano
By organisation
Computational Science and Technology (CST)
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf