袁亚湘-优化方法,从瞎子爬山谈起.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 小人物 ?? 大人物 Hotelling(1885-1973) ： “But we all know the world is nonlinear.” Von Neumann(1903-1957): “Mr. Chairman, Mr Chairman, if the speaker doesn’t mind, I would like to reply for him. The speaker titled his talk `linear programming’ and carefully stated his axioms. If you have an application that satisfies the axioms, well use it. If it does not, then don’t.” 线性规划：内点法 Interior Point Method (Karmarkar, 1984) xk 0 ? 内点 N. Karmarkar(1957- ) November 19, 1984 内点法 与 罚函数 min cTx s.t. A x = b x = 0 Log-barrier function: min cTx - ∑ log (xi) s.t. A x = b KKT ? Newton’s Step 内点法和平面几何 内点法 与 SDP Semi-Definite Programming (SDP) min C, X s.t. A, X = b X = 0 C,X = Trace CTX when X=xxT ? C,X = xTCx 交替方向法 交替方向方法 min f(x) x=(x1,…, xn) 固定 xj (j≠i), 对 xi 进行优化 例子： Gauss-Seidel 方法 求解 Ax = b 交替方向方法 -- L1 优化 min ||x||1 s.t. Ax = b 罚函数方法： 交替方向方法 -- L1 优化 对于: min ||Ay-b||2 可以 用梯度法 下降； 对于 min ||x||1 |x+i | = |xi| - δ (shrinkage operator) Now this supreme wisdom, united to goodness that is no less infinite, cannot but have chosen the best. For as a lesser evil is a kind of good, even so a lesser good is a kind of evil if it stands in the way of a greater good; and the would be something to correct in the actions of God if it were possible to the better. As in mathematics, when there is no maximum nor minimum, in short nothing distinguished, everything is done equally, or when that is n