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
10: Many other reformulations are possible and combinations of
11: feasible/infeasible and linesearch/trust region are possible.
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.
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.
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.
32: The theory for the feasible version follows from the feasible descent
33: algorithm framework.
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.
49: */
51: #ifndef __TAO_SSLS_H
53: #include <petsc/private/taoimpl.h>
55: typedef struct {
56: Vec ff; /* fischer function */
57: Vec dpsi; /* gradient of psi */
59: Vec da; /* work vector for subdifferential calculation (diag pert) */
60: Vec db; /* work vector for subdifferential calculation (row scale) */
61: Vec dm; /* work vector for subdifferential calculation (mu vector) */
62: Vec dxfree;
64: Vec t1; /* work vector */
65: Vec t2; /* work vector */
67: Vec r1,r2,r3,w; /* work vectors */
69: PetscReal merit; /* merit function value (norm(fischer)) */
70: PetscReal merit_eqn;
71: PetscReal merit_mu;
73: PetscReal delta;
74: PetscReal rho;
76: PetscReal rtol; /* Solution tolerances */
77: PetscReal atol;
79: PetscReal identifier; /* Active-set identification */
81: /* Interior-point method data */
82: PetscReal mu_init; /* initial smoothing parameter value */
83: PetscReal mu; /* smoothing parameter */
84: PetscReal dmu; /* direction in smoothing parameter */
85: PetscReal mucon; /* smoothing parameter constraint */
86: PetscReal d_mucon; /* derivative of smoothing constraint with respect to mu */
87: PetscReal g_mucon; /* gradient of merit function with respect to mu */
89: Mat J_sub, Jpre_sub; /* subset of jacobian */
90: Vec f; /* constraint function */
92: IS fixed;
93: IS free;
94: } TAO_SSLS;
96: PetscErrorCode TaoSetFromOptions_SSLS(PetscOptionItems *,Tao);
97: PetscErrorCode TaoView_SSLS(Tao,PetscViewer);
99: PetscErrorCode Tao_SSLS_Function(TaoLineSearch, Vec, PetscReal *, void *);
100: PetscErrorCode Tao_SSLS_FunctionGradient(TaoLineSearch, Vec, PetscReal *, Vec, void *);
102: #endif