• Previous Article
    State estimation for discrete linear systems with observation time-delayed noise
  • JIMO Home
  • This Issue
  • Next Article
    Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property
January  2011, 7(1): 67-78. doi: 10.3934/jimo.2011.7.67

Global optimality conditions for some classes of polynomial integer programming problems

1. 

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China, China

2. 

School of Information Technology and Mathematical Sciences, University of Ballarat, Victoria 3353

Received  November 2008 Revised  September 2010 Published  January 2011

In this paper, some verifiable necessary global optimality conditions and sufficient global optimality conditions for some classes of polynomial integer programming problems are established. The relationships between these necessary global optimality conditions and these sufficient global optimality conditions are also discussed. The main theoretical tool for establishing these optimality conditions is abstract convexity.
Citation: Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
References:
[1]

J. Baptiste and H. Urruty, Conditions for global optimality 2,, Journal of Global Optimization, 13 (1998), 349. doi: 10.1023/A:1008365206132. Google Scholar

[2]

J. Baptiste and H. Urruty, Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints,, Journal of Global Optimization, 21 (2001), 445. Google Scholar

[3]

A. Beck and M. Teboulle, Global optimality conditions for quadratic optimization problems with binary constraints,, SIAM Journal on Optimization, 11 (2000), 179. doi: 10.1137/S1052623498336930. Google Scholar

[4]

W. Chen and L. S. Zhang, Global optimality conditions for quadratic integer problems,, Proceedings of Eighth Symposium on Operations Research Society of China, (2006), 206. Google Scholar

[5]

D. S. Hanif and H. T. CIHAN, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique,, Journal of Global Optimization, 2 (1992), 101. doi: 10.1007/BF00121304. Google Scholar

[6]

P. Hansen, B. Jaumard and S. J. Lu, An analytical approach to global optimization,, Mathematical Programming, 52 (1991), 227. doi: 10.1007/BF01582889. Google Scholar

[7]

R. Horst and H. Tuy, "Global Optimization: Deterministic Approaches,", Springer-Verlag, (1990). Google Scholar

[8]

V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints,, Journal of Global Optimization, 36 (2006), 471. doi: 10.1007/s10898-006-9022-3. Google Scholar

[9]

J. B. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM Journal on Optimization, 11 (2001), 796. doi: 10.1137/S1052623400366802. Google Scholar

[10]

M. C. Pinar, Sufficient global optimality conditions for bivalent quadratic optimization,, Journal of Optimization Theory and Applications, 122 (2004), 433. doi: 10.1023/B:JOTA.0000042530.24671.80. Google Scholar

[11]

A. M. Rubinov, "Abstract Convexity and Global Optimization,", Kluwer, (2000). Google Scholar

[12]

M. Schweighofer, Optimization of polynomials on compact semialgebraic sets,, SIAM Journal on Optimization, 15 (2005), 805. doi: 10.1137/S1052623403431779. Google Scholar

[13]

H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems,, SIAM Journal on Discrete Mathematics, 3 (1990), 411. doi: 10.1137/0403036. Google Scholar

[14]

H. Sherali and C. Tuncbilek, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique,, Journal of Global Optimization, 2 (1992), 101. doi: 10.1007/BF00121304. Google Scholar

[15]

H. Waki, S. Kim, M. Kojima and M. Maramatsu, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity,, Dept. of Mathematical and Computing Sciences, (2004). Google Scholar

[16]

Z. B. Wang, S. C. Fang, D. Y. Gao and W. X. Xing, Global extremal conditions for multi-integer quadratic programming,, Journal of Industrial and Management Optimization, 4 (2008), 213. Google Scholar

show all references

References:
[1]

J. Baptiste and H. Urruty, Conditions for global optimality 2,, Journal of Global Optimization, 13 (1998), 349. doi: 10.1023/A:1008365206132. Google Scholar

[2]

J. Baptiste and H. Urruty, Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints,, Journal of Global Optimization, 21 (2001), 445. Google Scholar

[3]

