Gradient projection and conditional gradient methods for constrained nonconvex minimization
Maxim Balashov Boris Polyak Andrey Tremba

Gradient methods]Gradient projection  and  conditional gradient methods for constrained nonconvex minimization


 
V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences,
65 Profsoyuznaya street, Moscow 117997, Russia.

balashov73@mail.ru, boris@ipu.ru, atremba@ipu.ru

[2010]Primary: 49J53, 90C26, 90C52. Secondary: 46N10, 65K10.


[
     M. V. Balashov, B. T. Polyak, A. A. Tremba
    December 30, 2023
===============================================



ℝ


    Minimization of a smooth function on a sphere or, more generally,
    on a smooth manifold, is the simplest non-convex optimization
    problem. It has a lot of applications. Our goal is to propose a
    version of the gradient projection algorithm for its solution and
    to obtain results that guarantee convergence of the algorithm
    under some minimal natural assumptions. We use the
    Ležanski-Polyak-Lojasiewicz condition on a manifold to prove
    the global linear convergence of the algorithm.
    Another method well fitted for the problem is  the conditional gradient (Frank-Wolfe) algorithm.
    We examine some conditions which guarantee global convergence of full-step version of the method
    with linear rate.

    




§ INTRODUCTION


Consider  minimization  of a smooth function f(x)
on a closed set Q in the Euclidean space (^n,·)


    min_x∈ Q f(x).


Traditionally the set Q and the function f are assumed to be convex; in such convex setting the problem is well studied and numerous algorithms are known, see e.g.
<cit.> for details.
We plan to address the situation when the function or/and the set are nonconvex.

The function f under consideration is smooth with the Lipschitz continuous gradient, but nonconvex.
Regarding the set Q,  we mostly suppose that it is proximally smooth <cit.>.
In particular we consider the next important cases:

1) Q=S_R={x ∈ℝ^n | ||x||=R} (minimization on the sphere),

2) Q = { x∈^n | g(x)=0}, g:^n→^m (equality type constraints),

3) Q is the boundary of a strongly convex set B⊂^n.


Minimization on the sphere has numerous applications, for
instance finding minimal eigenvalue of a symmetric matrix
A∈^n× n (then f(x)=(Ax,x), Q=S_1) or choosing
step-size in trust-region methods <cit.>. The set
Q is obviously nonconvex thus (<ref>) is an example of
nonconvex optimization problems. The pioneering work in the field
is <cit.>. Special case of  problem (<ref>) (for
quadratic f(x)) has been studied by Hager <cit.>; the
solution can be reduced to solving 1D equations. Later
publications include <cit.>, in most of them Q is a
smooth (Riemannian) manifold. But in general, research in
nonconvex optimization is much less intensive than in convex
case. The main approaches use generalized convexity on the set
and/or consider geodesic-related steps. In contrast, we use
neither of these. There are numerous methods for optimization
with equality type constrains, see e.g <cit.>, <cit.>. However, most of them generate
points which are not admissible (x_k∉ Q) while our purpose
is to develop methods with admissible iterations.



The contribution of the present paper is triple:

    
  * We propose a new approach to the gradient projection algorithm for constrained optimization,
    based on the idea of upper approximation of the objective function. The resulting method is
    the gradient projection algorithm with constant step-size; it differs from versions proposed in <cit.>.
    Moreover we prove its convergence to a stationary point without any convexity-like assumptions.
    
  * We generalize well known in unconstrained optimization the Polyak-Loja­sie­wicz condition on
    the class of problems (<ref>). Under this assumption we prove
    linear convergence of the gradient projection algorithm (with projection on the 
    tangent subspace and a variant combined with the Newton method) to a global extremum under assumption of proximal smoothness of the manifold Q.
    As an example we consider a quadratic form on the unit sphere.
    
  * For approximately linear objective functions we propose a new version of the Frank-Wolfe
    (conditional gradient) method and establish its linear convergence to a global minimum in problem (<ref>). We prove
    linear convergence of the method for a surface, which is the boundary of a strongly convex set. Note, that such surface is not
    necessary smooth.


In the paper <cit.> linear convergence of the gradient projection algorithm was
proved for a proximally smooth set with constant R and for a strongly convex function with constant of strong convexity ϰ and Lipschitz constant L
under assumption L/ϰ<R. The last inequality is essential for linear convergence
of the method.
In subsection <ref> we prove convergence of the standard gradient projection algorithm
to a stationary point of the problem (<ref>) for any function with the Lipschitz
continuous gradient and for any proximally smooth set.


In subsection <ref> we extend  the Polyak-Lojasiewicz condition (well known in
unconstrained minimization)
<cit.> for the constrained case
(<ref>) with differentiable function and C^1 smooth
manifold Q. We want to pay attention that this
generalization is in fact some variant of the error bound
condition for the case of smooth set Q.

On the base of the new definition from subsection <ref> we
prove in subsection <ref> convergence of the gradient projection algorithm for
Q=S_1. For the case of general C^1 smooth
and proximally smooth manifold of codimension 1 we prove it in subsection
<ref>. In contrast with other approaches our algorithms
represent variants of the gradient projection algorithm with
admissible points x_k∈ Q and linear rate of convergence.

In subsection <ref> we consider the situation when the gradient projection
algorithm can be finalized by use of the Newton method. This is standard practice,
except that we are dealing with nonconvex problem.

Concluding section <ref>, we prove the
Ležanski-Polyak-Lojasiewicz condition for the quadratic function on the sphere.
Thus we extend the result <cit.>
by clarifying  constant μ in this condition. It is essential for estimate of the error
for the gradient projection algorithm in the case Q=S_1.

In section <ref> we consider application of the Frank-Wolfe method
for solving the problem (<ref>) in the case when Q is the boundary
of a strongly convex set of radius R.
It is well known that if the set Q is a convex compact and f
is a Lipschitz differentiable convex function then the method
converges (with respect to the objective function) with sublinear
rate. In <cit.> the authors discuss the choice of step-size
in the method. In <cit.> the author proved that under
certain assumptions
in the case of convex compact set Q and for a (nonconvex) function with the Lipschitz continuous gradient the Frank-Wolfe method converges to a stationary point in the problem
(<ref>) with sublinear rate.

We prove linear rate of convergence with respect to the point. In subsection
<ref> we proved it for so-called linear approximative function and in subsection
<ref> we proved it for a function with gradient domination.
In fact in both subsections the general idea consists in the fact that radius of ”curvature”
of the level sets for our function is larger than the radius of strong convexity. This leads
to the results. We only want to point out that we take the notation of radius of ”curvature” in the sense of supporting principles for proximally smooth and strongly convex sets.

For completeness in Appendix we prove necessary condition of
minimum in the problem (<ref>) for a proximally smooth
set Q and a function with the Lipschitz continuous gradient.

All mentioned parts are gathered together by the possibility of certain
“spherical" approximation (via the supporting principles) for the set/surface Q
in problem (<ref>).


The most part of mentioned results takes place in the case of the real Hilbert space.
Sometimes obvious patches should be applied in the infinite dimension case,
for example compactness of the set Q in Theorem <ref>.



§ DEFINITIONS AND MAIN NOTATIONS


Let B_R(a) = { x∈^n |  x-a≤ R} be the ball with center a∈^n
and radius R>0.
 For a set Q⊂^n the sets Q, ı Q, Q̣ are the closure, the interior and
the boundary of Q, respectively. We also denote by Q̣ the edge of the surface Q. 

Let P_Q be the operator of metric projection on the set Q, i.e. P_Q(x)={y∈ Q: ||y-x||=inf_z∈ Q ||x-z|| }. In general, P_Q can be set-valued for nonconvex sets, but for proximally smooth sets (see below) it is single-valued (provided x is close enough to Q).

For a closed set Q⊂^n the normal cone of proximal normals
(or simply the normal cone) at a point x∈ Q is defined as follows <cit.>

    N(Q,x) = { p∈^n | ∃δ>0 P_Q(x+δ p)= x }.

If the set Q is convex, then N(Q,x) coincides with normal cone
in the sense of convex analysis.

A closed set Q⊂^n is called proximally smooth with constant R>0 <cit.> if the distance
function ϱ (x,Q) =ϱ _Q(x)=inf_a∈ Qx-a
is continuously Frechet
differentiable on the set U_Q(R) = { x∈^n | 0<ϱ
_Q(x)<R}. The equivalent properties for a proximally smooth set
with constant R are

