More Web Proxy on the site http://driver.im/

research-article

Adaptive Global Algorithm for Solving Box-Constrained Non-convex Quadratic Minimization Problems

Authors:

Mohand Ouamer BibiAuthors Info & Claims

Journal of Optimization Theory and Applications, Volume 192, Issue 1

Pages 360 - 378

https://doi.org/10.1007/s10957-021-01980-2

Published: 01 January 2022 Publication History

Abstract

In this paper, we propose a new adaptive method for solving the non-convex quadratic minimization problem subject to box constraints, where the associated matrix is indefinite, in particular with one negative eigenvalue. We investigate the derived sufficient global optimality conditions by exploiting the particular form of the Moreau envelope (L-subdifferential) of the quadratic function and abstract convexity, also to develop a new algorithm for solving the original problem without transforming it, that we call adaptive global algorithm, which can effectively find one global minimizer of the problem. Furthermore, the research of the convex support of the objective function allows us to characterize the global optimum and reduce the complexity of the big size problems. We give some theoretical aspects of global optimization and present numerical examples with test problems for illustrating our approach.

References

[1]

Ajima Y and Fujie T A polyhedral approach for nonconvex quadratic programming problems with box constraints J. Glob. Optim. 1998 13 151-170

[2]

Best MJ and Ding B Global and local quadratic minimization J. Glob. Optim. 1997 10 77-90

[3]

Bibi MO, Ikeneche N, and Bentobache M A hybrid direction algorithm for solving a convex quadratic problem Int. J. Math. Oper. Res. 2020 16 2 159-178

[4]

Bomze IM and Danninger G A global optimization algorithm for concave quadratic programming problems SIAM J. Optim. 1993 3 826-842

[5]

Brahmi B and Bibi MO Dual Support method for Solving convex quadratic programs Optimization 2010 59 851-872

[6]

Cambini R and Sodini C A sequential method for a class of box constrained quadratic programming problems Math. Meth. Oper. Res. 2008 67 223-243

[7]

Chen J and Burer S Globally solving nonconvex quadratic programming problems via completely positive programming Math. Prog. Comp. 2012 4 33-52

[8]

Coleman TF and Li Y A reflective newton method for minimizing a quadratic function subject to bounds on some of the variables SIAM J. Optim. 1996 6 1040-1058

[9]

Coleman TF and Li Y A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints Math. Prog. Ser. A 2000 88 1-31

[10]

Fernandes L, Fischer A, Judice J, Requejo C, and Soares J A block active set algorithm for large-scale quadratic programing with box constraints Ann. Oper. Res. 1998 18 75-95

[11]

Gabasov R, Kirillova FM, Kostyukova OI, and Raketsky VM Constructive Methods of Optimization: Part 4: Convex Problems 1987 Minsk University Press

[12]

Gill PE, Murray W, and Wright MH Practical Optimization 1981 London Academic Press

[13]

Gratton S, Simon E, and Toint PL An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity Math. Prog. 2020 5 1-24

[14]

Han CG, Pardalos PM, and Ye Y On the solution of indefinite quadratic problems using an interior-point algorithm Informatica 1992 3 474-496

[15]

Horst R, Pardalos PM, and Thoai NV Introduction to Global Optimization 1995 Dordrecht Kluwer Academic Publishers

[16]

Jeyakumar V, Rubinov AM, and Wu ZY Sufficient global optimality conditions for nonconvex quadratic minimization problems with box constraints J. Glob. Optim. 2006 36 471-481

[17]

Jeyakumar V, Rubinov AM, and Wu ZY Generalized Fenchel’s conjugation formulas and duality for abstract convex functions J. Optim. Theory Appl. 2007 132 441-458

[18]

Kostina EA and Kostyukova OI An algorithm for solving quadratic programming problems with linear equality and inequality constraints Comput. Math. Math. Phys. 2001 41 960-973

[19]

Le Thi HA and Pham Dinh T Solving a class of linearly constrained indefinite quadratic problems by DC algorithms J. Glob. Optim. 1997 11 253-285

[20]

Le Thi HA, Huynh VN, and Pham Dinh T Convergence analysis of difference-of-convex algorithm with subanalytic data J. Optim. Theory Appl. 2018 179 103-126

