Actual source code: ssls.h

      1: // Context for SSXLS
      2: //   -- semismooth (SS) - function not differentiable
      3: //                      - merit function continuously differentiable
      4: //                      - Fischer-Burmeister reformulation of complementarity
      5: //                        - Billups composition for two finite bounds
      6: //   -- infeasible (I)  - iterates not guaranteed to remain within bounds
      7: //   -- feasible (F)    - iterates guaranteed to remain within bounds
      8: //   -- linesearch (LS) - Armijo rule on direction
      9: //
     10: // Many other reformulations are possible and combinations of
     11: // feasible/infeasible and linesearch/trust region are possible.
     12: //
     13: // Basic theory
     14: //   Fischer-Burmeister reformulation is semismooth with a continuously
     15: //   differentiable merit function and strongly semismooth if the F has
     16: //   lipschitz continuous derivatives.
     17: //
     18: //   Every accumulation point generated by the algorithm is a stationary
     19: //   point for the merit function.  Stationary points of the merit function
     20: //   are solutions of the complementarity problem if
     21: //     a.  the stationary point has a BD-regular subdifferential, or
     22: //     b.  the Schur complement F'/F'_ff is a P_0-matrix where ff is the
     23: //         index set corresponding to the free variables.
     24: //
     25: //   If one of the accumulation points has a BD-regular subdifferential then
     26: //     a.  the entire sequence converges to this accumulation point at
     27: //         a local q-superlinear rate
     28: //     b.  if in addition the reformulation is strongly semismooth near
     29: //         this accumulation point, then the algorithm converges at a
     30: //         local q-quadratic rate.
     31: //
     32: // The theory for the feasible version follows from the feasible descent
     33: // algorithm framework.
     34: //
     35: // References:
     36: //   Billups, "Algorithms for Complementarity Problems and Generalized
     37: //     Equations," Ph.D thesis, University of Wisconsin - Madison, 1995.
     38: //   De Luca, Facchinei, Kanzow, "A Semismooth Equation Approach to the
     39: //     Solution of Nonlinear Complementarity Problems," Mathematical
     40: //     Programming, 75, pages 407-439, 1996.
     41: //   Ferris, Kanzow, Munson, "Feasible Descent Algorithms for Mixed
     42: //     Complementarity Problems," Mathematical Programming, 86,
     43: //     pages 475-497, 1999.
     44: //   Fischer, "A Special Newton-type Optimization Method," Optimization,
     45: //     24, pages 269-284, 1992
     46: //   Munson, Facchinei, Ferris, Fischer, Kanzow, "The Semismooth Algorithm
     47: //     for Large Scale Complementarity Problems," Technical Report 99-06,
     48: //     University of Wisconsin - Madison, 1999.

     50: #ifndef __TAO_SSLS_H
     52: #include "src/tao_impl.h"

     54: typedef struct {
     55:   TaoVec *g;

     57:   TaoVec *ff;        // fischer function
     58:   TaoVec *dpsi;        // gradient of psi
     59:
     60:   TaoVec *d;        // direction
     61:   TaoVec *w;        // linesearch work vector

     63:   TaoVec *da;        // work vector for subdifferential calculation (diag pert)
     64:   TaoVec *db;        // work vector for subdifferential calculation (row scale)
     65:   TaoVec *dm;   // work vector for subdifferential calculation (mu vector)

     67:   TaoVec *t1;        // work vector
     68:   TaoVec *t2;        // work vector

     70:   TaoVec *xl;
     71:   TaoVec *xu;

     73:   double merit; // merit function value (norm(fischer))
     74:   double merit_eqn;
     75:   double merit_mu;

     77:   double delta;
     78:   double rho;

     80:   double rtol;        // Solution tolerances
     81:   double atol;

     83:   double identifier;        // Active-set identification

     85:   // Interior-point method data
     86:   double mu_init; // initial smoothing parameter value
     87:   double mu;      // smoothing parameter
     88:   double dmu;          // direction in smoothing parameter
     89:   double mucon;   // smoothing parameter constraint
     90:   double d_mucon; // derivative of smoothing constraint with respect to mu
     91:   double g_mucon; // gradient of merit function with respect to mu

     93:   TaoVec *f;        // constraint function
     94: } TAO_SSLS;

     96: int TaoSetUp_SSLS(TAO_SOLVER, void *);
     97: int TaoSetDown_SSLS(TAO_SOLVER, void *);
     98: int TaoSetOptions_SSLS(TAO_SOLVER, void *);
     99: int TaoView_SSLS(TAO_SOLVER, void *);

    101: int Tao_SSLS_Function(TAO_SOLVER, TaoVec *, double *, void *);
    102: int Tao_SSLS_FunctionGradient(TAO_SOLVER, TaoVec *, double *, TaoVec *, void *);
    103: int Tao_ASLS_FunctionGradient(TAO_SOLVER, TaoVec *, double *, TaoVec *, void *);
    104: int Tao_ISLS_FunctionGradient(TAO_SOLVER, TaoVec *, double *, TaoVec *, void *);

    106: #endif