A. Beck and M. Teboulle, Global optimality conditions for quadratic optimization problems with binary constraints,, SIAM Journal on Optimization, 11 (2000), 179. doi: 10.1137/S1052623498336930. Google Scholar

[4]

W. Chen and L. S. Zhang, Global optimality conditions for quadratic integer problems,, Proceedings of Eighth Symposium on Operations Research Society of China, (2006), 206. Google Scholar

[5]

D. S. Hanif and H. T. CIHAN, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique,, Journal of Global Optimization, 2 (1992), 101. doi: 10.1007/BF00121304. Google Scholar

[6]

P. Hansen, B. Jaumard and S. J. Lu, An analytical approach to global optimization,, Mathematical Programming, 52 (1991), 227. doi: 10.1007/BF01582889. Google Scholar

[7]

R. Horst and H. Tuy, "Global Optimization: Deterministic Approaches,", Springer-Verlag, (1990). Google Scholar

[8]

V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints,, Journal of Global Optimization, 36 (2006), 471. doi: 10.1007/s10898-006-9022-3. Google Scholar

[9]

J. B. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM Journal on Optimization, 11 (2001), 796. doi: 10.1137/S1052623400366802. Google Scholar

[10]

M. C. Pinar, Sufficient global optimality conditions for bivalent quadratic optimization,, Journal of Optimization Theory and Applications, 122 (2004), 433. doi: 10.1023/B:JOTA.0000042530.24671.80. Google Scholar

[11]

A. M. Rubinov, "Abstract Convexity and Global Optimization,", Kluwer, (2000). Google Scholar

[12]

M. Schweighofer, Optimization of polynomials on compact semialgebraic sets,, SIAM Journal on Optimization, 15 (2005), 805. doi: 10.1137/S1052623403431779. Google Scholar

[13]

H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems,, SIAM Journal on Discrete Mathematics, 3 (1990), 411. doi: 10.1137/0403036. Google Scholar

[14]

H. Sherali and C. Tuncbilek, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique,, Journal of Global Optimization, 2 (1992), 101. doi: 10.1007/BF00121304. Google Scholar

[15]

H. Waki, S. Kim, M. Kojima and M. Maramatsu, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity,, Dept. of Mathematical and Computing Sciences, (2004). Google Scholar

[16]

Z. B. Wang, S. C. Fang, D. Y. Gao and W. X. Xing, Global extremal conditions for multi-integer quadratic programming,, Journal of Industrial and Management Optimization, 4 (2008), 213. Google Scholar

[1]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[2]

Xiuhong Chen, Zhihua Li. On optimality conditions and duality for non-differentiable interval-valued programming problems with the generalized (F, ρ)-convexity. Journal of Industrial & Management Optimization, 2018, 14 (3) : 895-912. doi: 10.3934/jimo.2017081

[3]

Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235

[4]

Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018170

[5]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[6]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019102

[7]

Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131

[8]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361

[9]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089

[10]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[11]

Jan Andres, Luisa Malaguti, Martina Pavlačková. Hartman-type conditions for multivalued Dirichlet problem in abstract spaces. Conference Publications, 2015, 2015 (special) : 38-55. doi: 10.3934/proc.2015.0038

[12]

Poongodi Rathinasamy, Murugesu Rangasamy, Nirmalkumar Rajendran. Exact controllability results for a class of abstract nonlocal Cauchy problem with impulsive conditions. Evolution Equations & Control Theory, 2017, 6 (4) : 599-613. doi: 10.3934/eect.2017030

[13]

Monika Laskawy. Optimality conditions of the first eigenvalue of a fourth order Steklov problem. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1843-1859. doi: 10.3934/cpaa.2017089

[14]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871

[15]

Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851

[16]

Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333

[17]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[18]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[19]

Yong Xia. New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problems. Journal of Industrial & Management Optimization, 2009, 5 (4) : 881-892. doi: 10.3934/jimo.2009.5.881

[20]

Chadi Nour, Ron J. Stern, Jean Takche. Generalized exterior sphere conditions and $\varphi$-convexity. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 615-622. doi: 10.3934/dcds.2011.29.615

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]