Exact Augmented Lagrangian Duality for Nonconvex Mixed-Integer Nonlinear Optimization

Jointly with Martin Schmidt

Year: 2024

Abstract: In the context of mixed-integer nonlinear problems (MINLPs), it is well-known that strong duality does not hold in general if the standard Lagrangian dual is used. Hence, we consider the augmented Lagrangian dual (ALD), which adds a nonlinear penalty function to the classic Lagrangian function. For this setup, we study conditions under which the ALD leads to a zero duality gap for general MINLPs. In particular, under mild assumptions and for a large class of penalty functions, we show that the ALD yields zero duality gaps if the penalty parameter goes to infinity. If the penalty function is a norm, we also show that the ALD leads to zero duality gaps for a finite penalty parameter. Moreover, we show that such a finite penalty parameter can be computed in polynomial time in the mixed-integer linear case. This generalizes the recent results on linearly constrained mixed-integer problems by Bhardwaj et al. (2024), Boland and Eberhard (2014), Feizollahi et al. (2016), and Gu et al. (2020).

Cite as:

@misc{lefebvre2024exact,
  title={Exact Augmented Lagrangian Duality for Nonconvex Mixed-Integer Nonlinear Optimization},
  author={Henri Lefebvre and Martin Schmidt},
  year={2024},
  archivePrefix={Optimization Online},
  url={https://optimization-online.org/?p=27046}
}

Open Access

Optimization Online

Open Data

We did not use any data.

Open Methodology

We did not do data manipulation.

Open Source

We did not use any code.

Open Educational Resources