Exact augmented Lagrangian duality for mixed integer linear programming (Q507329): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
This paper deals with mixed integer linear programming problems of the form \[ z^{IP}:=\inf \left\{ c^{T}x:Ax=b,x\in X\right\}, \] where \(X=\left\{ x\in \mathbb{Z}^{p}\times \mathbb{R}^{q}:Ex\leq f\right\} ,\) with \(p+q=n,\) \(A\in \mathbb{Q}^{m\times n},\) \(E\in \mathbb{Q}^{r\times n},\) \( b\in \mathbb{Q}^{m},\) and \(f\in \mathbb{Q}^{r}.\;\)The linear system \(Ax=b\) contains the complicating constraints to be dualized. The augmented Lagrangian dual has the form \[ z_{\rho }^{LD_{+}}:=\sup_{\lambda \in \mathbb{R}^{n}}\inf_{x\in X}\left\{ c^{T}x+\lambda ^{T}\left( b-Ax\right) +\rho \psi \left( b-Ax\right) \right\}, \] where the \textit{penalty coefficient} \(\rho \) is a given positive scalar and the \textit{augmenting function} \(\psi \) satisfies \(\psi \left( 0_{m}\right) =0 \) and \(\psi \left( u\right) >0\) for all \(u\neq 0_{m}.\) The purpose of the summand \(\rho \psi \left( b-Ax\right) \) is to reduce the duality gap in the non-convex setting. Under certain conditions, depending on the choice of \( \psi ,\) a zero duality gap can be reached asymptotically by making \(\rho \longrightarrow +\infty \) or even it can be attained by taking a sufficient large \(\rho ,\) in which case \(z_{\rho }^{LD_{+}}\) is said to be \textit{exact}. In this paper, inspired in [\textit{N. L. Boland} and \textit{A. C. Eberhard}, Math. Program. 150, No. 2 (A), 491--509 (2015; Zbl 1346.90607), Proposition 3], the authors assume that \(z^{IP}\in \mathbb{R}\)\ and \(\psi \) belongs to the class of the so-called non-negative level bounded augmenting functions. The main contributions of the paper are improvements of results in the inspiring paper: 1. It is shown that \(z_{\rho }^{LD_{+}}\) can be seen as a classical Lagrangian dual in some lifted space. 2. A new proof is given of the known fact that the zero duality gap can be reached asymptotically. 3. It is proven, without assuming that \(X\) is a bounded subset of \(\mathbb{Z} ^{n},\) that \(z_{\rho }^{LD_{+}}\) is exact when \(\psi \) is an arbitrary norm. 4. An example of \(z_{\rho }^{LD_{+}}\)\ is given showing that a quadratic augmenting function is not able to close the duality gap for any finite penalty coefficient. | |||
Property / review text: This paper deals with mixed integer linear programming problems of the form \[ z^{IP}:=\inf \left\{ c^{T}x:Ax=b,x\in X\right\}, \] where \(X=\left\{ x\in \mathbb{Z}^{p}\times \mathbb{R}^{q}:Ex\leq f\right\} ,\) with \(p+q=n,\) \(A\in \mathbb{Q}^{m\times n},\) \(E\in \mathbb{Q}^{r\times n},\) \( b\in \mathbb{Q}^{m},\) and \(f\in \mathbb{Q}^{r}.\;\)The linear system \(Ax=b\) contains the complicating constraints to be dualized. The augmented Lagrangian dual has the form \[ z_{\rho }^{LD_{+}}:=\sup_{\lambda \in \mathbb{R}^{n}}\inf_{x\in X}\left\{ c^{T}x+\lambda ^{T}\left( b-Ax\right) +\rho \psi \left( b-Ax\right) \right\}, \] where the \textit{penalty coefficient} \(\rho \) is a given positive scalar and the \textit{augmenting function} \(\psi \) satisfies \(\psi \left( 0_{m}\right) =0 \) and \(\psi \left( u\right) >0\) for all \(u\neq 0_{m}.\) The purpose of the summand \(\rho \psi \left( b-Ax\right) \) is to reduce the duality gap in the non-convex setting. Under certain conditions, depending on the choice of \( \psi ,\) a zero duality gap can be reached asymptotically by making \(\rho \longrightarrow +\infty \) or even it can be attained by taking a sufficient large \(\rho ,\) in which case \(z_{\rho }^{LD_{+}}\) is said to be \textit{exact}. In this paper, inspired in [\textit{N. L. Boland} and \textit{A. C. Eberhard}, Math. Program. 150, No. 2 (A), 491--509 (2015; Zbl 1346.90607), Proposition 3], the authors assume that \(z^{IP}\in \mathbb{R}\)\ and \(\psi \) belongs to the class of the so-called non-negative level bounded augmenting functions. The main contributions of the paper are improvements of results in the inspiring paper: 1. It is shown that \(z_{\rho }^{LD_{+}}\) can be seen as a classical Lagrangian dual in some lifted space. 2. A new proof is given of the known fact that the zero duality gap can be reached asymptotically. 3. It is proven, without assuming that \(X\) is a bounded subset of \(\mathbb{Z} ^{n},\) that \(z_{\rho }^{LD_{+}}\) is exact when \(\psi \) is an arbitrary norm. 4. An example of \(z_{\rho }^{LD_{+}}\)\ is given showing that a quadratic augmenting function is not able to close the duality gap for any finite penalty coefficient. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Miguel Angel Goberna / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C11 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C27 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C46 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C59 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6680635 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
mixed integer linear programming | |||
Property / zbMATH Keywords: mixed integer linear programming / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Lagrangian duality | |||
Property / zbMATH Keywords: Lagrangian duality / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
penalty functions | |||
Property / zbMATH Keywords: penalty functions / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10107-016-1012-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2336243738 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Penalty/Barrier Multiplier Methods for Convex Programming Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3690580 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4830373 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The value function of a mixed integer program: I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The value function of a mixed integer program. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The value function of an integer program / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the augmented Lagrangian dual for integer programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Duality and exact penalization for general augmented Lagrangians / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The exact penalty map for nonsmooth and nonconvex optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the absence of duality gap for Lagrange-type functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Abstract Convexity and Augmented Lagrangians / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Calmness and Exact Penalization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Exact Penalization Viewpoint of Constrained Optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A New Approach to Lagrange Multipliers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4178782 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Unified Augmented Lagrangian Approach to Duality and Exact Penalization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mathematical Programs with Equilibrium Constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the existence of optimal solutions to integer and mixed-integer programming problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Integer and mixed-integer programming models: General properties / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A geometric framework for nonconvex optimization duality using augmented Lagrangian functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Separation of Nonconvex Sets with General Augmenting Functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Variational Analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Penalty functions with a small penalty parameter / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decreasing Functions with Applications to Penalization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Zero Duality Gap Property and Lower Semicontinuity of the Perturbation Function / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lagrange-type functions in constrained non-convex optimization. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonlinear Augmented Lagrangian and Duality Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4943600 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Nonlinear Lagrangian Approach to Constrained Optimization Problems / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:52, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Exact augmented Lagrangian duality for mixed integer linear programming |
scientific article |
Statements
Exact augmented Lagrangian duality for mixed integer linear programming (English)
0 references
3 February 2017
0 references
This paper deals with mixed integer linear programming problems of the form \[ z^{IP}:=\inf \left\{ c^{T}x:Ax=b,x\in X\right\}, \] where \(X=\left\{ x\in \mathbb{Z}^{p}\times \mathbb{R}^{q}:Ex\leq f\right\} ,\) with \(p+q=n,\) \(A\in \mathbb{Q}^{m\times n},\) \(E\in \mathbb{Q}^{r\times n},\) \( b\in \mathbb{Q}^{m},\) and \(f\in \mathbb{Q}^{r}.\;\)The linear system \(Ax=b\) contains the complicating constraints to be dualized. The augmented Lagrangian dual has the form \[ z_{\rho }^{LD_{+}}:=\sup_{\lambda \in \mathbb{R}^{n}}\inf_{x\in X}\left\{ c^{T}x+\lambda ^{T}\left( b-Ax\right) +\rho \psi \left( b-Ax\right) \right\}, \] where the \textit{penalty coefficient} \(\rho \) is a given positive scalar and the \textit{augmenting function} \(\psi \) satisfies \(\psi \left( 0_{m}\right) =0 \) and \(\psi \left( u\right) >0\) for all \(u\neq 0_{m}.\) The purpose of the summand \(\rho \psi \left( b-Ax\right) \) is to reduce the duality gap in the non-convex setting. Under certain conditions, depending on the choice of \( \psi ,\) a zero duality gap can be reached asymptotically by making \(\rho \longrightarrow +\infty \) or even it can be attained by taking a sufficient large \(\rho ,\) in which case \(z_{\rho }^{LD_{+}}\) is said to be \textit{exact}. In this paper, inspired in [\textit{N. L. Boland} and \textit{A. C. Eberhard}, Math. Program. 150, No. 2 (A), 491--509 (2015; Zbl 1346.90607), Proposition 3], the authors assume that \(z^{IP}\in \mathbb{R}\)\ and \(\psi \) belongs to the class of the so-called non-negative level bounded augmenting functions. The main contributions of the paper are improvements of results in the inspiring paper: 1. It is shown that \(z_{\rho }^{LD_{+}}\) can be seen as a classical Lagrangian dual in some lifted space. 2. A new proof is given of the known fact that the zero duality gap can be reached asymptotically. 3. It is proven, without assuming that \(X\) is a bounded subset of \(\mathbb{Z} ^{n},\) that \(z_{\rho }^{LD_{+}}\) is exact when \(\psi \) is an arbitrary norm. 4. An example of \(z_{\rho }^{LD_{+}}\)\ is given showing that a quadratic augmenting function is not able to close the duality gap for any finite penalty coefficient.
0 references
mixed integer linear programming
0 references
Lagrangian duality
0 references
penalty functions
0 references
0 references
0 references
0 references