EE 609: Convex Optimization in SP/COM

  1. Instructors: Ketan Rajawat
  2. Prerequisites: Linear Algebra, Probability
  3. Objective: Convex optimization has recently been applied to a wide variety of problems in EE, especially in signal processing, communications, and networks. The aim of this course is to train the students in application and analysis of convex optimization problems in signal processing and wireless communications. At the end of this course, the students are expected to:
    1. Know about the applications of convex optimization in signal processing, wireless communications, and networking research.
    2. Be able to recognize convex optimization problems arising in these areas.
    3. Be able to recognize ‘hidden’ convexity in many seemingly non-convex problems; formulate them as convex problems. 
    4. Be able to develop low-complexity, approximate solutions for difficult non-convex problems.
  4. References:
    1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press. [Online]. http://www.stanford.edu/~boyd/cvxbook/
    2. Convex Optimization in Signal Processing and Communications, D. P. Palomar, Y. C. Eldar. Cambridge Press, 2010.
    3. IEEE Signal Processing Magazine- Special Issue on Advances in Convex Optimization, Vol. 27, No. 3, May 2010.
    4. Dimitri P. Bertsekas, Convex Analysis and Optimization, Athena-Scientific, 2003.
  5. Time and place: Lectures will be made available online, Discussion every Friday at 11am on zoom
  6. This course will cover (approximately) 
    1. Background on linear algebra
    2. Convex sets, functions, and problems
    3. Examples of convex problems: LP, QCQP, SOCP
    4. Duality, KKT conditions
    5. Geometric programming and applications
    6. Linear and quadratic classification
    7. Network optimization
    8. Sparse regression, Lasso, ridge regression and applications in image processing
    9. Robust least squares and applications in signal processing
    10. Support vector machines and applications in machine learning
    11. Semidefinite programming and applications in experiment design
    12. Semidefinite relaxation and applications in MIMO detection, integer programming
    13. Low rank matrix completion and applications in recommendor systems
    14. Multidimensional scaling and applications in sensor localization
    15. Numerical linear algebra, basics of interior point methods
  7. Tentative list of topics for Term Paper (only sample papers are provided, others can also be chosen, specify: theory/mixed/application mode) 
    1. Low-Rank Matrix Factorization:
      1. Chi, Yuejie, Yue M. Lu, and Yuxin Chen. "Nonconvex optimization meets low-rank matrix factorization: An overview." IEEE Transactions on Signal Processing 67.20 (2019): 5239-5269.
      2. Chen, Yudong, and Yuejie Chi. "Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization." IEEE Signal Processing Magazine 35.4 (2018): 14-31.
    2. Non-convex optimization for Machine Learning (several topics):
      1. Jain, Prateek, and Purushottam Kar. "Non-convex optimization for machine learning." arXiv preprint arXiv:1712.07897 (2017).
      2. Relevant slides: https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/nonconvex.pdf
    3. Recent Theoretical Advances in Non-Convex Optimization
      1. Danilova, Marina, et al. "Recent theoretical advances in non-convex optimization." arXiv preprint arXiv:2012.06188 (2020).
      2. Zhang, Yuqian, Qing Qu, and John Wright. "From symmetry to geometry: Tractable nonconvex problems." arXiv preprint arXiv:2007.06753 (2020).
    4. Blind deconvolution, demixing, phase retrieval etc:
      1. S. Ling and T. Strohmer, “Blind deconvolution meets blind demixing: Algorithms and performance bounds,” IEEE Trans. Inf. Theory, vol. 63, no. 7, pp. 4497–4520, 2017. 
      2. A. Ahmed, A. Aghasi, P. Hand, “Simultaneous phase retrieval and blind deconvolution via convex programming,” arXiv preprint arXiv:1904.12680, 2019. 
      3. C. Ma, K. Wang, Y. Chi, and Y. Chen, “Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution,” arXiv preprint arXiv:1711.10467, 2017. 
      4. J. Dong and Y. Shi, “Nonconvex demixing from bilinear measurements,” IEEE Trans. Signal Process., vol. 66, pp. 5152–5166, Oct. 2018. 
      5. D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: phase transitions in convex programs with random data,” Inf. Inference, vol. 3, pp. 224–294, Jun. 2014.
    5. Difference-of-convex programming:
      1. J.-y. Gotoh, A. Takeda, and K. Tono, “DC formulations and algorithms for sparse optimization problems,” Math. Program., vol. 169, no. 1, pp. 141–176, 2018.
    6. Riemannian/geometric optimization (generalizes geometric programming):
      1. Introductory slides: https://www.math.fsu.edu/~whuang2/pdf/slides_2016-GMDL.pdf
      2. Papers by Suvrat Sra from MIT, see relevant talk at: https://www.youtube.com/watch?v=-1BK70HM6ME
      3. Blog post by Andreas Bloch: https://andbloch.github.io/Stochastic-Gradient-Descent-on-Riemannian-Manifolds
      4. H Zhang, S J. Reddi, S. Sra, Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
    7. Online learning and online convex optimization 
      1. Shai Shalev-Shwartz, Foundations and Trends in ML, 4(2), 2011 
      2. Introduction to Online optimization 
      3. Elad Hazan, Foundations and Trends in Optimization, 2(3-4), 2015 
    8. Proximal Algorithms 
      1. Neal Parikh and Stephen Boyd (2014), "Proximal Algorithms", Foundations and Trends in Optimization: Vol. 1: No. 3, pp 127-239 
    9. Multi-period investment 
      1. Stephen Boyd, Mark T. Mueller, Brendan O’Donoghue and Yang Wang (2014), "Performance Bounds and Suboptimal Policies for Multi–Period Investment", Foundations and Trends in Optimization: Vol. 1: No. 1 
      2. Stephen Boyd, Enzo Busseti, Steve Diamond, Ronald N. Kahn, Kwangmoo Koh, Peter Nystrup and Jan Speth (2017), "Multi-Period Trading via Convex Optimization", Foundations and Trends in Optimization: Vol. 3: No. 1 
    10. Submodularity and convexity
      1. Francis Bach (2013), "Learning with Submodular Functions: A Convex Optimization Perspective", Foundations and Trends in Machine Learning: Vol. 6: No. 2-3.
    11. Learning over Networks
      1. Ali H. Sayed (2014), "Adaptation, Learning, and Optimization over Networks", Foundations and Trends in Machine Learning: Vol. 7: No. 4-5, pp 311-801.
    12. Approximate dynamic programming in transportation/logistics
      1. W. B. Powell, H. Simao, B. Bouzaiene-Ayari, “Approximate Dynamic Programming in Transportation and Logistics: A Unified Framework,” European J. on Transportation and Logistics, Vol. 1, No. 3, pp. 237-284 (2012). DOI 10.1007/s13676-012-0015-8.
    13. Sequential stochastic optimization, dynamic programming
      1. http://castlelab.princeton.edu/html/Papers/Powell-UnifiedFrameworkStochasticOptimization_July222017.pdf
      2. Clearing the Jungle of Stochastic Optimization, Informs Tutorials in Operations Research: Bridging Data and Decisions, pp. 109-137, November, 2014 
    14. Subgradient methods (older papers, find newer ones):
      1. S. Boyd and A. Mutapcic, Subgradient  Methods , Notes for EE364b, Stanford University, 2006. Available online.
      2. N. Shor, Minimization  Methods  for  Non-Differentiable  Functions , Springer Series in Computational Mathematics, Springer, 1985.
      3. D. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.
    15. Robust Optimization
      1. Bertsimas, Dimitris, David B. Brown, and Constantine Caramanis. "Theory and applications of robust optimization." SIAM review 53.3 (2011): 464-501.
      1. Xu, Huan, Constantine Caramanis, and Sujay Sanghavi. "Robust PCA via outlier pursuit." Advances in Neural Information Processing Systems. 2010.
    16. Coordinate ascent/descent
      1. Yu. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM Journal on Optimization, 2012
      2. P.  Richt ́arik and M. Takac, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Mathematical Programming, 2014
      3. P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Mathematical Programming, 2009
    17. Large-scale optimization
      1. Feng Niu, Benjamin Recht, Christopher Re, and Stephen Wright. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pages 693–701, 2011
      2. Gemulla, Rainer, et al. "Large-scale matrix factorization with distributed stochastic gradient descent." Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2011.       
      3. Bottou, Leon. "Large-scale machine learning with stochastic gradient descent." Proceedings of COMPSTAT'2010. Physica-Verlag HD, 2010. 177-186.
    18. Semi-stochastic methods:
      1. Konecny, Jakub, and Peter Richtarik. "Semi-stochastic gradient descent methods." arXiv preprint arXiv:1312.1666 (2013).
      2. Konecny, Jakub, et al. "Mini-batch semi-stochastic gradient descent in the proximal setting." IEEE Journal of Selected Topics in Signal Processing 10.2 (2016): 242-255.
      3. Konecny, Jakub, Zheng Qu, and Peter Richtarik. "Semi-stochastic coordinate descent." Optimization Methods and Software 32.5 (2017): 993-1005.
      4. Konecny, Jakub, Zheng Qu, and Peter Richtarik. "S2cd: Semi-stochastic coordinate descent." NIPS Optimization in Machine Learning workshop. 2014.
    19. Stochastic and online optimization
      1. A. Nemirovski, A. Juditsky, G. Lan and A. Shapiro,Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization (2009)
      2. Yu. Nesterov, Primal-dual subgradient methods for convex problems, Mathematical Programming (2009)
      3. L. Xiao, Dual averaging methods for regularized stochastic learning and online optimization, Journal of Machine Learning Research (2010)
      4. N. Le Roux, M. Schmidt and F. Bach, A stochastic gradient method with an exponential convergence rate for strongly convex optimization with finite training sets, NIPS (2012)
    20. Variance reduced stochastic gradient descent
      1. R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction NIPS (2013)
      2. L. Xiao and T. Zhang, A proximal stochastic gradient method with progressive variance reduction
      3. Defazio, Aaron, Francis Bach, and Simon Lacoste-Julien. "SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives." Advances in neural information processing systems. 2014.
      4. Schmidt, Mark, Nicolas Le Roux, and Francis Bach. "Minimizing finite sums with the stochastic average gradient." Mathematical Programming 162.1-2 (2017): 83-112.
    21. ADMM variants
      1. D. Goldfarb, S. Ma, K. Scheinberg, Fast alternating linearization methods for minimizing the sum of two convex functions, (2010)
      2. T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM J. Imag. Sciences (2009)
    22. Subgradient methods
      1. Nedic, Angelia, and Asuman Ozdaglar. "Distributed subgradient methods for multi-agent optimization." IEEE Transactions on Automatic Control 54.1 (2009): 48-61.
      2. Ram, S. Sundhar, Angelia Nedić, and Venugopal V. Veeravalli. "Distributed stochastic subgradient projection algorithms for convex optimization." Journal of optimization theory and applications 147.3 (2010): 516-545.
      3. Tsitsiklis, John, Dimitri Bertsekas, and Michael Athans. "Distributed asynchronous deterministic and stochastic gradient optimization algorithms." IEEE transactions on automatic control 31.9 (1986): 803-812.
    23. Smoothing
      1. Yu. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming (2005).
      2. Yu. Nesterov, Excessive gap technique in nonsmooth convex minimization, SIAM Journal on Optimization (2005)
    24. Majorization Minimization    
      1. Sun, Ying, Prabhu Babu, and Daniel P. Palomar. "Majorization-minimization algorithms in signal processing, communications, and machine learning." IEEE Transactions on Signal Processing 65.3 (2017): 794-816.       
      2. Figueiredo, Mario AT, Jose M. Bioucas-Dias, and Robert D. Nowak. "Majorization–minimization algorithms for wavelet-based image restoration." IEEE Transactions on Image processing 16.12 (2007): 2980-2991.       
      3. Mairal, Julien. "Incremental majorization-minimization optimization with application to large-scale machine learning." SIAM Journal on Optimization 25.2 (2015): 829-855. 
    25. Convex optimization in Finance
      1. Yiyong Feng and Daniel P. Palomar,  A Signal Processing Perspective on Financial Engineering, Foundations and Trends in Signal Processing, Now Publishers, vol. 9, no. 1-2, 2016.
    26. Blind deconvolution
      1. Ahmed, Ali, Benjamin Recht, and Justin Romberg. "Blind deconvolution using convex programming." IEEE Transactions on Information Theory 60.3 (2014): 1711-1732.
      2. Chan, Tsung-Han, et al. "A convex analysis framework for blind separation of non-negative sources." IEEE Transactions on Signal Processing 56.10 (2008): 5120-5134.
      3. Gillis, Nicolas, and Stephen A. Vavasis. "Fast and robust recursive algorithmsfor separable nonnegative matrix factorization." IEEE transactions on pattern analysis and machine intelligence 36.4 (2014): 698-714.
    27. Network utility maximization (Palomar Chiang)       
      1. Palomar, Daniel Perez, and Mung Chiang. "A tutorial on decomposition methods for network utility maximization." IEEE Journal on Selected Areas in Communications 24.8 (2006): 1439-1451.       
      2. Palomar, Daniel P., and Mung Chiang. "Alternative distributed algorithms for network utility maximization: Framework and applications." IEEE Transactions on Automatic Control 52.12 (2007): 2254-2269.
    28. Segmentation and multiview 3D reconstruction in image processing
      1. Daniel Cremers, Thomas Pock, Kalin Kolev, and Antonin Chambolle, “Convex Relaxation Techniques for Segmentation, Stereo and Multiview Reconstruction” In Markov Random Fields for Vision and Image Processing. MIT Press, 2011.
      2. Antonin Chambolle, Daniel Cremers, and Thomas Pock,“A convex approach to minimal partitions” SIAM Journal on Imaging Sciences. 5(4):1113–1158, 2012
      3. Kalin Kolev, Maria Klodt, Thomas Brox, and Daniel Cremers,“Continuous global optimization in multiview 3d reconstruction,” International Journal of Computer Vision. 84(1):80–96, 2009.
    29. Game theoretic communication system design
      1. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Competitive Design of Multiuser MIMO Systems based on Game Theory: A Unified View,” IEEE JSAC: Special Issue on Game Theory , vol. 25, no. 7, Sept. 2008.
      2. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Optimal Linear Precoding Strategies for Wideband Noncooperative Systems Based on Game Theory,” IEEE Trans.  on Signal Processing , vol. 56, no. 3, March 2008.
      3. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa , “Asynchronous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels,” IEEE Trans.  on Information Theory, vol. 54, no. 7, July 2008.
      4. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Cognitive MIMO Radio:  A Competitive Optimality Design Based on Subspace Projections,” IEEE Signal Processing Magazine, Nov. 2008.
    30. Signomial Programming:
      1. Mung  Chiang,  “Geometric  programming  for  communication  systems,” Foundations and Trends in Communications and Information Theory , Now Publishers, vol.  2, no.  1-2, Aug.  2006.
      2. Mung  Chiang,  Chee  Wei  Tan,  Daniel  P.  Palomar,  Daniel  O’Neill,  and  David Julian,  “Power Control by Geometric  Programming,” IEEE Trans.  on Wireless Communications, vol.  6, no.  7, pp.  2640-2651, July 2007
    31. Index tracking in finance
      1. Benidis, K., Feng, Y., and Palomar, D. P. (2017). Sparse Portfolios for High-Dimensional Financial Index Tracking. IEEE Transactions on Signal Processing
      2. Xu, F., Xu, Z., and Xue, H., (2015). Sparse index tracking based on L1/L2 model and algorithm. arXiv preprint
      3. Jansen, R., and Van Dijk, R. (2002). Optimal benchmark tracking with small portfolios The Journal of Portfolio Management vol. 28, no. 2, pp. 33–39.
      4. Beasley, J. E., Meade, N., and Chang, T.-J. (2003). An evolutionary heuristic for the index tracking problem. European Journal of Operational Research, vol. 148, no. 3, pp. 621–643.
      5. Scozzari, A., Tardella, F., Paterlini, S., and, Krink, T. (2013). Exact and heuristic approaches for the index tracking problem with UCITS constraints. Annals of Operations Research, vol. 205, no. 1, pp. 235–250.
    32. Multiobjective optimization and pareto optimality
      1. Marler, R. Timothy, and Jasbir S. Arora. "Survey of multi-objective optimization methods for engineering." Structural and multidisciplinary optimization 26.6 (2004): 369-395.
      2. Desideri, Jean-Antoine. "Multiple-gradient descent algorithm (MGDA) for multiobjective optimization." Comptes Rendus Mathematique 350.5-6 (2012): 313-318.       
      3. Fliege, Jorg, and Benar Fux Svaiter. "Steepest descent methods for multicriteria optimization." Mathematical Methods of Operations Research 51.3 (2000): 479-494.
      4. Harada, Ken, Jun Sakuma, and Shigenobu Kobayashi. "Local search for multiobjective function optimization: pareto descent method." Proceedings of the 8th annual conference on Genetic and evolutionary computation. ACM, 2006.
      5. Fliege, Joerg, LM Grana Drummond, and Benar Fux Svaiter. "Newton's method for multiobjective optimization." SIAM Journal on Optimization 20.2 (2009): 602-626.
    33. Saddle point methods for convex optimization
      1. Zhu, Minghui, and Sonia Martinez. "On distributed convex optimization under inequality and equality constraints." IEEE Transactions on Automatic Control 57.1 (2012): 151-164.
      2. Chang, Tsung-Hui, Angelia Nedić, and Anna Scaglione. "Distributed constrained optimization by consensus-based primal-dual perturbation method." IEEE Transactions on Automatic Control 59.6 (2014): 1524-1538.
    34. Integer programming
      1. Park, Jaehyun, and Stephen Boyd. "A semidefinite programming method for integer convex quadratic minimization." Optimization Letters (2017): 1-20.       
      2. Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002). "Cutting planes in integer and mixed integer programming" (PDF). Discrete Applied Mathematics. 123: 387–446.
      3. Castro, J.; Nasini, S.; Saldanha-da-Gama, F. (2017). "A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method"
      4. Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Parallel Algorithm Design for Branch and Bound" (PDF). In Greenberg, H. J. Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press. 
    35. Distributed Optimization
      1. A.  Nedic  and  A.  Ozdaglar.   Distributed  subgradient  methods for multi-agent optimization. IEEE Transactions on Automatic Control , 54(1):48–61, Jan. 2009.
      2. J. C. Duchi, A. Agarwal, and M. J. Wainwright. "Dual averaging for distributed optimization: Convergence analysis and network scaling," IEEE Transactions on Automatic Control, 57(3):592–606, Mar. 2012
      3. E.  Wei  and  A.  Ozdaglar.    Distributed  alternating  direction method  of  multipliers.   In 51st  IEEE  Annual  Conference  on Decision and Control, pages 5445–5450, Dec. 2012.
      4. J. F. C. Mota, J. M. F. Xavier, P. M. Q. Aguiar, and M. Puschel. D-ADMM: A communication-efficient distributed algorithm for separable optimization. IEEE Transactions on Signal Processing, 61(10):2718–2723, May 2013.
      5. W.  Shi,  Q.  Ling,  K  Yuan,  G  Wu,  and  W  Yin.   On  the  linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing , 62(7):1750–1761, April 2014.
    36. Convex optimization in Control Theory
      1. Linear Matrix Inequalities in System and Control Theory Stephen Boyd, Laurent El Ghaoui, E. Feron, and V. Balakrishnan
      2. Linear Controller Design – Limits of Performance, Stephen Boyd and Craig Barratt
    37. Convex optimization in Smart Grid
      1. Samadi, Pedram, et al. "Optimal real-time pricing algorithm based on utility maximization for smart grid." Smart Grid Communications (SmartGridComm), 2010 First IEEE International Conference on. IEEE, 2010.       
      2. Mohsenian-Rad, Amir-Hamed, et al. "Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid." IEEE transactions on Smart Grid 1.3 (2010): 320-331.       
      3. Sortomme, Eric, et al. "Coordinated charging of plug-in hybrid electric vehicles to minimize distribution system losses." IEEE transactions on smart grid 2.1 (2011): 198-205.
    38. Convex optimization in robotics       
      1. Verscheure, Diederik, et al. "Time-optimal path tracking for robots: A convex optimization approach." IEEE Transactions on Automatic Control 54.10 (2009): 2318-2327.       
      2. Schulman, John, et al. "Finding Locally Optimal, Collision-Free Trajectories with Sequential Convex Optimization." Robotics: science and systems. Vol. 9. No. 1. 2013.
      3. Zhu, Minghui, and Sonia Martinez. "On distributed convex optimization under inequality and equality constraints." IEEE Transactions on Automatic Control 57.1 (2012): 151-164.
      4. Derenick, Jason C., and John R. Spletzer. "Convex optimization strategies for coordinating large-scale robot formations." IEEE Transactions on Robotics 23.6 (2007): 1252-1259.
    39. Convex optimization for motion planning
      1. Schulman, John, et al. "Finding Locally Optimal, Collision-Free Trajectories with Sequential Convex Optimization." Robotics: science and systems. Vol. 9. No. 1. 2013.
      2. Prajna, Stephen, Pablo A. Parrilo, and Anders Rantzer. "Nonlinear control synthesis by convex optimization." IEEE Transactions on Automatic Control 49.2 (2004): 310-314.
      3. Schulman, John, et al. "Motion planning with sequential convex optimization and convex collision checking." The International Journal of Robotics Research 33.9 (2014): 1251-1270