Exploiting Block Structures of KKT Matrices for Efficient Solution of Convex Optimization Problems

Zafar Iqbal; Saeid Nooshabadi; Ichitaro Yamazaki; Stanimire Tomov; Jack Dongarra

doi:10.1109/ACCESS.2021.3106054

Exploiting Block Structures of KKT Matrices for Efficient Solution of Convex Optimization Problems

Zafar Iqbal, Saeid Nooshabadi, Ichitaro Yamazaki, Stanimire Tomov, Jack Dongarra

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Convex optimization solvers are widely used in the embedded systems that require sophisticated optimization algorithms including model predictive control (MPC). In this paper, we aim to reduce the online solve time of such convex optimization solvers so as to reduce the total runtime of the algorithm and make it suitable for real-time convex optimization. We exploit the property of the Karush–Kuhn–Tucker (KKT) matrix involved in the solution of the problem that only some parts of the matrix change during the solution iterations of the algorithm. Our results show that the proposed method can effectively reduce the runtime of the solvers.

Original language	English
Pages (from-to)	116604-116611
Number of pages	8
Journal	IEEE Access
Volume	9
DOIs	https://doi.org/10.1109/ACCESS.2021.3106054
State	Published - 2021
Externally published	Yes

Funding

This work was supported by the National Science Foundation under Grant 1709069.

Funders	Funder number
National Science Foundation
Directorate for Computer and Information Science and Engineering	1709069

Keywords

Convex optimization
Karush–Kuhn–Tucker (KKT)
embedded systems
linear solver

Access to Document

10.1109/ACCESS.2021.3106054

Cite this

@article{eab7b937154348eab6cad15a49d2e772,

title = "Exploiting Block Structures of KKT Matrices for Efficient Solution of Convex Optimization Problems",

abstract = "Convex optimization solvers are widely used in the embedded systems that require sophisticated optimization algorithms including model predictive control (MPC). In this paper, we aim to reduce the online solve time of such convex optimization solvers so as to reduce the total runtime of the algorithm and make it suitable for real-time convex optimization. We exploit the property of the Karush–Kuhn–Tucker (KKT) matrix involved in the solution of the problem that only some parts of the matrix change during the solution iterations of the algorithm. Our results show that the proposed method can effectively reduce the runtime of the solvers.",

keywords = "Convex optimization, Karush–Kuhn–Tucker (KKT), embedded systems, linear solver",

author = "Zafar Iqbal and Saeid Nooshabadi and Ichitaro Yamazaki and Stanimire Tomov and Jack Dongarra",

year = "2021",

doi = "10.1109/ACCESS.2021.3106054",

language = "English",

volume = "9",

pages = "116604--116611",

journal = "IEEE Access",

issn = "2169-3536",

publisher = "Institute of Electrical and Electronics Engineers",

}

TY - JOUR

T1 - Exploiting Block Structures of KKT Matrices for Efficient Solution of Convex Optimization Problems

AU - Iqbal, Zafar

AU - Nooshabadi, Saeid

AU - Yamazaki, Ichitaro

AU - Tomov, Stanimire

AU - Dongarra, Jack

PY - 2021

Y1 - 2021

N2 - Convex optimization solvers are widely used in the embedded systems that require sophisticated optimization algorithms including model predictive control (MPC). In this paper, we aim to reduce the online solve time of such convex optimization solvers so as to reduce the total runtime of the algorithm and make it suitable for real-time convex optimization. We exploit the property of the Karush–Kuhn–Tucker (KKT) matrix involved in the solution of the problem that only some parts of the matrix change during the solution iterations of the algorithm. Our results show that the proposed method can effectively reduce the runtime of the solvers.

AB - Convex optimization solvers are widely used in the embedded systems that require sophisticated optimization algorithms including model predictive control (MPC). In this paper, we aim to reduce the online solve time of such convex optimization solvers so as to reduce the total runtime of the algorithm and make it suitable for real-time convex optimization. We exploit the property of the Karush–Kuhn–Tucker (KKT) matrix involved in the solution of the problem that only some parts of the matrix change during the solution iterations of the algorithm. Our results show that the proposed method can effectively reduce the runtime of the solvers.

KW - Convex optimization

KW - Karush–Kuhn–Tucker (KKT)

KW - embedded systems

KW - linear solver

UR - http://www.scopus.com/inward/record.url?scp=85113284984&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2021.3106054

DO - 10.1109/ACCESS.2021.3106054

M3 - Article

AN - SCOPUS:85113284984

SN - 2169-3536

VL - 9

SP - 116604

EP - 116611

JO - IEEE Access

JF - IEEE Access

ER -

Exploiting Block Structures of KKT Matrices for Efficient Solution of Convex Optimization Problems

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this