-
Previous Article
Principal component analysis with drop rank covariance matrix
- JIMO Home
- This Issue
-
Next Article
Computing shadow prices with multiple Lagrange multipliers
Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming
1. | School of Economics and Management, Tongji University, Shanghai 200092, China |
2. | School of Information Science, Changzhou University, Jiangsu 203164, China |
The paper proposes a novel class of quadratically constrained convex reformulations (QCCR) for semi-continuous quadratic programming. We first propose the class of QCCR for the studied problem. Next, we discuss how to polynomially find the best reformulation corresponding with the tightest continuous bound within this class. The properties of the proposed QCCR are then studied. Finally, preliminary computational experiments are conducted to illustrate the effectiveness of the proposed approach.
References:
[1] |
D. Bienstock,
Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), 121-140.
doi: 10.1007/BF02592208. |
[2] |
A. Billionnet and S. Elloumi,
Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem, Mathematical Programming, 109 (2007), 55-68.
doi: 10.1007/s10107-005-0637-9. |
[3] |
A. Billionnet, S. Elloumi and A. Lambert,
Extending the QCR method to general mixed-integer programs, Mathematical Programming, 131 (2012), 381-401.
doi: 10.1007/s10107-010-0381-7. |
[4] |
A. Billionnet, S. Elloumi and M. Plateau,
Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method, Discrete Applied Mathematics, 157 (2009), 1185-1197.
doi: 10.1016/j.dam.2007.12.007. |
[5] |
A. Borghetti, A. Frangioni, F. Lacalandra and C. Nucci,
Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment, IEEE Transactions on Power Systems, 18 (2003), 313-323.
|
[6] |
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.
doi: 10.1017/CBO9780511804441.![]() ![]() ![]() |
[7] |
A. Frangioni and C. Gentile,
Perspective cuts for a class of convex 0–1 mixed integer programs, Mathematical Programming, 106 (2006), 225-236.
doi: 10.1007/s10107-005-0594-3. |
[8] |
A. Frangioni and C. Gentile,
Solving nonlinear single-unit commitment problems with ramping constraints, Operations Research, 54 (2006), 767-775.
doi: 10.1287/opre.1060.0309. |
[9] |
A. Frangioni and C. Gentile,
SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Operations Research Letters, 35 (2007), 181-185.
doi: 10.1016/j.orl.2006.03.008. |
[10] |
A. Frangioni and C. Gentile,
A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes, Operations Research Letters, 37 (2009), 206-210.
doi: 10.1016/j.orl.2009.02.003. |
[11] |
A. Frangioni, C. Gentile, E. Grande and A. Pacifici,
Projected perspective reformulations with applications in design problems, Operations Research, 59 (2011), 1225-1232.
doi: 10.1287/opre.1110.0930. |
[12] |
M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming (web page and software), 2009. |
[13] |
O. Günlük and J. Linderoth,
Perspective reformulations of mixed integer nonlinear programs with indicator variables, Mathematical Programming, 124 (2010), 183-205.
doi: 10.1007/s10107-010-0360-z. |
[14] |
P. Hammer and A. Rubin,
Some remarks on quadratic programming with 0-1 variables, R.I.R.O., 3 (1970), 67-79.
|
[15] |
R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1985.
doi: 10.1017/CBO9780511810817.![]() ![]() ![]() |
[16] |
S. Kazarlis, A. Bakirtzis and V. Petridis,
A genetic algorithm solution to the unit commitment problem, IEEE Transactions on Power Systems, 11 (1996), 83-92.
doi: 10.1109/59.485989. |
[17] |
P. Pardalos and G. Rodgers,
Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144.
doi: 10.1007/BF02247879. |
[18] |
L. Vandenberghe and S. Boyd,
Semidefinite programming, SIAM Review, 38 (1996), 49-95.
doi: 10.1137/1038003. |
[19] |
B. Wu, X. Sun, D. Li and X. Zheng,
Quadratic convex reformulations for semicontinuous quadratic programming, SIAM Journal on Optimization, 27 (2017), 1531-1553.
doi: 10.1137/15M1012232. |
[20] |
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 (2014), 690-703.
doi: 10.1287/ijoc.2014.0592. |
show all references
References:
[1] |
D. Bienstock,
Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), 121-140.
doi: 10.1007/BF02592208. |
[2] |
A. Billionnet and S. Elloumi,
Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem, Mathematical Programming, 109 (2007), 55-68.
doi: 10.1007/s10107-005-0637-9. |
[3] |
A. Billionnet, S. Elloumi and A. Lambert,
Extending the QCR method to general mixed-integer programs, Mathematical Programming, 131 (2012), 381-401.
doi: 10.1007/s10107-010-0381-7. |
[4] |
A. Billionnet, S. Elloumi and M. Plateau,
Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method, Discrete Applied Mathematics, 157 (2009), 1185-1197.
doi: 10.1016/j.dam.2007.12.007. |
[5] |
A. Borghetti, A. Frangioni, F. Lacalandra and C. Nucci,
Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment, IEEE Transactions on Power Systems, 18 (2003), 313-323.
|
[6] |
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.
doi: 10.1017/CBO9780511804441.![]() ![]() ![]() |
[7] |
A. Frangioni and C. Gentile,
Perspective cuts for a class of convex 0–1 mixed integer programs, Mathematical Programming, 106 (2006), 225-236.
doi: 10.1007/s10107-005-0594-3. |
[8] |
A. Frangioni and C. Gentile,
Solving nonlinear single-unit commitment problems with ramping constraints, Operations Research, 54 (2006), 767-775.
doi: 10.1287/opre.1060.0309. |
[9] |
A. Frangioni and C. Gentile,
SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Operations Research Letters, 35 (2007), 181-185.
doi: 10.1016/j.orl.2006.03.008. |
[10] |
A. Frangioni and C. Gentile,
A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes, Operations Research Letters, 37 (2009), 206-210.
doi: 10.1016/j.orl.2009.02.003. |
[11] |
A. Frangioni, C. Gentile, E. Grande and A. Pacifici,
Projected perspective reformulations with applications in design problems, Operations Research, 59 (2011), 1225-1232.
doi: 10.1287/opre.1110.0930. |
[12] |
M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming (web page and software), 2009. |
[13] |
O. Günlük and J. Linderoth,
Perspective reformulations of mixed integer nonlinear programs with indicator variables, Mathematical Programming, 124 (2010), 183-205.
doi: 10.1007/s10107-010-0360-z. |
[14] |
P. Hammer and A. Rubin,
Some remarks on quadratic programming with 0-1 variables, R.I.R.O., 3 (1970), 67-79.
|
[15] |
R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1985.
doi: 10.1017/CBO9780511810817.![]() ![]() ![]() |
[16] |
S. Kazarlis, A. Bakirtzis and V. Petridis,
A genetic algorithm solution to the unit commitment problem, IEEE Transactions on Power Systems, 11 (1996), 83-92.
doi: 10.1109/59.485989. |
[17] |
P. Pardalos and G. Rodgers,
Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144.
doi: 10.1007/BF02247879. |
[18] |
L. Vandenberghe and S. Boyd,
Semidefinite programming, SIAM Review, 38 (1996), 49-95.
doi: 10.1137/1038003. |
[19] |
B. Wu, X. Sun, D. Li and X. Zheng,
Quadratic convex reformulations for semicontinuous quadratic programming, SIAM Journal on Optimization, 27 (2017), 1531-1553.
doi: 10.1137/15M1012232. |
[20] |
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 (2014), 690-703.
doi: 10.1287/ijoc.2014.0592. |
gap(%) | time | nodes | gap(%) | time | nodes | |||||
6 | 18.94 | 141.81 | 3.02 | 1800.00 | 8305 | 0.02 | 727.71 | 533846 | ||
8 | 18.85 | 138.23 | 3.15 | 1800.00 | 7726 | 0.91 | 1753.91 | 1777822 | ||
10 | 18.74 | 110.77 | 3.49 | 1800.00 | 6052 | 1.67 | 1800.00 | 2084181 | ||
12 | 18.35 | 124.77 | 3.52 | 1800.01 | 6100 | 1.86 | 1800.00 | 1941049 | ||
6 | 20.40 | 124.90 | 34.75 | 1800.01 | 11038 | 27.09 | 1800.01 | 2183238 | ||
8 | 17.60 | 126.74 | 33.74 | 1800.01 | 10520 | 28.67 | 1800.01 | 2020237 | ||
10 | 16.68 | 116.01 | 34.17 | 1800.00 | 6104 | 27.61 | 1800.00 | 2612416 | ||
12 | 16.31 | 126.23 | 33.17 | 1800.00 | 8758 | 28.65 | 1800.01 | 2293060 | ||
6 | 18.78 | 129.74 | 58.70 | 1800.01 | 12628 | 50.00 | 1800.01 | 1990354 | ||
8 | 19.52 | 125.89 | 58.91 | 1800.00 | 11850 | 53.12 | 1800.01 | 2428332 | ||
10 | 19.00 | 125.75 | 58.75 | 1800.01 | 10990 | 55.25 | 1800.01 | 1911470 | ||
12 | 17.80 | 128.07 | 58.80 | 1800.00 | 11449 | 55.41 | 1800.01 | 1456779 | ||
6 | 48.31 | 314.17 | 3.01 | 1447.96 | 4793 | 1.97 | 1800.01 | 1357610 | ||
8 | 49.16 | 298.87 | 3.37 | 1445.44 | 3134 | 1.88 | 1441.80 | 1249562 | ||
10 | 48.54 | 320.01 | 3.37 | 1454.77 | 2186 | 2.04 | 1800.01 | 1024344 | ||
12 | 48.83 | 340.17 | 3.32 | 1502.79 | 2077 | 2.37 | 1800.01 | 811791 | ||
6 | 46.55 | 298.79 | 40.90 | 1800.00 | 3321 | 32.88 | 1800.01 | 2435679 | ||
8 | 43.08 | 295.82 | 40.66 | 1800.01 | 3452 | 34.04 | 1800.00 | 2132799 | ||
10 | 39.67 | 301.40 | 40.49 | 1800.00 | 3146 | 34.83 | 1800.00 | 1855355 | ||
12 | 42.47 | 279.30 | 40.24 | 1800.00 | 3648 | 35.28 | 1800.00 | 1701796 | ||
6 | 51.64 | 327.34 | 61.71 | 1800.00 | 4049 | 51.76 | 1800.01 | 1820914 | ||
8 | 51.08 | 294.60 | 61.29 | 1800.00 | 3859 | 53.30 | 1800.00 | 1806775 | ||
10 | 49.27 | 299.97 | 60.96 | 1800.00 | 3157 | 53.70 | 1800.00 | 1491932 | ||
12 | 50.44 | 276.10 | 60.52 | 1800.00 | 3824 | 55.42 | 1800.01 | 1238498 | ||
6 | 106.29 | 655.85 | 4.53 | 1800.00 | 1955 | 2.91 | 1800.00 | 760852 | ||
8 | 104.59 | 606.55 | 4.62 | 1800.00 | 1588 | 3.99 | 1800.01 | 546502 | ||
10 | 111.16 | 558.01 | 4.43 | 1800.01 | 1602 | 3.16 | 1800.00 | 608266 | ||
12 | 104.56 | 604.67 | 4.47 | 1800.00 | 1888 | 3.18 | 1800.00 | 687127 | ||
6 | 110.19 | 603.64 | 35.42 | 1800.00 | 1919 | 31.80 | 1800.01 | 736142 | ||
8 | 105.99 | 524.36 | 35.37 | 1800.00 | 1973 | 31.16 | 1800.00 | 800639 | ||
10 | 112.22 | 498.27 | 35.33 | 1800.00 | 2127 | 32.78 | 1800.01 | 764762 | ||
12 | 104.45 | 531.99 | 35.07 | 1800.01 | 2825 | 31.24 | 1800.00 | 954640 | ||
6 | 112.19 | 650.55 | 65.45 | 1800.00 | 1795 | 60.67 | 1800.01 | 571066 | ||
8 | 117.85 | 574.13 | 65.25 | 1800.01 | 1767 | 60.43 | 1800.00 | 695491 | ||
10 | 115.66 | 634.48 | 65.00 | 1800.00 | 2169 | 60.07 | 1800.00 | 707309 | ||
12 | 121.61 | 560.47 | 64.68 | 1800.00 | 2815 | 60.63 | 1800.00 | 831108 |
gap(%) | time | nodes | gap(%) | time | nodes | |||||
6 | 18.94 | 141.81 | 3.02 | 1800.00 | 8305 | 0.02 | 727.71 | 533846 | ||
8 | 18.85 | 138.23 | 3.15 | 1800.00 | 7726 | 0.91 | 1753.91 | 1777822 | ||
10 | 18.74 | 110.77 | 3.49 | 1800.00 | 6052 | 1.67 | 1800.00 | 2084181 | ||
12 | 18.35 | 124.77 | 3.52 | 1800.01 | 6100 | 1.86 | 1800.00 | 1941049 | ||
6 | 20.40 | 124.90 | 34.75 | 1800.01 | 11038 | 27.09 | 1800.01 | 2183238 | ||
8 | 17.60 | 126.74 | 33.74 | 1800.01 | 10520 | 28.67 | 1800.01 | 2020237 | ||
10 | 16.68 | 116.01 | 34.17 | 1800.00 | 6104 | 27.61 | 1800.00 | 2612416 | ||
12 | 16.31 | 126.23 | 33.17 | 1800.00 | 8758 | 28.65 | 1800.01 | 2293060 | ||
6 | 18.78 | 129.74 | 58.70 | 1800.01 | 12628 | 50.00 | 1800.01 | 1990354 | ||
8 | 19.52 | 125.89 | 58.91 | 1800.00 | 11850 | 53.12 | 1800.01 | 2428332 | ||
10 | 19.00 | 125.75 | 58.75 | 1800.01 | 10990 | 55.25 | 1800.01 | 1911470 | ||
12 | 17.80 | 128.07 | 58.80 | 1800.00 | 11449 | 55.41 | 1800.01 | 1456779 | ||
6 | 48.31 | 314.17 | 3.01 | 1447.96 | 4793 | 1.97 | 1800.01 | 1357610 | ||
8 | 49.16 | 298.87 | 3.37 | 1445.44 | 3134 | 1.88 | 1441.80 | 1249562 | ||
10 | 48.54 | 320.01 | 3.37 | 1454.77 | 2186 | 2.04 | 1800.01 | 1024344 | ||
12 | 48.83 | 340.17 | 3.32 | 1502.79 | 2077 | 2.37 | 1800.01 | 811791 | ||
6 | 46.55 | 298.79 | 40.90 | 1800.00 | 3321 | 32.88 | 1800.01 | 2435679 | ||
8 | 43.08 | 295.82 | 40.66 | 1800.01 | 3452 | 34.04 | 1800.00 | 2132799 | ||
10 | 39.67 | 301.40 | 40.49 | 1800.00 | 3146 | 34.83 | 1800.00 | 1855355 | ||
12 | 42.47 | 279.30 | 40.24 | 1800.00 | 3648 | 35.28 | 1800.00 | 1701796 | ||
6 | 51.64 | 327.34 | 61.71 | 1800.00 | 4049 | 51.76 | 1800.01 | 1820914 | ||
8 | 51.08 | 294.60 | 61.29 | 1800.00 | 3859 | 53.30 | 1800.00 | 1806775 | ||
10 | 49.27 | 299.97 | 60.96 | 1800.00 | 3157 | 53.70 | 1800.00 | 1491932 | ||
12 | 50.44 | 276.10 | 60.52 | 1800.00 | 3824 | 55.42 | 1800.01 | 1238498 | ||
6 | 106.29 | 655.85 | 4.53 | 1800.00 | 1955 | 2.91 | 1800.00 | 760852 | ||
8 | 104.59 | 606.55 | 4.62 | 1800.00 | 1588 | 3.99 | 1800.01 | 546502 | ||
10 | 111.16 | 558.01 | 4.43 | 1800.01 | 1602 | 3.16 | 1800.00 | 608266 | ||
12 | 104.56 | 604.67 | 4.47 | 1800.00 | 1888 | 3.18 | 1800.00 | 687127 | ||
6 | 110.19 | 603.64 | 35.42 | 1800.00 | 1919 | 31.80 | 1800.01 | 736142 | ||
8 | 105.99 | 524.36 | 35.37 | 1800.00 | 1973 | 31.16 | 1800.00 | 800639 | ||
10 | 112.22 | 498.27 | 35.33 | 1800.00 | 2127 | 32.78 | 1800.01 | 764762 | ||
12 | 104.45 | 531.99 | 35.07 | 1800.01 | 2825 | 31.24 | 1800.00 | 954640 | ||
6 | 112.19 | 650.55 | 65.45 | 1800.00 | 1795 | 60.67 | 1800.01 | 571066 | ||
8 | 117.85 | 574.13 | 65.25 | 1800.01 | 1767 | 60.43 | 1800.00 | 695491 | ||
10 | 115.66 | 634.48 | 65.00 | 1800.00 | 2169 | 60.07 | 1800.00 | 707309 | ||
12 | 121.61 | 560.47 | 64.68 | 1800.00 | 2815 | 60.63 | 1800.00 | 831108 |
[1] |
Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871 |
[2] |
Xin Zhao, Jinyan Fan. On subspace properties of the quadratically constrained quadratic program. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1625-1640. doi: 10.3934/jimo.2017010 |
[3] |
Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 |
[4] |
Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075 |
[5] |
Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213 |
[6] |
Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 |
[7] |
Ling Zhang, Xiaoqi Sun. Stability analysis of time-varying delay neural network for convex quadratic programming with equality constraints and inequality constraints. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022035 |
[8] |
Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 |
[9] |
Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129 |
[10] |
René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 |
[11] |
Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 |
[12] |
Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317 |
[13] |
Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319 |
[14] |
Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185 |
[15] |
Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete and Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653 |
[16] |
Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125 |
[17] |
Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543 |
[18] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
[19] |
Yue Qi, Tongyang Liu, Su Zhang, Yu Zhang. Robust Markowitz: Comprehensively maximizing Sharpe ratio by parametric-quadratic programming. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2021235 |
[20] |
Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]