O método ADMM para um problema de otimização polinomial não convexo
DOI:
https://doi.org/10.5540/03.2022.009.01.0281Keywords:
Problema de otimização cúbico, método ADMM, ponto de KKT, otimização polinomial, otimização global, ótimo local.Abstract
Consideramos o problema NP-difícil de minimizar uma função polinomial de grau três sobre a fronteira da esfera. Devido à não convexidade do problema e às importantes aplicações em processamento de imagens, o desenvolvimento de algoritmos para encontrar boas soluções viáveis para o mesmo tem recebido considerável atenção. Neste trabalho, detalhamos o algoritmo ADMM para este problema, assim como particularizamos seus resultados de convergência. Comparamos numericamente o algoritmo com o solver fmincon, do Matlab, e analisamos o comportamento do algoritmo para diferentes inicializações do mesmo.
Downloads
References
P. J. Basser e D. K. Jones. “Diffusion-tensor MRI: theory, experimental design and data analysis-a technical review”. Em: NMR Biomed. 15 (2002), pp. 456–467. doi: 10.1002/ nbm.783.
P. J. Basser, J. Mattiello e D LeBihan. “Estimation of the effective seldiffusion tensor from the NMR spin echo”. Em: Journal of Magnetic Resonance 8 (1994), pp. 247–254. doi: 10.1006/jmrb.1994.1037.
C. Buccheim, M. Fampa e O. Sarmiento. “Lower Bounds for Cubic Optimization over the Sphere”. Em: Journal of Optimization Theory and Applications 3 (2021), pp. 823–846. doi: 10.1007/s10957-021-01809-y.
S. He, Z. Li e S Zhang. “Approximation algorithms for homogeneous polynomial optimization with quadratic constraints”. Em: Mathematical Programming 2 (2010), pp. 353–383. doi: 10.1007/s10107-010-0409-z.
D. Henrion, J. B. Lasserre e J. Loefberg. “GloptiPoly3: moments, optimization and semidefinite programming.” Em: Optim. Meth. Softw. 24 (2009), pp. 761–779. doi: 10.1080/ 10556780802699201.
B. Jiang, S. Ma e S. Zhang. “Alternating direction method of multipliers for real and complex polynomial optimization models”. Em: Optimization: A Journal of Mathematical Programming and Operations Research 6 (2014), pp. 883–898. doi: 10.1080/02331934. 2014.895901.
J. B. Laserre. “Global optimization with polynomials and the problem of moments”. Em: SIAM Journal on Optimization 3 (2001), pp. 796–817. doi: 10.1137/S1052623400366802.
J. Nie. “Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces”. Em: Frontiers of Mathematics in China 2 (2012), pp. 321–346. doi: 10.1007/ s11464-012-0187-4.
J. Nie e L. Wang. “Semidefinte relaxations for best rank-1 tensor approximations”. Em: SIAM Journal on Matrix Analysis and Applications 35 (2014), pp. 1155–1179. doi: 10.1137/130935112.
A. M. So. “Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems”. Em: Mathematical Programming 2 (2011), pp. 357–382. doi: 10.1007/s10107-011-0464-0.
R. J. Stern e Wolkowicz H. “Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations”. Em: SIAM Journal on Optimization 5 (1995), pp. 286–313. doi: 10. 1137/0805016.
X. Zhang, C. Ling e L. Qi. “The best rank-1 approximation of a symmetric tensor and related spherical optimization problems”. Em: SIAM J. Matrix Anal. Appl. 33 (2012), pp. 806– 821. doi: 10.1137/110835335.
X. Zhang, L. Qi e Y. Ye. “The cubic spherical optimization problems”. Em: Mathematics of Computation 81 (2012), pp. 1513–1525. doi: 10.1090/S0025-5718-2012-02577-4.