[21]

Lu C and Deng Z DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs Optim. Lett. 2018 12 985-996

[22]

Lua Y, Pang LP, Liang XJ, and Xia ZQ An approximate decomposition algorithm for convex minimization J. Comput. Appl. Math. 2010 234 658-666

[23]

Mangasarian OL, Rosen JB, and Thompson ME Nonconvex piecewise-quadratic underestimation for global minimization J. Glob. Optim. 2006 34 475-488

[24]

Martinez JM Local minimizers of quadratic functions on Euclidean balls and spheres SIAM J. Optim. 1994 4 159-176

[25]

Pardalos PM Global optimization algorithms for linearly constrained indefinite quadratic problems Comput. Math. Appl. 1991 59 851-872

[26]

Pardalos PM Construction of test problems in quadratic bivalent programming Math. Softw. 1991 17 74-87

[27]

Pardalos PM and Vavasis SA Quadratic programming with one negative eigenvalue is NP-hard J. Glob. Optim. 1991 1 15-22

[28]

Pham Dinh T, Le Thi HA, and Akoa F Combining DCA and interior point techniques for large-scale nonconvex quadratic programming Optim. Method Softw. 2008 23 4 609-629

[29]

Pinar MC Sufficient global optimality conditions for bivalent quadratic optimization J. Optim. Theory Appl. 2004 122 2 433-440

[30]

Radjef S and Bibi MO An effective generalization of the direct support method in quadratic convex programming Appl. Math. Sci. 2012 6 1525-1540

[31]

Rubinov AM Abstract Convexity and Global Optimization 2000 Dordrecht Kluwer Academic

[32]

Tuan HN Convergence rate of the Pham Dinh-Le Thi algorithm for the trust-region subproblem J. Optim. Theory Appl. 2012 154 3 904-915

[33]

Vandenbussche D and Nemhauser GL A branch-and-cut algorithm for nonconvex quadratic programs with box constraints Math. Prog. 2005 102 559-575

[34]

Wu ZY Sufficient global optimality conditions for weakly convex minimization problems J. Glob. Optim 2007 39 427-440

[35]

Wu ZY, Jeyakumar V, and Rubinov AM Sufficient conditions for globally optimality of bivalent nonconvex quadratic programs J. Optim. Theory Appl. 2007 133 123-130

[36]

Wu ZY and Rubinov AM Global optimality conditions for some classes of optimization problems J. Optim. Theory Appl. 2010 145 164-185

[37]

Yi SN, Joaquim J, An LTH, and Tao PD Improved DC programming approaches for solving the quadratic eigenvalue complementarity problem Appl. Math. Comput. 2019 353 95-113

Cited By

Fearnley JGoldberg PHollender ASavani RMohar BShinkar IO'Donnell R(2024)The Complexity of Computing KKT Solutions of Quadratic ProgramsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649647(892-903)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649647

Index Terms

Adaptive Global Algorithm for Solving Box-Constrained Non-convex Quadratic Minimization Problems
1. Mathematics of computing
  1. Mathematical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions

In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization ...
Sufficient Global Optimality Conditions for Non-convex Quadratic Minimization Problems With Box Constraints

In this paper we establish conditions which ensure that a feasible point is a global minimizer of a quadratic minimization problem subject to box constraints or binary constraints. In particular, we show that our conditions provide a complete ...
Sufficient global optimality conditions for weakly convex minimization problems

In this paper, we present sufficient global optimality conditions for weakly convex minimization problems using abstract convex analysis theory. By introducing ( L , X )-subdifferentials of weakly convex functions using a class of quadratic functions, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Optimization Theory and Applications

Journal of Optimization Theory and Applications Volume 192, Issue 1

Jan 2022

400 pages

ISSN:0022-3239

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.

Publisher

Plenum Press

United States

Publication History

Published: 01 January 2022

Accepted: 17 November 2021

Received: 04 March 2020

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fearnley JGoldberg PHollender ASavani RMohar BShinkar IO'Donnell R(2024)The Complexity of Computing KKT Solutions of Quadratic ProgramsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649647(892-903)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649647

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents