Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.16330 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916702902550528 |
|---|---|
| author | Choi, Soobin Cepeda, Valentina Gomez, Andres Han, Shaoning |
| author_facet | Choi, Soobin Cepeda, Valentina Gomez, Andres Han, Shaoning |
| contents | We investigate convexification for convex quadratic optimization with step function penalties. Such problems can be cast as mixed-integer quadratic optimization problems, where binary variables are used to encode the non-convex step function. First, we derive the convex hull for the epigraph of a quadratic function defined by a rank-one matrix and step function penalties. Using this rank-one convexification, we develop copositive and semi-definite relaxations for general convex quadratic functions. Leveraging these findings, we construct convex formulations to the support vector machine problem with 0--1 loss and show that they yield robust estimators in settings with anomalies and outliers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16330 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rank-one convexification for quadratic optimization problems with step function penalties Choi, Soobin Cepeda, Valentina Gomez, Andres Han, Shaoning Optimization and Control 90 We investigate convexification for convex quadratic optimization with step function penalties. Such problems can be cast as mixed-integer quadratic optimization problems, where binary variables are used to encode the non-convex step function. First, we derive the convex hull for the epigraph of a quadratic function defined by a rank-one matrix and step function penalties. Using this rank-one convexification, we develop copositive and semi-definite relaxations for general convex quadratic functions. Leveraging these findings, we construct convex formulations to the support vector machine problem with 0--1 loss and show that they yield robust estimators in settings with anomalies and outliers. |
| title | Rank-one convexification for quadratic optimization problems with step function penalties |
| topic | Optimization and Control 90 |
| url | https://arxiv.org/abs/2504.16330 |