Buradasınız

Anasayfa » Content

Küme eleman sayılarının (cardinality) optimizasyon problemlerine yönelik yakınsak, yeniden formüle etmeli ve dışbükey teknikler

Approximation, reformulation and convex techniques for cardinality optimization problems

Journal Name:

  • İstanbul Üniversitesi İşletme Fakültesi Dergisi

Publication Year:

  • 2011

Key Words:

Keywords (Original Language):

Author NameUniversity of Author
Abstract (2. Language): 
The cardinality minimization problem (CMP) is finding a vector with minimum cardinality, which satisfies certain linear (or non-linear) constraints. This problem is closely related to the so-called compressive sensing problems. In this paper we survey and study different approximation, reformulation and convex relaxations for both cardinality constraint problems and cardinality minimization problems, and discuss how to add a penalty function to the objective in order to get a reformulation/approximation model of the original problems, instead of simply dropping the rank constraint. By reformulation techniques, under some mild condition we may either transform the problem to a mixed integer linear program (MILP) or the so-called bilevel SDP problems. We also point out that a continuous approximation of cardinality functions can enable us to apply majorization method to extract proper weights for the (re)weighted l1 algorithms.
Bookmark/Search this post with
Abstract (Original Language): 
Küme eleman sayılarının minimizasyon problemi, belirli doğrusal (veya doğrusal olmayan) kısıtları karşılayan minimum küme eleman sayısını içeren bir vektör bulmakla ilgilidir. Problem, başınç algılama problemi olarak da anılan problemle yakından ilişkilidir. Bu çalışmada, küme eleman kısıt problemleri ve küme eleman sayılarının minimizasyon problemleri için çeşitli yakınsak, yeniden formüle etme ve dışbükey gevşetmeler yer almakta ve yalnızca rank kısıtını dışlamaktan çok orijinal problemin yeniden formüle edilmesi/yakınsanması için amaca nasıl bir ceza fonksiyonu ekleneceğini tartışılmaktadır. Yeniden formüle etme teknikleri ile bazı hafif koşullarda, problem, ya karma tam sayılı doğrusal programlama ya da iki kademeli yarı tanımlı programlama problemlerine dönüştürülebilir. Küme eleman sayısı fonksiyonlarının sürekli yakınsanması, l1 algoritmalarının (yeniden) ağırlıklandırılarak uygun ağırlıklarının belirlenmesi amacıyla majorlaştırma yönteminin uygulanmasına izin verir.
FULL TEXT (PDF): 
PDF icon arastirmax-kume-eleman-sayilarinin-cardinality-optimizasyon-problemlerine-yonelik-yakinsak-yeniden-formule-etmeli-disbukey-teknikler.pdf
  • 2
124-137
  • English

REFERENCES

References: 

