CSE591 (Fall 2008) Optimization Algorithms with Engineering Applications
Professor Guoliang (Larry) Xue
Lectures: MW 03:30pm--04:45pm, BYAC190
Office Hours: MW 04:45pm--06:00pm, BYAC442
Class Website:
https://my.asu.edu
Overview:
This course is designed for graduate students in Computer Science and
Engineering, as well as graduate students in other Engineering fields.
During your dissertation or thesis research, most of you will be faced
with some non-trivial optimization problems. The following are some
examples. In video-delivery, you may need to find the fastest way to
deliver the video. In QoS routing, you may need to find a path subject
to several QoS constraints, or you may need to find a multicast tree
subject to several QoS constraints. In cross-layer design of wireless
networks, you may need to find a good combination of channel assignment,
transmission
scheduling, and routing, in order to meet some communication requirement
while satisfying fairness and/or interference constraints. In sensor
networks, you may need to maximize lifetime, guarantee coverage, maintain
a good topology, etc. In VLSI design, you may need to find the shortest
circuit interconnecting a set of pins while satisfying some constraints.
In bioinformatics, you may need to find biclusters or network motifs.
In multimedia services, you may need to deliver some on-demand video
files of a given quality to the clients within a specified delay bound.
In survivable design, you may need to design a system that can provide
guaranteed recovery while using not too much resource. The list goes on
and on.
If you have
been trying to solve the optimization problems in your research and wish
to have more powerful techniques, this may be the course you need to take.
In the first part of this course, we will study some fundamental theory
and algorithms/techniques of optimization (linear, nonlinear, convex,
as well as combinatorial). These include
- Convex sets
- Convex functions
- Optimality conditions
- Duality
- Unconstrained minimization
- Equality constrained minimization
- Interior-point methods for convex optimization
The materials for this part will be Part 1 and Part 3 of
Boyd and Vandenberghe, plus some materials from Bazaraa+Sherali+Shetty.
In the second part of this course, we will study applications of these
methods in engineering applications, plus some approximation schemes the
instructor has developed for hard problems. The materials will come from
research papers from the literature (Science, Nature, SIAM Journal on
Optimization, IEEE Transactions on Networking, IEEE Transactions on
Communications, IEEE Journal on Selected Areas in Communications,
IEEE Infocom, ACM MobiCom, ACM MobiHoc).
The problems include (tentatively) the following.
- Interference-aware scheduling in wireless networks
- Survivable network design
- Video-on-demand delivery
- Relay node placement in wireless sensor networks
- Grade of service multicasting
- Coverage and data aggregation in sensor networks
- Multi-constrained QoS Routing
- Cross-layer design in wireless networks
- Topology control in wireless networks
Grading:
There is NO formal exam (midterm, final).
Your grade will be based on the following
- 60% homework: basics plus paper critiques/reviews;
- 40% class project.
References:
-
Convex Optimization by Boyd and Vandenberghe,
www.stanford.edu/~boyd/cvxbook
-
Nonlinear Programming: Theory and Algorithms,
Mokhtar S. Bazaraa, Hanif D. Sherali, and C.M. Shetty.
-
Lecture Notes and Selected Papers,
will be available electronically.