Complementarity problem
From Wikimization
(New page: == An application to nonlinear complementarity problems == === Fixed point problems === Let <math>\mathcal A</math> be a set and <math>F:\mathcal A\to\mathcal A </math> a mapping. The ''...) |
|||
Line 1: | Line 1: | ||
- | == An application to nonlinear complementarity problems == | ||
- | |||
=== Fixed point problems === | === Fixed point problems === | ||
- | |||
Let <math>\mathcal A</math> be a set and <math>F:\mathcal A\to\mathcal A </math> a mapping. The '''fixed point problem''' defined by <math>F\,</math> is the problem | Let <math>\mathcal A</math> be a set and <math>F:\mathcal A\to\mathcal A </math> a mapping. The '''fixed point problem''' defined by <math>F\,</math> is the problem | ||
Line 17: | Line 14: | ||
=== Nonlinear complementarity problems === | === Nonlinear complementarity problems === | ||
- | |||
Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Recall that the dual cone of <math>\mathcal K</math> is the closed convex cone <math>\mathcal K^*=-\mathcal K^\circ,</math> where <math>\mathcal K^\circ</math> is the [[Moreau's_decomposition_theorem#Moreau.27s_theorem |polar]] of <math>\mathcal K.</math> The '''nonlinear complementarity problem''' defined by <math>\mathcal K</math> and <math>f\,</math> is the problem | Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Recall that the dual cone of <math>\mathcal K</math> is the closed convex cone <math>\mathcal K^*=-\mathcal K^\circ,</math> where <math>\mathcal K^\circ</math> is the [[Moreau's_decomposition_theorem#Moreau.27s_theorem |polar]] of <math>\mathcal K.</math> The '''nonlinear complementarity problem''' defined by <math>\mathcal K</math> and <math>f\,</math> is the problem | ||
Line 32: | Line 28: | ||
=== Every nonlinear complementarity problem is equivalent to a fixed point problem === | === Every nonlinear complementarity problem is equivalent to a fixed point problem === | ||
- | |||
Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Then, the nonlinear complementarity problem <math>NCP(f,\mathcal K)</math> is equivalent to the fixed point problem | Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Then, the nonlinear complementarity problem <math>NCP(f,\mathcal K)</math> is equivalent to the fixed point problem | ||
<math>Fix(P_{\mathcal K}\circ(I-f)),</math> where <math>I:\mathbb H\to\mathbb H</math> is the identity mapping defined by <math>I(x)=x.\,</math> | <math>Fix(P_{\mathcal K}\circ(I-f)),</math> where <math>I:\mathbb H\to\mathbb H</math> is the identity mapping defined by <math>I(x)=x.\,</math> | ||
=== Proof === | === Proof === | ||
- | |||
For all <math>x\in\mathbb H</math> denote <math>z=x-f(x)\,</math> and <math>y=-f(x).\,</math> Then, <math>z=x+y.\,</math> | For all <math>x\in\mathbb H</math> denote <math>z=x-f(x)\,</math> and <math>y=-f(x).\,</math> Then, <math>z=x+y.\,</math> | ||
<br> | <br> | ||
Line 54: | Line 48: | ||
Hence, <math>P_{\mathcal K^\circ}(z)=z-x=y,</math>. Thus, <math>y\in\mathcal K^\circ</math>. [[Moreau's_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] also implies that <math>\langle x,y\rangle=0.</math> In conclusion, | Hence, <math>P_{\mathcal K^\circ}(z)=z-x=y,</math>. Thus, <math>y\in\mathcal K^\circ</math>. [[Moreau's_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] also implies that <math>\langle x,y\rangle=0.</math> In conclusion, | ||
<math>x\in\mathcal K,</math> <math>f(x)=-y\in\mathcal K^*</math> and <math>\langle x,f(x)\rangle=0.</math> Therefore, <math>x\,</math> is a solution of <math>NCP(f,\mathcal K).</math> | <math>x\in\mathcal K,</math> <math>f(x)=-y\in\mathcal K^*</math> and <math>\langle x,f(x)\rangle=0.</math> Therefore, <math>x\,</math> is a solution of <math>NCP(f,\mathcal K).</math> | ||
+ | |||
=== An alternative proof without [[Moreau's_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] === | === An alternative proof without [[Moreau's_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] === | ||
- | |||
==== Variational inequalities ==== | ==== Variational inequalities ==== | ||
- | |||
Let <math>\mathcal C</math> be a closed convex set in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. The '''variational inequality''' defined by <math>\mathcal C</math> and <math>f\,</math> is the problem | Let <math>\mathcal C</math> be a closed convex set in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. The '''variational inequality''' defined by <math>\mathcal C</math> and <math>f\,</math> is the problem | ||
Line 73: | Line 66: | ||
==== Every variational inequality is equivalent to a fixed point problem ==== | ==== Every variational inequality is equivalent to a fixed point problem ==== | ||
- | |||
Let <math>\mathcal C</math> be a closed convex set in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Then the variational inequality <math>VI(f,\mathcal C)</math> is equivalent to the fixed point problem <math>Fix(P_{\mathcal C}\circ(I-f)).</math> | Let <math>\mathcal C</math> be a closed convex set in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Then the variational inequality <math>VI(f,\mathcal C)</math> is equivalent to the fixed point problem <math>Fix(P_{\mathcal C}\circ(I-f)).</math> | ||
==== Proof ==== | ==== Proof ==== | ||
- | |||
<math>x\,</math> is a solution of <math>Fix(P_{\mathcal C}\circ(I-f))</math> if and only if | <math>x\,</math> is a solution of <math>Fix(P_{\mathcal C}\circ(I-f))</math> if and only if | ||
<math>x=P_{\mathcal C}(x-f(x)).</math> By using the [[Moreau's_decomposition_theorem#Characterization_of_the_projection | characterization of the projection]] the latter equation is equivalent to | <math>x=P_{\mathcal C}(x-f(x)).</math> By using the [[Moreau's_decomposition_theorem#Characterization_of_the_projection | characterization of the projection]] the latter equation is equivalent to | ||
Line 89: | Line 80: | ||
===== Remark ===== | ===== Remark ===== | ||
- | |||
The next section shows that the equivalence of variational inequalities and fixed point problems is much stronger than the equivalence of nonlinear complementarity problems and fixed point problems, because each nonlinear complementarity problem is a variational inequality defined on a closed convex cone. | The next section shows that the equivalence of variational inequalities and fixed point problems is much stronger than the equivalence of nonlinear complementarity problems and fixed point problems, because each nonlinear complementarity problem is a variational inequality defined on a closed convex cone. | ||
==== Every variational inequality defined on a closed convex cone is equivalent to a complementarity problem ==== | ==== Every variational inequality defined on a closed convex cone is equivalent to a complementarity problem ==== | ||
- | |||
Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Then, the nonlinear complementarity problem <math>NCP(f,\mathcal K)</math> is equivalent to the variational inequality <math>VI(f,\mathcal K).</math> | Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f:\mathbb H\to\mathbb H</math> a mapping. Then, the nonlinear complementarity problem <math>NCP(f,\mathcal K)</math> is equivalent to the variational inequality <math>VI(f,\mathcal K).</math> | ||
==== Proof ==== | ==== Proof ==== | ||
- | |||
Suppose that <math>x\,</math> is a solution of <math>NCP(f,\mathcal K).</math> Then, <math>x\in\mathcal K,</math> <math>f(x)\in\mathcal K^*</math> and <math>\langle x,f(x)\rangle=0.</math> Hence, | Suppose that <math>x\,</math> is a solution of <math>NCP(f,\mathcal K).</math> Then, <math>x\in\mathcal K,</math> <math>f(x)\in\mathcal K^*</math> and <math>\langle x,f(x)\rangle=0.</math> Hence, | ||
Line 118: | Line 106: | ||
==== Concluding the alternative proof ==== | ==== Concluding the alternative proof ==== | ||
- | |||
Since <math>\mathcal K</math> is a closed convex cone, the nonlinear complementarity problem <math>NCP(f,\mathcal K)</math> is equivalent to the variational inequality <math>VI(f,\mathcal K),</math> which is equivalent to the fixed point problem <math>Fix(P_{\mathcal K}\circ(I-f)).</math> | Since <math>\mathcal K</math> is a closed convex cone, the nonlinear complementarity problem <math>NCP(f,\mathcal K)</math> is equivalent to the variational inequality <math>VI(f,\mathcal K),</math> which is equivalent to the fixed point problem <math>Fix(P_{\mathcal K}\circ(I-f)).</math> | ||
- | + | == Implicit complementarity problems == | |
- | + | ||
- | + | ||
Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f,g:\mathbb H\to\mathbb H</math> two mappings. Recall that the dual cone of <math>\mathcal K</math> is the closed convex cone <math>\mathcal K^*=-\mathcal K^\circ,</math> where <math>\mathcal K^\circ</math> is the | Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f,g:\mathbb H\to\mathbb H</math> two mappings. Recall that the dual cone of <math>\mathcal K</math> is the closed convex cone <math>\mathcal K^*=-\mathcal K^\circ,</math> where <math>\mathcal K^\circ</math> is the | ||
[[Moreau's_decomposition_theorem#Moreau.27s_theorem |polar]] | [[Moreau's_decomposition_theorem#Moreau.27s_theorem |polar]] | ||
Line 141: | Line 126: | ||
=== Every implicit complementarity problem is equivalent to a fixed point problem === | === Every implicit complementarity problem is equivalent to a fixed point problem === | ||
- | |||
Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f,g:\mathbb H\to\mathbb H</math> two mappings. Then, the implicit complementarity problem <math>ICP(f,g,\mathcal K)</math> is equivalent to the [[Moreau's_decomposition_theorem#Fixed_point_problems | fixed point problem]] | Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>f,g:\mathbb H\to\mathbb H</math> two mappings. Then, the implicit complementarity problem <math>ICP(f,g,\mathcal K)</math> is equivalent to the [[Moreau's_decomposition_theorem#Fixed_point_problems | fixed point problem]] | ||
<math>Fix(I-g+P_{\mathcal K}\circ(g-f)),</math> where <math>I:\mathbb H\to\mathbb H</math> is the identity mapping defined by <math>I(x)=x.\,</math> | <math>Fix(I-g+P_{\mathcal K}\circ(g-f)),</math> where <math>I:\mathbb H\to\mathbb H</math> is the identity mapping defined by <math>I(x)=x.\,</math> | ||
=== Proof === | === Proof === | ||
- | |||
For all <math>u\in\mathbb H</math> denote <math>z=g(u)-f(u),\,</math> <math>x=g(u)\,</math> and <math>y=-f(u).\,</math> Then, | For all <math>u\in\mathbb H</math> denote <math>z=g(u)-f(u),\,</math> <math>x=g(u)\,</math> and <math>y=-f(u).\,</math> Then, | ||
<math>z=x+y.\,</math> | <math>z=x+y.\,</math> | ||
Line 173: | Line 156: | ||
=== Remark === | === Remark === | ||
- | |||
In particular if <math>g=I,</math> we obtain the result | In particular if <math>g=I,</math> we obtain the result | ||
[[Moreau%27s_decomposition_theorem#Every_nonlinear_complementarity_problem_is_equivalent_to_a_fixed_point_problem | Every nonlinear complementarity problem is equivalent to a fixed point problem]], | [[Moreau%27s_decomposition_theorem#Every_nonlinear_complementarity_problem_is_equivalent_to_a_fixed_point_problem | Every nonlinear complementarity problem is equivalent to a fixed point problem]], | ||
but the more general result [[Moreau%27s_decomposition_theorem#Every_implicit_complementarity_problem_is_equivalent_to_a_fixed_point_problem | Every implicit complementarity problem is equivalent to a fixed point problem]] has no known connection with variational inequalities. Therefore, using [[Moreau's_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] is essential for proving the latter result. | but the more general result [[Moreau%27s_decomposition_theorem#Every_implicit_complementarity_problem_is_equivalent_to_a_fixed_point_problem | Every implicit complementarity problem is equivalent to a fixed point problem]] has no known connection with variational inequalities. Therefore, using [[Moreau's_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] is essential for proving the latter result. |
Revision as of 12:17, 17 July 2009
Contents |
Fixed point problems
Let be a set and
a mapping. The fixed point problem defined by
is the problem
Nonlinear complementarity problems
Let be a closed convex cone in the Hilbert space
and
a mapping. Recall that the dual cone of
is the closed convex cone
where
is the polar of
The nonlinear complementarity problem defined by
and
is the problem
Every nonlinear complementarity problem is equivalent to a fixed point problem
Let be a closed convex cone in the Hilbert space
and
a mapping. Then, the nonlinear complementarity problem
is equivalent to the fixed point problem
where
is the identity mapping defined by
Proof
For all denote
and
Then,
Suppose that is a solution of
Then,
with
and
Hence, by using Moreau's theorem, we get
Therefore,
is a solution of
Conversely, suppose that is a solution of
Then,
and by using Moreau's theorem
Hence, . Thus,
. Moreau's theorem also implies that
In conclusion,
and
Therefore,
is a solution of
An alternative proof without Moreau's theorem
Variational inequalities
Let be a closed convex set in the Hilbert space
and
a mapping. The variational inequality defined by
and
is the problem
Every variational inequality is equivalent to a fixed point problem
Let be a closed convex set in the Hilbert space
and
a mapping. Then the variational inequality
is equivalent to the fixed point problem
Proof
is a solution of
if and only if
By using the characterization of the projection the latter equation is equivalent to
for all But this holds if and only if
is a solution
of
Remark
The next section shows that the equivalence of variational inequalities and fixed point problems is much stronger than the equivalence of nonlinear complementarity problems and fixed point problems, because each nonlinear complementarity problem is a variational inequality defined on a closed convex cone.
Every variational inequality defined on a closed convex cone is equivalent to a complementarity problem
Let be a closed convex cone in the Hilbert space
and
a mapping. Then, the nonlinear complementarity problem
is equivalent to the variational inequality
Proof
Suppose that is a solution of
Then,
and
Hence,
for all Therefore,
is a solution of
Conversely, suppose that is a solution of
Then,
and
for all Particularly, taking
and
, respectively, we get
Thus,
for all
or equivalently
In conclusion,
and
Therefore,
is a solution of
Concluding the alternative proof
Since is a closed convex cone, the nonlinear complementarity problem
is equivalent to the variational inequality
which is equivalent to the fixed point problem
Implicit complementarity problems
Let be a closed convex cone in the Hilbert space
and
two mappings. Recall that the dual cone of
is the closed convex cone
where
is the
polar
of
The implicit complementarity problem defined by
and the ordered pair of mappings
is the problem
Every implicit complementarity problem is equivalent to a fixed point problem
Let be a closed convex cone in the Hilbert space
and
two mappings. Then, the implicit complementarity problem
is equivalent to the fixed point problem
where
is the identity mapping defined by
Proof
For all denote
and
Then,
Suppose that is a solution of
Then,
with
and
Hence, by using
Moreau's theorem,
we get
Therefore,
is a solution of
Conversely, suppose that is a solution of
Then,
and by using
Moreau's theorem
Hence, . Thus,
.
Moreau's theorem
also implies that
In conclusion,
and
Therefore,
is a solution of
Remark
In particular if we obtain the result
Every nonlinear complementarity problem is equivalent to a fixed point problem,
but the more general result Every implicit complementarity problem is equivalent to a fixed point problem has no known connection with variational inequalities. Therefore, using Moreau's theorem is essential for proving the latter result.