pith. sign in

arxiv: 1907.00920 · v1 · pith:5MPKVYGTnew · submitted 2019-07-01 · 🧮 math.OC

Exact Augmented Lagrangian Duality for Mixed Integer Quadratic Programming

Xiaoyi Gu , Shabbir Ahmed , Santanu S. Dey This is my paper

Pith reviewed 2026-05-25 11:33 UTC · model grok-4.3

classification 🧮 math.OC
keywords mixed integer quadratic programmingaugmented Lagrangianduality gappenalty weightnorm penalty
0
0 comments X

The pith

Finite norm penalties yield zero duality gap for mixed integer quadratic programs

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

The paper proves that the augmented Lagrangian dual for mixed integer quadratic programming reaches zero duality gap asymptotically as the penalty weight goes to infinity under mild conditions on the penalty function. When the penalty is any norm, a finite weight is sufficient to close the gap. A polynomial upper bound on this weight is established. This allows exact dual solutions without infinite penalties.

Core claim

For MIQP, the ALD with a norm penalty function has zero duality gap at a finite penalty weight that is polynomially bounded.

What carries the argument

Augmented Lagrangian dual with weighted nonlinear penalty on dualized constraints

Load-bearing premise

The penalty function meets the mild conditions needed for the asymptotic zero-gap result.

What would settle it

A counterexample MIQP instance where the duality gap stays positive for arbitrarily large finite weights with a norm penalty.

read the original abstract

Mixed integer quadratic programming (MIQP) is the problem of minimizing a convex quadratic function over mixed integer points in a rational polyhedron. This paper focuses on the augmented Lagrangian dual (ALD) for MIQP. ALD augments the usual Lagrangian dual with a weighted nonlinear penalty on the dualized constraints. We first prove that ALD will reach a zero duality gap asymptotically as the weight on the penalty goes to infinity under some mild conditions on the penalty function. We next show that a finite penalty weight is enough for a zero gap when we use any norm as the penalty function. Finally, we prove a polynomially bound on the weight on the penalty term to obtain a zero gap.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper establishes three results on the augmented Lagrangian dual (ALD) for mixed-integer quadratic programming (MIQP) over rational polyhedra with convex quadratic objectives: (i) asymptotic zero duality gap as the penalty weight tends to infinity, under mild conditions on the penalty function; (ii) zero duality gap at a finite penalty weight when the penalty is any norm; (iii) a polynomial bound on the minimal such weight.

Significance. If the proofs are correct, the results supply exactness guarantees and explicit parameter bounds for ALD applied to MIQP, strengthening the theoretical basis for dual methods on this important class. The polynomial bound, if truly polynomial in the input size, is a notable strengthening over mere existence results. The manuscript is credited for handling the mixed-integer setting and for separating the asymptotic, finite-weight, and bounded-weight claims.

major comments (2)
  1. [asymptotic result statement] The mild conditions required for the asymptotic zero-gap result are referenced but never stated explicitly in the theorem (see the paragraph beginning 'We first prove that ALD will reach a zero duality gap asymptotically'). This is load-bearing for claims (ii) and (iii), because it is impossible to verify whether every norm satisfies those conditions without the precise list.
  2. [polynomial bound result] The polynomial bound claim (final sentence of the abstract) does not specify the variables in which the bound is polynomial (bit length of the data, dimension, number of integer variables, etc.). Without this, it is impossible to assess whether the bound is practically useful or merely polynomial in an exponential quantity.
minor comments (1)
  1. [abstract] The abstract uses 'polynomially bound' where 'polynomial bound' is intended.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major points below and have revised the manuscript accordingly to improve clarity.

read point-by-point responses

  1. Referee: [asymptotic result statement] The mild conditions required for the asymptotic zero-gap result are referenced but never stated explicitly in the theorem (see the paragraph beginning 'We first prove that ALD will reach a zero duality gap asymptotically'). This is load-bearing for claims (ii) and (iii), because it is impossible to verify whether every norm satisfies those conditions without the precise list.

    Authors: We agree that the mild conditions on the penalty function should be stated explicitly within the theorem statement itself rather than only in the surrounding text. In the revised version we have added the precise list of conditions directly to the theorem. However, claims (ii) and (iii) do not rely on those mild conditions; they are established separately by exploiting the specific properties of norm penalties (positive homogeneity and the triangle inequality) and therefore hold independently of the asymptotic result. revision: yes

  2. Referee: [polynomial bound result] The polynomial bound claim (final sentence of the abstract) does not specify the variables in which the bound is polynomial (bit length of the data, dimension, number of integer variables, etc.). Without this, it is impossible to assess whether the bound is practically useful or merely polynomial in an exponential quantity.

    Authors: We thank the referee for this observation. The bound we prove is polynomial in the bit length of the input data, the ambient dimension, and the number of integer variables. We have updated both the abstract and the statement of the relevant theorem to make these variables explicit. The proof proceeds by bounding the size of a suitable dual multiplier via standard results on the geometry of rational polyhedra and the Lipschitz constant of the quadratic objective, all of which are polynomial in the quantities listed above. revision: yes

Circularity Check

0 steps flagged

No circularity: self-contained mathematical proofs

full rationale

The paper presents a sequence of mathematical proofs establishing asymptotic zero duality gap under mild conditions on the penalty, followed by finite-weight exactness for norms and a polynomial bound on the weight. These are derived from the problem structure (convex quadratic over rational polyhedron) and standard duality arguments without any data fitting, self-referential definitions, or reduction of claims to fitted inputs. No load-bearing self-citations or ansatzes imported from prior author work appear in the provided abstract or claims; the derivation chain relies on external mathematical facts about polyhedra and norms rather than internal redefinitions. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard MIQP assumptions (convex quadratic, rational polyhedron) plus unspecified mild conditions on the penalty function for the asymptotic result.

