=Paper=
{{Paper
|id=Vol-1623/papermp16
|storemode=property
|title=Modified Duality Method for Obstacle Problem
|pdfUrl=https://ceur-ws.org/Vol-1623/papermp16.pdf
|volume=Vol-1623
|authors=Elina Vikhtenko
|dblpUrl=https://dblp.org/rec/conf/door/Vikhtenko16
}}
==Modified Duality Method for Obstacle Problem==
https://ceur-ws.org/Vol-1623/papermp16.pdf
Modified Duality Method for Obstacle Problem
Ellina Vikhtenko
Pacific National University,
Tikhookeanskaya 136, 680035 Khabarovsk, Russia
vikht.el@gmail.com
Abstract. In this paper we proposed a modified Lagrangian functional for
obstacle problem, investigated its properties. Then we construct Uzawa method
for finding a saddle point, proved the convergence theorems. Some numerical
examples are provided.
Keywords: Obstacle problem, sensitivity functional, duality scheme, modified
Lagrangian functional, saddle point, Uzawa method
1 Introduction
We consider a modified duality method for solving the obstacle problem. The obsta-
cle problem is a typical example of the elliptic variational inequality. Many important
problems ranging from contact problems in continuum mechanics to option pricing in
computational finance can be formulated as the obstacle problem. See for instance the
book [1] where many of these applications are described, as well as the classical liter-
ature on this problem. Finally, apart from their practical relevance, obstacle problems
are fascinating mathematical objects of their own value. The basic properties of the
solution, including existence and uniqueness, were established by Lions and Stampac-
chia [2]. Many approaches for the numerical solution of obstacle problems have been
suggested and pursued [3–5]. The main existing numerical methods for the solution of
obstacle problems in particular, are mathematical programming approach, and schemes
based on penalty formulations and Lagrangian multiplier formulations [6–8].
The modified Lagrangian functional for the first time were developed and investi-
gated for solving the problem of finite-dimensional optimization. Their emergence was
related to the fact that classical Lagrangian functionals that are linear functions of
the dual variables are not suitable for solving the singular optimization problems. The
construction of modified Lagrangian function (functional) actually comprises regular-
ization of dual variables. In last time the Lagrangian multiplier method is successfully
applied to the solution of infinite-dimensional variational inequalities in mechanics [9–
11]. In this paper the duality scheme based on the modified Lagrangian functional is
examined for the obstacle problem.
The paper is structures as follows. In Sect. 2, we introduce the obstacle problem. In
Sect. 3, we present the sensitivity functional for the obstacle problem and we investigate
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
304 Ellina Vikhtenko
its properties. In Sect. 4, we propose the modified Lagrangian functional and construct
the Uzawa method for finding a saddle point, prove the convergence theorems. Finally,
in Sect. 5 we present the numerical examples. Sect. 6 contains some concluding remarks.
2 The Obstacle Problem
Let us consider a simple model for a problem with obstacle. There are horizontal
circular wire and a membrane hanging on this wire (see fig. 1(a)). We assume that
this membrane is horizontal and above a plate. This plate is a obstacle for plate’s
deflection. When we load the membrane with a force f in the vertical direction, it
undergoes deflection (fig. 1(b) — the case without the plate). If there is the place we
get a contact area between the membrane and the obstacle which is the plate. This
contact area is called the coincidence set (fig 1(c)).
Fig. 1. Membrane over a plate
The obstacle problem can be described as follows: find the equilibrium position
u(x), x ∈ Ω ⊂ R2 of an elastic membrane constrained to lie above a given obstacle
ψ(x) under an external force f (x). Then u(x) is the formal solution of the boundary
problem
−∆u(x) = f (x) a.e. in N = {x ∈ Ω : u(x) > ψ(x)},
u(x) = ψ(x) in Λ = {x ∈ Ω : u(x) = ψ(x)},
u(x) = 0, x ∈ Γ.
Here Ω ⊂ R be a bounded and open domain with smooth boundary Γ ; where f is an
2
element L2 (Ω); ψ is an element of H01 (Ω) with ψ ≤ 0 on Γ .
Therefore the obstacle problem can be posed as a variation problem. Set
∫ ∫
1
J(v) = |∇v| dΩ − f v dΩ
2
(1)
2
Ω Ω
and
K = {w : w ∈ H01 (Ω), w ≥ ψ a.e. in Ω}.
The set K is not empty.
Modified Duality Method for Obstacle Problem 305
We consider the following variational inequality:
{
Find v ∈ K such that
(2)
J(v) − min .
The problem (2) is called the obstacle problem, and the set K is called the set of
constraints [1].
The functional J(v) is strongly coercive in H01 (Ω), it means J(v) → +∞ for
∥v∥H 1 (Ω) → ∞. Hence the problem (2) has a unique solution u. It is known if ∆ψ(x) ∈
L2 (Ω), then u is an element H 2 (Ω) (see [1, 12]).
In [13] the duality method with classical Lagrangian functional
∫
L(v, l) = J(v) + l (ψ − v) dΩ, v ∈ H01 (Ω), l ∈ L2 (Ω)
Ω
is consider, and it shows that a point (v ∗ , l∗ ) = (u, −∆u − f ) is a unique saddle point
of the Lagrangian functional L(v, l),
+
L(u, l) ≤ L(u, −∆u − f ) ≤ L(v, −∆u − f ), ∀ v ∈ H01 (Ω), l ∈ (L2 (Ω))
where
+
(L2 (Ω)) = {w ∈ L2 (Ω) : w ≥ 0 a.e. in Ω}.
It is known that duality methods based on classical Lagrangian functionals don’t
guarantee the convergence of the available methods for finding saddle points in varia-
tional inequalities in mechanics. The convergence of duality methods can be established
according to direct variable only. In addition the step according to dual variable must
be sufficiently small.
3 The Sensitivity Functional
For arbitrary m ∈ L2 (Ω) we introduce the set
Km = {v ∈ H01 (Ω) : ψ − v ≤ m a.e. on Ω}
and for all functions m ∈ L2 (Ω) define the sensitivity functional
{
inf J(v), if Km ̸= ∅,
χ(m) = v∈Km
+∞, otherwise.
It is easy to see that if a function m ∈ L2 (Ω) is lower bounded on Ω, the corre-
sponding set Km is not empty and inf J(v) > −∞ [14]. The set Km can be empty
v∈Km
if m ∈ L2 (Ω) \ H 1 (Ω) and not lower bounded on Ω. Then χ(m) is a proper convex
functional on L2 (Ω), but it’s effective domain domχ = {m ∈ L2 (Ω) : χ(m) < +∞}
does not coincide with L2 (Ω). Notice that domχ is a convex but not closed set. In this
case, domχ = L2 (Ω).
306 Ellina Vikhtenko
Since the functional J(v) is coercive then the problem
{
Find v ∈ Km such that
J(v) − min .
has a unique solution um for any m ∈ domχ. Hence χ(m) = J(um ) and χ(0) =
inf J(v) = J(u).
v≥ψ
We have the next result.
Theorem 1. The sensitivity functional χ(m) is weakly lower semicontinuous on L2 (Ω).
Since χ(m) is convex functional, it is suffices to show that χ(m) is lower semicon-
tinuous on L2 (Ω) (in norm space L2 (Ω)).
We take an arbitrary sequence {mi } ⊂ L2 (Ω) such that m̄ = lim mi . We can show
i→∞
that the conditions
1) lim χ(mi ) = +∞ if m̄ ∈
/ domχ;
i→∞
2) lim χ(mi ) ≥ χ(m̄) if m̄ ∈ domχ
i→∞
are satisfied. Desirable property of lower semicontinuous for χ(m) follows from these
conditions. The proof is complete.
For an arbitrary l ∈ L2 (Ω), we consider the functional
∫ ∫
r
Fl (m) = χ(m) + l m dΩ + m2 dΩ,
2
Ω Ω
where r > 0 is a constant. The functional Fl (m) is very important for constructing the
duality methods based on modified Lagrangian functionals [11].
For a fixed l ∈ L2 (Ω), we examined the functional Fl (m) for m ∈ L2 (Ω). From
theorem 1 follows that Fl (m) is a weakly semicontinuous functional on L2 (Ω).
Theorem 2. The functional Fl (m) is coercive in L2 (Ω).
Since χ(m) is a lower semicontinuous functional, then the epigraph of sensitivity
functional
epiχ ≡ {(v, a) ∈ L2 (Ω) × R : χ(v) ≤ a}
is a convex closed set in L2 (Ω) × R. According Mazur separation theorem [15, p. 164]
there are α ∈ L2 (Ω) and γ ∈ R, such that
∫
α m dΩ + χ(m) + γ ≥ 0 ∀ m ∈ domχ.
Ω
Hence the estimate
∫ ∫ ∫
r
Fl (m) ≥ − α m dΩ + l m dΩ + m2 dΩ + γ ∀ m ∈ L2 (Ω)
2
Ω Ω Ω
Modified Duality Method for Obstacle Problem 307
is satisfied and Fl (m) → +∞ if ∥m∥L2 (Ω) → ∞.
The proof is complete.
Therefore for any l ∈ L2 (Ω) there exists a unique element
m(l) = arg min Fl (m).
m∈L2 (Ω)
It is obvious that m(l) ∈ domχ.
Let us introduce the function
Φ(l) = χ(m(l)), ∀l ∈ L2 (Ω).
Theorem 3. The function Φ(l) is continuous in L2 (Ω).
Since Fl (m) is a strongly convex functional, then the inequality
∫ ∫
r r
χ(m(l)) + l m(l) dΩ + (m(l))2 dΩ + ∥m(l) − m∥2L2 (Ω) ≤
2 2
Ω Ω
∫ ∫
r
≤ χ(m) + l m dΩ + m2 dΩ
2
Ω Ω
is fulfilled for a given element l ∈ L2 (Ω) and every m ∈ L2 (Ω).
Choose two elements l′ , l′′ on L2 (Ω). Let m′ = m(l′ ) and m′′ = m(l′′ ). Last inequal-
ity implies the relations
∫ ∫
′ ′ ′ r r
χ(m ) + l m dΩ + (m′ )2 dΩ + ∥m′ − m′′ ∥2L2 (Ω) ≤
2 2
Ω
∫ Ω ∫ (3)
r
≤ χ(m′′ ) + l′ m′′ dΩ + (m′′ )2 dΩ,
2
Ω Ω
∫ ∫
r r
χ(m′′ ) + l′′ m′′ dΩ + (m′′ )2 dΩ + ∥m′′ − m′ ∥2L2 (Ω) ≤
2 2
Ω
∫ Ω ∫ (4)
r
≤ χ(m′ ) + l′′ m′ dΩ + (m′ )2 dΩ.
2
Ω Ω
Combining (3) and (4), we find that
∫
r∥m′ − m′′ ∥2L2 (Ω) ≤ (l′ − l′′ )(m′′ − m′ ) dΩ, (5)
Ω
From (5), we derive
1 ′
∥m′ − m′′ ∥L2 (Ω) ≤ ∥l − l′′ ∥L2 (Ω) . (6)
r
308 Ellina Vikhtenko
Relations (3) and (4) also imply the two-sided inequality
∫ ∫
r
l′′ (m′′ − m′ ) dΩ + ((m′′ )2 − (m′ )2 ) dΩ ≤ χ(m′ ) − χ(m′′ ) ≤
2
Ω Ω
∫ ∫
′ ′′ ′ r
≤ l (m − m ) dΩ + ((m′′ )2 − (m′ )2 ) dΩ.
2
Ω Ω
Let l′′ approaches l′ in L2 (Ω). The above two-sided inequality and relation (6) lead to
the equality ′′lim ′ Φ(l′′ ) = Φ(l′ ). Hence the theorem is proved.
l →l
4 Modified Duality Method
We define the modified Lagrangian functional on the set H01 (Ω) × L2 (Ω) as
∫ ( )
1 ( )2
M (v, l) = J(v) + (l + r(ψ − v))+ − l2 dΩ,
2r
Ω
where w+ = max{w, 0}, r > 0 — constant.
A point (v ∗ , l∗ ) is called a saddle point of functional M (v, l) if two-sided inequality
M (u∗ , l) ≤ M (u∗ , l∗ ) ≤ M (v, l∗ )
is fulfilled for any v ∈ H01 (Ω), l ∈ L2 (Ω). The sets of saddle points of modified and
classical Lagrangian functionals are equal[16].
Let us introduce the dual functional
M(l) = inf M(v, l) =
v∈H01 (Ω)
∫ ( ) (7)
1 ( )
+ 2
= inf J(v) + (l + r(ψ − v)) − l 2
dΩ .
v∈H01 (Ω) 2r
Ω
We can write the another presentation the functional M(l) with using the sensitivity
functional:
∫ ∫
r
M(l) = inf χ(m) + l m dΩ + m2 dΩ = inf Fm (l). (8)
m∈L2 (Ω) 2 m∈L2 (Ω)
Ω Ω
If (v ∗ , l∗ ) is a saddle point of M (v, l), then v ∗ is a solution of problem (2) and l∗ is a
solution of dual problem
{
Find l ∈ L2 (Ω) such that
(9)
M(l) − max .
From theorems 2, 3 and inequality (6) it follows that convex functional (−M(l)) is
a continuous functional in L2 (Ω).
We have the next theorem [16].
Modified Duality Method for Obstacle Problem 309
Theorem 4. The dual functional M(l) is Gáteaux differentiable in L2 (Ω) and its
derivative ∇M(l) satisfies the Lipschitz condition with the constant 1/r; that is, for
all l′ , l′′ ∈ L2 (Ω), it holds that
1 ′
∥∇M(l′ ) − ∇M(l′′ )∥L2 (Ω) ≤ ∥l − l′′ ∥L2 (Ω) .
r
It is easy to show [16] that ∇M(l) = m(l) = max{−l/r, ψ − v}.
Since the gradient of the functional M(l) satisfies the Lipschitz condition, the dual
problem (9) can be solved by using the gradient method for maximizing a functional
(see [17])
lk+1 = lk + r∇M(lk ), k = 0, 1, 2, . . . (l0 ∈ L2 (Ω) is given).
The gradient method can be written as
lk+1 = lk + r max{−lk /r, ψ − v} = (lk + r(ψ − v))+ . (10)
Theorem 5. The sequence {lk } constructed by the gradient method (10) satisfies the
limit equality lim ∥m(lk )∥L2 (Ω) = 0.
k→∞
The proof of this theorem can be found in [16], it is analogous to that of the theorem
[17, p. 31].
The gradient method (10) can be used for construct an algorithm for solving prob-
lem (2) :
(i) uk+1 = arg min M(v, lk );
v∈H01 (Ω)
(11)
(ii) lk+1 = lk + r∇M(lk ) = (lk + r(ψ − uk+1 ))+ ,
i=0,1,2,. . . ; l0 ∈ L2 (Ω) is given.
We can show that the sequence {uk , lk } is bounded sequence in H 1 (Ω) × L2 (Ω).
Theorem 6. The algorithm (11) converges with respect to the functional; that is,
lim J(uk ) = min J(v) = J(u).
k→∞ v∈K
As before, u is a solution of the problem (2).
Indeed, the sequence {lk } is bounded sequence in L2 (Ω), and the functional χ(m)
is weakly lower semicontinuous on L2 (Ω), which yields
∫ ∫
r
lim χ(m(lk )) + lk m(lk ) dΩ + (m(lk ))2 dΩ =
k→∞ 2
Ω Ω
= lim χ(m(lk )) ≥ χ(0) = J(u∗ ).
k→∞
310 Ellina Vikhtenko
On the other hand, we have from the definition M(l)
∫ ∫
r
M(lk ) = χ(m(lk )) + lk m(lk ) dΩ + (m(lk ))2 dΩ =
2
Ω
Ω
∫ ∫
r
= inf χ(m) + lk m dΩ + m2 dΩ ≤ χ(0), k = 0, 1, 2, . . . .
m∈L2 (Ω) 2
Ω Ω
Therefore,
∫ ∫
r
lim χ(m(lk )) + lk m(lk ) dΩ + (m(lk ))2 dΩ ≤ χ(0).
k→∞ 2
Ω Ω
Consequently, there exists the limit
∫ ∫
r
lim χ(m(lk )) + lk m(lk ) dΩ + (m(lk ))2 dΩ = χ(0) = J(u∗ ).
k→∞ 2
Ω Ω
Now, theorem 5 implies that
lim J(uk ) = lim χ(m(lk )) = χ(0) = J(u).
k→∞ k→∞
The proof is complete.
By using the convexity of (−M(l)) and the theorem 5 we get the following estimate
M(lk ) − M(l∗ ) ≤ ∥m(lk )∥L2 (Ω) ∥lk − l∗ ∥L2 (Ω) .
Hence, lim M(lk ) = M(l∗ ). It means that algorithm (11) converges with respect to
k→+∞
dual functional. This fact can not be shown for the classical Lagrangian functional.
The convergence of this algorithm with respect to the argument uk was examined in
[16].
5 A Numerical Example
In this section we present some numerical experiments in solving an obstacle problem
by using the algorithm (11).
For the numerical realization (11) we use the finite element method. Suppose that
the boundary Γ is polygonal. For a triangulation T of Ω, let h = h(T ) be the max of
the lengths of the edges. Then T satisfies the shape regularity and the maximum angle
condition if
(a) there is a positive constant ρ such that for any τ ∈ T , there is a disk B of radius r
with B ⊂ τ and ρh ≤ r < h,
(b) maximum angle ≤ π/2.
Modified Duality Method for Obstacle Problem 311
We call a family of triangulations regular if each triangulation in it satisfies (a) and
(b) with ρ uniform for the family. Given a triangulation Th , let V̄h = Vh (Th ) denote
the collection of all H 1 (Ω) functions which are affine on each triangle in Th ; V̄h is the
space of continuous piecewise linear functions over Th . Take Vh = V̄h ∩ H01 (Ω). For
v ∈ C 0 (Ω̄), let vh ∈ V̄h be the interpolant of v; v = vh at each vertex in Th . Define
Kh = {vh ∈ Vh : vh ≥ ψh }.
The discrete approximation of u is given by uh ∈ Kh , where uh is a solution the
next problem {
Find vh ∈ Kh such that
J(vh ) − min .
Let k be an integer number denoting the iteration parameter. The algorithm pre-
sented in Sect. 4, to solve the obstacle problem, can be expressed as follows.
Step 0 (Initialization). Given an element lh0 in Vh .
Step 1. Find a solution uk+1
h ∈ Vh of the problem
∫
( k )2
M(vh , lk ) = J(vh ) + 1 (l + r(ψ − vh ))+ dΩ → min,
2r
Ω
vh ∈ Vh .
Step 2. Compute
lhk+1 = (lhk + r([ψ]h − uk+1 +
h )) .
Step 3. Repeat steps 1 and 2 until a stopping criterion is satisfied.
Let Ω be a square, Ω = {(x1 , x2 ): 0 < x1 < 1, 0 < x2 < 1}. We define an obstacle
in a ring, and the parameters problem (2) so that its solution has the form shown in
Fig. 1. As a result, we obtain the numerical solution of obstacle problem shown in Figs.
2.
In Fig. 3 a dashed line (blue) is a graph solution of the problem without obstacle,
a thin solid line (green) is a graph of the function that defines an obstacle, and a thick
line (red) a graph solution of the obstacle problem.
The numerical experiments demonstrate the possibility to use Uzawa algorithm
for modified Lagrange functional. In paper [18] it was found that for problems with
constraints on the boundary the best convergence rate is achieved for large values r
(r = 106 , 108 ). In this work we we have shown that the optimum value of the parameter
r is in the range 20 − 200.
6 Conclusion
In this paper, we have considered a modified Lagrangian functional for the obsta-
cle problem. The modified Lagrangian functionals considered in the present paper
are analogs of the corresponding modified functions constructed to solve the finite-
dimensional optimization problems. The duality methods based on the modified La-
grangian functionals offer a convenient and efficient tool to solve the infinite-dimensional
variational inequalities of mechanics.
The author makes no attempt to compare the effectiveness of the proposed method
with other methods of numerical optimization with constraints. The objective of this
312 Ellina Vikhtenko
Fig. 2. A solution of the problem without obstacles
Fig. 3. A solution of the obstacle problem
paper was demonstrate the application of the duality scheme based on the modified
Lagrangian functional for the problem with constraints in the domain.
Modified Duality Method for Obstacle Problem 313
Fig. 4. A solution of the obstacle problem, x2 = 0
References
1. Friedman, A.: Variational Principles and Free-boundary Problems. John Wiley, New York
(1982)
2. Lions, J.L., Stampacchia G.: Variational Inequalities. Commun. Pure Appl. Math. 20, 493–
519 (1967)
3. Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer- Verlag,
Berlin-Heidelberg-New York (1984)
4. Xue, L., Cheng, X. L.: An Algorithm for Solving the Ostacle Problems. Comp. and Math.
with Appl., 48, 1651–1657 (2004)
5. Brugnano, L., Sestini, A,: Iterative Solution of Piecewise Linear Systems for the Numerical
Solution of Obstacle Problems. J. of Numerical Analysis, Industrial and Applied Mathe-
matics 6, 67–82 (2011)
6. Zulehner, W.: Analysis of iterative Methods for Saddle Point Problems: a Unified Approach.
Math. Comp. 71, 479–505 (2002)
7. Karkkainen, T., Kulisch, K., Tarvainen, P.: Augmented Lagrangian Active Set Methods
for Obstacle Problems. J. of Opt. Theory and Appl. 119, 499–533 (2003)
8. Graser, C., Kornhuber, R.: Multigrid Methods For Obstacle Problems. Review Article. J.
Comp. Math. 27, No.1, 1–44 (2009)
9. Namm, R.V., Vikhtenko, E.M.: Modified Lagrangian Functional for Solving the Signorini
Problem with Friction. Advances in Mechanics Research, Nova Science Publishers, New-
York, 1, 435–446 (2011)
10. Namm R.V., Woo, Gyungsoo, Shu-Sen Xie, and Yi Sucheol: Solution of Semicoercive Sig-
norini Problem Based on a Duality Scheme with Modified Lagrangian Functional. J. Korean
Math. Soc. 49 , No. 4, 843– 854 (2012)
11. Namm, R.V., Vikhtenko, E.M., Woo, G.: Sensitivity Functionals in Contact Problems of
Elasticity Theory. J. Comp. Math. and Math. Phys. 54, No. 7, 1190–1200 (2014)
12. Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their
Applications. Academic Press, New York, (1980)
13. Kaplan, A.A.: Variational inequalities and semi-infinite optimization convex problems.
Novosibirsk, Institute of Mathematics, preprint No 27 (1989)
314 Ellina Vikhtenko
14. Duvaut, G., Lions, J.L.: Inequalities in Mechanics and Physics. Springer-Verlag, Berlin
(1976)
15. Fučik, S., Kufner, A.: Nonlinear Differential Equations. Mir, Moscow (1988)
16. Vikhtenko, E.M.: The Lagrangian Multipliers Method for Obstacle Problem. Vestnik
TOGU, No 2, 35–46 (2010)
17. Polyak, B.T.: Introduction to Optimization. Nauka, Moscow (1980)
18. Namm, R.V., Sachkov, S.A.: Solving the Quasi-Variational Signorini Inequality by the
Method ff Successive Approximations. J. Comp. Math. and Math. 49, No 5, 776–785 (2009)