SESOP-TN: Combining Sequential Subspace Optimization with Truncated Newton method

Michael Zibulevsky

 

SESOP-TN is a method for very large scale unconstrained optimization of smooth functions. It combines ideas of Sequential Subspace Optimization (SESOP) [1, 4] with those of the Truncated Newton (TN) method [2]. Replacing TN line search with subspace optimization, we allow Conjugate Gradient (CG) iterations to stay matched through consequent TN steps. This resolves the problem of TN sensitivity to an early break of the CG process. For example, when an objective function is quadratic, the SESOP-TN trajectory coincides with the trajectory of CG as applied directly to the objective. Standard TN lacks this property and converges more slowly. Numerical experiments illustrate the effectiveness of the method.

 

Download  the paper                

Old MATLAB code (08.08.2008)     New Beta-version  MATLAB code (04.02.2009)  

   

SESOP-TN MATLAB tool implements the following methods:

  • Polak-Ribiere nonlinear Conjugate Gradients
  • Truncated Newton
  • SESOP:        Sequential Subspace Optimization
  • SESOP-TN:  Sequential Subspace Optimization combined with Truncated Newton

 

 

Directories:

  • Sesop_Basic_BP                -  SESOP-TN Optimization tool + simple example (Basis Pursuit)
  • Sesop_PCD_BasisPursuit  -  Basis Pursuit via PCD-SESOP (parallel coordinate descent)  [4]
  • Sesop_NeuralNet                - Neural Net Training.   Applications: Signal Denoising and Prediction
  • Sesop_SVM                        - Linear L1-L2 Support Vector Machine for Pattern Recognition

 

Brief description of SESOP-TN algorithm

We minimize a function f(x), which has gradient g(x) and Hessian H(x).  Note that the Hessian is not computed explicitly: just Hessian-vector products are used.

Iteration of   SESOP-TN

  1.  TN step: solve Newton system  Hd=-g approximately, using limited number of Conjugate Gradient (CG) steps.

  2. Optimize f(x) over affine subspace spanned by:

  • Directions of several previous steps and gradients of  f(x_k)
  • Direction of the TN step
  • Exit value of the gradient of the quadratic model minimized at TN step
  • Last CG direction of TN step

  3.  Goto  Step 1  (TN), feeding the resulting subspace optimization step into CG starting condition.

Presented procedure allows resolving the typical TN problem, related to the early break of CG process. For example, when f(x) is quadratic, SESOP-TN trajectory is the same as one of CG applied to f(x).  Standard TN would converge slower in this case.

Note that subspace optimization step 2 can be carried very efficiently, if  f(x)= f1(Ax)+f2(x),  where Ax is computationally heavy, and f1(.) and f2(.) are inexpensive (see [1] for the details).

 

 

 

My collaborators at various stages of the work on SESOP and its applications

 

  • Arkadi Nemirovski, Guy Narkiss, Michael Elad, Boaz Matalon, Joseph Shtok, Grigory Begelman, Eli  Osherovich,  Yehuda Pfeffer, Ehud Rivlin, Irad Yavneh

 

 

 

References:

  1. Guy Narkiss and Michael Zibulevsky (2005). "Sequential Subspace Optimization Method for Large-Scale Unconstrained Problems", Tech. Report CCIT No 559, EE Dept., Technion. pdf file
  2. Stephen G. Nash, “A Survey of Truncated-Newton Methods”, Journal of Computational and Applied Mathematics, 124 (2000), pp. 45-59.
  3. Guy Narkiss and Michael Zibulevsky (2005). "Support Vector Machine via Sequential Subspace Optimization", Tech. Report CCIT No 557, EE Dept., Technion. pdf file
  4. Michael Elad, Boaz Matalon, and Michael Zibulevsky, "Coordinate and Subspace Optimization Methods for Linear Least Squares with Non-Quadratic Regularization", Applied and Computational Harmonic Analysis, Vol. 23, pp. 346-367, November 2007. pdf file

 

 

Haifa,   August 8 – September 29,  2008