Jun 17, 2009

最优化的Tricks

1. minimax
minimize max{f_i(x)}
to
minimize c
s.t. f_i(x) <= c

SVM 中 maximin 的推导,见 MLPR p328 的note。


2. 带绝对值
minimize |f(x)|
to:
minimize c
st. f(x)<=c
-f(x)<=c

理解:
原问题等价于
minimize max{f(x) -f(x)}

3. non-negative


minimize \quad [f(x)]_+ 
to
minimize c
s.t. f(x) <= c
c >= 0

理解
原问题等价于
minimize max{f(x) 0}




例子:
Hinge loss
参见 MLPR by bishop, p337
minimize [1-y_n t_n]+

转化为
\eta >=0
1-y_n t_n <= \eta

4. slack variables
Two kinds of slack variables. The first one converts inequalities to equalities constraints. The second one provides soft margin as in SVM.


3.

0 comments: