Pith. sign in

REVIEW 3 major objections 5 minor 95 references

Rank-one convexification for quadratic optimization problems with step function penalties

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves a two-term perspective inequality is the exact convex hull of a rank-one quadratic with sign-indicator step penalties, and uses it to build fast convex relaxations for 0-1-loss support vector machines.

desk verdict A correct new convex hull for sign-indicator step penalties, with an honestly reported SVM application; the proof gaps are small and worth a serious referee. read the letter →

arxiv 2504.16330 v1 pith:X5LJHMHF submitted 2025-04-23 math.OC

Soobin Choi , Valentina Cepeda , Andres Gomez , Shaoning Han This is my paper · ORCID
classification math.OC MSC 90C1190C2090C2290C2590C26
keywords convexhullrank-onequadraticstepfunctionpenaltiessignindicatorconstraintscopositiveprogrammingsemidefiniterelaxationrobustsupportvectormachine0-1loss
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper works with mixed-integer quadratic problems in which a binary variable $z_i$ records the sign of a continuous variable $x_i$, so a fixed cost is paid exactly when $x_i>0$; these are step-function penalties. The central result is an exact description of the convex hull of the epigraph set $t\ge (d^\top x)^2$ under those sign constraints: the quadratic splits into a positive part and a negative part, each divided by the number of coordinates whose binary setting allows that sign, with each denominator capped at one. Because the general convex quadratic case can be reached through the matrix variable $X\succeq xx^\top$, this rank-one hull is converted into copositive and semidefinite valid inequalities. In the support vector machine application with the 0-1 loss, the resulting relaxations produce bounds that are much stronger than big-M branch-and-bound in hard instances, and the relaxed solution itself behaves as a robust classifier under label noise and outliers. If the paper is right, a non-convex 0-1 loss becomes a convex program whose size grows linearly in the number of data points.

What carries the argument

The load-bearing object is the rank-one epigraph set $X_d$ with sign-indicator constraints, together with the two-term perspective inequality of Theorem 1. The proof of exactness works by linear separation: for any objective, unbounded rays force the linear coefficient vector to be proportional to $d$, after which the relaxation decomposes into two totally unimodular linear programs with integer optimal solutions. The machinery then lifts this inequality from scalars $t$ and vectors $x$ to the matrix level: the infinite family over all $d\in\mathbb{R}^n_+$ is encoded by two copositive-matrix constraints via the copositive Schur complement, and because $X\succeq xx^\top$ holds, those copositive constraints are equivalent to semidefinite constraints with auxiliary vectors $g,h$ sandwiching $x$. In the SVM application the same inequalities are expressed through $W\succeq ww^\top$, replacing $n$-dimensional cones by $(p+1)$-dimensional ones.

What would settle it

Fix $d=(1,1)$, add the bound $-1\le x_i\le 1$ to every continuous variable in $X_d$, and minimize $\alpha^\top x+\beta^\top z+t$ with $\alpha=(0,1)$, $\beta=0$ over the mixed-integer set and over the convex set of Theorem 1; if the two optimal values differ, the unboundedness assumption is essential and the claimed hull description does not extend to bounded variables.

Watch

Extended reading notes

Core claim

The claim is Theorem 1: for any vector $d\in\mathbb{R}^n$, the closure of the convex hull of $X_d=\{(x,z,t)\in\mathbb{R}^n\times\{0,1\}^n\times\mathbb{R}: t\ge (d^\top x)^2,\ x_i z_i\ge 0,\ x_i(1-z_i)\le 0\text{ for all }i\}$ is exactly the set with $0\le z\le 1$ and $$t\ge \frac{(d^\top x)_+^2}{\min\{1,\sum_{i\in\operatorname{supp}_+(d)}z_i+\sum_{i\in\operatorname{supp}_-(d)}(1-z_i)\}}+\frac{(d^\top x)_-^2}{\min\{1,\sum_{i\in\operatorname{supp}_-(d)}z_i+\sum_{i\in\operatorname{supp}_+(d)}(1-z_i)\}},$$ where $(v)_+=\max\{v,0\}$ and $(v)_-=\min\{v,0\}$. The denominators count the coordinates that can actually contribute the relevant sign: a coordinate with $d_i>0$ is allowed to be positive when $z_i=1$, while a coordinate with $d_i<0$ allows a positive contribution when $z_i=0$, and similarly for the negative part. The paper then shows that requiring this inequality to hold for every nonnegative direction $d$ is equivalent to two copositive constraints on the matrix $X$, and because the relaxation already has $X\succeq xx^\top$, those copositive constraints can be rewritten as semidefinite constraints with auxiliary vectors $g,h$; in the SVM setting the same inequalities are expressed through $W\succeq ww^\top$, with cone dimension $p+1$ rather than $n+1$.

