We present recent advances in nonlinear optimization, which have been obtained based on p-regularity theory, successfully developing for the last years. The main result of this theory gives a detailed description of the structure of the zero set of an irregular nonlinear mapping. We illustrate the theory with an application in different branches of optimization. Amongst the applications, the construction of p-factor operator is used to construct numerical methods for solving degenerate optimization problems and p-order necessary and sufficient optimality conditions are formulated. The reducibility of inequality-constrained optimization problems to the equality constrained optimization problems is proved in the framework of p-regularity theory. Moreover, the connection between singular problems and nonlinear problems is shown.
F (x) = 0,
Introduction This work concerns the problem of solving a nonlinear equation of the form or optimization problem where F : X → Y is a sufficiently smooth mapping from a Banach space X to a Banach space Y . Of course, the solution to many interesting nonlinear problems can be cast in this form and there have been many works devoted to this problem. The purpose of this paper is to present some of our own work and that of others in this area in a coherent way, which has hitherto been scattered throughout various references, as well as giving a number of new results. This paper is based on [Tretyakov, 1984], [Brezhneva & Tretyakov, 2007] and [Prusinska & Tretyakov, 2016].
We separate nonlinear mappings F and problems of the form (1) into two classes, called regular and irregular. Roughly speaking, regular problems are those to which implicit function theorem arguments can be applied and the irregular ones are those to which it cannot, at least not directly. (1) (2)
Goal of the Present Contribution In this work, we show how to apply p-regularity theory, also known as factor-analysis of nonlinear mappings to the description and investigation of singular mappings and, in addition, to develop methods for finding solutions to related singular problems. In particular, we show how these ideas apply to some specific situations, such as optimization problems. 2.1
then the properties of the linear approximation of F locally correspond to the properties of the mapping F , since the mapping F can be locally linearized by a local diffeomorphism; that is, by a nondegenerate transformation of coordinates. Namely, there exist a neighborhood U of the point 0 and a C1 mapping φ : U → X such that φ(0) = x∗, φ′(0) = IX , (the identity map on X), and
F (φ(x)) = F (x∗) + F ′(x∗)x for all x ∈ U . If the regularity condition (3) is not satisfied, then there is no such correspondence in general.
There exist numerous problems where the linear approximation of F is not enough to describe the properties of the mapping. For example, there are essential nonlinear mappings, i.e., mappings whose local linearization does not give a good approximation. We formalize this as follows.
Let V be a neighborhood of x∗ in X. A C2 mapping F : V → Y is referred to as essentially nonlinear at the point x∗, if there exists a perturbation of the form Fe(x∗ + x) = F (x∗ + x) + ω(x), where ∥ω(x)∥ = o(∥x∥), such that there does not exist any C1 nondegenerate transformation of coordinates φ(x) : U → X such that φ(0) = x∗, φ′(0) = IX and (4) holds with φ and Fe.
We say the mapping F is singular (or degenerate, abnormal ) at x∗ if it fails to be regular; that is, its derivative is not onto:
Im F ′(x∗) ̸= Y. 2.2
The following Theorem establishes the relationship between these two notions.
Suppose F : V → Y is C2 and that x∗ is a solution of (1). Then F is essentially nonlinear at the point x∗ if and only if F is singular at the point x∗.
Consider the following singular optimization problem min ϕ(x), 2.4
If F ′(x∗) · X = Y then there exists λ∗ ∈ Y ∗ such that ϕ′(x∗) = F ′(x∗)∗ · λ∗.
Let us ϕ(x) = x21 + x3, F (x) = F ′(0) = ( 0 0 0 ) 0 0 0 but ϕ′(0) ̸= F ′(0)T · λ.
( Consider in general the problem of solving nonlinear equation (1) where F : X → Y, X, Y – B-spaces in general case, and F ∈ Cp+1(X), p ∈ N. Let x∗ solution point to (6), i.e. F (x∗) = 0. We will consider the singular case, i.e. F ′(x∗) is singular.
For X = Rn, Y = Rn it means that matrix F ′(x∗) is degenerate.
F : R2 → R2, where x∗ = (0, 0)T solution to (8) and is singular at x∗ = (0, 0)T .
Newton method k = 0, 1, 2, 3, . . . .
Let x0 = (x10, x20)T and x0 ∈ U"(0), ε > 0 sufficiently small. Then we have for k = 1 F (x) = ( x1 + x2 ) x1x2
, F ′(0) = xk+1 = xk − {F ′(xk)}−1F (xk)
But even ever ∃{F ′(x0)}−1, say for x0 = (t + t3, t)T , we have x1 = If t = 10−5 then ∥x1 − 0∥ ≈ 105 and we have rejecting effect. ( − 1t − t ) 1t + t 2.6
and ∥x1 − 0∥ ≈ 1t → ∞, t → 0.
Consider and x∗ = (0, 0)T , n = 2 at the initial point, x0 = (x01, x02)T where x01 = x02√6(1 + x02), ϕ′′(x0) = ( 2 + 2x02 2x02√6(1 + x02) ) , det ϕ′′(x0) = 0, ̸ ∃{ϕ′′(x0)}−1. 2x02√6(1 + x02) 12x202 min ϕ(x) x∈Rn ϕ(x) = x12 + x12x2 + x24 xk+1 = xk − {ϕ′′(xk)}−1ϕ′(xk), 2.7
Consider the following constrained optimization problem and modified Lagrange function of the following form w = (x, λ) min ϕ(x) gi(x) ≤ 0, i = 1, m LE(x, λ) = ϕ(x) + 1 ∑m λi2gi(x)
2 i=1 G(w) =
m ∇ϕ(x) + i∑=1 λi2∇gi(x)
D(λ)g(x) = 0n+m G′(w) =
m ∇2ϕ(x) + i∑=1 λi2∇2gi(x) (g′(x))T D(λ) , D(λ)g(x)
D(g(λ)) where D(u) := diag{ui}, i = 1, . . . , m, u ∈ Rm.
If at the solution point of (14) w∗ = (x∗, λ∗), gi(x∗) = 0 and λi∗ = 0 then G′(w∗) is singular. 2.8
Let us recall the basic constructions of p-regularity theory which is used in solving of singular problems. The construction of the p-factor-operator. Suppose that the space Y is decomposed into a direct sum
Y = Y1 ⊕ . . . ⊕ Yp, where Y1 = Im F ′(x∗), Z1 = Y. Let Z2 be closed complementary subspace to Y1 (we assume that such closed complement exists), and let PZ2 : Y → Z2 be the projection operator onto Z2 along Y1. By Y2 we mean the closed linear span of the image of the quadratic map PZ2 F (2)(x∗)[·]2. More generally, define inductively,
Yi = span Im PZi F (i)(x∗)[·]i ⊆ Zi, i = 2, . . . , p − 1, where Zi is a chosen closed complementary subspace for (Y1 ⊕ . . . ⊕ Yi−1) with respect to Y, i = 2, . . . , p and PZi : Y → Zi is the projection operator onto Zi along (Y1 ⊕ . . . ⊕ Yi−1) with respect to Y, i = 2, . . . , p. Finally, Yp = Zp.
The order p is chosen as the minimum number for which (15) holds. Let us define the following mappings
Fi(x) = PYi F (x), Fi : X → Yi i = 1, . . . , p, where PYi : Y → Yi is the projection operator onto Yi along (Y1 ⊕ . . . ⊕ Yi−1 ⊕ Yi+1 ⊕ . . . ⊕ Yp) with respect to Y, i = 1, . . . , p.
The linear operator Ψp(h) ∈ L(X, Y1 ⊕ . . . ⊕ Yp), h ∈ X, h ̸= 0 Ψp(h) = F1′(x∗) + F2′′(x∗)h + . . . + Fp(p)(x∗)[h]p−1, is called the p-factor operator.
We say that the mapping F is p-regular at x∗ along an element h, if Im Ψp(h) = Y. (12) (13) (14) (15)
We say that the mapping F is p-regular at x∗ if it is p-regular along any h from the set where k-kernel of the k-order mapping Fk(k)(x∗) is as follows
p Hp(x∗) = { ∩ KerkFk(k)(x∗)} \ {0},
k=1
KerkFk(k)(x∗) = {ξ ∈ X : Fk(k)(x∗)[ξ]k = 0}.
For a linear surjective operator Ψp(h) : X 7→ Y between Banach spaces we denote by {Ψp(h)}−1 its right inverse. Therefore {Ψp(h)}−1 : Y 7→ 2X and we have
{Ψp(h)}−1(y) = {x ∈ X : Ψp(h)x = y} .
We define the norm of {Ψp(h)}−1 via the formula ∥{Ψp(h)}−1∥ = sup inf{∥x∥ : x ∈ {Ψp(h)}−1(y)}.
∥y∥=1 We say that {Ψp(h)}−1 is bounded if ∥{Ψp(h)}−1∥ < ∞.
The following theorem gives a description of a solution set in degenerate case.
Theorem 2 (Generalized Lyusternik Theorem) Let X and Y be Banach spaces and U be a neighborhood of x∗ ∈ X. Assume that F : X→Y, F ∈ Cp(U ) is p-regular at x∗. Then
T1M (x∗) = Hp(x∗).
We now give another version of the theorem.
To state the result, we shall denote by dist(x, M ), the distance function from a point x ∈ X to a set M : dist(x, M ) = yi∈nMf ∥x − y∥, x ∈ X.
Theorem 3. Let X and Y be Banach spaces, and U be a neighborhood of a point x∗ ∈ X. Assume that F : X → Y is a p-times continuously Fr´echet differentiable mapping in U and satisfies the condition of strong p-regularity at x∗. Then there exist a neighborhood U ′ ⊆ U of x∗, a mapping ξ 7→ x(ξ) : U ′ → X, and constants δ1 > 0 and δ2 > 0 such that F (ξ + x(ξ)) = F (x∗), ∥x(ξ)∥X ≤ δ1
p ∑ ∥fi(ξ) − fi(x∗)∥Yi i=1 ∥ξ − x∗∥i−1 (16) and ∥x(ξ)∥X ≤ δ2 ∑ip=1 ∥fi(ξ) − fi(x∗)∥1Y=ii for all ξ ∈ U ′.
here x∗ = (0, 0, 0)T , and F ′(0) = 0 Let h = (1, 1, 0)T then ImF ′′(0)h = R2.
It means that the mapping F (x) is 2-regular at x∗ = 0 and where λ ∈ Y ∗ and where
The mapping F is called strongly p-regular at the point x∗ if there exists γ > 0 such that
Lp(x, λ, h) = φ(x) + L¯p(x, λ, h) = φ(x) + ( p ) ∑ F (k−1)(x)[h]k−1, λ ,
k k=1 ( p ∑ k=1
2 F (k−1)(x)[h]k−1, λ) .
k(k + 1) k sup h∈H {Ψp(h)}−1
< ∞ H = { h ∈ X : Fk(k)(x∗)[h]k
Yk
} ≤ γ, i = 1, p, ∥h∥ = 1 .
Lp′x(x∗, λ∗(h), h) = 0.
L¯pxx(x∗, λ∗(h), h)[h]2 ≥ α∥h∥2. x22 + x3 → min, F (x) = ( x122 − x22 + x23 x1 − x22 + x23 + x2x3 )
Let us recall the following basic theorems of the p-regularity theory.
Theorem 4. (Necessary and sufficient conditions for optimality) Let X and Y be Banach spaces, φ ∈ C2(X), F ∈ Cp+1(X), F : X → Y, φ : X → R. Suppose that h ∈ Hp(x∗) and F is p-regular along h at the point x∗. If x∗ is a local solution to the problem (6)–(7) then there exist multipliers, λ∗(h) ∈ Y ∗ such that Moreover, if F is strongly p-regular at x∗, there exist α > 0 and a multiplier λ∗(h) such that (17) is fulfilled and for every h ∈ Hp(x∗), then x∗ is a strict local minimizer to the problem (6)–(7).
It is easy to verify that the point x∗ = 0 is a local minimum to problem (19).
For x∗ = 0, we have that F ′(0) = 0 is singular. Consider the element h = (1, 1, 0)T .
Since ImF ′′(0)h = R2. It means that the mapping F (x) is 2-regular at x∗ = 0 along h. Consider the 2-factorLagrange function with λ0 = 1. After some transformations we obtain
L2(x, λ(h), h) = x22 + x3 + α(x1 − x2) + β(x1 − x2 + x3), where λ(h) = (λ1(h), λ2(h)) and λ1(h) = (0, 0)T , λ2(h) = (α, β)T . Let us calculate the coefficients α and β.
Using the equality L′2 x(x∗, λ(h), h) = 0 we obtain α = 1 and β = −1. Putting the coefficients into we have
L¯2(x∗, λ(h), h) = 32 x22.
L¯′2′xx(x∗, λ(h), h)[h]2 = Based on p-factor operator construction we give new method for solving nonlinear equations
F (x) = 0, F : Rn → Rn where matrix F ′(x∗) is singular at the solution point x∗. Let Y1 = ImF ′(x∗), P¯1 = PY1? , Y2 = Im (F ′(x∗) + P¯1F ′′(x∗)h), P¯2 = PY2? ,
k Yk+1 = Im F ′(x∗) + ∑P¯iF ′′(x∗)h +
i=1 P¯k+1 = PYk?+1 , k = 2, p − 1.
Then the principal scheme of p-factor method the following where P1 = p∑−1 P¯i, xk+1 = xk − {F ′(xk) + P1F ′′(xk)h}−1 · (F (xk) + P1F ′(xk)h) where P1 is ortoprojection on to Im(F ′(x∗))⊥ and element h, (∥h∥ = 1), such that 2-factor matrix nonsingular (2-regular along h). Then at the solution point will be hold and we can solve the following equation where by virtue of (25) x∗ will be locally unique solution.
F ′(x∗) + P1F ′′(x∗)h F (x∗) + P1F ′(x∗)h = 0
F (x) + P1F ′(x)h = 0
Theorem 5. Let F ∈ Cp(Rn) and there exists h, ∥h∥ = 1 such that p-factor matrix (23) is nonsingular. Then for any x0 ∈ U"(x∗) (ε > 0 sufficiently small) will be fulfilled for scheme (21)
∥xk+1 − x∗∥ ≤ c∥xk − x∗∥2, k = 0, 1, 2, . . . . where c > 0 – constant. N
( x1 + x2 ) F (x) =
x1x2 method is the following , x∗ = (0, 0)T and F ′(0) = is singular at x∗ = (0, 0)T . The scheme of 2-factor (20)
(21) (22) (23) (24) (25) (26) (27) where P1 = and It means, that ∥xk+1 − 0∥ ≤ c∥xk − 0∥2.
F (x) = φ′(x) = ( 2x1 + 2x1x2 ) x21 + 4x32
F ′(xk) + P1F ′′(xk)h = ( )
. , x∗ = (0, 0)T , F is 3-regular at x∗ along h = (1, 1)T
F ′(0) + P1F ′′(0)h + P2F (3)(0)[h]2 = φ′′(0) + P1φ(3)(0)h + P2φ(4)(0)[h]2 = Here P¯1 = ( 0 0 ) 0 1 Consider the 3-factor scheme
This work is partially supported by the Russian Foundation for Basic Research Grant No. 17-07-00510 and Leading Scientific Schools Grant 8 660.2017.1 and by the Russian Academy of Sciences, Presidium Programme I.33 P RAS.