1.1 math optimization
1.2 application
1.3 Solving optimization problems
general optimization problem
- very difficult to solve
- methods involve some compromise. e.g.,very long computation time, or not always finding the solution
exceptions: certain problem class efficiently and reliably
- least-square problems
- linear programming problem
- convex optimization ~
| - | least-squrares | linear programs | Convex | ||||
|---|---|---|---|---|---|---|---|
| fomula | $minimize | Ax-b | _2^2$ | $min \text{ }c^Tx\\s.t. a_i^Tx \le b_i$ | $min f_0(x)\\s.t. f_i(x)\le b_i,i=1,…m$ | ||
| Analytical Solution | $x^*=(A^TA)^{-1}A^Tb$ | - | - | ||||
| Reliable and Efficient | Y | Y | Y | ||||
| Computation Time | $n^2k(A \in R^{k*m})$ | $ n^2m \text{ if } m \ge n $ | $max\{n^3,n^2m,F\}$where $F$ is cout of evaluating $f_i’s$ and their first and second derivatives | ||||
| A Mature Technique | Y | Y | Y | ||||
| Easy to Recognize | Y | N | N | ||||
| extract | few standard tech increase flexiblility(e.g., including weights, add regularization terms) | few standard trick use to convert problems into linear program(e.g. problems involving $l1$ or $l{\inf}$norms, piecewise-linear fun) | many trick for transforming problem into convex form.surprisingly may problem can be solved via convex optimization |
1.4 Least-squares
solve
- analytical solu: $x^*=(A^TA)^{-1}A^Tb$
- reliable and efficient
- computation time: $n^2k(A \in R^{k*m})$, less if structured
- a mature tech
using
- easy to recognize
- a few standard tech increase flexibility(e.g. including weights, add regularization terms)
Linear program
solve
- no analytic formula
- reliable
- com $ n^2m \text{ if } m \ge n $
- mature
using
- not as easy to recognize
- a few standard trick use to convert problems into linear program(e.g. problems involving $l1$ or $l{\inf}$norms, piecewise-linear fun)
Convex
objective and constraint fun are convex:
if$\alpha + \beta = 1, \alpha \ge 0, \beta \ge 0$
includes least-squares problem and linear programs as special case