Load-bearing premise

The convex hull description is exact only when the continuous variables $x$ are unbounded and the feasible set imposes no constraints beyond the sign indicators; the proof uses unbounded rays $x_i=-x_j=\lambda$ to eliminate coefficient differences, so bounded variables or extra coupling constraints break the argument, a case the paper explicitly leaves out.

Editorial extensions

If this is right

  • For any fixed rank-one matrix $Q=dd^\top$, the relaxation given by Theorem 1 is exact: solving the convex SOCP gives the same value as the mixed-integer problem, so the nonconvex step penalty costs nothing in this case.
  • For a general positive-semidefinite $Q$, the family of rank-one inequalities is equivalent to finitely many copositive constraints, and these can be rewritten as semidefinite constraints; this gives a tractable relaxation that dominates the plain $X\succeq xx^\top$ relaxation.
  • In SVM with the 0-1 loss, the relaxation can be formulated with semidefinite cones of dimension $p+1$ and, for singleton subsets, $O(n)$ conic constraints, so runtime grows linearly in the number of data points and the method scales to thousands of points when $p$ is small.
  • Used directly as an estimator, the relaxation's solution matches or beats the hinge-loss SVM under clustered or spread label noise, and combines well with hinge loss when no outliers are present.
  • The derived loss $\phi(x;d,\lambda)$ is a closed-form non-convex robust loss that is globally solvable through the convex relaxation, giving a convex surrogate for the 0-1 loss with a concave penalty on large violations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's convex hull is stated for unconstrained sign indicators; a natural testable extension is to bounded or box-constrained $x$, where the denominators would likely count how many coordinates can actually reach the boundary, and the paper's own proof of Proposition 3 pinpoints where unboundedness enters.
  • Because the hull handles arbitrary sign patterns of $d$, it applies directly to any quadratic whose Hessian is a single rank-one term, such as one-dimensional projections in sparse PCA or pairwise interaction models, suggesting a decomposition algorithm that strengthens one rank-one direction at a time.
  • The equivalence between the infinite rank-one inequalities and copositive constraints suggests that approximation hierarchies for the copositive cone could yield polyhedral relaxations with controlled size, extending the approach beyond low-dimensional feature spaces.
  • The closed-form loss in Proposition 12 predicts a specific shape for robust losses; one could test whether plugging $\phi$ into other classifiers, such as logistic regression with label noise, preserves the out-of-sample gains observed for SVM.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies mixed-integer quadratic programs with sign-indicator constraints (z_i=1 implies x_i>=0, z_i=0 implies x_i<=0) and step-function penalties, and develops convex relaxations for them. The central theoretical result, Theorem 1, gives an explicit description of cl conv(X_d) for rank-one Q=dd^T in terms of two perspective terms whose denominators depend on the signs of the entries of d. Using this rank-one description, the authors derive copositive and semidefinite valid inequalities for the extended set \bar X, specialize the resulting relaxations to support vector machines with 0-1 loss, and report computational experiments on synthetic and UCI data.

Significance. The proof of Theorem 1 is a genuine linear-objective separation argument rather than a restatement of a known result, and the hull description is parameter-free and directly usable. If correct, the paper provides a useful bridge between the extensively studied indicator-variable set Y_Q and the sign-indicator set X_Q, and the copositive/SDP relaxations for \bar X, together with their SVM specialization, are of clear practical interest. The computational study is extensive, compares against big-M MIO in a fair way, and documents numerical issues honestly. The main weakness is that not all load-bearing supporting results are proved in the manuscript, which is the reason for the requested revision.

