Skip to content

Latest commit

 

History

History
635 lines (516 loc) · 23.2 KB

faf.org

File metadata and controls

635 lines (516 loc) · 23.2 KB
Raw

Development in Siconos/Numerics

VI methods

  • Projection Contraction techniques ==> in Fixed point VI
  • Prediction Correction type Extragradient ==> in Extragradient He.Liao_JOTA2002 Noor_CMA2002 Algo 3.8 of Noor_JOTA2003
  • Two-step forward–backward splitting-type algorithms Noor_CMA1999 Noor_MCM1999
    • Forward–backward splitting de Tseng.

Newton method based on SOCCP formulation

General SOCCP solver

  • Interior points methods
    • Work of Kleinert, Simeon and Obermayr
  • FB and regularized FB for SOCCP

    smoothing and its smoothed version with a regularization parameter $τ>0$ as \begin{equation} \label{eq:Jordan-FB-smoothed} φ\fb, τ(x,y) = x+y - (x^2 + y^2 + 2 τ^2 e)1/2 \end{equation} where $e = (1,0,0)$ is the identity element of the Jordan algebra, that is $e ⋅ x =x$. In the same vein, the class of smoothing function of the natural map for NCP developed in~\cite{Chen.Mangasarian1996} is extended to SOCCP in~\cite{Fukushima.ea2001}.

    \cite{Fukushima.ea2001} \cite{Zhang.ea2009} \cite{Hayashi.ea_SIOPT2005} \end{itemize}

  • Have a look to cvxopt (python and C)

Proximal point algorithm

  • Continue to study the influence of the regularization parameter

LocalAlartCurnier

  • Possibility to avoid the LU factor of W ?
  • Guess rho with VIFixedPointProjection

Krylov techniques

  • Work of Heyn et al.

Acceleration of Gauss-Seidel Strategy

  • Aitken–like strategy
  • have a look to FISTA and Nesterov work. INPPA

ACLM formulation.

  • Implement Fixed point Iteration
    • Which internal solver ?
      • the internal solver must use the convexity of the problem SOCQP ?
      • Block-splitting + local solver (PSOR + list of solver). Copy of nsgs with psor options DONE
      • Remain to add Newton–based solver ?
  • ACLM with SOCLCP solver
    • What is the good strategy for the internal solver ? very accurate convergence or loose ONE
  • Newton method of convex SOCLCP or SOCQP Newton method on the problem $F(s)=s$

Alternative strategy to drive to convergence. ?

Literature

Check for “solving frictional contact problem” \begin{itemize} \item in google, and scholar \item Zentralblatt and MAthSciNet \end{itemize}

Renard

add http://math.univ-lyon1.fr/~renard/papers/2008_frst.pdf in the list of reading

Read work of Kucera Dostal

CCP / SOCP

Read Goldfarb Alizabeh

SOCCP Fukushima, Hyashi Works

Christian Kanzow, Izabella Ferenczi, and Masao Fukushima

ON THE LOCAL CONVERGENCE OF SEMISMOOTH NEWTON METHODS FOR LINEAR AND NONLINEAR SECOND-ORDER CONE PROGRAMS WITHOUT STRICT COMPLEMENTARITY∗ /Users/acary/Publi/Optimisation/SOCCP/Kanzow.Ferenczi.Fukushima_SIOPT2009.pdf

Smoothing and BFGS work of Chen and Tseng

SOCLCP

Existing software

SOCP: Software for Second-Order Cone Programming

M. Lobo, L. Vandenberghe, and S. Boyd http://stanford.edu/~boyd/old_software/SOCP.html

RESNA :

COMPASS: A Free Solver for Mixed Complementarity Problems

D. A. Schmelzer http://www.mat.univie.ac.at/~neum/software/compass/schmelzerDA.pdf

Extra gradient method and De Saxce Fixed point

The value of the parameter strongly influences the convergence.

