- Instructors: Ketan Rajawat
- Prerequisites:
Linear Algebra, Probability
**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:- Know about the applications of convex optimization in signal processing, wireless communications, and networking research.
- Be able to recognize convex optimization problems arising in these areas.
- Be able to recognize ‘hidden’ convexity in many seemingly non-convex problems; formulate them as convex problems.
- Be able to develop low-complexity, approximate solutions for difficult non-convex problems.
- References:
- Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press. [Online]. http://www.stanford.edu/~boyd/cvxbook/
- Convex Optimization in Signal Processing and Communications, D. P. Palomar, Y. C. Eldar. Cambridge Press, 2010.
- IEEE Signal Processing Magazine- Special Issue on Advances in Convex Optimization, Vol. 27, No. 3, May 2010.
- Dimitri P. Bertsekas, Convex Analysis and Optimization, Athena-Scientific, 2003.
- Time and place: Lectures will be made available online, Discussion every Friday at 11am on zoom
- This course will cover (approximately)
- Background on linear algebra
- Convex sets, functions, and problems
- Examples of convex problems: LP, QCQP, SOCP
- Duality, KKT conditions
- Geometric programming and applications
- Linear and quadratic classification
- Network optimization
- Sparse regression, Lasso, ridge regression and applications in image processing
- Robust least squares and applications in signal processing
- Support vector machines and applications in machine learning
- Semidefinite programming and applications in experiment design
- Semidefinite relaxation and applications in MIMO detection, integer programming
- Low rank matrix completion and applications in recommendor systems
- Multidimensional scaling and applications in sensor localization
- Numerical linear algebra, basics of interior point methods
- Tentative list of topics for Term Paper (only sample papers are provided, others can also be chosen, specify: theory/mixed/application mode)
- Low-Rank Matrix Factorization:
- 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. - 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. - Non-convex optimization for Machine Learning (several topics):
- Jain, Prateek, and Purushottam Kar. "Non-convex optimization for machine learning."
*arXiv preprint arXiv:1712.07897*(2017). - Relevant slides: https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/nonconvex.pdf
- Recent Theoretical Advances in Non-Convex Optimization
- Danilova, Marina, et al. "Recent theoretical advances in non-convex optimization."
*arXiv preprint arXiv:2012.06188*(2020). - Zhang, Yuqian, Qing Qu, and John Wright. "From symmetry to geometry: Tractable nonconvex problems."
*arXiv preprint arXiv:2007.06753*(2020). - Blind deconvolution, demixing, phase retrieval etc:
- 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.
- A. Ahmed, A. Aghasi, P. Hand, “Simultaneous phase retrieval and blind deconvolution via convex programming,” arXiv preprint arXiv:1904.12680, 2019.
- 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.
- J. Dong and Y. Shi, “Nonconvex demixing from bilinear measurements,” IEEE Trans. Signal Process., vol. 66, pp. 5152–5166, Oct. 2018.
- 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.
- Difference-of-convex programming:
- 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. - Riemannian/geometric optimization (generalizes geometric programming):
- Introductory slides: https://www.math.fsu.edu/~whuang2/pdf/slides_2016-GMDL.pdf
- Papers by Suvrat Sra from MIT, see relevant talk at: https://www.youtube.com/watch?v=-1BK70HM6ME
- Blog post by Andreas Bloch: https://andbloch.github.io/Stochastic-Gradient-Descent-on-Riemannian-Manifolds
- H Zhang, S J. Reddi, S. Sra, Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
- Online
learning and online convex optimization
- Shai
Shalev-Shwartz, Foundations and Trends in ML, 4(2), 2011
- Introduction
to Online optimization
- Elad
Hazan, Foundations and Trends in Optimization, 2(3-4), 2015
- Proximal
Algorithms
- Neal
Parikh and Stephen Boyd (2014), "Proximal Algorithms", Foundations and
Trends in Optimization: Vol. 1: No. 3, pp 127-239
- Multi-period
investment
- 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
- 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
- Submodularity
and convexity
- Francis
Bach (2013), "Learning with Submodular Functions: A Convex Optimization
Perspective", Foundations and Trends in Machine Learning: Vol. 6: No.
2-3.
- Learning
over Networks
- Ali
H. Sayed (2014), "Adaptation, Learning, and Optimization over
Networks", Foundations and Trends in Machine Learning: Vol. 7: No.
4-5, pp 311-801.
- Approximate
dynamic programming in transportation/logistics
- 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.
- Sequential
stochastic optimization, dynamic programming
- http://castlelab.princeton.edu/html/Papers/Powell-UnifiedFrameworkStochasticOptimization_July222017.pdf
- Clearing
the Jungle of Stochastic Optimization, Informs Tutorials in Operations
Research: Bridging Data and Decisions, pp. 109-137, November, 2014
- Subgradient
methods (older papers, find newer ones):
- S.
Boyd and A. Mutapcic, Subgradient Methods , Notes for EE364b,
Stanford University, 2006. Available online.
- N.
Shor, Minimization Methods for
Non-Differentiable Functions , Springer Series in
Computational Mathematics, Springer, 1985.
- D.
Bertsekas, Nonlinear Programming. Athena Scientific, 1999.
- Robust
Optimization
- Bertsimas,
Dimitris, David B. Brown, and Constantine Caramanis. "Theory and
applications of robust optimization."
*SIAM review*53.3 (2011): 464-501. - Xu,
Huan, Constantine Caramanis, and Sujay Sanghavi. "Robust PCA via
outlier pursuit."
*Advances in Neural Information Processing Systems*. 2010. - Coordinate
ascent/descent
- Yu.
Nesterov, Efficiency of coordinate descent methods on huge-scale
optimization problems, SIAM Journal on Optimization, 2012
- P.
Richt ́arik and M. Takac, Iteration complexity of randomized
block-coordinate descent methods for minimizing a composite function,
Mathematical Programming, 2014
- P.
Tseng and S. Yun, A coordinate gradient descent method for nonsmooth
separable minimization, Mathematical Programming, 2009
- Large-scale
optimization
- 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
- 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. - Bottou,
Leon. "Large-scale machine learning with stochastic gradient descent."
*Proceedings of COMPSTAT'2010*. Physica-Verlag HD, 2010. 177-186. - Semi-stochastic
methods:
- Konecny,
Jakub, and Peter Richtarik. "Semi-stochastic gradient descent methods."
*arXiv preprint arXiv:1312.1666*(2013). - 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. - Konecny,
Jakub, Zheng Qu, and Peter Richtarik. "Semi-stochastic coordinate
descent."
*Optimization Methods and Software*32.5 (2017): 993-1005. - Konecny,
Jakub, Zheng Qu, and Peter Richtarik. "S2cd: Semi-stochastic coordinate
descent."
*NIPS Optimization in Machine Learning workshop*. 2014. - Stochastic
and online optimization
- A.
Nemirovski, A. Juditsky, G. Lan and A. Shapiro,Robust stochastic
approximation approach to stochastic programming, SIAM Journal on
Optimization (2009)
- Yu.
Nesterov, Primal-dual subgradient methods for convex problems,
Mathematical Programming (2009)
- L.
Xiao, Dual averaging methods for regularized stochastic learning and
online optimization, Journal of Machine Learning Research (2010)
- 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)
- Variance
reduced stochastic gradient descent
- R.
Johnson and T. Zhang, Accelerating stochastic gradient descent using
predictive variance reduction NIPS (2013)
- L.
Xiao and T. Zhang, A proximal stochastic gradient method with
progressive variance reduction
- 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. - Schmidt,
Mark, Nicolas Le Roux, and Francis Bach. "Minimizing finite sums with
the stochastic average gradient."
*Mathematical Programming*162.1-2 (2017): 83-112. - ADMM
variants
- D.
Goldfarb, S. Ma, K. Scheinberg, Fast alternating linearization methods
for minimizing the sum of two convex functions, (2010)
- T.
Goldstein and S. Osher, The split Bregman method for L1-regularized
problems, SIAM J. Imag. Sciences (2009)
- Subgradient
methods
- Nedic,
Angelia, and Asuman Ozdaglar. "Distributed subgradient methods for
multi-agent optimization." IEEE Transactions on Automatic Control 54.1
(2009): 48-61.
- 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. - 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. - Smoothing
- Yu.
Nesterov, Smooth minimization of non-smooth functions, Mathematical
Programming (2005).
- Yu.
Nesterov, Excessive gap technique in nonsmooth convex minimization,
SIAM Journal on Optimization (2005)
- Majorization
Minimization
- 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. - 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. - Mairal,
Julien. "Incremental majorization-minimization optimization with
application to large-scale machine learning."
*SIAM Journal on Optimization*25.2 (2015): 829-855. - Convex
optimization in Finance
- 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.
- Blind
deconvolution
- Ahmed,
Ali, Benjamin Recht, and Justin Romberg. "Blind deconvolution using
convex programming."
*IEEE Transactions on Information Theory*60.3 (2014): 1711-1732. - 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. - 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. - Network
utility maximization (Palomar Chiang)
- 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. - 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. - Segmentation
and multiview 3D reconstruction in image processing
- 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.
- Antonin
Chambolle, Daniel Cremers, and Thomas Pock,“A convex approach to
minimal partitions” SIAM Journal on Imaging Sciences. 5(4):1113–1158,
2012
- 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.
- Game
theoretic communication system design
- 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.
- 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.
- 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.
- 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.
- Signomial
Programming:
- Mung
Chiang, “Geometric programming
for communication systems,” Foundations and Trends
in Communications and Information Theory , Now Publishers,
vol. 2, no. 1-2, Aug. 2006.
- 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
- Index
tracking in finance
- Benidis,
K., Feng, Y., and Palomar, D. P. (2017). Sparse Portfolios for
High-Dimensional Financial Index Tracking. IEEE Transactions on Signal
Processing
- Xu,
F., Xu, Z., and Xue, H., (2015). Sparse index tracking based on L1/L2
model and algorithm. arXiv preprint
- 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.
- 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.
- 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.
- Multiobjective
optimization and pareto optimality
- Marler,
R. Timothy, and Jasbir S. Arora. "Survey of multi-objective
optimization methods for engineering." Structural and multidisciplinary
optimization 26.6 (2004): 369-395.
- Desideri,
Jean-Antoine. "Multiple-gradient descent algorithm (MGDA) for
multiobjective optimization." Comptes Rendus Mathematique 350.5-6
(2012): 313-318.
- Fliege,
Jorg, and Benar Fux Svaiter. "Steepest descent methods for
multicriteria optimization."
*Mathematical Methods of Operations Research*51.3 (2000): 479-494. - 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.
- Fliege,
Joerg, LM Grana Drummond, and Benar Fux Svaiter. "Newton's method for
multiobjective optimization." SIAM Journal on Optimization 20.2 (2009):
602-626.
- Saddle
point methods for convex optimization
- Zhu,
Minghui, and Sonia Martinez. "On distributed convex optimization under
inequality and equality constraints." IEEE Transactions on Automatic
Control 57.1 (2012): 151-164.
- 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.
- Integer
programming
- Park,
Jaehyun, and Stephen Boyd. "A semidefinite programming method for
integer convex quadratic minimization."
*Optimization Letters*(2017): 1-20. - Marchand,
Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002).
"Cutting planes in integer and mixed integer programming" (PDF).
Discrete Applied Mathematics. 123: 387–446.
- 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"
- 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.
- Distributed
Optimization
- A.
Nedic and A.
Ozdaglar. Distributed
subgradient methods for multi-agent optimization. IEEE
Transactions on Automatic Control , 54(1):48–61, Jan. 2009.
- 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
- 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.
- 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.
- 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.
- Convex
optimization in Control Theory
- Linear
Matrix Inequalities in System and Control Theory Stephen Boyd, Laurent
El Ghaoui, E. Feron, and V. Balakrishnan
- Linear
Controller Design – Limits of Performance, Stephen Boyd and Craig
Barratt
- Convex
optimization in Smart Grid
- 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.
- 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. - 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. - Convex
optimization in robotics
- Verscheure,
Diederik, et al. "Time-optimal path tracking for robots: A convex
optimization approach."
*IEEE Transactions on Automatic Control*54.10 (2009): 2318-2327. - Schulman,
John, et al. "Finding Locally Optimal, Collision-Free Trajectories with
Sequential Convex Optimization."
*Robotics: science and systems*. Vol. 9. No. 1. 2013. - Zhu,
Minghui, and Sonia Martinez. "On distributed convex optimization under
inequality and equality constraints." IEEE Transactions on Automatic
Control 57.1 (2012): 151-164.
- 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.
- Convex
optimization for motion planning
- Schulman,
John, et al. "Finding Locally Optimal, Collision-Free Trajectories with
Sequential Convex Optimization."
*Robotics: science and systems*. Vol. 9. No. 1. 2013. - Prajna,
Stephen, Pablo A. Parrilo, and Anders Rantzer. "Nonlinear control
synthesis by convex optimization."
*IEEE Transactions on Automatic Control*49.2 (2004): 310-314. - 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