Algoritmo de corte y continuación con ramificación y acotación para la solución del problema cuadrático con restricciones de caja

Autores/as

  • Ridelio Miranda Pérez Universidad de Cienfuegos
  • Sira Allende Alonso Departamento de Matemática Aplicada, Facultad de Matemática y Computación, Universidad de La Habana, Cuba
  • Boris Pérez Cañedo Universidad de Cienfuegos
  • Gemayqzel Bouza Allende Departamento de Matemática Aplicada, Facultad de Matemática y Computación, Universidad de La Habana, Cuba

Palabras clave:

optimización cuadrática no cóncava, programación cuadrática no convexa, optimización paramétrica, ramificación-y-límite, relajación semidefinida positiva, programación semidefinida

Resumen

Se presenta un algoritmo híbrido que combina una estrategia global de optimización con un métodode ramificación y acotamiento basado en relajación semidefinida positiva para el cálculo de una solución ε-aproximada del problema cuadrático con restricciones de caja. Los experimentos realizados demuestran que el algoritmo propuesto disminuye el número de iteraciones necesarias, el número de nodos explorados y el tiempo de ejecución en comparación con otros métodos de optimización global concebidos para este problema.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Claire S. Adjiman and Christodoulos A. Floudas. The αBB global aoptimization algoritm for nonconvex problems: An overview, volume 53 of Nonconvex Optimization and Its Applications, chapter 8, pages 155–186. Kluwer Academic, 2001.

E.L. Allgower and K. Georg. Numerical Continuation Methods: An Introduction. Berlin, Heidelberg, New York, 1990.

Samuel Burer and Jieqiu Chen. Relaxing the optimality conditions of box QP. Computational Optimization and Applications, 48:653–673, 2011.

Samuel Burer and Dieter Vandenbussche. A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program., 113(Ser. A):259–282, 2008.

Jieqiu Chen. Convex relaxations in nonconvex and applied optimization. PhD thesis, University of Iowa, 2010.

J.W. Chinneck. The constraint consensus method for finding approximately feasible points in ninlinear programs. INFORMS Journal on Computing, 16(3):255–265, 2004.

T.F. Coleman and L.A. Hulbert. A direct active set algorithm for large sparse quadratic programs with simple bounds. Mathematical Programming, (45):373–406, 1989.

W. Gomez, J. Guddat, H.Th. Jongen, J. Ruckmann, and C.Solano. Curvas críticas y saltos en optimización no lineal. On Line, 2000. http://www.emis.de/monogrphs/curvas/index.html.

MC. Grant and SP. Boyd. The CVX Users Guide. CVX Research, Inc., 2014

P. Hansen and B. Joumard. Reduction of indefinite quadratic programs to bilinear programs. Journal of Global Optimization, (2):41–62, 1992.

P. Hansen, B. Joumard, M. Ruiz, and J. Xiong. Global minimization of indefinite quadratic functions subject to box constraints. Technical report, GERAD, Ecole

Polytechnique Universite MacGill, Montreal, Canada, 1991. Technical Report.

F. Twilt H.Th. Jongen, P. Jonker. Critical sets in parametric optimization. Mathematical Programming, (34):333–353, 1986.

M.K. Kozlov, S.P. Tarasov, and L.G. Khachiyan. Polynomial solvability of convex quadratic programming. Dokl. Akad. Nauk SSSR, 248(5):10491051, 1979.

R. Miranda. On the generic character of the problem pr(t). Optimization, 2009.

M. Padberg. The boolean quadric polytope: Some characteristics, facets and relatives. Mathematical Programming, 45:139–172, 1989.

P.M. Pardalos and S.A. Vavasis. Quadratic programming with one negative eigenvalue is np-hard. Journal of Global Optimization, (1):15–22, 1991.

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(3):411–430, 1990.

H. D. Sherali and A Alameddine. A new reformulation-linearization technique for solving bilinear programming problems. Journal of Global Optimization, 2:379–410, 1992.

H. D. Sherali and C. H. Tuncbilek. A reformulation-convexification approach for solving nonconvex quadratic programming problems. Journal of Global Optimization, (7):101–112, 1995.

N.Z. Shor. Quadratic optimization problems. Tekhnicheskaya Kibernetika, 1:128–139, 1987.

Laurence Smith, John Chinneck, and Victor Aitken. Constraint Consensus Concentration for Identifying Disjoint Feasible Regions in Nonlinear Programs. Optimization Methods and Software, 00(00):1–30, 2011.

Laurence Smith, John Chinneck, and Victor Aitken. Improved Constraint Consensus Methods for Seeking Feasibility in Nonlinear Programs. Computational Optimization with Applications, 2012.

MatLab Team. Matlab users Guide. The mathWorks, Inc., 2013.

KC Toh, RH Tutuncu, and MJ Todd. Solving semidefinite-quadratic-linear programs using sdpt3. Mathematical Programming, Series B, (95):189–217, 2003.

Dieter Vandenbussche and George L Nemhauser. A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program., 102:559–575, 2005.

Yasutoshi Yajima and Tetsuya Fujie. A Polyhedral Approach for Nonconvex Quadratic Programming Problems with Box Constraints. Journal of Global Optimization, 13(2):151–170, 1998.

Descargas

Publicado

2024-03-18

Cómo citar

[1]
Miranda Pérez, R. et al. 2024. Algoritmo de corte y continuación con ramificación y acotación para la solución del problema cuadrático con restricciones de caja. Ciencias matemáticas. 29, 1 (mar. 2024), 19–29.

Número

Vol. 29 Núm. 1: Junio, 2015

Sección

Artículo Original

Licencia

Derechos de autor 2024 Ciencias Matemáticas

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Esta licencia permite copiar y redistribuir el material en cualquier medio o formato bajo los siguientes términos: se debe dar crédito de manera adecuada, no se puede hacer uso del material con propósitos comerciales, y si remezcla, transforma o crea a partir del material, no podrá distribuir el material modificado. Bajo la licencia mencionada, los autores mantienen los derechos de autor de su trabajo.