axioms (1)
  • domain assumption mild conditions on the penalty function
    Invoked for the asymptotic zero-gap result in the first claim.

pith-pipeline@v0.9.0 · 5641 in / 1029 out tokens · 23295 ms · 2026-05-25T11:33:03.290752+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    D. P. Bertsekas, A. Nedi, A. E. Ozdaglar, et al. , Convex analysis and optimization , Athena Scientific, 2003

    work page 2003

  2. [2]

    Borosh and L

    I. Borosh and L. B. Treybig , Bounds on positive integral solutions of linear diophantin e equations, Proceedings of the American Mathematical Society, 55 (197 6), pp. 299–304, doi:10.2307/2041711

    work page doi:10.2307/2041711

  3. [3]

    S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al. , Distributed optimization and statistical learning via the alternating direction method of multipliers , Foundations and Trends R⃝ in Machine learning, 3 (2011), pp. 1–122, doi:10.1561/2200000016

    work page doi:10.1561/2200000016 2011

  4. [4]

    R. S. Burachik, A. N. Iusem, and J. G. Melo , Duality and exact penalization for gen- eral augmented lagrangians , Journal of optimization theory and applications, 147 (201 0), pp. 125–140, doi:10.1007/s10957-010-9711-4

    work page doi:10.1007/s10957-010-9711-4

  5. [5]

    R. S. Burachik, X. Yang, and Y. Zhou , Existence of augmented lagrange multipliers for semi-infinite programming problems , Journal of optimization theory and applications, 173 (2017), pp. 471–503, doi:10.1007/s10957-017-1091-6

    work page doi:10.1007/s10957-017-1091-6 2017

  6. [6]

    J. V. Burke , An exact penalization viewpoint of constrained optimizati on, SIAM Journal on control and optimization, 29 (1991), pp. 968–998, doi:10.1137/0329054

    work page doi:10.1137/0329054 1991

  7. [7]

    Del Pia, S

    A. Del Pia, S. S. Dey, and M. Molinaro , Mixed-integer quadratic programming is in np , Mathematical Programming, 162 (2017), pp. 225–240, doi:10.1007/s10107-016-1036-0

    work page doi:10.1007/s10107-016-1036-0 2017

  8. [8]

    S. S. Dey and D. A. Mor ´an R. , Some properties of convex hulls of integer points con- tained in general convex sets , Mathematical Programming, 141 (2013), pp. 507–526, doi:10.1007/s10107-012-0538-7

    work page doi:10.1007/s10107-012-0538-7 2013

  9. [9]

    M. J. Feizollahi, S. Ahmed, and A. Sun , Exact augmented lagrangian duality for mixed integer linear programming , Mathematical Programming, 161 (2017), pp. 365–387, doi:10.1007/s10107-016-1012-8

    work page doi:10.1007/s10107-016-1012-8 2017

  10. [10]

    Huang and X

    X. Huang and X. Yang , A unified augmented lagrangian approach to duality and exact penalization , Mathematics of Operations Research, 28 (2003), pp. 533–55 2, doi:10.1287/moor.28.3.533.16395

    work page doi:10.1287/moor.28.3.533.16395 2003

  11. [11]

    R. R. Meyer , On the existence of optimal solutions to integer and mixed-i nteger programming problems, Mathematical Programming, 7 (1974), pp. 223–235, doi:10.1007/BF01585518

    work page doi:10.1007/bf01585518 1974

  12. [12]

    Moran and B

    D. Moran and B. Kocuk , On subadditive duality for conic mixed-integer programs , arXiv preprint arXiv:1808.10419, (2018)

    work page arXiv 2018

  13. [13]

    D. A. Moran R, S. S. Dey, and J. P. Vielma , A strong dual for conic mixed-integer programs , SIAM Journal on Optimization, 22 (2012), pp. 1136–1150, doi:10.1137/110840868

    work page doi:10.1137/110840868 2012

  14. [14]

    R. T. Rockafellar , Augmented lagrange multiplier functions and duality in non convex pro- gramming, SIAM Journal on Control, 12 (1974), pp. 268–285, doi:10.1137/0312021

    work page doi:10.1137/0312021 1974

  15. [15]

    R. T. Rockafellar and R. J.-B. Wets , Variational analysis , vol. 317, Springer Science & Business Media, 2009, doi:10.1007/978-3-642-02431-3

    work page doi:10.1007/978-3-642-02431-3 2009

  16. [16]

    A. M. Rubinov, X. Huang, and X. Yang , The zero duality gap property and lower semi- continuity of the perturbation function , Mathematics of Operations Research, 27 (2002), pp. 775–791, doi:10.1287/moor.27.4.775.295

    work page doi:10.1287/moor.27.4.775.295 2002

  17. [17]

    Takapoui, N

    R. Takapoui, N. Moehle, S. Boyd, and A. Bemporad , A simple effective heuristic for embedded mixed-integer quadratic programming , International Journal of Control, (2017), pp. 1–11, doi:10.1080/00207179.2017.1316016

    work page doi:10.1080/00207179.2017.1316016 2017

  18. [18]

    S. A. V avasis, Quadratic programming is in np , Information Processing Letters, 36 (1990), pp. 73–77, doi:10.1016/0020-0190(90)90100-C

    work page doi:10.1016/0020-0190(90)90100-c 1990

  19. [19]

    von zur Gathen and M

    J. von zur Gathen and M. Sieveking , A bound on solutions of linear integer equalities and inequalities, Proceedings of the American Mathematical Society, 72 (197 8), pp. 155–158, doi:10.1090/S0002-9939-1978-0500555-0

    work page doi:10.1090/s0002-9939-1978-0500555-0 1978