1) P_Q:U_Q(R)→ Q is a single-valued continuous function,

2) supporting principle: p∈ N(Q,x), p=1, if and only if Q∩ı
B_R(x+Rp)=∅.

Note that the mapping Q∋ x→ N(Q,x) is upper semicontinuous for a proximally smooth set Q
with constant R. For a point x∈ı Q we have N(Q,x)= 0 and it is sufficient to prove upper semicontinuity on the boundary Q̣.
Choose x_k∈Q̣, x_k→ x∈Q̣, and p_k∈ N(Q,x_k), p_k=1, with
p_k→ p. Suppose that p∉ N(Q,x), the last means that N(Q,·) is not
upper semicontinuous at the point x. By the supporting principle for proximally smooth sets

    ∃ ∈ Q∩ı B_R(x+Rp).

The sets ı B_R(x_k+Rp_k) converge to the set ı B_R(x+Rp) in the Hausdorff metric,
thus ∈ Q∩ı B_R(x_k+Rp_k) for sufficiently large k. A contradiction.


If we consider a continuously differentiable (n-1)-dimensional surface Q without edge which is also proximally smooth with constant R>0, then for any point x∈ Q the normal cone N(Q,x) is
1-dimensional subspace. If p=1 and p∈ N(Q,x) then the surface Q is trapped between the supporting
spheres (see supporting principle 2)):

    Q⊂( ^n\ı B_R(x-Rp))∩( ^n\ı B_R(x+Rp)).


A closed convex set B⊂^n is called strongly convex
of radius r>0 if it can be represented in the form
B=⋂_x∈ XB_r(x) <cit.>.
There are few equivalent properties for strong convexity:

1) A convex
compact set B⊂^n is strongly convex of radius r if and only if
for any pair of points x,y∈ B the ball with center
1/2 (x+y) of radius 1/8r x-y^2 belongs to B
<cit.>. 

2) Another equivalent property for
strong convexity is supporting principle: for any x∈Ḅ and p∈ N(B,x), p=1, we have

    B⊂ B_r(x-rp).

3) The set B⊂^n is
strongly convex of radius r if and only if for any unit vectors
p,q and for supporting elements x_p=max_x∈
B(p,x), x_q=max_x∈ B(q,x) we have the next
inequality <cit.>

    x_p-x_q≤ r p-q.


If Q is a smooth manifold, then the subspace T_x is the tangent subspace to  Q at a point x∈ Q, i.e.

    T_x = { v∈^n:  ϱ (x+tv, Q)=o_v(t) },

where lim_t→+0o_v(t)/t=0 for all v∈
T_x.

Define Ł_f(β) = { x∈^n | f(x)≤β} the lower level set
of the function f.


We  say that the function f has the Lipschitz continuous gradient
with constant L_1>0 if

    f'(x)-f'(y)≤ L_1x-y,   ∀ x,y.


It is well known that (<ref>) implies the upper bound for f
<cit.>:

    |f(y) - f(x) - (f'(x),y-x)|≤C/2||y-x||^2,   ∀ x,y,

for any C≥ L_1.

We write f(t)≍ g(t), t∈^1, t→ +0, if there exist 0<C_1<C_2 and δ>0
such that C_1 f(t)≤ g(t)≤ C_2f(t) for all t∈ (0,δ).

For a differentiable vector function g(x) = (g_1(x),…, g_m(x))^T denote the Jacobi
matrix as

    g'(x) = (g_1'(x)… g_m'(x))

and we treat g_i'(x) as columns.

The set Ω⊂ Q is the set of stationary points of the differentiable function f on the
set Q (which is associated with the problem (<ref>)) if
for any point x∈Ω we have f'(x)∈ - N(Q,x). The last
inclusion is necessary condition of optimality for a proximally
smooth set Q and a smooth function f. We prove it in Appendix for
completeness.



§ THE GRADIENT PROJECTION ALGORITHM



The gradient projection algorithm
for (<ref>) in convex case has been proposed in
<cit.>. The simplest version (with constant step-size) looks as follows:
for an iteration x_k∈ Q it generates the new point x_k+1 as the minimizer
of the upper bound on Q (with C_1≥ L_1) or, equivalently, as projection of the gradient step on Q:

Gradient Projection Algorithm (GPA1)



Step 1.
Choose a constant C_1 > 0, initial point x_0 ∈ Q and put k = 0.

Step 2.
Repeat

    [                                                      x_k+1 = min_x∈ Q{f(x_k) + (f'(x_k), x-x_k) + C_1/2||x-x_k||^2} =;                                                                                            =  P_Q( x_k-1/C_1f'(x_k)), ]


The condition C_1≥ L_1 is equivalent to choice of the constant step-size t ≤1/L_1.
Below we shall consider the extensions of the method for nonconvex set Q and nonconvex function f(x).


One of the possible ways for extension
 is gradient projection along geodesics  proposed by Luenberger <cit.>. It is not hard to design geodesics on the sphere (arcs of big circles on the sphere),
but the original algorithm in <cit.> requires one-dimensional minimization on each iteration.
Another problem is that in the case of an arbitrary manifold Q construction of geodesics is a hard procedure.
Thus we avoid geodesics and try to deal with gradient projection method with constant step-size in the form (<ref>).






 §.§ The case of an arbitrary proximally smooth set Q. General algorithm


The next result shows that for any function f:^n→ with the Lipschitz continuous
gradient and for any proximally smooth set Q⊂^n  iterations of the standard gradient
projection algorithm (<ref>) are well-defined and
 converge to a stationary point of the function f on the set Q
for the appropriate choice of the step-size.



 Let Q⊂^n be a bounded proximally smooth set with constant R>0.
    Suppose that the function f:^n→ is the Lipschitz continuous with constant L>0
    and its gradient f' is also the Lipschitz continuous with constant L_1>0.
    Take C>0 with L/C+L_1<R. Then
    for any x_0∈ Q
    GPA1 with C_1 = C + L_1
converges to the set of stationary points Ω: lim_k→∞ϱ_Ω(x_k) = 0 and
    
    f(x_k+1)+C/2 x_k+1-x_k^2≤ f(x_k)

    for all k≥ 0.
Define for each natural k the function

    ψ_k(x) = f(x_k)+
    (f'(x_k),x-x_k)+C+L_1/2 x-x_k^2.

It's easy to see (due to the Lipschitz continuity of gradient f') that

    ψ_k(x) ≥ f(x)+C/2 x-x_k^2

for all x∈^n and

    ϱ_Q(x_k-1/C+L_1f'(x_k) )≤1/C+L_1f'(x_k)≤L/C+L_1<R.

Hence the distance from the point x_k-1/C+L_1f'(x_k) to the set Q is less than
R and the metric projection x_k+1 is defined uniquely by the definition of proximally smooth set.
We have

    f(x_k)=ψ_k (x_k)≥ψ_k (x_k+1)≥ f(x_k+1)+C/2 x_k+1-x_k^2.


Assume that lim_k→∞ϱ_Ω(x_k) 0 for some
sequence {x_k}⊂ Q which is generated by the gradient
projection algorithm.
Then
there is a number >0
and a subsequence {x_k_m}⊂{x_k}
with ϱ_Ω(x_k_m)≥ for all m.
Consider a
converging subsequence of the sequence {x_k_m}
(that again is denoted by {x_k_m})
and x_* = lim_m→∞x_k_m.
Then from the necessary conditions of minimum of the function ψ_k_m on the set Q we get

    ψ'_k(x_k_m +1 )∈ - N(Q,x_k_m +1 ),

in other words

    f'(x_k_m)+(C+L_1)(x_k_m +1 -x_k_m)∈ - N(Q,x_k_m +1 ).

Passing to the limit as m→∞, using upper semicontinuity of the normal cone N(Q,·)
and the property lim_m→∞(x_k_m +1 -x_k_m)=0
we have

    f'(x_*)∈ - N(Q,x_*).

Thus lim_m→∞ϱ_Ω(x_k_m)=0, a contradiction.


With the help of Theorem <ref> we can find a stationary point with error >0,
namely we can find a point x∈ Q with ϱ (0, -f'(x)-N(Q,x))<.


Stationary-point Algorithm

Step 1.
Choose > 0 and C > max{0, L/R-L_1 }. Put Δ f= sup_Q f - inf_Q f, δ=/C+2L_1,
and set k = 0.

Step 2. Perform a Step 2 (<ref>) of GPA1 with C_1 = C + L_1.

Step 3. If x_k - x_k+1≥δ, increase k and continue to the Step 2.

Otherwise stop the algorithm and return x_k+1 as the solution.



The algorithm do at most N = ⌊2 Δ f/Cδ^2⌋ + 1 steps.
Assume the contrary, that x_k+1-x_k≥δ for k=0,…,N-1.
Then assumptions of Theorem <ref> holds, thus
C/2δ^2≤ f(x_k)-f(x_k+1) and after N steps we get

    f(x_0) - f(x_N) ≥ NC/2δ^2 > Δ f,

i.e. a contradiction.
When the algorithm stops with x_k - x_k+1 < δ, by the optimality condition for the function ψ_k we get

    f'(x_k)+(C+L_1)(x_k+1-x_k)∈ - N(Q,x_k+1).

Using the Lipschitz continuity of f' we obtain

    ϱ (f'(x_k+1),-N(Q,x_k+1))≤δ (C + 2L_1)=.


Note that the parameter C of the
step t=1/C+L_1 depends on Lipschitz constant L of the function
f because the point x_k-t f'(x_k)
should not go very far from the set Q.
Moreover, conditions on constant C mean that the step-size t satisfies the inequality t<min{R/L,1/L_1}.


Sometimes projection can be found explicitly, for example for the unit sphere
Q=S_1:

    x_k+1 =  x_k -t f'(x_k)/ x_k - t f'(x_k),

thus the algorithm is the gradient-projection method with
constant step-size.


By Proposition <ref> the first-order optimality condition in (<ref>) for Q=S_1
means f'(x)=λ x,  x=1, λ∈ℝ, and it can be immediately rewritten in the form

    (I - x x^T) f'(x)=0,

(here I is the unit matrix) or
as

    L_1 x - f'(x) = |( L_1 x - f'(x), x)|.






 §.§ The Ležanski-Polyak-Lojasiewicz condition on a manifold.


Now the main task is to propose conditions which guarantee convergence of the method to the global minimum in the problem
(<ref>) and to estimate the rate of convergence.

In unconstrained minimization we have such powerful tool as convexity; gradient method for convex functions converges to global minima while for strongly convex functions one has linear rate of convergence. There are extensions of convexity for minimization on manifolds, see e.g. the monograph
<cit.> and the paper <cit.>. Unfortunately there exist no (globally) convex functions on compact manifolds <cit.>, thus we need  some other tools.

However in the unconstrained case there are conditions which validate convergence for nonconvex functions. Probably the first one is due to T. Ležanski <cit.>. He considered
a problem of unconstrained minimization for a Lipschitz differentiable function f such that there exists
a positive continuous function φ with

    f'(x)≥φ (f(x)-f_0),  ∀ x∈^n,     f_0=min_x∈^nf(x),  ∫_0^f(x)-f_0ds/φ (s)<∞.


Under these assumptions he proved for φ (s)=c√(s) the convergence of the gradient descent
algorithm
x_k+1=x_k-t_kf'(x_k)
with linear rate.
The same assumption

    f'(x)^2≥μ (f(x)-f_0)

(where μ>0, f_0=min f(x)) was considered in
<cit.>. Sometimes <cit.> this
 is referred as the Polyak-Lojasiewicz condition (works of Ležanski were not widely known). Thus it is fair to call the above condition as Ležanski-Polyak-Lojasiewicz (LPL) one.


Analogously we can propose the analog of LPL condition for the constrained minimization of a differentiable
function f:^n→ on a smooth
manifold Q⊂^n. Define by P_T_x the metric projection on the tangent subspace
T_x to the manifold Q at the point x∈ Q.
Note that N(Q,x) is the polar cone (subspace) for the tangent space T_x.


Let Q⊂^n be a C^1 manifold and f:^n→ be a differentiable function. Let μ>0, α≥ 1, β∈^n,
f_0 = min_Q f. We shall say that the Ležans­ki-Po­lyak-Lo­ja­sie­wicz LPL condition with exponent α holds
for the function f on the set Q if

    P_T_xf'(x)^α≥μ (f(x)-f_0)

for all x∈ Q∩Ł_f(β).


If α=2 then we shall call (<ref>) simply the LPL condition for the function f
on the manifold Q.

We want to admit that we consider such manifold Q that
its edge Q̣ has empty intersection with the set Ł_f(β).
For example, Q can be a manifold without edge.

 Note that if Q is given by the system S={ x∈^n | g(x)=0} of
full rank then P_T_x = I - g'(x)(g'(x)^Tg'(x))^-1g'(x)^T for all x∈ Q.
Here I is the identity operator in ^n.




 In the case Q=S_1 LPL condition reads

    (I - x x^T) f'(x) ^2 ≥μ (f(x)-f_0),

 for all x∈ S_1∩Ł_f(β).


Later we shall consider quadratic case (f(x) is a quadratic function) and confirm fulfillment of condition (<ref>).


Now consider a special 2D example which exhibits possible situations.

 Let Q={ (x,y)∈^2 | x^2+(y-1/2)^2=1/4}  (the set Q is the circle with
 center (0,1/2) and radius r=1/2). Let f(x,y) =
 y-px^2, where p∈ (0,1] is a parameter. We have
 
    (0,0) = min_(x,y)∈ Qf(x,y)

 and f_0 = f(0,0)=0.


 3.1. Suppose that p∈ (0,1). Consider t>0 and
 a_0=(x_0,y_0)∈ Q, x_0>0, with f(x_0,y_0) =
 y_0-px_0^2=t. Note that x_0→ 0 is equivalent to
 t→ 0. The angle between tangent lines to the circle Q and
 curve f(x,y)=y-px^2=t at the point a_0 asymptotically
 equals 2(1-p)x_0 when x_0→ 0. Substituting
 y_0=px_0^2+t to the equation
 x_0^2+(y_0-1/2)^2=1/4 we obtain that
 x_0^2≍ t, x_0→ 0. Hence P_T_a_0f'(a_0)≍ x_0, x_0→ 0. From the
 other hand f(a_0)-f_0=t≍ x_0^2. Thus the exponent
 in the LPL condition equals α = 2.

 3.2. Suppose that p=1. Consider t>0 and a_0=(x_0,y_0)∈
 Q, x_0>0, with f(x_0,y_0) = y_0-x_0^2=t. The
 angle between tangent lines to the circle Q and curve
 f(x,y)=y-x^2=t at the point a_0 asymptotically equals
 x_0^3 when x_0→ 0 and x_0^4≍ t when
 x_0→ 0. Hence P_T_a_0f'(a_0)≍
 x^3_0, x_0→ 0. From the other hand
 f(a_0)-f_0=t≍ x_0^4 when x_0→ 0. Thus the
 exponent in the LPL condition equals α = 4/3.

 We conjecture that these two situations are the only possible ones for quadratic objects.

 Let A_i∈^n× n be a symmetric matrix, b_i∈^n,
i=1,2 and c∈. Suppose that the set Q is a quadric nonempty
surface, i.e. Q={ x∈^n | (x,A_1x)+(b_1,x)+c=0},
f(x)=(x,A_2x)+(b_2,x) and there exists a unique point of the
global minimum for the problem min_Qf. Then the exponent
α in the LPL condition near the global
minimum equals 2 or 4/3.




 §.§ The gradient projection algorithm on the unit sphere


Next we consider a special case when Q=S_1. In this case all projections can
be explicitly calculated.

 Suppose that f is the Lipschitz function with constant L>0,
f' is the Lipschitz function with constant L_1>0 and 0<μ<2( L_1+L).
Under LPL condition (<ref>) algorithm (<ref>) with
t=1/L_1 converges to a point of minimum x_* with
linear rate.


First, let's describe quantitative connection between the
term (I - x x^T) f'(x) of optimality condition (<ref>) and the residual
z = z(x)= L_1 x - f'(x) - (L_1 x - f'(x), x) ≥ 0.

After simple arithmetical calculations we get

    z · (L_1 x - f'(x) + (L_1 x - f'(x), x)) = (I - x x^T) f'(x)^2,

and

    z = (I - x x^T) f'(x)^2/L_1 x - f'(x) + (L_1 x - f'(x), x)≥(I - x x^T) f'(x)^2/2L_1 x - f'(x),

and calculations are well defined for any nonstationary point x, see conditions (<ref>), (<ref>).

Fix a point x_0∈ S_1∩Ł_f(β).
We have x_k+1-x_k^2=

    = L_1 x_k - f'(x_k)/ L_1 x_k - f'(x_k) -
    x_k^2 = 2 - 2  (L_1 x_k - f'(x_k), x_k)/ L_1 x_k
    - f'(x_k) = 2 z_k/ L_1 x_k - f'(x_k).


By the previous formula, (<ref>) and definition of x_k+1
by (<ref>) with t=1/L_1 the next estimate
holds

    f(x_k+1)-f(x_k)≤
    (f'(x_k),x_k+1-x_k)+L_1/2 x_k+1-x_k^2 =
    -z(x_k).

Hence

    f(x_k+1) - f(x_k) ≤ -z(x_k) ≤ -(I - x_k x_k^T) f'(x_k)^2/2L_1 x_k - f'(x_k)

and thus f(x_k)≤β implies f(x_k+1)≤ f(x_k)≤β.
Denoting φ_k = f(x_k) - f_0 and using condition
(<ref>) we get

    φ_k+1 - φ_k ≤ -μ/2L_1 x_k - f'(x_k)φ_k,

or

    φ_k+1≤(1 - μ/2L_1 x_k - f'(x_k)) φ_k,

From the latter inequality follows

    φ_k+1≤ q^k φ_0,

where q = 1 - μ/2(L_1 + max_x ∈ S_1f'(x))≤
1 - μ/2(L_1 + L)∈ (0,1).

Now prove the convergence with respect to x. Note that obvious condition q≥ 0 implies L_1 x_k - f'(x_k)≥μ / 2. Thus for δ_k=x_k+1-x_k and x_k = x_k+1 = 1 we get

    δ_k^2 = 2 z_k/ L_1 x_k - f'(x_k)≤4/μ z_k ≤4/μ(f(x_k) - f(x_k+1))
    ≤4/μφ_k≤4φ_0/μ q^k.

Hence δ_k≤√(4φ_0/μ)  q^k/2 and {x_k} is the Cauchy sequence. This  implies its convergence to a point x_* with linear rate, while inequality φ_k+1≤ q^k φ_0 and continuity of f(x) provides f(x_*)=f_0. 





 §.§ The gradient projection algorithm with the metric
projection on the tangent plane


The next version of the gradient projection algorithm uses the metric projection of the point
x_k-tf'(x_k)
on the tangent plane to the set Q={ x∈^n | g(x)=0}, g:^n→ is a C^1 function, at the point x_k. After this step we localize the next point x_k+1 on some segment and finding it
 by dividing the segment in half.

For a point x, g(x)=0, denote T_x = { v∈^n | (g'(x),v)=
0
} i.e. the tangent subspace to the surface Q at the point x∈ Q.



Assume that the function f:^n→
is the Lipschitz continuous with constant L>0
and its gradient f' is also the Lipschitz continuous with constant L_1>0.
Let g:^n→ be a continuously differentiable function and
Q = { x∈^n | g(x)=0} be a surface without edge and
a proximally smooth set with constant R>0 with g'(x) 0 for all x∈ Q. Put

    t_0 = 1/L_1+2L/R

and fix t∈ (0, 2 t_0). Let g(x_0)=0,
z=x_0-tP_T_x_0f'(x_0), p=g'(x_0)/ g'(x_0),

    {x_1}=[ z-p( R-√(R^2 -  x_0 - z^2)),
    z+p( R-√(R^2 -  x_0 - z^2))]∩ Q.

Then

    f(x_1)-f(x_0)≤ - P_T_x_0f'(x_0)^2[ t-t^2(L_1/2+L/R)].

The maximal value of the function q(t) = t-t^2(L_1/2+L/R) is
q_0 = q(t_0) = 1/2 t_0, and q(t) > 0 for all t ∈ (0, 2 t_0).


The Lemma implements following algorithm,
preferably with t = t_0.

Gradient Projection on Tangent Hyperplane (GPA2)



Step 1. Let Q satisfy Lemma <ref> condition.
Set x_0 ∈ Q, 0< t < 2 t_0, and k = 0.

Step 2. Make a step and project onto tangent hyperplane:

    z_k = x_k - t P_T_x_k f'(x_k)
,

Step 3. Find intersection of a segment and the surface (i.e. by iterative bisection of the segment)

    {x_k+1} =
    [           [
    
    z_k - g'(x_k)/g'(x_k)(R - √(R^2 - x_k - z_k^2)) .,; [3mm]
    
    . z_k + g'(x_k)/g'(x_k)(R - √(R^2 - x_k - z_k^2))
    ] ∩ Q. ]


Step 4.
Increase k and continue to the Step 2.




The maximality of q_0 is obvious. Let's prove (<ref>).
By (<ref>) the segment

    [A,B]=[ z-p( R-√(R^2 -  x_0 - z^2)),
    z+p( R-√(R^2 -  x_0 - z^2))]

has (unique) intersection x_1 with the set Q. The point x_1 can be found by
dividing the segment [A,B] in half. See Figure <ref> for details.




We have

    f(x_1)-f(x_0)= f(x_1)-f(z)+f(z)-f(x_0),

x_0-z = t P_T_x_0f'(x_0),


    x_1 - z≤ R-√(R^2 -  x_0 - z^2)≤ x_0-z^2/R = t^2 P_T_x_0f'(x_0)^2/R.


    | f(x_1)-f(z)|≤ L  x_1-z≤t^2 L/R P_T_x_0f'(x_0)^2,

and

    f(z)-f(x_0)≤ (f'(x),z-x_0)+L_1/2 z-x_0^2 =  P_T_x_0f'(x_0)^2 ( -t+L_1/2t^2).

Substituting the last inequality and (<ref>) in Formula (<ref>) we get (<ref>).

Note that if the function g in Lemma <ref> has the
Lipschitz continuous gradient with Lipschitz constant L_1 and
there exists m>0 with g'(x)≥ m for all x, g(x)=0,
then the set { x | g(x)=0} is proximally smooth with
constant R=m/L_1 <cit.>.



    Suppose that conditions of Lemma <ref> hold, t∈ (0, 2t_0), and the function f satisfies
    the LPL condition with constant μ>0 on the set Q∩Ł_f (β).
    Then the GPA2 with initial condition
    x_0∈ Q∩Ł_f(β),
    converges with linear rate to the minimum point.
    
Put φ (x) = f(x)-f_0, where f_0 = min_Q
f. From the LPL condition for the function f on the surface Q

    P_T_xf'(x)^2≥μ (f(x)-f_0)

for all x∈ Q∩Ł_f(β) by Lemma <ref> we have

    f(x_k+1)-f(x_k)≤ -q(t)μ (f(x_k)-f_0),


    φ (x_k+1)≤ (1-q(t)μ)φ (x_k).

Now consider the rate of convergence with respect to the point. By (<ref>) we get

    x_k+1-x_k^2 =  x_k-z_k^2 +  z_k-x_k+1^2 ≤ t^2 P_T_x_kf'(x_k)^2
    ( 1+ P_T_x_kf'(x_k)^2/R^2t^2).

Using (<ref>) for x_0=x_k and x_1=x_k+1 we obtain that

    x_k+1-x_k^2 ≤( 1+L^2/R^2t^2)t^2/q(t)(f(x_k)-f_0),


    x_k+1-x_k^2 ≤( 1+L^2/R^2t^2)t^2/q(t)φ (x_k) ≤( 1+L^2/R^2t^2)t^2/q(t) (1-q(t)μ)^kφ (x_0).

Due to inequalities for t, q(t) this implies x_k+1-x_k^2 ≤ cp^k, p<1. The end of the proof is standard (compare the proof of Theorem 2).




Let Q be a C^1 and proximally smooth with constant R
manifold without edge, f:^n→ be a strongly convex function (with
constant of strong convexity ϰ>0) with the Lipschitz
continuous gradient. Suppose that f is the Lipschitz function
with constant L>0 on the level set Ł_f(β) and 
L/ϰ<R.
Then the function f satisfies the LPL
condition on the set Q∩Ł_f(β). We shall give a sketch
of proof for this fact.




 By <cit.> the function f has unique minimum x_*∈
Q∩Ł_f(β). Fix a point x_0∈
Q∩Ł_f(β) and put z=x_0-τ P_T_x_0f'(x_0). Choose a positive number 
τ  from the 
conditions of Lemma <ref>,  τ less than t from <cit.> and τ≤R/2L. Then by strong convexity of the function f by <cit.>
we have linear rate of convergence for the GPA1 with step τ. From Theorem 2.3 <cit.> for
_1=P_Q(x_0-τ f'(x_0)) we get

    x_0-x_*≤∑_k=0^∞ q^k   x_0 - _1≤ x_0-_1/1-q

where q=q(τ)∈(0,1) <cit.> and q
does not depend upon x_0.

Let w=P_x_0+T_x_0_1, y=x_0-τ f'(x_0). Then from the definition of
_1 we have y-x_0≥ y-_1, thus we get the inequality w-z≤ x_0-z. By
Formula (<ref>) we obtain that _1-w≤1/R( 2
x_0-z)^2. Hence by the Pythagoras theorem

    _1-z^2 =  z-w^2 +  w-_1^2≤


    ≤ x_0-z^2+ 1/R^2( 2
    x_0-z)^4≤ x_0-z^2( 1+
    4τ^2L^2/R^2),


    x_0-x_*≤ x_0-_1/1-q≤
    x_0-z+ z-_1/1-q≤ D  x_0-z = Dτ
    P_T_x_0f'(x_0),

where D = (1+√(1+ 4τ^2L^2/R^2))/(1-q).

Suppose that f'(x_*) 0. Put p=f'(x_*)/ f'(x_*).  By the supporting
principle for proximally smooth sets

    x_*-x_0± Rp≥ R,


    (p,x_0-x_*)≤1/2R x_0-x_*^2,  
    (f'(x_*),x_0-x_*)≤ f'(x_*)/2R
    x_0-x_*^2.

In the case f'(x_*)= 0 the last formula also takes place.
From (<ref>) and (<ref>) we obtain that

    f(x_0)-f(x_*)≤ (f'(x_*),x_0-x_*)+L_1/2
    x_0-x_*^2≤ x_0-x_*^2( 
    f'(x_*)/2R+L_1/2)≤


    ≤ x_0-x_*^2( 
    L/2R+L_1/2)≤ D^2τ^2( 
    L/2R+L_1/2) P_T_x_0f'(x_0)^2.




 §.§ The gradient method combined with the Newton method on the unit sphere


Describe some symbiosis of the gradient projection algorithm and
the Newton method for finding a stationary point for the problem
min_Q f. We shall assume that f∈ C^2.

Consider again the problem with Q=S_1. Define S_1 with the
help of the function g(x) = 1/2 ( x^2-1)=0. For any x=1 define the number λ∈ as a solution of the extremal problem

    f'(x)+λ g'(x)^2→min_λ,

thus λ = -(g'(x)^Tg'(x))^-1g'(x)^Tf'(x) = - (x,f'(x)).
Denote by z the variable (x,λ)∈^n+1,

    F(z) = [[ f'(x) + λ x;        g(x) ]],
      
    F'(z) = [[ f”(x) + λ I           x;         x^T           0 ]].


Fix z=(x,≪), where x∈ S_1, ≪ = -(x,f'(x)). Define
also

    σ_1 = min_σ∈σ (F'(z)) |σ|

the minimal by absolute value element of spectrum for the matrix F'(z).

Suppose that σ_1>0 and F' is the Lipschitz continuous
with Lipschitz constant L_1>0 on the set B_r(z), where
r=2/σ_1 F(z). Then in the case

    L_1/σ_1^2√( f'(x)+ ≪ x^2 +g^2(x) )=
    L_1/σ_1^2√( f'(x)- (x,f'(x))x^2 +g^2(x)
    )<1/4

the modified Newton method starting from the point
z=(x,-(x,f'(x))) converges with super-linear rate <cit.>.

Note that P_T_xf'(x) =  f'(x)-(x,f'(x))x = 
(I-xx^T)f'(x).


    Gradient Projection — Newton Method (GPA3)

    Step 1.
    Take x_0 ∈S_1, and put C = σ_1^2/4 L_1, k = 0.

    Step 2. (GPA2 phase) While P_T_x_kf'(x_k)≥ C,
    perform Steps 2-4 of GPA2, increasing k.
    If P_T_x_kf'(x_k) < C, proceed to Step 3.

    Step 3. Put x_0=x_k, λ_0 = -(x_k,f'(x_k)),
    k=0.

    Step 4. (Newton phase) do Newton steps for equation F(z) = 0, increasing k:
    
    [                                                                                                                             [ x_k+1; λ_k+1 ]                                                                           =
        [ x_k; λ_k ]
        - F'([ x_0; λ_0 ])^-1
        F([ x_k; λ_k ]) =;                                                                                                                                              =
        [ x_k; λ_k ]
        -
        [ f”(x_0) + λ_0 I             x_0;           x_0^T               0 ]^-1[ f'(x_k) + λ_k x_k;            g(x_k) ] ]



Conditions of Lemma <ref> are satisfied at Step 2.
Thus we can do steps (<ref>) of the GPA2
and decrease the function:

    f(x_k+1)-f(x_k) ≤ - C^2 q(t).

Put Δ f = max_S_1 f - min_S_1 f. It's easy to
see that by the inequality P_T_x_kf'(x_k)≥ C we'll
switch to the Newton method at Step 4 after no more than
Δ f/C^2q(t) steps of the gradient projection
algorithm. In the case when condition (<ref>) is valid at
the point z=(x_k,-(x_k,f'(x_k))) the modified Newton
method starting from z converges with super-linear rate.





 §.§ Quadratic form


Consider homogeneous quadratic function f(x)=(Ax,x) with symmetric
real n× n matrix A. Denote by λ_k eigenvalues of
A, e_k — corresponding eigenvectors A e_k = λ_k e_k
and suppose that λ_1 < λ_2 ≤…≤λ_n.
Then f_0=λ_1, L_1= 2λ_n and two global
minimizers are ± e_1. All other eigenvectors are stationary
points, but not local minimums. Thus the problem
(<ref>) is equivalent to the problem of finding the minimal eigenvalue and
eigenvector, and algorithm (<ref>) has the form

    x_k+1 =  x_k -(2/L_1)Ax_k/ x_k -(2/L_1) Ax_k.


Probably, the first gradient-like algorithm for eigenvalue
problem has been proposed by Kantorovich <cit.>. He converted eigenvalue problem to
unconstrained minimization of Rayleigh quotient
R(x)=(Ax,x)/(x,x) and obtained the algorithm x_k+1 = 
x_k -t_k Ax_k/ x_k -t_k Ax_k where t_k was taken from 1D
minimization of R(x_k+1). One can see that this method has
the same form as (<ref>), but has more complicated
step-size rule. Kantorovich proved linear convergence of the
algorithm.

We analyse iterative process (<ref>) by use of the above presented
results. For x_0 = ∑_i=1^nα_i e_i we shall prove
convergence to +e_1 or -e_1 depending on the sign of α_1.
Suppose that α_1>0 (if α_1=0, there is no convergence
to global minimum). It is obvious that if α_1>0, the same
is true for decompositions of all iterates x_k, thus all of
them remain in the open half-sphere H={ x | (x,e_1)>0,
||x||=1}. We also introduce H_τ={ x |  (x, e_1) ≥τ,   ||x|| = 1}, for 0 < τ <1.

 Fix τ∈ (0,1). Suppose that
    λ_1 < λ_2 ≤ ... ≤λ_n are eigenvalues
    of A.
Then the quadratic function f(x) = (A x, x) satisfies the LPL condition
on the set H_τ with μ = 4 τ^2(λ_2 - λ_1),


Express any point x = ∑_i=1^nα_i e_i ∈
H_τ through the residual vector δ:
δ = x -e_1.
From τ∈ (0,1) we have 0<δ < √(2). Put C=δ^2-δ^4/4>0. Using notation y for the unit vector y =
1/√(C)[α_2, α_3, ..., α_n]^T ∈ℝ^n-1 (see (<ref>)), and B for the
diagonal matrix with strictly positive diagonal elements

    B = [ λ_2 - λ_1         0         ⋯         0;         0 λ_3 - λ_1         ⋯         0;         ⋮         ⋮         ⋱         ⋮;         0         0         ⋯ λ_n - λ_1;           ]

we have the next obvious equalities below


    1 = x^2 = ∑_i=1^nα_i^2,     δ^2 = (1 - α_1)^2 +
    ∑_i=2^nα_i^2 = 2 - 2 α_1,
    ∑_i=2^nα_i^2 = 1 -
    α_1^2 = δ^2 - δ^4/4≐
    C,     (A - λ_1 I) δ = ∑_i=2^n (λ_i -
    λ_1) α_i e_i,
    (A - λ_1 I) δ^2 = ∑_i=2^n (λ_i - λ_1)^2 α_i^2 = C B y^2,
    
    ((A - λ_1 I) δ, δ) = ∑_i=2^n (λ_i - λ_1) α_i^2 = C (B y, y), 
    
    f(x) - f_0 = (Ax, x) - λ_1 = ∑_i=1^n(λ_i - λ_1)α_i^2 =
    ∑_i=2^n(λ_i - λ_1)α_i^2 = C (By, y).

It is clear that (By, y) ≥λ_2 - λ_1 > 0.

From the equality f'(x) = 2Ax = 2A(e_1 + δ) we get

    (I - x x^T) f'(x)^2 = (I - (e_1 + δ) (e_1 + δ)^T) (2A (e_1 + δ))^2 = 
    
    = 4 (A - λ_1 I)δ
    + (e_1 + δ) (A δ - λ_1 δ, δ) ^2
    = 
    
    = 4(A - λ_1 I) δ^2 - 4 ( (A - λ_1 I)δ, δ )^2 = 
    
    = 4C B y^2 - 4 C^2 (By, y)^2 = 4 C (B y^2 - C (By, y)^2) = 
    
    = 4 C (B y^2 - (By, y)^2) + 4 C (1 - C) (By, y)^2 ≥
    ≥ 4 (1 - C) (By, y) [C (By, y)] = 4 (1 - C) (By, y) (f(x) - f_0).

By 4(1-C) = (2 - δ^2)^2 the latter expression has the form

    (I - x x^T) f'(x)^2 ≥ (2 - δ^2)^2 (λ_2 - λ_1) (f(x) - f(x^*)).

for all x∈ H_τ.
The inequality 2 - δ^2 = 2 - x - e_1^2 = 2 (x, e_1)
≥ 2 τ holds for x ∈ H_τ, and thus the LPL condition
takes place with μ = 4 τ^2(λ_2 - λ_1).



Thus for any (x_0, e_1) ≥τ we get (Ax_k, x_k) -
λ_1 ≤ ((A x_0, x_0) - λ_1) q^k, q = 1 - τ^2
λ_2 - λ_1/λ_n - λ_1 (denominator
L x_k - f'(x_k) from (<ref>) is bounded from
above by 2(λ_n - λ_1) for the quadratic function),
while asymptotically |(x_k, e_1)| → 1, and
(Ax_k,x_k)-λ_1=O (q_1^k),  q_1 = λ_n -
λ_2/λ_n - λ_1.

Condition λ_1<λ_2… can be weakened.
If λ_1=…=λ_k<λ_k+1≤…≤λ_n, then the function
f(x)=(Ax,x) also satisfies the LPL condition on the set
H_τ = { x∈ S_1 | ∑_i=1^kx_i^2≥τ^2}
 of the unit sphere S_1
 for any τ∈ (0,1)
 in the basis from eigenvectors.

x

Indeed, put z=(x_1,…,x_k), = (x_k+1,…,x_n), x=(z,).
Then

    f(x) = ∑_i=1^nλ_ix_i^2 = λ_1 z^2+
    ∑_i=k+1^nλ_ix_i^2 = h( z,).

For the function h( z,) we have the LPL condition on the set
{ z> τ} with constant μ = 4τ^2(λ_k+1-λ_1), i.e.

    4( λ_1^2z^2+∑_i=k+1^nλ_ix_i^2)≥μ (h(z,)-f_0),

or equivalently

    4( ∑_i=1^nλ_ix_i^2)≥μ (f(x)-f_0).






§ THE FRANK-WOLFE METHOD


 The Frank-Wolfe method (also known as the conditional gradient method) has been proposed for minimization of a convex quadratic
function on a convex set <cit.> and later was extended for general convex objectives, see e.g. <cit.> and recent survey <cit.>.
The idea of the method for problem (<ref>) is to solve (on each step) the
auxiliary problem

    z_k∈min_z∈ Q(f'(x_k),z),

find
t∈ [0,1] that minimizes f(x_k+t(z_k-x_k)) and take the next point
x_k+1=x_k+t(z_k-x_k).
The method requires minimization of a linear function on the admissible set at each iteration. There are also some extensions of the
method for nonconvex objective functions and for matrix optimization <cit.>.



 §.§ Minimization of an approximately linear function


However our problem (<ref>)
deals with non-convex admissible set Q. We consider a special version of the FW method for our problem as a limiting version of the
gradient projection method (<ref>). Indeed suppose that the function f(x) is approximately linear (see (<ref>) below) on the set Q=S_1, i.e., informally, constant L_1 is
small enough in comparison with other parameters.
 For this extreme case method (<ref>) turns into the next iteration process

    x_k+1 = -f'(x_k)/f'(x_k).

This is exactly the FW method with t=1: we take linearized
function f(x_k)+(f'(x_k), x-x_k), find its minimum on Q and
proceed to the minimum point. Notice that in standard versions
of the FW method we make a step in the direction of the
minimizer;  this full-step version diverges in general case.



Full-step Frank-Wolfe method (FFW)

Step 1. Take x_0 and set k = 0.

Step 2. Solve auxiliary problem

    z_k ∈min_z∈ Q(f'(x_k),z),


Step 3. Update
x_k+1 = z_k.

Step 4. Increase k and go to Step 2.


To get the rigorous validation of method (<ref>) we need
specification of the above mentioned approach.
A function f(x) defined on the ball B_1(0) with L_1-Lipschitz gradient (<ref>) is called approximately linear on S_1 if

    ||f'(0)|| > 2 L_1.



 
Suppose that (<ref>) holds. There are just two
stationary points in problem (<ref>) x_* =
min_S_1f(x), x^*=max_S_1 f(x), and
FFW method (<ref>)
converges to x_*
for arbitrary x_0∈ S_1 with linear rate

    ||x_k-x_*||≤ q^k ||x_0-x_*||,    q=
    L_1/f'(0) - L_1∈ (0,1).


Theorem <ref> is close enough to Theorem 4.3 from
<cit.> where minimization on B_1 instead of S_1 has been considered. But indeed the solutions of these two problems coincide under condition (<ref>).
The proof of Theorem <ref> follows from the following
 fact regarding strongly convex sets of radius r and
functions with the Lipschitz continuous gradient
<cit.>.

Suppose that B⊂^n is a strongly convex set of radius r
and a function f:^n→ has the Lipschitz continuous
gradient with constant L_1, m=inf_x∈Q̣f'(x) and
m/L_1>r. Then the iteration process x_0∈Ḅ,

    x_k+1=min_x∈ B(f'(x_k),x),     k=0,1,…

converges to the unique solution x_*∈Ḅ of the problem
min_B f with linear rate:

    x_k -x_*≤( rL_1/m)^k x_0 - x_*.


We shall further consider a closed surface Q in ^n which is the
boundary of some strongly convex set of radius r, i.e. Q=Ḅ.
It is worth to admit that Q is not necessary smooth.




 §.§ Another gradient domination condition



We introduce a sort of the gradient domination condition, formulated at a stationary point x_* of (1).
Assume that the next inequality

    ||f'(x_*)|| > L_1

holds. This condition reminds sharp minimum condition <cit.>.



    Let B⊂^n be a strongly convex set of radius r,
    m>1, x_*∈Ḅ. Suppose that f:^n→ is a function
    with the Lipschitz continuous gradient with constant L_1. If
    f'(x_*)∈ -N(B,x^*) and f'(x_*)≥ mrL_1 then
    x_*=min_a∈ Bf(a), i.e. x_* is the strict
    global minimum of the function f on the set B, and hence on the boundary Q=Ḅ.


Put p=f'(x_*)/ f'(x_*). Then by the
supporting principle for strongly convex sets

    B⊂ B_r(x_*+rp).

Fix a number >0 and a unit vector q such that

    x=x_*+ q∈ B_r(x_*+rp).

We claim that f(x)>f(x_*).

By Formula (<ref>)

    f(x)≥ f(x_*)+(f'(x_*),x-x_*)-L_1/2
    x-x_*^2.

From (<ref>) we get rp- q≤ r. Hence -2r
(p,q)+^2≤ 0 or /2≤ r(p,q). By inequality m>1 we obtain that

    /2≤ m r(p,q).

Further

    (f'(x_*),x-x_*) = (f'(x_*), q) ≥ m rL_1(p,q)

and x-x_*^2=^2. The last two formulae and (<ref>)
gives the next estimate

    f(x)≥ f(x_*)+  m rL_1(p,q) -
    L_1/2^2=f(x_*) +  L_1(
    mr(p,q)-/2),

and taking in mind (<ref>) we have f(x)>f(x_*). By
inclusions (<ref>), (<ref>) x_*=min_a∈ Bf(a).


    If m=1 and other assumptions of Theorem <ref> hold then
    x^* is also a global minimum of f on the set B, but this
    minimum is not necessary strict.


The particular example is given by the set B=B_1(0) and the
function f(x)=-1/2x^2.


    If in Theorem <ref> m∈ (0,1)
    and other assumptions of
    Theorem <ref> hold then x_* is a stationary point of
    the function f on the set B but not necessarily the minimum point.



Consider an example in ^2. Fix r>1, let B={ (x,y)∈
R^2 | x^2+(y+r)^2≤ r^2}=B_r((0,-r)).

Define the function ψ

    ψ (x) = {[ -1/2 x^2,   x≤ 0,;        0,   x> 0,;                   ].
        ψ' (x) = {[ -x,   x≤ 0,;   0,   x> 0;             ].

and f(x,y) = ψ (x)-y for all (x,y)∈^2.

Consider the
problem min_Bf. We have f'(x,y) = (ψ'(x),-1) and
thus f' is the Lipschitz continuous with constant L_1=1.


The point a=(0,0)∈Ḅ is a stationary point: f'(a)
=(0,-1)∈ -N(B,a), f'(a) = 1 = mrL_1 = mr, i.e.
m=1/r<1 and f(a)=0. But  a is not a local
minimum. The solution of the problem is a_0 =
(-√(r^2-1),1-r) with f(a_0) = -(r-1)^2/2.




Define the function h(θ) = 2sin(1/2arcsinθ) for θ∈ [0,1]. The function h is convex, monotonically increasing and 1/θh(θ)>1
for θ >0. By convexity of h we have for any t∈ (0,θ) that
h(t)≤1/θh(θ) t. Note that 1≤1/θh(θ)
≤√(2) if θ∈ [0,1].



For any real number m>1 define θ_m as follows

    θ_m = {[ θ,    1/θh(θ)=m  m∈ (1,√(2)],;                   1,  m>√(2). ].



    Let B⊂^n be a strongly convex set of radius r,
    m>1, x_*∈Ḅ. Suppose that f:^n→ is a function
    with the Lipschitz continuous gradient with constant L_1,
    f'(x_*)∈ -N(B,x_*) and f'(x_*)≥ mrL_1. Fix a
    point x_0∈Ḅ, x_0-x_*<
    θ mr and θ∈ (0,θ_m). Then the
    iterations
    
    x_k+1=max_x∈Ḅ(-f'(x_k),x),  
        k=0,1,…

    of FFW method converge to the point x_* with linear rate:
    
    x_k+1-x_*≤1/θh(θ)/m x_k-x_*

    for all k.


Note that by Theorem <ref> x_* is the strict global
minimum of f on the set B. Also
1/θh(θ)/m<1 due to choice of θ.

Put t_k= x_k-x_*.

From the inequality L_1t_k<
f'(x_*) (which follows by induction) and the inclusion f'(x_k)∈ B_L_1t_k(f'(x_*)) the sine of the angle φ_k
between f'(x_*) and f'(x_k) is estimated as follows

    sinφ_k ≤L_1t_k/ f'(x_*)≤t_k/mr.

Put p_k=- f'(x_k)/ f'(x_k), p_*=- f'(x_*)/ f'(x_*).
From the triangle 0p_kp_* we have p_k-p_*=2sin1/2φ_k.
By strong convexity of the set B and inequality t_k/mr<θ we obtain that

    t_k+1= x_k+1-x_*≤ r p_k-p_*=2rsin1/2φ_k ≤
    2rsin(1/2arcsint_k/mr)≤1/θh(θ)/mt_k.





    Let B⊂^n be a strongly convex set of radius r,
    m>1, β∈. Suppose that
    f:^n→ is a function with the Lipschitz continuous
    gradient with constant L_1 and for any point x∈Ḅ∩Ł_f(β)
we have the inequality  f'(x)≥ mrL_1.
    Then for any choice of the initial point x_0∈Ḅ∩Ł_f(β)
    the iterations
    
    x_k+1=max_x∈Ḅ(-f'(x_k),x),  
        k=0,1,…

    converge to the global strict minimum x_* with linear rate:
    
    x_k+2-x_k+1≤1/m x_k+1-x_k.

    for all k.


Put t_k= x_k+1-x_k and p_k=-f'(x_k)/ f'(x_k).

Suppose that f(x_i)≤β for all 0≤ i≤ k.

Prove that f(x_k+1)≤β.

    f(x_k+1)-f(x_k)≤ (f'(x_k),x_k+1-x_k)+L_1/2 x_k+1-x_k^2.

From the supporting principle for strongly convex sets

    x_k+1-rp_k - x_k <r,

or

    x_k+1-x_k^2≤ 2r(p_k, x_k+1-x_k)≤ -2/mL_1(f'(x_k), x_k+1-x_k).

Hence we obtain the next estimate

    f(x_k+1)-f(x_k)≤ -(m-1 )L_1/2 x_k+1-x_k^2,

and f(x_k+1)≤ f(x_k)≤β.


For any unit vectors p,q and numbers λ,μ≥ 1 we have p-q≤λ p - μ q. Using the last inequality and strong convexity of the set B we get

    t_k+1= x_k+2-x_k+1≤ rf'(x_k+1)/mrL_1- f'(x_k)/mrL_1≤1/mt_k.

Thus the sequence { x_k} converges, x_k→ x_*∈Ḅ.
Passing to the limit as k→∞ in the inclusion
-f'(x_k)∈ N(B,x_k+1) and using upper semicontinuity of the
normal cone we have -f'(x_*)∈ N(B,x_*), f'(x_*)≥
mrL_1. By Theorem <ref> the point x_* is the strict global
minimum. 



Consider examples that show importance of the condition m>1 in both
Theorems <ref> and <ref>.

 Suppose that f(x,y) and B are the function and the set from
Example <ref>. Notice that in this case m<1. Take a
starting point for the FFW algorithm (x_0,y_0)∈Ḅ with
x_0>0, y_0∈ (-1,0). Then f'(x_0,y_0)=(0,-1) and
one step of the FFW method leads us to the stationary point
(0,0). But extremum is the point (-√(r^2-1),1-r), see Figure <ref>.





 Consider the set Q={ (x,y)∈^2 |x^2+(y-1/2)^2=1/4}. Let f(x,y) =
y-x^2.
For the function f we have L_1=2, 1= f'(0,0)=mrL_1 =m1/2· 2=m, i.e. m=1,

    (0,0) = min_(x,y)∈ Qf(x,y)

and f_0 = f(0,0)=0. Put t>0 and a_0=(x_0,y_0)∈
Q, x_0>0, y_0∈ (0,1/2) with f(x_0,y_0) = y_0-x_0^2=t. As we've seen at
subsection <ref> the
angle between tangent lines to the circle Q and curve
f(x,y)=y-x^2=t at the point a_0 asymptotically equals
x_0^3 when x_0→ 0.
Starting the FFW algorithm from the point
a_0 we obtain the next point a_1(x_1,y_1). We have
x_0^3≍ a_0-a_1≍ | x_0-x_1| when x_0→ 0. The
last means that

    ∃δ>0  ∃ C>0 ∀ x_0∈ (0,δ) |
    x_0-x_1|<Cx_0^3.

Thus for any sufficiently small x_0>0 we get x_1≥
x_0-Cx_0^3. There is no linear rate of convergence.











§ APPENDIX




    Suppose that the set Q⊂^n is proximally smooth with
    constant R>0, the function f has the Lipschitz continuous
    gradient f' with constant L_1>0 and the point x_0 is a local
    minimum in the problem min_Qf.
    Then -f'(x_0)∈ N(Q,x_0).


If f'(x_0)=0 then -f'(x_0)=0∈ N(Q,x_0) by the definition of normal cone.

Assume that f'(x_0) 0.
Prove the proposition by contradiction.
Put p=-f'(x_0)/f'(x_0).
Suppose that p∉ N(Q,x_0). Then by the
supporting principle for a proximally smooth set we have

    ∃ x_1∈ Q∩ı B_R(x_0+Rp).


For a set B define by D_RB the intersection of all closed balls of radius
R each of which contains the set B. From <cit.> there exists a continuous curve Γ⊂ Q with endpoints x_0
and x_1 such that Γ⊂
D_R{x_1,x_0}⊂{ x_0}∪ı B_R(x_0+Rp). By the inclusion x_1∈ı
B_R(x_0+Rp) there exists δ>0 with
B_δ(x_1)⊂ı B_R(x_0+Rp),

    D_R{x_1,x_0}⊂ D_R(B_δ(x_1)∪{x_0}).

Let L be a 2-dimensional plane, { x_0,x_1}⊂ L.
Choose a point x∈Γ, x-x_0=, x=x_0+ q,
q=1. The angle φ between arcs L∩Ḍ_R{x_1,x_0} and L∩Ḍ_R(B_δ(x_1)∪{x_0}) at the point x_0 (see Figure <ref>)
is strictly positive
and hence the angle between p and q is less than π/2-φ∈
(0,π/2). Thus there exists C= cos( π/2-φ)>0 (that does not depend on vector q)
with (p,q)>C.



By Formula (<ref>)

    f(x) - f(x_0)≤ (f'(x_0),x-x_0)+L_1/2
    x-x_0^2

and

    (f'(x_0),x-x_0) = (f'(x_0), q) = -  f'(x_0)
    (p,q).

Hence

    f(x) - f(x_0)≤ -  f'(x_0) (p,q) +
    L_1/2^2≤ -  f'(x_0) C +
    L_1/2^2<0

for sufficiently small >0. A contradiction.



§ ACKNOWLEDGEMENTS


The work was supported by Russian Science Foundation (Project 16-11-10015).

10

Absil-2008
P.-A. Absil, R. Mahony, R. Sepulchre,
Optimization Algorithms on Matrix Manifolds,
Princeton University Press, Princeton and Oxford, 2008.

Balashov12
M. V. Balashov,
Uniformly convex subsets of the Hilbert space with modulus of convexity of the second order,
Journal of Math. Anal. Appl.,
377:2 (2011), 754–761.

Balashov2015
M. V. Balashov,
Maximization of a function with Lipschitz continuous gradient,
Journal of Mathematical Sciences,
209:1, (2015), 12–18.


Balashov2017

M. V. Balashov,
About the gradient projection algorithm for a strongly convex function and a proximally smooth set,
Journal of Convex Analysis,
24:2, (2017), 493–500.

PBMsb
M. V. Balashov, E. S. Polovinkin,
M-strongly convex subsets and their generating sets,
Sbornik: Mathematics,
191:1 (2000), 25–60.

BI
M. V. Balashov, G. E. Ivanov,
Weakly convex and proximally smooth sets in Banach spaces,
Izv. RAN. Ser. Mat.,
73:3 (2009), 23–66.

Bertsekas
D. Bertsekas,
Mathematical Programming,
Athena-Publishing, 2013.

Boyd
S. Boyd, L. Vanderberghe,
Convex Optimization,
Cambridge University Press, 2004.


Clarke1
F. H. Clarke, Yu. S. Ledyaev, R. J. Stern, P. R. Wolenski,
Nonsmooth Analysis and Control Theory,
Springer-Verlag New-York Inc., 1998.

Clarke
F. H. Clarke, R. J. Stern, P. R. Wolenski,
Proximal smoothness and lower–C^2 property,
J. Convex Anal.,
2:1-2 (1995), 117–144.

trust-region
A. R. Conn, N. I. M. Gould, Ph. L. Toint,
Trust-Region Methods,
SIAM,
Philadelphia, 2000.

Nesterov

C. Fraikin, Yu. Nesterov, P. Van Dooren,
A gradient-type algorithm optimizing the coupling between matrices,
Linear Algebra and its Applications,
429 (2008), 1229–1242.

Ferreira-on-sphere-2014
O. P. Ferreira, A. N. Iusem, and S. Z. Németh,
Concepts and techniques of optimization on the sphere,
TOP,
22:3 (2014), 1148–1170.

FW_1
R. M. Freund, P. Grigas,
New analysis and results for the Frank-Wolfe method,
Mathem. Progr.,
155:1-2 (2016), 199–230.

FW
M. Frank, Ph. Wolfe,
Algorithm for quadratic programming,
Nav. Res. Log. Quart.,
3:1-2 (1956), 95–110.

Hager
W. W. Hager,
Minimizing a quadratic over a sphere,
SIAM J. Optim. and Contr.,
12:1 (2001), 188–208.

gao-etal-exponent-2016

B. Gao, X. Liu, X. Chen, Ya. Yuan,
On the Lojasiewicz exponent of the quadratic sphere constrained optimization problem,

(2016), arXiv:1611.08781v2


Goldstein
A. A. Goldstein,
Convex programming in Hilbert space,
Bull. Amer. Math. Soc.,
70:5 (1964), 709-710.

Karimi
H. Karimi, J. Nutini, M. Schmidt,
Linear convergence of gradient and proximal-gradient methods under the Polyak-Lojasiewicz
condition.
In: Frasconi P., Landwehr N., Manco G., Vreeken J. (eds)
Machine Learning and Knowledge Discovery in Databases.
Lecture Notes in Computer Science, vol 9851.
Springer, 2016.

Kantorovich
L. V. Kantorovich,
Functional analysis and applied mathematics,
Russ. Math. Surveys,
3:6(28) (1948), 89–185.

KF
A. N. Kolmogorov, S. V. Fomin,
Elements of the Theory of Functions and Functional Analysis,
Dover Publications, 1999.


PolykLevitin
E. S. Levitin, B. T. Polyak,
Constrained minimization methods,

USSR Comp. Math. and Math. Phys.,
6:5 (1966), 787–823.

Lez0
T. Ležanski,
Über das Minimumproblem von Funktionalen in Banachschen Räumen,
Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys.,
10 (1962), 107–110.

Lez
T. Ležanski,
Über das Minimumproblem für Funktionale in Banachschen Räumen,
Mathematische Annalen,
152 (1963), 271–274.

L
D. G. Luenberger,
The gradient projection methods along geodesics,
Management Science,
18:11 (1972), 620–631.

Lacoste-2016

S. Lacoste-Julien,
Convergence rate of Frank-Wolfe for non-convex objectives,
(2016), arXiv:1607.00345


Lojasiewicz
S. Lojasiewicz,
Une propriet e topologique des sous-ensembles analytiques reels,
Les Equations aux Derivees Partielles,
CNRS, Paris,
(1963), 87–89.

Neto
J.X. da Cruz Neto, L. L. De Lima, P. R. Oliveira,
Geodesic algorithms on Riemannian manifolds,
Balkan J. of Geom. and its Appl.,
3:2 (1998), 89–100.

Nesterov1
Yu. Nesterov,


Lectures on Convex Optimization,
Springer, 2018.

NesterovNemir
Yu. Nesterov, A. Nemirovski
Interior-point Polynomial Algorithms in Convex Programming,
SIAM, 1994.

Polyak_book
B. T. Polyak,
Introduction to Optimization.
New York, Optimization Software, 1987.


Polyak2001
B. T. Polyak,
Local programming,
USSR Computational Mathematics and Mathematical Phys.
41:9 (2001), 1259–1266.

Polyak-63
B. T. Polyak,
Gradient Methods for the minimization of functionals,
USSR Comp. Math. and Math. Phys.,
3:4 (1963), 643–653.

Polyak66
B. T. Polyak,
Existence theorems and convergence of minimizing sequences for extremal problems with constraints,

Soviet Math. Dokl.,

1966, 7, 72–75.

Udriste
C. Udrişte,
Convex Functions and Optimization Methods on Riemannian Manifolds,
Mathematics and Its Applications series, vol. 297,
Springer, 1994.




Vial
J.-Ph. Vial,
Strong and weak convexity of sets and functions,
Mathematics of Operations Research,
8:2 (1983), 231–259.

Weber-Sra-



M. Weber, S. Sra,
Riemannian Frank-Wolfe with application to the geometric mean of positive definite matrices,
(2018), arXiv:1710.10770v2






