EE392o: Optimization Projects
In 2006-07, EE392 was turned into a permanent course,
EE364b:
Convex Optimization II.
Lecture topics and notes
- Introduction. Structure of course, student requirements,
timeline. About the project; ideas for projects.
- Subgradients. Basics of
subgradients and the subdifferential. Subgradient calculus,
examples. Optimality conditions for nondifferentiable problems.
Relation to directional derivative.
- Localization methods. Basic idea
of localization and cutting-plane methods. CG method, ACCPM.
Notes on localization and
cutting-plane methods.
- Ellipsoid method.
- Subgradient
methods. Subgradient method with fixed and diminishing step
lengths. Convergence theorems and proofs. Projected subgradient
method. Example: Decentralized dual algorithm for optimal network
flow. Notes on subgradient
methods.
- Primal and dual decomposition. Primal and dual
decomposition for decentralized, distributed methods.
Notes on decomposition methods.
Decomposition method example
(slides).
- Alternating projections. Alternating projections and
extensions. Convergence results and proofs. Examples.
Notes on alternating projections.
Alternating projections example
(slides).
- Numerical linear algebra. Covers material in Appendix C
of Boyd and Vandenberghe.
- Numerical linear algebra
software. Practical aspects and issues. BLAS levels I, II,
III; ATLAS. LAPACK. Sparse packages. Notes on
numerical linear algebra software.
- Convex/concave games. Matrix games, mixed strategies,
maxmin theorem, solution via LP. Bilinear polyhedral games; robust
LP example. Continuous convex-concave games, maxmin theorem,
transforming to minmin via duality. Numerical methods for
convex-concave games: Newton's method; barrier method. Example:
minimax power allocation in wireless system.
Notes on convex-concave games and
minimax.
- Branch-and-bound methods. Branch-and-bound, global
optimization, integer programming.
Notes on branch and bound methods.
Notes on branch and bound methods (slides).
- Relaxation methods for nonconvex QCQP. SDP and
Lagrangian relaxations; connection to randomized algorithms.
Notes on relaxation and randomized methods
for nonconvex QCQP..
- Robust optimization. Lecture
by Professor Laurent El Ghaoui.
- Convex optimization in
classification problems. Lecture by Professor Laurent El
Ghaoui.
- Sum-of-squares (SOS)
relaxations for hard problems. Lecture by Professor S.
Lall.
- Convex optimization applications in signal processing.
Lecture by Professor Z.-Q. Luo. Interior-point
optimization techniques for adaptive filtering.
- Convex optimization applications in communications.
Lecture by Professor Z.-Q. Luo.
Minimum BER linear transceivers for block communication systems.
- SDP for Euclidean distance
geometric optimization. Ad hoc wireless network sensor
location. Euclidean ball packing. Lecture by Professor Yinyu
Ye.
- Convex optimization applications in communications.
Lecture by Professor Z.-Q. Luo.
Optimal tranceiver design for
multi-access communication.
top of EE392o page
Project topics
top of EE392o page
Project presentation schedule (Tentative)
Dec. 4th, Thursday:
- 1:00-1:30 pm: Vivek Farias (Scheduling Projects with Shared Resources)
- 1:30-2:00 pm: Ritesh Madan (A Distributed Algorithm for Maximum
Lifetime Routing in Ad Hoc Wireless Networks)
- 2:00-2:30 pm: Erik Stauffer (Maximizing Outage Capacity)
- 2:30-3:00 pm: Unscheduled
Dec. 11th, Thursday, Session 1 (Packard 277):
- 10:00-10:30 am: Elad Alon and Vladimir Stojanovic (Optimal
Utilization of Multi-mode Fiber for Optical Communications)
- 10:30-11:00 am: Randy Cowgill (Convex Relaxations for
Decentralized Decision Problems)
- 11:00-11:30 am: Eunchul Yoon and Taesang Yoo (Optimal Linear
pre-coder and Power Allocation for MIMO-OFDM Systems with Partial
and Imperfect Channel Knowledge)
- 11:30-12:00 pm: Amal Ekbal (Distributed Power Control in Multiple
Antenna Wireless Networks)
- 12:00-12:30 pm: Jun Sun and Arpita Ghosh (Eigenvalue Optimization
for Laplacian Matrices of Graphs)
Dec. 11th, Thursday, Session 2 (Packard 277):
- 2:00-2:30 pm: Christopher Gadda (Optimal Grasp Selection for
Climbing Robots)
- 2:30-3:00 pm: Alok Agarwal (Minimization of PAPR in OFDM Systems)
- 3:00-3:30 pm: Sunghee Yun and Dinesh Patil (Optimal Sizing of
Digital Circuits via Statistical Problem Formulation using
Generalized Geometric Programming)
- 3:30-4:00 pm: Almir Mutapcic and Majid Emami (Dynamic Routing with
Active Queue Management)
Dec. 12th, Friday, Session 1 (Packard 277) :
- 10:00-10:30 am: Ramesh Kumar and Joy Rajiv (Option Pricing Based
on Dual Underlying Assets Using Convex Optimization)
- 10:30-11:00 am: Mehdi Mohseni (Sub-optimal Throughput Maximization
Schemes for Vector Broadcast Channels)
- 11:00-11:30 am: Mayank Sharma
- 11:30-12:00 pm: Alessandro Magnani (Maximum a-posteriori
Probability Estimation of Sigma-Delta Raw Data)
Dec. 11th, Friday, Session 2 (Packard 277):
- 2:00-2:30 pm: Robin Raffard (Decentralized Control of Multiple
Vehicle Systems using Convex Optimization)
- 2:30-3:00 pm: Kaustuv (Exploiting Sparsity in
the Dual-Scaling Method for Semidefinite Programs via Automatic
Differentiation of the Logarithmic Barrier Function
- 3:00-3:30 pm: Mark Brady (The Worst-case Interference in DSL
Systems Employing Dynamic Spectral Management)
- 3:30-4:00 pm: Sina Zahedi (Gaussian Channel Capacity with Feedback)
top of EE392o page
Basic course information
Course description:
EE392o is a new advanced project-based course that follows
EE364. Some lectures will be on topics not covered in EE364,
including subgradient methods, decomposition and decentralized
convex optimization, exploiting problem structure in
implementation, global optimization via branch & bound, and
convex-optimization based relaxations. Other lectures will cover
applications in areas such as control, circuit design, signal
processing, and communications in more depth. The main course
requirement is a substantial project, carried out in small
groups.
Credit: 3 units.
Lectures: Tuesdays and Thursdays, 1:15-2:30, location
380-380D.
Instructors:
Administrative assistant:
Denise Murphy,
Packard 267, 723-4731, Fax 723-8473,
denise@ee.stanford.edu
Teaching Assistants:
TA office hours & location: Monday 4pm to 6pm and
Friday 5pm to 6pm in Packard 242
Textbook:
Convex
Optimization, S. Boyd and L. Vandenberghe, Cambridge
University Press 2003.
Course requirements: There will be no homework or exams;
the only formal requirement is a substantial class project. Class
attendance (within reason) is also required.
Prerequisite: EE364 or consent of instructor.