Ignizio and Cavalier: Linear Programming, Prentice Hall, 1994. (There
are many good LP texts.)
Baldick: Applied Optimization, Cambridge, 2006. (There are several
powerpoint type presentations available on the web at Prof. Baldick's website.)
Boyd and Vandenberghe, Convex Optimization, Cambridge, 2004.
Jang, Sun and Mizutani, Neuro-Fuzzy and Soft Computing: A
Computational Approach to Learning and Machine Intelligence, Prentice
Hall, 1997.
Various journal papers and notes. See assignment page.
Overview
This course will cover application of optimization and some computational
intelligent system methods to engineering problems. We will begin with
mathematical programming techniques and the formulation of practical
application using these methods. We then begin loosening up the restrictions
of the linear formulation to consider a broad class of problems both convex
and non-convex. As time permits, computational intelligence approaches as
represented by stochastic optimization, neural networks and other pattern
matching approaches (sometimes referred to as soft computation methods) will
then be contrasted with these more traditional approaches. The recommended
background for this course is primarily a solid foundation in linear
algebra. There will be some minor programming required in Matlab, so it
will be desirable to be familiar with Matlab. Most of the examples will be
chosen from applications to power systems but the course will be taught in a
general way and no specific background in power systems is necessary.
The following list of topics is way too long to cover in a semester so I
will pick and choose among the latter topics. Students with a preference for
certain topics should feel to make requests.
I. Fundamentals of Constrained Optimization
Linear Formulation
Overview (Reading: Baldick
Chapter 1 and 2)
Linear optimization/programming
(Reading: Baldick Chapter 4; ref. Ignizio and Cavalier, pp. 10-75;
167-182)
General form
Standard form
Extreme points
Feasible regions
Convexity
Optimality conditions
Duality
Relationship to graphs and network structure
Linear programming solution methods
(ref. Ignizio and Cavalier, pp. 80-93; 192-199)
Simplex method
Dual simplex method
Integer, logical and network
constraints (ref. Notes)
Formulation
Piece-wise linear transformations convex and non-convex
Branch and bound method
Binary programming
Non-linear integer programming - transformation to linear
programming
Other linear programming solution
methods
Network simplex method (brief overview)
Interior point methods (brief overview for now)
Ellipsoid algorithm
Karmarkar's projective algorithm
Computational complexity
Example applications
Shortest path and flow problems
Weighted Least Absolute Value estimation
WLAV vs Weighted Least Squares (WLS) estimation
Alarm processing using a set covering approach
Unit commitment or other scheduling problems (skipped for now)
Graph Problems and Concepts of Search
Graph formulations (ref.
Notes)
Network structure
Search methods
Depth-first
Breadth-first
Shortest path algorithms
Heuristic search
A* algorithm
Relationship to linear programming and other constrained
optimization
Search as a component of other optimization approaches
Example applications
Map problems
Routing - system restoration
Lagrangian Duality
Deeper concepts of duality (ref.
Notes, Chapter 3 Baldick)
General duality
Karesh Kuhn Tucker conditions
Convexity and the duality gap
Lagrangian relaxation
Example applications
Scheduling
Unit commitment
Constrained network problems with Lagrangian Relations - my
lightly annotated version
on example from MIT
Open Course
Gradient and gradient derived methods
Using derivative information - review of
gradient and related methods
Gauss/Steepest Descent
Newton
Levenberg-Marquardt modifications
Relationship between zeros of a function and optimal solutions
Alternatives to the derivative
calculations (derivative free) (ref. Jang, et al, pp.
129-195).
Secant method
Line section methods (bisection)
Downhill Simplex search
Quadratic programming and successive quadratic programming
Formulation
Solutions methods - reformulation as equivalent to a linear
program
Example applications
Coming later in vector support machines
More on formulating meaningful and useful optimization problems
Simple
techniques to improve problem formulation (ref. Notes,
Chapter 3 Baldick)
Utility theory and goal programming
Multi-objectives and soft constraints (ref. Notes, Ignizio and
Cavalier, pp. 506-570)
Objectives vs. constraints - levels of aspirations
Multi-objectives
Trade-offs
Soft constraints: interval or fuzzy approaches
Detailed example
Vector optimization
II. Constrained Optimization for Understanding Data - Curve fitting,
Model Identification and Classification
Data driven optimization - classification and constrained
optimization; statistical methods
Vector support machines - linear program solutions
Regression and traditional statistical methods
Example applications
Load forecasting
Other data driven approaches
- pattern matching as optimization; network and decision methods
(ref. Notes, Jang, et al, pp. 226-238, 316-327)
Pre-processing of data as constrained optimization
Principle component analysis
Networks of computation based methods
Hopfield neural net skipped for now
Stability
Capacity
Solving optimization problems
Example: Hopfield net limits
Feedforward neural networks
Activation functions
Learning methods and parameters
Training as an optimization problem
Decision methods
Bayesian
Decision trees
Example applications
Electricity price forecasting
Wind power forecasting
Population based methods
(ref. Jang, et al, pp. 129-195).