major comments (3)
  1. [§5, Proposition 9] Proposition 9 is stated without proof even though Proposition 10, the SDP relaxation used in all SVM experiments of §7, is built directly on it. Because the computational claims depend on this inequality, the manuscript should either provide a proof, which should be parallel to the proof of Proposition 8, or cite a source where the result is proved.
  2. [§4, Proposition 3] The proof of Proposition 3 handles the remaining case gamma=1, d=1, alpha=eta*1 only for eta<=0, and the sentence "A similar analysis applies to the case eta>0" omits the corresponding subproblems. Since Theorem 1 and all subsequent relaxations reduce to this proposition, the eta>0 case should be written out; the needed reduction to two totally unimodular linear programs is short, but it is not present in the manuscript.
  3. [§4, Theorem 1] The extension from d>0 to d>=0 in the proof of Theorem 1 is asserted with the sentence "taking sums over the support of d removes the unused components of z." Variables with d_i=0 still satisfy sign-indicator constraints in X_d, so a brief argument that their convex hull contributes no additional inequalities is needed for the proof to be self-contained.
minor comments (5)
  1. [§4, Proof of Proposition 3] In the gamma=0 case, the phrase "letting x_i->infinity and setting z_i=1, or by letting x_i->-infinity or z_i=0" should read "... and setting z_i=0," as the current wording is a typo.
  2. [§7.1] The remark that MIO problems are "in most cases infeasible" for p<=5 is confusing because formulation (11) is feasible for any w when M is sufficiently large; please clarify whether solver-reported infeasibility or a modeling choice is meant.
  3. [§6.3] The sentence "the proposed formulation in Proposition 10 retains convexity and can be solved to global optimality" should be worded as a statement about a convex relaxation of the 0-1 problem, since (36) is a relaxation and not an exact reformulation of (9).
  4. [§7] The experimental section would benefit from a statement on code and data availability; the paper reports averages over many replications but no repository is referenced.
  5. [§7.1, Tables 1 and 2] The caption should state explicitly that the gaps reported for conic1 and conic2 are computed against the best feasible solution found by Gurobi and are therefore upper bounds on the true optimality gap, since the relaxation value is a lower bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convex-hull derivation is self-contained, and the authors' prior work is cited only for context and comparison.

full rationale

The central claim, Theorem 1, is established by a direct separation proof rather than by importing the result from the authors' own earlier papers. Proposition 3 proves equality of the MIP (20) and relaxation (21) for every linear objective by case analysis: the unbounded cases are handled by explicit feasible rays, and the remaining case d=1, alpha=eta*1, gamma=1 is reduced to the function f(z), which splits into two totally unimodular linear programs over z. An integer optimal z is obtained, and an integer-feasible point with the same objective is constructed explicitly, so cl conv(X_d)=bX_d follows from the definition of convex hull. Theorem 1 extends this to arbitrary signs by the substitution x_i=-x'_i, z_i=1-z'_i on supp_-(d), which is an exact equivalence of feasible sets rather than a restatement of the target formula. The self-citation to Atamturk and Gomez [7] appears in Proposition 1, which summarizes the sparsity-based sets Y1 and Y_R1; Proposition 1 is not invoked in the proof of Theorem 1, and the later citations of [6], [49], and [75] are comparisons of formulation complexity, not load-bearing assumptions. Proposition 5 uses only the definition of convex hull and the equality of linear optimization values, not any fitted or imported hull description. The SVM loss phi in Proposition 12 is obtained by algebraically minimizing the perspective terms over z; its parameters are not fitted to reproduce the 0-1 loss. The only self-identified gaps are Proposition 9 (stated without proof) and the deferred proof of Proposition 4(a) in Appendix A; both are completeness issues and do not make the central derivation circular. The computational claims are benchmarked against Gurobi, Mosek, and external methods, so the empirical findings are not circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted in the theoretical derivations. The SVM experiments use standard hyperparameters (regularization lambda, cardinality budget k, big-M in the baseline only) chosen by cross-validation, not fitted to produce the convex hull result. No new physical or model entities are postulated beyond the mathematical sets and loss function derived from the problem.

assumptions (4)
  • standard math Copositive Schur complement: M = [t, -x^T; -x, X] in C^{n+1}_+ iff t >= x^T X^{-1} x for X >= 0 with appropriate signs (Ping and Yu [72]).
    Used in Proposition 7 to rewrite the infinite family of conic inequalities (29) as two copositive constraints (30).
  • standard math Duality between copositive and completely positive cones: (C^n_+)^* = CP^n.
    Used in Appendix B (Proposition 14) to show equivalence between a copositive constraint and an SDP with bounds g,h.
  • standard math Schur complement: X >= xx^T iff [1, x^T; x, X] >= 0.
    Used throughout, e.g., in Proposition 5 and Proposition 8, to relate PSD constraints and quadratic inequalities.
  • domain assumption Unboundedness of continuous variables x in the rank-one set X_d.
    The proof of Proposition 3 reduces to the case alpha = eta*1 by constructing arbitrarily large opposing coordinates x_i = -x_j = lambda; this requires unbounded x. The paper does not cover bounded-variable generalizations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rank-one convexification for quadratic optimization problems with step function penalties." pith.science (2026). https://pith.science/paper/X5LJHMHF

@misc{pith2026250416330,
  author       = {Pith},
  title        = {Pith review of: Rank-one convexification for quadratic optimization problems with step function penalties},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X5LJHMHF}},
  note         = {Machine review of arXiv:2504.16330}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2504.16330 by the authors.

Figure 1
Figure 1. Non-convex robust losses approximating the 0-1 loss, as a function of x = yia ⊤ i w. Top row: loss functions from the literature: the normalized sigmoid loss [68], the ψ-learning loss [76] and the ramp loss [87]. Bottom row: the derived ϕ loss in Proposition 12 for different values of hyperparameters d (with λ = 1) . By solving the conic optimization problem (36), d is chosen automatically to ensure the convexity of… view at source ↗
Figure 2
Figure 2. (e) illustrates a generation of this class of dataset with p = 2 and σ = 0.5. In all cases, the ideal Bayes classifier is the line perpendicular to α1 − α−1 going through the origin, that is, wˆ ⊤ = (0 d ⊤). y=-1 y=1 (a) none with σ = 0.2 y=-1 y=1 (b) none with σ = 0.5 y=-1 y=1 (c) none with σ = 1.0 y=-1 y=1 (d) clustered with σ = 0.5 y=-1 y=1 (e) spread with σ = 0.5 [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Distribution of out-of-sample misclassification for data with clustered outliers and [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

95 extracted references · 70 canonical work pages

  1. [1]

    Abdi and R

    A. Abdi and R. Fukasawa. On the mixing set with a knapsack constraint. Mathematical Programming, 157:191–217, 2016

    2016

  2. [2]

    M. S. Akt¨ urk, A. Atamt¨ urk, and S. G¨ urel. A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Operations Research Letters, 37:187–191, 2009. 30

    2009

  3. [3]

    K. M. Anstreicher and S. Burer. Quadratic optimization with switching variables: The convex hull for n = 2. Mathematical Programming, 188(2):421–441, 2021

    2021

  4. [4]

    Atamt¨ urk and A

    A. Atamt¨ urk and A. G´ omez. Strong formulations for quadratic optimization with M-matrices and indicator variables. Mathematical Programming, 170(1):141–176, 2018

    2018

  5. [5]

    Atamt¨ urk and A

    A. Atamt¨ urk and A. G´ omez. Safe screening rules for L0-regression from perspective relaxations. In International Conference on Machine Learning , pages 421–430. PMLR, 2020

    2020

  6. [6]

    Atamt¨ urk and A

    A. Atamt¨ urk and A. G´ omez. Supermodularity and valid inequalities for quadratic optimization with indicators. Mathematical Programming, 201(1):295–338, 2023

    2023

  7. [7]

    Atamt¨ urk and A

    A. Atamt¨ urk and A. G´ omez. Rank-one convexification for sparse regression.Forthcoming in the Journal of Machine Learning Research, 2025

    2025

  8. [8]

    Bacci, A

    T. Bacci, A. Frangioni, C. Gentile, and K. Tavlaridis-Gyparakis. New mixed-integer nonlinear program- ming formulations for the unit commitment problems with ramping constraints. Operations Research, 72(5):2153–2167, 2024

    2024

Show all 95 references
  1. [9]

    P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association , 101(473):138–156, 2006

    2006

  2. [10]

    Bertsimas and A

    D. Bertsimas and A. King. OR forum—an algorithmic approach to linear regression. Operations Research, 64(1):2–16, 2016

    2016

  3. [11]

    Bertsimas and B

    D. Bertsimas and B. Van Parys. Sparse high-dimensional regression: Exact scalable algorithms and phase transitions. The Annals of Statistics , 48(1):300–323, 2020

    2020

  4. [12]

    Bertsimas, A

    D. Bertsimas, A. King, and R. Mazumder. Best subset selection via a modern optimization lens. The Annals of Statistics , 44(2):813–852, 2016

    2016

  5. [13]

    Bertsimas, J

    D. Bertsimas, J. Dunn, C. Pawlowski, and Y. D. Zhuo. Robust classification. INFORMS Journal on Optimization, 1(1):2–34, 2019

    2019

  6. [14]

    Bhathena, S

    A. Bhathena, S. Fattahi, A. G´ omez, and S. K¨ u¸ c¨ ukyavuz. A parametric approach for solving convex quadratic optimization with indicators over trees. Forthcoming in Mathematical Programming, 2025

    2025

  7. [15]

    Bienstock

    D. Bienstock. Computational study of a family of mixed-integer quadratic programming problems. Mathematical Programming, 74:121–140, 1996

    1996

  8. [16]

    Bienstock and T

    D. Bienstock and T. Chen. Solving convex QPs with structured sparsity under indicator conditions. arXiv preprint arXiv:2411.11722 , 2024

    2024 arXiv

  9. [17]

    Bixby and E

    R. Bixby and E. Rothberg. Progress in computational mixed integer programming–a look back from the other side of the tipping point. Annals of Operations Research, 149(1):37, 2007

    2007

  10. [18]

    R. E. Bixby. A brief history of linear and mixed-integer programming computation. Documenta Math- ematica, (2012):107–121, 2012

    2012

  11. [19]

    J. P. Brooks. Support vector machines with the ramp loss and the hard margin loss. Operations Research, 59(2):467–479, 2011. 31

    2011

  12. [20]

    Ceria and J

    S. Ceria and J. Soares. Convex programming for disjunctive convex optimization. Mathematical Pro- gramming, 86(3):595–614, 1999

    1999

  13. [21]

    Chang, C.-J

    K.-W. Chang, C.-J. Hsieh, and C.-J. Lin. Coordinate descent method for large-scale l2-loss linear support vector machines. Journal of Machine Learning Research , 9(7), 2008

    2008

  14. [22]

    K. L. Cheung, P. M. Ten Klooster, C. Smit, H. de Vries, and M. E. Pieterse. The impact of non-response bias due to sampling in public health studies: A comparison of voluntary versus mandatory recruitment in a dutch national survey on adolescent health. BMC public health , 17:...

    2017

  15. [23]

    Cortes and V

    C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20:273–297, 1995

    1995

  16. [24]

    Cozad, N

    A. Cozad, N. V. Sahinidis, and D. C. Miller. Learning surrogate models for simulation-based optimiza- tion. AIChE Journal, 60(6):2211–2227, 2014

    2014

  17. [25]

    Cozad, N

    A. Cozad, N. V. Sahinidis, and D. C. Miller. A combined first-principles and data-driven approach to model building. Computers & Chemical Engineering , 73:116–127, 2015

    2015

  18. [26]

    Das and D

    A. Das and D. Kempe. Algorithms for subset selection in linear regression. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages 45–54, 2008

    2008

  19. [27]

    De Rosa and A

    A. De Rosa and A. Khajavirad. Explicit convex hull description of bivariate quadratic sets with indicator variables. Mathematical Programming, pages 1–43, 2024

    2024

  20. [28]

    Dedieu, H

    A. Dedieu, H. Hazimeh, and R. Mazumder. Learning sparse classifiers: Continuous and mixed integer optimization perspectives. The Journal of Machine Learning Research , 22(1):6008–6054, 2021

    2021

  21. [29]

    S. S. Dey, R. Mazumder, and G. Wang. A convex integer programming approach for optimal sparse pca. 2018

    2018

  22. [30]

    Deza and A

    A. Deza and A. Atamt¨ urk. Safe screening for logistic regression with ℓ0-ℓ2 regularization. In KDIR, pages 119–126, 2022

    2022

  23. [31]

    H. Dong, K. Chen, and J. Linderoth. Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. arXiv preprint arXiv:1510.06083 , 2015

    2015 arXiv

  24. [32]

    Dua and C

    D. Dua and C. Graff. UCI machine learning repository, 2017. URL http://archive.ics.uci.edu/ml

    2017

  25. [33]

    M. A. Duran and I. E. Grossmann. An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming, 36(3):307–339, 1986

    1986

  26. [34]

    Fogliato, A

    R. Fogliato, A. Chouldechova, and M. G’Sell. Fairness evaluation in presence of biased noisy labels. In International conference on artificial intelligence and statistics , pages 2325–2336. PMLR, 2020

    2020

  27. [35]

    Frangioni and C

    A. Frangioni and C. Gentile. Perspective cuts for a class of convex 0–1 mixed integer programs. Math- ematical Programming, 106(2):225–236, 2006

    2006

  28. [36]

    Frangioni and C

    A. Frangioni and C. Gentile. SDP diagonalizations and perspective cuts for a class of nonseparable MIQP. Operations Research Letters, 35(2):181–185, 2007

    2007

  29. [37]

    Frangioni, F

    A. Frangioni, F. Furini, and C. Gentile. Approximated perspective relaxations: A project and lift approach. Computational Optimization and Applications , 63:705–735, 2016. 32

    2016

  30. [38]

    Frangioni, C

    A. Frangioni, C. Gentile, and J. Hungerford. Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Mathematics of Operations Research , 45(1):15–33, 2020

    2020

  31. [39]

    Fr´ enay and M

    B. Fr´ enay and M. Verleysen. Classification in the presence of label noise: a survey. IEEE Transactions on Neural Networks and Learning Systems , 25(5):845–869, 2013

    2013

  32. [40]

    Ghosh, N

    A. Ghosh, N. Manwani, and P. Sastry. Making risk minimization tolerant to label noise.Neurocomputing, 160:93–107, 2015

    2015

  33. [41]

    A. G´ omez. Outlier detection in time series via mixed-integer conic quadratic optimization. SIAM Journal on Optimization , 31(3):1897–1925, 2021

    1925

  34. [42]

    G´ omez and J

    A. G´ omez and J. Neto. Outlier detection in regression: conic quadratic formulations. arXiv preprint arXiv:2307.05975, 2023

    2023 arXiv

  35. [43]

    G´ omez and O

    A. G´ omez and O. A. Prokopyev. A mixed-integer fractional optimization approach to best subset selection. INFORMS Journal on Computing , 33(2):551–565, 2021

    2021

  36. [44]

    Gomez, S

    A. Gomez, S. Han, and L. Lozano. Real-time solution of quadratic optimization problems with banded matrices and indicator variables. arXiv preprint arXiv:2405.03051 , 2024

    2024 arXiv

  37. [45]

    W. Guan, A. Gray, and S. Leyffer. Mixed-integer support vector machine. In NIPS workshop on optimization for machine learning , 2009

    2009

  38. [46]

    Guerdan, A

    L. Guerdan, A. Coston, Z. S. Wu, and K. Holstein. Ground (less) truth: A causal framework for proxy labels in human-algorithm decision-making. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 688–704, 2023

    2023

  39. [47]

    G¨ unl¨ uk and J

    O. G¨ unl¨ uk and J. Linderoth. Perspective reformulations of mixed integer nonlinear programs with indicator variables. Mathematical Programming, 124:183–205, 2010

    2010

  40. [48]

    G¨ unl¨ uk and Y

    O. G¨ unl¨ uk and Y. Pochet. Mixing mixed-integer inequalities.Mathematical Programming, 90:429–457, 2001

    2001

  41. [49]

    Han and A

    S. Han and A. G´ omez. Compact extended formulations for low-rank functions with indicator variables. Mathematics of Operations Research, 2024

    2024

  42. [50]

    S. Han, A. G´ omez, and A. Atamt¨ urk. 2× 2-convexifications for convex quadratic optimization with indicator variables. Mathematical Programming, 202(1):95–134, 2023

    2023

  43. [51]

    Hazimeh and R

    H. Hazimeh and R. Mazumder. Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms. Operations Research, 68(5):1517–1537, 2020

    2020

  44. [52]

    Hazimeh, R

    H. Hazimeh, R. Mazumder, and A. Saab. Sparse regression at scale: Branch-and-bound rooted in first-order optimization. Mathematical Programming, 196(1-2):347–388, 2022

    2022

  45. [53]

    Insolia, A

    L. Insolia, A. Kenney, F. Chiaromonte, and G. Felici. Simultaneous feature selection and outlier detection with optimality guarantees. Biometrics, 78(4):1592–1603, 2022. 33

    2022

  46. [54]

    Jammal, S

    M. Jammal, S. Canu, and M. Abdallah. Robust and sparse support vector machines via mixed integer programming. In International Conference on Machine Learning, Optimization, and Data Science , pages 572–585. Springer, 2020

    2020

  47. [55]

    Kılın¸ c-Karzan, S

    F. Kılın¸ c-Karzan, S. K¨ u¸ c¨ ukyavuz, and D. Lee. Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens. arXiv preprint arXiv:1910.01353 , 2019

    1910 arXiv

  48. [56]

    J. Kim, M. Tawarmalani, and J.-P. P. Richard. Convexification of permutation-invariant sets and an application to sparse principal component analysis. Mathematics of Operations Research , 47(4):2547– 2584, 2022

    2022

  49. [57]

    K¨ u¸ c¨ ukyavuz

    S. K¨ u¸ c¨ ukyavuz. On mixing sets arising in chance-constrained programming.Mathematical Programming, 132(1):31–56, 2012

    2012

  50. [58]

    I. G. Lee, S. W. Yoon, and D. Won. A mixed integer linear programming support vector machine for cost-effective group feature selection: branch-cut-and-price approach. European Journal of Operational Research, 299(3):1055–1068, 2022

    2022

  51. [59]

    J. Lee, A. G´ omez, and A. Atamt¨ urk. Convexification of multi-period quadratic programs with indicators. arXiv preprint arXiv:2412.17178 , 2024

    2024 arXiv

  52. [60]

    J. Lee, H. Im, and A. Atamt¨ urk. Strong formulations for hybrid system control. arXiv preprint arXiv:2412.11541, 2024

    2024 arXiv

  53. [61]

    Lee and O

    Y.-J. Lee and O. L. Mangasarian. Ssvm: A smooth support vector machine for classification. Compu- tational optimization and Applications , 20:5–22, 2001

    2001

  54. [62]

    Li and W

    Y. Li and W. Xie. Exact and approximation algorithms for sparse principal component analysis. IN- FORMS Journal on Computing , 2024

    2024

  55. [63]

    P. Liu, S. Fattahi, A. G´ omez, and S. K¨ u¸ c¨ ukyavuz. A graph-based decomposition method for convex quadratic optimization with indicators. Mathematical Programming, 200(2):669–701, 2023

    2023

  56. [64]

    P. Liu, A. Atamt¨ urk, A. G´ omez, and S. K¨ u¸ c¨ ukyavuz. Polyhedral analysis of quadratic optimization problems with stieltjes matrices and indicators. arXiv preprint arXiv:2404.04236 , 2024

    2024 arXiv

  57. [65]

    Luedtke, S

    J. Luedtke, S. Ahmed, and G. L. Nemhauser. An integer programming approach for linear programs with probabilistic constraints. Mathematical Programming, 122(2):247–272, 2010

    2010

  58. [66]

    Malossini, E

    A. Malossini, E. Blanzieri, R. T. Ng, et al. Detecting potential labeling errors in microarrays by data perturbation. Bioinformatics, 22(17):2114, 2006

    2006

  59. [67]

    Manwani and P

    N. Manwani and P. Sastry. Noise tolerance under risk minimization. IEEE Transactions on Cybernetics, 43(3):1146–1151, 2013

    2013

  60. [68]

    Mason, J

    L. Mason, J. Baxter, P. Bartlett, and M. Frean. Boosting algorithms as gradient descent. Advances in Neural Information Processing Systems, 12, 1999

    1999

  61. [69]

    Miyashiro and Y

    R. Miyashiro and Y. Takano. Subset selection by Mallows’ CP: A mixed integer programming approach. Expert Systems with Applications , 42(1):325–331, 2015. 34

    2015

  62. [70]

    Nguyen and S

    T. Nguyen and S. Sanner. Algorithms for direct 0–1 loss optimization in binary classification. In International conference on machine learning , pages 1085–1093. PMLR, 2013

    2013

  63. [71]

    Obermeyer, B

    Z. Obermeyer, B. Powers, C. Vogeli, and S. Mullainathan. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464):447–453, 2019

    2019

  64. [72]

    Ping and F

    L. Ping and F. Y. Yu. Criteria for copositive matrices of order four. Linear Algebra and its Applications, 194:109–124, 1993

    1993

  65. [73]

    F. Qiu, S. Ahmed, S. S. Dey, and L. A. Wolsey. Covering linear programming with violations.INFORMS Journal on Computing , 26(3):531–546, 2014

    2014

  66. [74]

    T. Sato, Y. Takano, R. Miyashiro, and A. Yoshise. Feature subset selection for logistic regression via mixed integer optimization. Computational Optimization and Applications , 64:865–880, 2016

    2016

  67. [75]

    Shafiee and F

    S. Shafiee and F. Kılın¸ c-Karzan. Constrained optimization of rank-one functions with indicator variables. Mathematical Programming, pages 1–47, 2024

    2024

  68. [76]

    X. Shen, G. C. Tseng, X. Zhang, and W. H. Wong. On ψ-learning. Journal of the American Statistical Association, 98(463):724–734, 2003

    2003

  69. [77]

    Z.-J. M. Shen, C. Coullard, and M. S. Daskin. A joint location-inventory model. Transportation Science, 37:40–55, 2003

    2003

  70. [78]

    Q. Song, W. Hu, and W. Xie. Robust support vector machine with bullet hole image classification. IEEE transactions on systems, man, and cybernetics, part C (applications and reviews) , 32(4):440–448, 2002

    2002

  71. [79]

    Y. Song, J. R. Luedtke, and S. K¨ u¸ c¨ ukyavuz. Chance-constrained binary packing problems.INFORMS Journal on Computing , 26(4):735–747, 2014

    2014

  72. [80]

    Ustun and C

    B. Ustun and C. Rudin. Supersparse linear integer models for optimized medical scoring systems. Machine Learning, 102:349–391, 2016

    2016

  73. [81]

    Ustun and C

    B. Ustun and C. Rudin. Learning optimized risk scores. Journal of Machine Learning Research , 20 (150):1–75, 2019

    2019

  74. [82]

    H. Wang, Y. Shao, S. Zhou, C. Zhang, and N. Xiu. Support vector machine classifier via l0/1 soft-margin loss. IEEE Transactions on Pattern Analysis and Machine Intelligence , 44(10):7253–7265, 2021

    2021

  75. [83]

    L. Wei, A. G´ omez, and S. K¨ u¸ c¨ ukyavuz. On the convexification of constrained quadratic optimization problems with indicator variables. In International Conference on Integer Programming and Combina- torial Optimization, pages 433–447. Springer, 2020

    2020

  76. [84]

    L. Wei, A. G´ omez, and S. K¨ u¸ c¨ ukyavuz. Ideal formulations for constrained convex optimization problems with indicator variables. Mathematical Programming, 2021

    2021

  77. [85]

    L. Wei, A. Atamt¨ urk, A. G´ omez, and S. K¨ u¸ c¨ ukyavuz. On the convex hull of convex quadratic optimiza- tion problems with indicators. Mathematical Programming, 204(1):703–737, 2024

    2024

  78. [86]

    Z. T. Wilson and N. V. Sahinidis. The ALAMO approach to machine learning. Computers & Chemical Engineering, 106:785–795, 2017. 35

    2017

  79. [87]

    Wu and Y

    Y. Wu and Y. Liu. Robust truncated hinge loss support vector machines. Journal of the American Statistical Association, 102(479):974–983, 2007

    2007

  80. [88]

    Xie and S

    W. Xie and S. Ahmed. On quantile cuts and their closure for chance constrained optimization problems. Mathematical Programming, 172:621–646, 2018

    2018

  81. [89]

    Xie and X

    W. Xie and X. Deng. Scalable algorithms for the sparse ridge regression. SIAM Journal on Optimization, 30(4):3359–3386, 2020

    2020

  82. [90]

    G. Xu, Z. Cao, B.-G. Hu, and J. C. Principe. Robust support vector machines based on the rescaled hinge loss function. Pattern Recognition, 63:139–148, 2017

    2017

  83. [91]

    J. Zhao, T. Stockwell, and S. Macdonald. Non–response bias in alcohol and drug population surveys. Drug and Alcohol Review , 28(6):648–657, 2009

    2009

  84. [92]

    M. Zhao, K. Huang, and B. Zeng. A polyhedral study on chance constrained program with random right-hand side. Mathematical Programming, 166:19–64, 2017

    2017

  85. [93]

    Zheng, X

    X. Zheng, X. Sun, and D. Li. Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach. INFORMS Journal on Computing, 26(4):690–703, 2014

    2014

  86. [94]

    Zioutas and A

    G. Zioutas and A. Avramidis. Deleting outliers in robust regression with mixed integer programming. Acta Mathematicae Applicatae Sinica, 21(2):323–334, 2005

    2005

  87. [95]

    Zioutas, L

    G. Zioutas, L. Pitsoulis, and A. Avramidis. Quadratic mixed integer programming and support vectors for deleting outliers in robust regression. Annals of Operations Research, 166(1):339–353, 2009. A Proof of Proposition 4.(a) For convenience, we repeat the proposition to be pr...

    2009

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.