ALVAREZ, F., and ATTOUCH, H., An Inertial Proximal Method for Maximal Monotone Operators ûia Discretization of a Nonlinear Oscillator with Damping, Set-Valued Analysis, Vol. 9, pp. 3–11, 2001.

  • long review of various algorithm
  • Algo 3.1. Fixed point
  • Algo 3.2. Inertial proximal method.
  • Algo 3.3. Extragradient method
  • Algo 3.4. Extragradient method with Wiener Hopf (Projection correction) He.Liao_JOTA2002
  • Algo 3.5. Prediction–Correction type extragradient. bvery similar to previous one Noor_CMA2002
  • Algo 3.6. Two-step forward–backward splitting-type algorithms Noor_CMA1999 Noor_MCM1999
  • Algo 3.7. Self-adaptative version of 3.6
  • Algo 3.8. unified extragradient type method. contains 3.4
    • Wang.ea_JOTA2001 Unified framework of extragradient-type methods for pseudomonotone variational inequalities YJ Wang, NH Xiu, CY Wang - Journal of Optimization Theory and …, 2001 - Springer

==> Retrieve NOOR, M. A., A Modified Extragradient Method for General Monotone Vari- ational Inequalities, Computers and Mathematics with Applications, Vol. 38, pp. 19–24, 1999.

NOOR, M. A., New Extragradient-Type Methods for General Variational Inequalities, Journal of Mathematical Analysis and Applications, Vol. 277, pp. 379–395, 2002.

NOOR, M. A., Some Algorithms for General Monotone Mixed Variational Inequalities, Mathematics and Computer Modelling, Vol. 29, pp. 1–9, 1999.

IUSEM, A. N., and SVAITER, B. F., A Variant of Korpeleûich’s Method for Vari- ational Inequalities with a New Search Strategy, Optimization, Vol. 42, pp. 309– 321, 1997.

  1. SOLODOV, M. V., and SVAITER, B. F., A New Projection Method for Variational Inequality Problems, SIAM Journal on Control and Optimization, Vol. 37, pp. 765–776, 1999.

Proximal point algorithms

  • Chen.Teboublle_SIOPT1993 /Users/acary/Publi/Optimisation/Chen.Teboulle_SIOPT1993.pdf
  • ALVAREZ, F., and ATTOUCH, H., An Inertial Proximal Method for Maximal Monotone Operators ûia Discretization of a Nonlinear Oscillator with Damping, Set-Valued Analysis, Vol. 9, pp. 3–11, 2001.
  • A new proximal-based globalization strategy for the Josephy-Newton method for variational inequalities Optimization Methods and Software (Impact Factor: 1.21). 01/2002; 17(5). Solodov Svaiter

Have a look to paper about a Gauss-Newton

approach with quite elaborate line search: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5509

Target journal Archives of Computational Methods in Engineering

http://www.springer.com/engineering/computational+intelligence+and+complexity/journal/11831

extended state-of-the-art reviews

Optimization

QVI implementation

  • Work of Facchinei (Singapore Talk)
  • Work of Michael Ulbrich (Singapore Talk)

Augmented Lagrangian formulation

  • Discuss with Paul Armand

I.N. Doudoumis, E.N. Mitsopoulou, G.N. Nikolaidis

A comparative numerical study on the unilateral contact problem with friction Proceedings of the 1st National Congress of Computational Mechanics, Athens (1992)

