Outline
- Mathematical Optimization
- Least-squares and linear programming
- Convex Optimization
- Example
- Course goals and topics
- Nonlinear optimization
- Brief history of convex optimization
Mathematical Optimization
(mathematical) optimization problem
minimize f_0(x)
subject to f_i(x)\leq b_i,i=1,...,m
optimal solution x^* has smallest value of f_0 among all vectors that satisfy the constraints
Least-squares
problem: minimize ||Ax-b||_2^2
solving least-square problems:
- analytical solution: x^* = (A^TA)^{-1}A^Tb
- reliable and effiecient algorithms and software
- computation time proportional to n^2k(A\in R^{k\times n}); less if structured
- a mature technology
using least-squares:
- least-squares problems are easy to recognize
- a few standard techniques increase flexibility
Linear Programming
problem:
minimize c^Tx
subject to a_i^Tx\leq b_i,i=1,...,n
In a word, linear programming is not easy to solve,there is no analytical solution.
Convex Optimization Problem
Same as Mathematical Optimization,but the constraint functions are Convex.