[1] R.G. Baraniuk, Compressive Ensing, IEEE Signal Processing Magazine.4, 24, 118, (2007).
[2] A. Ben-Tal and A.S. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization (2001).
[3] D.P. Bertsekas, A. Nedic, and A.E. Ozdaglar, Convex Analysis and Optimization. Athena Scientific, (2003).
[4] M. Bruglieri, M. Ehrgott, H.W. Hamacher, and F. Maffili, An Annotated Bibliography of Combinatorial Optimization Problems with Fixed Cardinality Constraints. Discrete Applied Mathematics, 154, 9, 1344-1357, (2006).
[5] E.J. Cand`es and M.B. Wakin, An Introduction to Compressive Sampling, IEEE Signal Processing Magazine, 25, 2, 21-30, (2008).
[6] E.J. Cand`es, M.B. Wakin, and S.P. Boyd, Enhancing Sparsity by Reweighted l1 Min- imization, Journal of Fourier Analysis and Applications. 14, 5, 877-905, (2008).
[7] T.J. Chang, N. Meade, JE Beasley, and YM Sharaiha, Heuristics for Cardinality Constrained Portfolio Optimisation, Computers and Operations Research, 27, 13, 1271-1302, (2000).
[8] A. d’Aspremont, A Semidefinite Representation for Some Minimum Cardinality Problems, Arxiv preprint math/0302092. (2003).
[9] A. d’Aspremont, L.E. Ghaoui, M.I. Jordan, and G.R.G. Lanckriet, A Direct Formulation for Sparse PCA Using Semidefinite Programming, Arxiv preprint cs/0406021. (2004).
[10] J. Dattorro, Convex Optimization & Euclidean Distance Geometry, Meboo Publishing USA, 2005.
[11] D.L. Donoho, Compressed Sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306, (2006).
[12] M. Fazel, Matrix Rank Minimization with Applications, Ph.D. Thesis, Stanford University, 2002.
[13] M. Fazel, H. Hindi, and S.P. Boyd, Log-Det Heuristic for Matrix Rank Minimization with Applications to Hankel and Euclidean Distance Matrices, American Control Conference, 2003. Proceedings of the 2003, vol. 3, IEEE, 2003, pp. 2156-2162.
[14] M. Fazel, H. Hindi, and S.P. Boyd, Rank Minimization and Applications in System Theory, American Control Conference, 2004.
[15] G.H. Golub and C.F. Van Loan, Matrix Computations, Johns Hopkins Univ Pr, 1996.
[16] I.F. Gorodnitsky and B.D. Rao, Sparse Signal Reconstruction from Limited Data Using
M.J. Abdi, Y. Zhao / İstanbul Üniversitesi İşletme Fakültesi Dergisi 40, 2, (2011) 124-137 © 2011
137
FOCUSS: A re-weighted minimum norm algorithm, IEEE Transactions on Signal Pro-cessing, 45, 600-616, (1997).
[17] A.J. Laub, Matrix Analysis for Scientists and Engineers, SIAM, 2005.
[18] C. Lemar´echal and F. Oustry, Semidefinite Relaxations and Lagrangian Duality with Application to Combinatorial Optimization, Preprint, 1999.
[19] M. Lustig, D. Donoho, and J.M. Pauly, Sparse MRI: The Application of Compressed Sensing for Rapid MR Imaging, Magnetic Resonance in Medicine. 58, 6, 1182-1195, (2007).
[20] M. Lustig, D.L. Donoho, J.M. Santos, and J.M. Pauly, Compressed Sensing MRI, IEEE Signal Processing Magazine. 25, 2, 72-82, (2008).
[21] D. Malioutov, M. Cetin, and A.S. Willsky, A Sparse Signal Reconstruction Perspective for Source Localization with Sensor Arrays, IEEE Transactions on Signa Processing. 53, 8, 3010-3022, (2005).
[22] D. Maringer and H. Kellerer, Optimization of Cardinality Constrained Portfolios with a Hybrid Local Search Algorithm, OR Spectrum. 25, 4, 481-495, (2003).
[23] C.D. Meyer, Matrix Analysis and Applied Linear Algebra: Solutions Manual, SIAM, 2000.
[24] B. Moghaddam, Y. Weiss, and S. Avidan, Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms, Advances in Neural Information Processing Systems. 18, 915, (2006).
[25] F. Streichert, H. Ulmer, and A. Zell, Evolutionary Algorithms and The Cardinality Con- Strained Portfolio Optimization Problem, Proceedings of the International Conference on Operations Research (OR 2003), Heidleberg, September 3-5, 2003.
[26] M.Y.J. Ting, Signal Processing for Magnetic Resonance Force Microscopy, Ph.D. Thesis, 2006.
[27] Y. Tsaig and D.L. Donoho, Extensions of Compressed Sensing, Signal processing. 86, 3, 549-571, (2006).
[28] L. Vandenberghe and S.P. Boyd, Semidefinite Programming, SIAM Review. 38, 1, 49-95, (1996).
[29] S. Wold, K. Esbensen, and P. Geladi, Principal Component Analysis, Chemometrics and Intelligent Laboratory Systems, 2, 1-3, 37-52, (1987).
[30] H. Xu, C. Caramanis, and S. Mannor, Robust Regression and Lasso, Arxiv preprint arXiv: 0811.1790, 2008.
[31] Y.B. Zhao, Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations, Arxiv preprint arXiv:1010.0851, 2010.
[32] X. Zheng, X. Sun, and D. Li, Convex Relaxations and Mixed-integer Quadratic Reformulations for Cardinality Constrained Quadratic Programs, Preprint, 2010.
[33] H. Zou, T. Hastie, and R. Ibshirani, Sparse Principal Component Analysis, Journal of Computational and Graphical Statistics. 15, 2, 265-286, (2006).

Thank you for copying data from http://www.arastirmax.com