@article{ year={1975}, issn={0020-1154}, journal={Ingenieur-Archiv}, volume={44}, number={6}, doi={10.1007/BF00534623}, title={A nonlinear programming approach to the unilateral contact-, and friction-boundary value problem in the theory of elasticity}, url={http://dx.doi.org/10.1007/BF00534623}, publisher={Springer-Verlag}, author={Panagiotopoulos, P.D.}, pages={421-432}, language={English} }

Comparison tools

using comp

  • parallel usage ls *.hdf5 | parallel comp.py –timeout=100 –no-collect ‘–file={}’
  • –no-collect leave the result into separate file that are named according the solver and the name of the problem
  • –just–collect collect all the result into comp.hdf5
  • –timeout=10 set the maximum time of computation for a solver to 10 seconds
  • –domain=’a:d:b’ restrict the domain of the performance profile to the interval [a,b] with a step of d or a perfomance profile a should be greater or equal 1
  • –iter OBSOLETE ? select the number iteration as the measure for the perfomance profile
  • –time OBSOLETE ? select the computation time as the measure for the perfomance profile
  • –flop OBSOLETE ?
  • –measure=value select the value as the measure for the perfomance profile possible values are time, iter, flpops
  • usage

    comp.py –display –domain=’1:0.1:10’ comp.hdf5

comp.py –display –measure=time –solvers=Gauss,Tresca,SOCLCP,ACLM –domain=1:0.1:100

Paper contact-friction

Objectives

  • Simple iteratives methods
    • Fixed point
    • Projection/splitting (PSOR)
    • Fake Coulomb Friction (Anitescu \& Tasora)
  • Complementarity function (zeroes of functions)
    • Alart–Curnier method
    • Jean–Moreau method
    • DeSaxce + Newton (Joli Feng)
    • Fischer–bursmeister for SOCCP (smoothing hayashima fukushima)
    • Newton
      • line search (GP, Armijo, Non-monotone watch dogs)
  • Optimisation-based methods
    • Successive approximations (Haslinger, …) QP et SOC (Kucera)
    • ACLM (Fixed point, Newton, Quasi-Newton, ....)
    • SOCLCP (Kanno, et al.)
  • Optional approach
    • SOCP (Optimization approach)
    • Interior point

Beyond the scope of the paper.

  • no LCP
  • no pivoting

Monotonicity of VI

{\blue

\paragraph{monotonicity}

For Problem~\ref{prob:II},% we have the VI (\ref{eq:vi-II}) that we rewrite for our convenience with % \begin{equation} % \label{eq:vi-II} % F\vitwo(u,r) =\left[ % \begin{array}{c} % u - Wr -q % u + g(u) % \end{array}\right] % \text{ and } X\vitwo = \RRn_c× K. % \end{equation} % \begin{equation} % \label{eq:mono-IIa} % (F\vitwo(u,r)-F\vitwo(v,s))^T( % \left[\begin{array}{c} % u \ r % \end{array}\right] % - % \left[\begin{array}{c} % v \ s v% \end{array}\right] % ) = (r-s)^T W (r-s) + \|u-v\|^2 + ∑ {α =1}n_c μ^α (x\n-y_n) [\|[Wx+q]^α_\t \| - \|[Wy+q]^α_\t \|] % \end{equation}

\begin{equation} \label{eq:mono-II} (F\vitwo(x)-F\vitwo(y))^T(x-y) = (x-y)^T W (x-y) + ∑ {α =1}n_c μ^α (x\n-y_n) [\|[Wx+q]^α_\t \| - \|[Wy+q]^α_\t \|] \end{equation}

\begin{equation} \label{eq:Jac-II} ∇_r F\vitwo(r) = W + W\left[ \begin{array}{cc} 0 & μ \Frac{[W r+q]_\t}{\|[W r+q]_\t\|}
0 & 0 \end{array}\right] \end{equation}

Tests problems (FCLIB)

  • collections
    • spheres
      • flows and stacking (Example Tasora)
    • sticks
      • flows and stacking (Example Tasora)
    • hair, LMGC clumps ??
  • deformables quasi-static / dynamic
    • Hertz 3D FEM
    • masonry

POSTPONED Redaction article ABH

  • Complete the introduction
    • Add a list of approach not discussed in the paper. leave it as future work.
  • Complete Section 3
    • Understand the continuity argument of Alart
    • Find references for alternating projection N and after T
  • Complete Section 4
    • Section 4.1 \begin{itemize} \item situate the work of \cite{DeSaxce.Feng90,DeSaxce.Feng1998} and \cite{Simo.Laursen1992,Laursen.Simo1993b}. \item implement the work of Simo just to laugh \item Have a careful look to the work of Krause. \end{itemize}
    • Section 4.2 \begin{itemize} \item Rule and efficient Choice of $ρ$. \item Should we remove hyperplane projection ? \item Acceleration techniques and Nesterov Method ? FISTA and Nesterov work. INPPA \end{itemize}
    • Section 4.3 What can be retained from\cite{Heyn_PhD2013} ? Krylov techniques

Meeting <2015-12-04 Fri>

MB, VA

  • Methods:
    • NSN : Technical report on Jacobians computation
    • NSN : regularization approach, computation of ρ
    • PROX : Try to find a all–terrain strategy, Hager, FISTA, INPPA
    • Try to think alll remaining approach to develop : ACLM+NSN, TRESCA+?, BFGS, Options N after T
  • Tests
    • Rerun all the tests on Luke to get a full-test.pdf
    • Plan a meeting to discuss the conclusion to draw of the document (redo, check, conclude, …)

Meeting <2016-03-07 Mon>

MB, VA, OH

  • Journals
  • Solvers
    • VI : FixedPoint, ExtraGradient, Hyperplane
    • Nonsmooth Newton (NSN)
      • Validation of gradients:
        • AlartCurnier, JeanMoreau OK
        • Natural map, Fischer Burmeister: stability problem
      • Line search does not seem that help at all
    • Hybrid
      • Predconditioning NSN by a VI solvers.
    • Interior Point (IP)
      • does not work that well -> remove?
  • Conclusion :
    • NSN.
      • Difficulty related to the computation of gradients for FB and Natural
    • Hyperstaticity :
      • All the NSN fails.
      • NSGS supersedes.
      • PROX may improve the situation.
      • VI not so bad in view of parrelism
    • KerH trivial (flexible) (Cube_H8)
      • NSN supersedes
      • Line search does not help much (nonmonotone version?)
      • JM and AC work better -> analyse this maybe from an Augmented Lagrangian perspective

Meeting <2016-03-17 Thu>

MB, VA, OH.

  • MB: new generatation of the gradient
    • Jean Moreau, Alart Curnier, k
    • Natural map. pb de division par la norme de x_t
    • VA: Scaling Nesterov Todd
  • VA: Why nothing on Interior points?
  • OH:
    • Remark on the introduction. restructuration
    • Delete problem I
    • Notation des variables

Meeting <2016-03-31 Thu>

  • MB : natural map correct. meme chose pour le Fisher
  • OH: remark sur le papier.

Meeting <2016-04-20 Wed>

  • MB
    • clean gradients in the tex file. AC Natural Map
    • killed job on luke.ciment ?
    • swig version 2.11
  • VA

List of actions. Last update <2016-11-24 Thu>

  • Paper. General Work :
    • All sections : Clean redaction note and report here the items :VA:
    • Complete the introduction
      • Add a list of approach not discussed in the paper. leave it as future work.
      • Detail where it is possible why some approaches are not discussed (IPM)
    • Section 3.
      • Understand the continuity argument of Alart (V.A., O.H.)
      • Find references for alternating projection N and after T (V.A)
      • Section 3.3 Remork to send the maximum in Appendix (V.A.)
      • NDRVA 3.3 Comment of Olivier ? (O.H.)
      • Discuss remark about smoothing
      • Section 3.4 in Appendix.
      • NDRVA 3.5 Remark Olivier ?
    • Section 4.
      • Section 4.1

\begin{itemize} \item Have a careful look to the work of Krause. \end{itemize}

  • NDROH 4.1 : to be discussed (V.A. O.H.)
  • Section 4.2

\begin{itemize} \item Should we remove hyperplane projection ? \item Acceleration techniques and Nesterov Method ? FISTA and Nesterov work. INPPA \end{itemize} NRDOH 4.3 4.4 To be discussed, not so clear for me.

  • Further work
  • What can be retained from\cite{Heyn_PhD2013} ?
    • Krylov techniques
  • cite somewhere~\citep{Laborde.Renard_MMAS2008}
  • Have a careful look to the work of Krause.
    • Implement the FP-QVI-MJ and FP-QVI-AC within the De Saxce approach ? Useful ?
    • Section 5.
      • Section 5.2
  • In~\cite{Hayashi.ea_SIOPT2005}, spectral decomposition of the projection + smoothing. semi-smooth Newton method
  • Choice of $ρ_\n$ $ρ_\t$. Discussion paper Alart~\citep{Alart1993} or \citep{Jourdan.Alart.ea98}.
  • Is the proj formulation better than FB for all the reason related to the augmented Lagrangian approach ?
  • See~\cite{Mirar.Arora_SMO2004-I} for an automatic adaption of the penalization coefficient ? Link woth the work of Armand
    • Section 5.3 TBW
  • question about the naming convention : FBLSA ?
    • Section 6
      • Section 6.1
  • Situate~\cite{Hayashi.ea_JCAM2005}
  • Acceleration technique. Aitken acceleration. Lebon, Raous et al. contractive sequence transformations in C. Brezinski et M. Redivo-Zaglia, Extrapolation Methods, Theory and Practise, North- Holland, Amsterdam, 1992. J.P. Delahaye, Sequence transformations, Springer Verlag, Berlin, 1988.
    • Section 6.2 Work on the proximal point.
    • Section 7. (Optimization)
      • ACML
      • SOCCP
    • Misc.
      • Where to write the formulation of hybrid Solvers :VA:
      • Investigate the best journal to submit (and format) :VA:
  • CMAME ?
    • Fixes + new parts in paper :OH:
  • Devel and comparisons:
    • Devel alternating solution approaches. :VA:
      • Panagiotoupolos
    • Rerun computation :MB:VA:
    • Fclib. Thinking of how to bind with Matlab :OH:
    • Fclib and swig python tranlastion from siconos to fclib :MB:
    • Add a small description file for example directory. texfile img profile. :VA:
    • Add description of examples in fclib report. :VA:
    • Update and correct naming for the line-searches. FBLSA :MB:OH:
    • Merge line–searches procedures and undertand why they are failing :MB:OH:
    • improvement of Tresca approach ? :VA:
    • debug LMGC90 global interface :VA:
    • debug proximal point algorithm :VA:
    • evaluate the effect of filtering local solution in NSGS
    • reask for the IP method of Jan Kleinert.

targeted List of actions. Last update <2017-07-06 Thu>

  • Paper. General Work :
    • All sections : Clean redaction note and report here the items :VA:
    • Complete the introduction
      • Add a list of approach not discussed in the paper. leave it as future work. :VA
    • Section 3.
      • remove 3.4., DONE
      • Section 3.3 Remark to send the maximum in Appendix (V.A.) DONE
      • NDRVA 3.3 Comment of Olivier ? (O.H.) DONE
      • Discuss remark about smoothing DONE
      • Section 3.4 in Appendix. DONE
      • NDRVA 3.5 Remark Olivier ? DONE
  • Section 4.
    • Section 4.1
    • NDROH 4.1 : to be discussed (V.A. O.H.) –> mode in section 6.2
    • remove hyperplane projection

NRDOH 4.3 4.4 To be discussed, not so clear for me. VA

  • Implement the FP-QVI-MJ and FP-QVI-AC within the De Saxce approach ? Useful ?
  • Section 5.
    • Merge 5.1 5.2
    • Section 5.2
    • Section 5.3 TBW
  • question about the naming convention : FBLSA ?
    • Section 6
      • Section 6.1
  • Situate~\cite{Hayashi.ea_JCAM2005}
    • Section 6.2 Work on the proximal point.
    • Section 7. (Optimization)
      • ACML
      • SOCCP
  • Annex
    • formulation of subgradient.
  • Devel and comparisons:
    • Devel alternating solution approaches. :VA:
      • Panagiotoupolos
    • Rerun computation :MB:VA:
    • Add description of examples in fclib report. :VA:
  • Update and correct naming for the line-searches. FBLSA :MB:OH:
  • Merge line–searches procedures and undertand why they are failing :MB:OH:
  • improvement of Tresca approach ? :VA:
  • debug proximal point algorithm :VA:
  • evaluate the effect of filtering local solution in NSGS

New campaign of compatisons <2017-09-01 Fri>

Estimating the timeout parameters

method

For estimating, the timeout parameters, we use comp.py –compute-hardness –measure=time on a comparison very a “large” timeout.

For instance for Chain with timeout=100 , we get:

----- ~/Work/faf/benchs/Luke/3538793_Chain_1e-8_100/Chain ----- [09:57:00][0] [acary@ohana]$ comp.py –compute-hardness –measure=time warning : fc3d_nsgs_openmp is not in siconos numerics 1 – Creation of solver list 2 – Creation of problem list nc_avg 18.9539748954 Average min resolution measure (avg fastest solver measure) = 1.08750295e-03 Std min resolution measure (std fastest solver measure) = 8.61037569e-04 Average min resolution measure by contact = 5.73759837e-05 Average max resolution measure (avg slowest suceeded solver measure) = 1.10524911e+01 Std max resolution measure (std fastest solver measure) = 2.25526808e+01 Average max resolution measure by contact = 5.83122599e-01

The average time of the slowest solver is aroud 11s fwith a std deviation of 22s. We may choose 50 s a timeout

results

  • Chain 50 s
  • Capsules 100s
  • LowWall_FEM 1000s

On Chain example, Armijo line-search seems to slowest the convergence but the robutness is increased. To be confirmed