MS&E 310: Linear Programming
Formulation of standard linear programming models. Theory of polyhedral convex sets, linear inequalities, alternative theorems, and duality. Variants of the simplex method and the state of art interiorpoint algorithms. Sensitivity analyses, economic interpretations, and primaldual methods. Relaxations of harder optimization problems and recent convex conic linear programs. Applications include game equilibrium facility location. Prerequisite:
MATH 113 or consent of instructor.
Terms: Aut

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Ye, Y. (PI)
MS&E 311: Optimization
Applications, theories, and algorithms for finitedimensional linear and nonlinear optimization problems with continuous variables. Elements of convex analysis, first and secondorder optimality conditions, sensitivity and duality. Algorithms for unconstrained optimization, and linearly and nonlinearly constrained problems. Modern applications in communication, game theory, auction, and economics. Prerequisites:
MATH 113, 115, or equivalent.
Terms: not given this year

Units: 3

Grading: Letter or Credit/No Credit
MS&E 312: Advanced Methods in Numerical Optimization (CME 334)
Topics include interiorpoint methods, relaxation methods for nonlinear discrete optimization, sequential quadratic programming methods, optimal control and decomposition methods. Topic chosen in first class; different topics for individuals or groups possible. Individual or team projects. May be repeated for credit.
Terms: Aut

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
Instructors:
Murray, W. (PI)
MS&E 314: Linear and Conic Optimization with Applications (CME 336)
Linear, semidefinite, conic, and convex nonlinear optimization problems as generalizations of classical linear programming. Algorithms include the interiorpoint, barrier function, and cutting plane methods. Related convex analysis, including the separating hyperplane theorem, Farkas lemma, dual cones, optimality conditions, and conic inequalities. Complexity and/or computation efficiency analysis. Applications to combinatorial optimization, sensor network localization, support vector machine, and graph realization. Prerequisite: MS&E 211 or equivalent.
Terms: alternate years, given next year

Units: 3

Grading: Letter or Credit/No Credit
MS&E 315: Numerical Optimization (CME 304)
Solution of nonlinear equations; unconstrained optimization; linear programming; quadratic programming; global optimization; general linearly and nonlinearly constrained optimization. Theory and algorithms to solve these problems. Prerequisite: background in analysis and numerical linear algebra.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Murray, W. (PI)
;
Sing Long Collao, C. (TA)
MS&E 316: Discrete Mathematics and Algorithms (CME 305)
Topics: Basic Algebraic Graph Theory, Matroids and Minimum Spanning Trees, Submodularity and Maximum Flow, NPHardness, Approximation Algorithms, Randomized Algorithms, The Probabilistic Method, and Spectral Sparsification using Effective Resistances. Topics will be illustrated with applications from Distributed Computing, Machine Learning, and largescale Optimization. Prerequisites:
CS 261 is highly recommended, although not required.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
MS&E 317: Algorithms for Modern Data Models (CS 263)
We traditionally think of algorithms as running on data available in a single location, typically main memory. In many modern applications including web analytics, search and data mining, computational biology, finance, and scientific computing, the data is often too large to reside in a single location, is arriving incrementally over time, is noisy/uncertain, or all of the above. Paradigms such as mapreduce, streaming, sketching, Distributed Hash Tables, Bulk Synchronous Processing, and random walks have proved useful for these applications. This course will provide an introduction to the design and analysis of algorithms for these modern data models. Prerequisite: Algorithms at the level of
CS 261.
Terms: not given this year

Units: 3

Grading: Letter or Credit/No Credit
MS&E 318: LargeScale Numerical Optimization (CME 338)
The main algorithms and software for constrained optimization emphasizing the sparsematrix methods needed for their implementation. Iterative methods for linear equations and least squares. The simplex method. Basis factorization and updates. Interior methods. The reducedgradient method, augmented Lagrangian methods, and SQP methods. Prerequisites: Basic numerical linear algebra, including LU, QR, and SVD factorizations, and an interest in MATLAB, sparsematrix methods, and gradientbased algorithms for constrained optimization. Recommended: MS&E 310, 311, 312, 314, or 315;
CME 108, 200, 302, 304, 334, or 335.
Terms: Spr

Units: 3

Grading: Letter (ABCD/NP)
Instructors:
Saunders, M. (PI)
;
Sun, Y. (PI)
MS&E 319: Approximation Algorithms
Combinatorial and mathematical programming techniques to derive approximation algorithms for NPhard optimization problems. Prossible topics include: greedy algorithms for vertex/set cover; rounding LP relaxations of integer programs; primaldual algorithms; semidefinite relaxations. May be repeated for credit. Prerequisites: 112 or
CS 161.
Terms: Aut

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
Instructors:
Saberi, A. (PI)
MS&E 321: Stochastic Systems
Topics in stochastic processes, emphasizing applications. Markov chains in discrete and continuous time; Markov processes in general state space; Lyapunov functions; regenerative process theory; renewal theory; martingales, Brownian motion, and diffusion processes. Application to queueing theory, storage theory, reliability, and finance. Prerequisites: 221 or
STATS 217;
MATH 113, 115. (Glynn)
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Glynn, P. (PI)
Filter Results: