-
Previous Article
A trust-region filter-SQP method for mathematical programs with linear complementarity constraints
- JIMO Home
- This Issue
-
Next Article
Global convergence of an inexact operator splitting method for monotone variational inequalities
Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems
1. | Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606, United States |
2. | Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China |
References:
[1] |
K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization, Math. Program, 91 (2001), 49-52. |
[2] |
A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," 2nd edition, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15, Springer-Verlag, New York, 2003. |
[3] |
A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92 (1996), 310-325.
doi: 10.1016/0377-2217(94)00229-0. |
[4] |
A. Billionnet, A. Faye and E. Soutif, A new upper bound for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 113 (1999), 664-672.
doi: 10.1016/S0377-2217(97)00414-1. |
[5] |
D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Math. Program, 74 (1996), 121-140.
doi: 10.1007/BF02592208. |
[6] |
I. M. Bomze, Global optimization: A quadratic programming perspective, in "Nonlinear Optimization," Lecture Notes in Mathematics, 1989, Springer, Berlin, (2010), 1-53. |
[7] |
I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs, Optimization Letter, 4 (2010), 465-472.
doi: 10.1007/s11590-010-0174-1. |
[8] |
S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120 (2009), 479-495.
doi: 10.1007/s10107-008-0223-z. |
[9] |
S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs," Manuscript, Department of Mathematics, Technische Universitat Darmstadt, Darmstadt, Germany, 2008. |
[10] |
S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 4 (2008), 125-142. |
[11] |
D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Global Optimization, 17 (2000), 127-160.
doi: 10.1023/A:1026537630859. |
[12] |
D. Y. Gao, Advances in canonical duality theory with applications to global optimization, Available from: http://www.math.vt.edu/people/gao/papers/focapo08.pdf. |
[13] |
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. |
[14] |
G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography," Computer Science and Applied Mathematics. Academic Press,Inc., New York-London, 1980. |
[15] |
V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Math. Program., 110 (2007), 521-541.
doi: 10.1007/s10107-006-0012-5. |
[16] |
E. de Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), 875-892.
doi: 10.1137/S1052623401383248. |
[17] |
C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, working paper, 2010. |
[18] |
C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 6 (2010), 779-793.
doi: 10.3934/jimo.2010.6.779. |
[19] |
C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint, in "Advances in Convex Analysis and Global Optimization" (eds. N. Hadijsavvas and P. M. Paradalos), Nonconvex Optim. Appl., 54, Kluwer Acad. Publ., Dordrecht, (2001), 119-134. |
[20] |
J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optimization, 11 (2001/01), 796-817.
doi: 10.1137/S1052623400366802. |
[21] |
P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables, BIT, 24 (1984), 206-224. |
[22] |
P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization," Ph.D. Thesis, California Institute of Technology, 2000. |
[23] |
J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.
doi: 10.1287/moor.28.2.246.14485. |
[24] |
X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming, Available from: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf. |
[25] |
Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming, J. Industrial and Management Optimization, 4 (2008), 213-225.
doi: 10.3934/jimo.2008.4.213. |
[26] |
L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms, SIAM J. Optimization, 16 (2006), 1076-1091. |
show all references
References:
[1] |
K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization, Math. Program, 91 (2001), 49-52. |
[2] |
A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," 2nd edition, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15, Springer-Verlag, New York, 2003. |
[3] |
A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92 (1996), 310-325.
doi: 10.1016/0377-2217(94)00229-0. |
[4] |
A. Billionnet, A. Faye and E. Soutif, A new upper bound for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 113 (1999), 664-672.
doi: 10.1016/S0377-2217(97)00414-1. |
[5] |
D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Math. Program, 74 (1996), 121-140.
doi: 10.1007/BF02592208. |
[6] |
I. M. Bomze, Global optimization: A quadratic programming perspective, in "Nonlinear Optimization," Lecture Notes in Mathematics, 1989, Springer, Berlin, (2010), 1-53. |
[7] |
I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs, Optimization Letter, 4 (2010), 465-472.
doi: 10.1007/s11590-010-0174-1. |
[8] |
S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120 (2009), 479-495.
doi: 10.1007/s10107-008-0223-z. |
[9] |
S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs," Manuscript, Department of Mathematics, Technische Universitat Darmstadt, Darmstadt, Germany, 2008. |
[10] |
S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 4 (2008), 125-142. |
[11] |
D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Global Optimization, 17 (2000), 127-160.
doi: 10.1023/A:1026537630859. |
[12] |
D. Y. Gao, Advances in canonical duality theory with applications to global optimization, Available from: http://www.math.vt.edu/people/gao/papers/focapo08.pdf. |
[13] |
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. |
[14] |
G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography," Computer Science and Applied Mathematics. Academic Press,Inc., New York-London, 1980. |
[15] |
V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Math. Program., 110 (2007), 521-541.
doi: 10.1007/s10107-006-0012-5. |
[16] |
E. de Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), 875-892.
doi: 10.1137/S1052623401383248. |
[17] |
C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, working paper, 2010. |
[18] |
C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 6 (2010), 779-793.
doi: 10.3934/jimo.2010.6.779. |
[19] |
C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint, in "Advances in Convex Analysis and Global Optimization" (eds. N. Hadijsavvas and P. M. Paradalos), Nonconvex Optim. Appl., 54, Kluwer Acad. Publ., Dordrecht, (2001), 119-134. |
[20] |
J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optimization, 11 (2001/01), 796-817.
doi: 10.1137/S1052623400366802. |
[21] |
P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables, BIT, 24 (1984), 206-224. |
[22] |
P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization," Ph.D. Thesis, California Institute of Technology, 2000. |
[23] |
J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.
doi: 10.1287/moor.28.2.246.14485. |
[24] |
X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming, Available from: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf. |
[25] |
Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming, J. Industrial and Management Optimization, 4 (2008), 213-225.
doi: 10.3934/jimo.2008.4.213. |
[26] |
L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms, SIAM J. Optimization, 16 (2006), 1076-1091. |
[1] |
Lihua Li, Yan Gao, Hongjie Wang. Second order sufficient optimality conditions for hybrid control problems with state jump. Journal of Industrial and Management Optimization, 2015, 11 (1) : 329-343. doi: 10.3934/jimo.2015.11.329 |
[2] |
RazIye Mert, A. Zafer. A necessary and sufficient condition for oscillation of second order sublinear delay dynamic equations. Conference Publications, 2011, 2011 (Special) : 1061-1067. doi: 10.3934/proc.2011.2011.1061 |
[3] |
M. Soledad Aronna. Second order necessary and sufficient optimality conditions for singular solutions of partially-affine control problems. Discrete and Continuous Dynamical Systems - S, 2018, 11 (6) : 1233-1258. doi: 10.3934/dcdss.2018070 |
[4] |
J.-P. Raymond, F. Tröltzsch. Second order sufficient optimality conditions for nonlinear parabolic control problems with state constraints. Discrete and Continuous Dynamical Systems, 2000, 6 (2) : 431-450. doi: 10.3934/dcds.2000.6.431 |
[5] |
B. Bonnard, J.-B. Caillau, E. Trélat. Second order optimality conditions with applications. Conference Publications, 2007, 2007 (Special) : 145-154. doi: 10.3934/proc.2007.2007.145 |
[6] |
A. C. Eberhard, C.E.M. Pearce. A sufficient optimality condition for nonregular problems via a nonlinear Lagrangian. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 301-331. doi: 10.3934/naco.2012.2.301 |
[7] |
Ana P. Lemos-Paião, Cristiana J. Silva, Delfim F. M. Torres. A sufficient optimality condition for delayed state-linear optimal control problems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2293-2313. doi: 10.3934/dcdsb.2019096 |
[8] |
Louis Tcheugoue Tebou. Equivalence between observability and stabilization for a class of second order semilinear evolution. Conference Publications, 2009, 2009 (Special) : 744-752. doi: 10.3934/proc.2009.2009.744 |
[9] |
Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 |
[10] |
Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108 |
[11] |
Lucas Bonifacius, Ira Neitzel. Second order optimality conditions for optimal control of quasilinear parabolic equations. Mathematical Control and Related Fields, 2018, 8 (1) : 1-34. doi: 10.3934/mcrf.2018001 |
[12] |
Qilin Wang, Xiao-Bing Li, Guolin Yu. Second-order weak composed epiderivatives and applications to optimality conditions. Journal of Industrial and Management Optimization, 2013, 9 (2) : 455-470. doi: 10.3934/jimo.2013.9.455 |
[13] |
Yong Xia. New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problems. Journal of Industrial and Management Optimization, 2009, 5 (4) : 881-892. doi: 10.3934/jimo.2009.5.881 |
[14] |
Ferenc A. Bartha, Ábel Garab. Necessary and sufficient condition for the global stability of a delayed discrete-time single neuron model. Journal of Computational Dynamics, 2014, 1 (2) : 213-232. doi: 10.3934/jcd.2014.1.213 |
[15] |
Hongwei Lou. Second-order necessary/sufficient conditions for optimal control problems in the absence of linear structure. Discrete and Continuous Dynamical Systems - B, 2010, 14 (4) : 1445-1464. doi: 10.3934/dcdsb.2010.14.1445 |
[16] |
Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial and Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921 |
[17] |
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 |
[18] |
Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089 |
[19] |
Yi Jiang, Yuan Cai. A reformulation-linearization based algorithm for the smallest enclosing circle problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3633-3644. doi: 10.3934/jimo.2020136 |
[20] |
Tran Hong Thai, Nguyen Anh Dai, Pham Tuan Anh. Global dynamics of some system of second-order difference equations. Electronic Research Archive, 2021, 29 (6) : 4159-4175. doi: 10.3934/era.2021077 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]