A note on the generalised Hessian of the least squares associated with systems of linear inequalities
M. V. Dolgopolik


Mapping Incidence and Prevalence Peak Data for SIR Forecasting Applications
    [
    
===========================================================================




The goal of this note is to point out an erroneous formula for the generalised Hessian of the least squares associated
with a system of linear inequalities, that was given in the paper “A finite Newton method for classification” by O.L.
Mangasarian (Optim. Methods Softw. 17: 913–929, 2002) and reproduced multiple times in other publications. We also
provide sufficient contiditions for the validity of Mangasarian's formula and show that Slater's condition 
guarantees that some particular elements from the set defined by Mangasarian belong to the generalised Hessian of 
the corresponding function.






§ INTRODUCTION




The generalised Jacobian of a locally Lipschitz continuous function F ℝ^n →ℝ^m is defined
as

    ∂ F(x) = { A ∈ℝ^m × n| 
      ∃{ x_n }⊂ D_F lim_n →∞ x_n = x,
       lim_n →∞ J F(x_n) = A },

where D_F is the set of points at which F is differentiable and JF(x_n) is the classical Jacobian of F at x_n 
(see <cit.> for more details). The generalised Jacobian is a nonempty compact convex set. In turn, the
generalised Hessian <cit.> of a continuously differentiable function 
f ℝ^n →ℝ with locally Lipschitz continuous gradient is defined as the generalised Jacobian
of the gradient of f (see <cit.>) and is denoted by ∂^2 f(x). The generalised 
Hessian is a nonempty compact convex set of symmetric matrices.

In <cit.>, the generalised Hessian of the function f(x) = 0.5  (Ax - b)_+ ^2 associated with the
system of linear inequalities

    A x ≤ b

with some A ∈ℝ^m × n and b ∈ℝ^m was considered. Here · is the Euclidean
norm and (x)_+ is a vector with components max{ 0, x_i }. In <cit.>, it was claimed
that 

    ∂^2 f(x) = A^T ((Ax - b)_*) A   ∀ x ∈ℝ^n,

where

    [(y)_*]_i = 
        1,    if  y_i > 0,
        
    
        [0, 1],    if  y_i = 0,
        
    
        0,    if  y_i < 0,
        ∀ y ∈ℝ^m,

without any assumptions on the matrix A. Formula (<ref>) has been reproduced and used in
multiple publications (see, e.g. <cit.>).
In many other articles (see, e.g. <cit.>), the following
corollary to formula (<ref>) was used without any assumptions on the matrix A:

    A^T D_±(x) A ∈∂^2 f(x)	  ∀ x ∈ℝ^n,

where D_+(x) and D_-(x) are diagonal matrices such that

    D_+(x)_ii = 
        1,    if ⟨ A_i, x ⟩ > b_i,
        
    
        0,    if ⟨ A_i, x ⟩≤ b_i,
        
      D_-(x)_ii = 
        1,    if ⟨ A_i, x ⟩≥ b_i,
        
    
        0,    if ⟨ A_i, x ⟩ < b_i

for all i ∈{ 1, …, m }.

The aim of this note is to show that neither equality (<ref>) nor inclusion
(<ref>) hold true in the general case and provide sufficient conditions for these formulas to be
valid.





§ A COUNTEREXAMPLE




Let us provide a simple counterexample to (<ref>) and (<ref>). Let 
n = m = 2. Consider the following system of linear inequalities:

    x_1 ≤ 0,    - x_1 ≤ 0.

In this case A = ( [  1  0; -1  0 ]), 
b = ( [ 0; 0 ]). Hence

    f(x) = 1/2 (Ax - b)_+ ^2 = 1/2( max{ x_1, 0 }^2 + max{ - x_1, 0 })^2 
      = 1/2 x_1^2,

which implies that

    ∇ f(x) = [ x_1;   0 ],   ∇^2 f(x) = [ 1 0; 0 0 ]  ∀ x ∈ℝ^2,

that is, the function f is twice continuously differentiable. Therefore, in particular, 
∂^2 f(x) = ∇^2 f(x) for all x ∈ℝ^2.

One the other hand, for any x ∈ℝ^2 such that x_1 = 0 one has

    A^T ((Ax - b)_*) A = [  1 -1;  0  0 ][ [0, 1]      0;      0 [0, 1] ][  1  0; -1  0 ]   = [ [0, 2]      0;      0      0 ]
       ∇^2 f(x)


    A^T D_+(x) A = [  1 -1;  0  0 ][ 0 0; 0 0 ][  1  0; -1  0 ] = [ 0 0; 0 0 ]∇^2 f(x),
      
       A^T D_-(x) A = [  1 -1;  0  0 ][ 1 0; 0 1 ][  1  0; -1  0 ] = [ 2 0; 0 0 ]∇^2 f(x).

Thus, formulas (<ref>) and (<ref>) do not hold true in the general case.





§ SUFFICIENT CONDITIONS




Let us provide sufficient conditions for (<ref>) and (<ref>) to be valid.
Denote 

    I_0(x)    = { i ∈{ 1, …, m }| ⟨ A_i, x ⟩ = b_i }, 
      
    
      I_+(x)    = { i ∈{ 1, …, m }| ⟨ A_i, x ⟩ > b_i }, 
      
    
      I_-(x)    = { i ∈{ 1, …, m }| ⟨ A_i, x ⟩ < b_i },

where A_i are the rows of the matrix A written as column vectors, that is, A^T = (A_1, …, A_m).

As usual, we say that Slater's condition holds true, if there exists x∈ℝ^n such that 
A x < b (i.e. ⟨ A_i, x ⟩ < b_i for all i ∈{ 1, …, m }). As is well-known and easy
to check, Slater's conditions is equivalent to the assumption that the solution set of the system of linear inequalities
(<ref>) has nonempty interior.

 
Let Slater's condition hold true. Then for any x ∈ℝ^n one has A^T D_±(x) A ∈∂^2 f(x).



If I_0(x) = ∅, then

    f(y) = 1/2∑_i ∈ I_+(x)( ⟨ A_i, y ⟩ - b_i )^2

for any y in a sufficiently small neighbourhood of x. Consequenlty, f is twice continuously differentiable at x
and the claim of the proposition can be readily verified directly.

Suppose now that I_0(x) ∅. Choose any sequence { t_n }⊂ (0, + ∞) converging to zero and
denote
y_n = (1 - t_n) x + t_n x, where x is from Slater's condition. Then 

    ⟨ A_i, y_n ⟩ - b_i 
      = (1 - t_n) (⟨ A_i, x ⟩ - b_i) + t_n (⟨ A_i, x⟩ - b_i).

Therefore, ⟨ A_i, y_n ⟩ < b_i for all n ∈ℕ and i ∈ I_0(x) ∪ I_-(x), while for any 
i ∈ I_+(x) there exists n_i ∈ℕ such that ⟨ A_i, y_n ⟩ > b_i for any n ≥ n_i. Hence
for any n ≥ n^* := max_i ∈ I_+(x) n_i there exists a neighbourhood 𝒰(y_n) of y_n such that

    f(y) = 1/2∑_i ∈ I_+(x)( ⟨ A_i, y ⟩ - b_i )^2 
        ∀ y ∈𝒰(y_n),

which implies that f is twice continuously differentiable at y_n and ∇^2 f(y_n) = A^T D_+(x) A. Passing to
the limit as n →∞ one obtains that A^T D_+(x) A ∈∂^2 f(x).

Define z_n = x + t_n(x - x). Note that

    ⟨ A_i, z_n ⟩ - b_i = ( ⟨ A_i, x ⟩ - b_i ) 
      + t_n ( ⟨ A_i, x ⟩ - b_i - (⟨ A_i, x⟩ - b_i ) )

Hence taking into account the facts that ⟨ A_i, x⟩ - b_i < 0 and the sequence { t_n }
converges to zero one can conclude that ⟨ A_i, z_n ⟩ - b_i > 0 for any i ∈ I_0(x) and 
n ∈ℕ, and there exists n^* such that 

    ⟨ A_i, z_n ⟩ - b_i 
        > 0,    if  i ∈ I_+(x), 
        
    
        < 0,    if  i ∈ I_-(x)
        ∀ n ≥ n^*.

Therefore, for any n ≥ n^* there exists a neighbourhood 𝒰(z_n) of z_n such that

    f(y) = 1/2∑_i ∈ I_+(x) ∪ I_0(x)( ⟨ A_i, y ⟩ - b_i )^2   ∀ y
    ∈𝒰(z_n).

Consequently, f is twice continuously differentiable at z_n for any n ≥ n^* and 
∇^2 f(z_n) = A^T D_-(x) A. Now, passing to the limit as n →∞ one can conclude that 
A^T D_-(x) A ∈∂^2 f(x).


As the following example demonstrates, Slater's conditions by itself is not sufficient for equality
(<ref>) to hold true.


Let n = 2 and m = 3. Consider the following system of linear inequalities:

    x_1 ≤ 0,    x_2 ≤ 0,    x_1 + x_2 ≤ 0.

In this case

    A = ( [ 1 0; 0 1; 1 1 ]),    b = 0.

and Slater's condition holds true with x = (-1, -1)^T. Note that

    f(x)    = 1/2( max{ x_1, 0 }^2 + max{ x_2, 0 }^2 + max{ x_1 + x_2, 0 }^2 ), 
      
    ∇ f(x)    = [ max{ x_1, 0 } + max{ x_1 + x_2, 0 }; max{ x_2, 0 } + max{ x_1 + x_2, 0 } ]

One can readily verify that f is twice differentiable if and only if x_1  0, x_2  0, and x_1 + x_2  0.
Moreover, one has

    ∇^2 f(x) = 𝕆_2 × 2,    if  x_1 < 0  and  x_2 < 0
        
    ( [ 0 0; 0 1 ]), 
            if  x_1 < 0  and  x_2 > 0  and  x_1 + x_2 < 0
        
    ( [ 1 1; 1 2 ]), 
          if  x_1 < 0  and  x_2 > 0  and  x_1 + x_2 > 0
        
    ( [ 1 0; 0 0 ]), 
          if  x_1 > 0  and  x_2 < 0  and  x_1 + x_2 < 0
        
    ( [ 2 1; 1 1 ]), 
          if  x_1 > 0  and  x_2 < 0  and  x_1 + x_2 > 0
        
    ( [ 2 1; 1 2 ]), 
         if  x_1 > 0   and  x_2 > 0,
 
where 𝕆_2 × 2 is the zero matrix of dimension 2 × 2. Therefore

    ∂^2 f(0) = {𝕆_2 × 2, 
      ( [ 0 0; 0 1 ]),
      ( [ 1 1; 1 2 ]), 
      ( [ 1 0; 0 0 ]),
      ( [ 2 1; 1 1 ]), 
      ( [ 2 1; 1 2 ])
      }.

On the other hand, note that for x = 0 one has (Ax - b)_* = ([0, 1], [0, 1], [0, 1])^T and for 
y = (0, 0, 1)^T ∈ (Ax - b)_* one has

    A^T (y) A = [ 1 0 1; 0 1 1 ][ 0 0 0; 0 0 0; 0 0 1 ][ 1 0; 0 1; 1 1 ] = [ 1 1; 1 1 ].

However, A^T (y) A ∉∂^2 f(0), since otherwise one could find α_i ≥ 0, 
i ∈{ 1, …, 6 }, such that α_1 + … + α_6 = 1 and

    α_2 [ 0 0; 0 1 ]
      + α_3 [ 1 1; 1 2 ]
      + α_4 [ 1 0; 0 0 ]
      + α_5 [ 2 1; 1 1 ]
      + α_6 [ 2 1; 1 2 ]
      = [ 1 1; 1 1 ]

or, equivalently,

    α_3 + α_4 + 2 α_5 + 2 α_6 = 1
        
    α_3 + α_5 + α_6 = 1
        
    α_2 + 2 α_3 + α_5 + 2 α_6 = 1.

Subtracting the second equation from the first one one gets α_4 + α_5 + α_6 = 0, which due to the
nonnegativity of α_i implies that α_4 = α_5 = α_6 = 0. Hence with the use of the second equation
we get α_3 = 1, and taking into account the third equation we obtain α_2 + 2 = 1, which is impossible.
Thus, equality (<ref>) does not hold true for the system of linear inequalities
(<ref>), despite the fact that it satisfies Slater's condition.


Note that in the previous example the vectors A_i, i ∈ I_0(x), are linearly dependent. Our aim is to show that
equality (<ref>) holds true, provided these vectors are linearly independent. First we show that
equality (<ref>) is satisfied as inclusion “⊆” in the general case and then prove that
the opposite inclusion holds true under the linear independence assumption.

 
For any x ∈ℝ^n one has ∂^2 f(x) ⊆ A^T ((Ax - b)_*) A.



Observe that ∇ f(x) = (f'_x_1(x), …, f'_x_n(x))^T with

    f'_x_j(x) = ∑_i = 1^m a_ijmax{⟨ A_i, x ⟩ - b_i ⟩, 0 },

where a_ij are the elements of the matrix A. As is easily seen, for any locally Lipschitz continuous function 
F = (F_1, …, F_n)^T one has 

    ∂ F(·) ⊆( [ ∂ F_1(·);        ⋮; ∂ F_n(·) ]).

Therefore

    ∂^2 f(·) ⊆( [ ∂ f'_x_1(·)^T;             ⋮; ∂ f'_x_n(·)^T ]).

With the use of standard calculus rules for the Clarke subdifferential <cit.> one gets

    ∂ f'_x_j(x) ⊆∑_i ∈ I_+(x) a_ij A_i + ∑_i ∈ I_0(x) a_ij{ 0, A_i }.

Hence taking into account the fact the transposed right-hand side of this inclusion is equal to the j-th row of the
matrix A^T ((Ax - b)_*) A we arrive at the required result.


Denote by |I| the cardinality of a set I.


Let |I_0(x)| ≤ n and the vectors A_i, i ∈ I_0(x), be linearly independent for some x ∈ℝ^n. Then
∂^2 f(x) = A^T ((Ax - b)_*) A.



If I_0(x) = ∅, then the claim of the proposition can be readily verified directly (see the proof of
Proposition <ref>). Therefore, suppose that I_0(x) ∅.

Let V ⊆{ 0, 1 }^m be the set of all those vectors v for which v_i = 1 for any i ∈ I_+(x) and 
v_i = 0 for any i ∈ I_-(x). Note that V is the set of all extreme points of the set (Ax - b)_*. Let us show
that A^T (v) A ∈∂^2 f(x) for any v ∈ V. Then thanks to the convexity of the generalised Hessian and
the fact that (Ax - b)_* =  V one can conclude that

    A^T ((Ax - b)_*) A = { A^T (v) A | v ∈ V }⊆∂^2 f(x),

which along with Lemma <ref> implies the required result.

Fix any v ∈ V. From the fact that the vectors A_i, i ∈ I_0(x), are linearly independent it follows that there
exists y ∈ℝ^n such that

    ⟨ A_i, y ⟩ = 
        1,    if  v_i = 1,
        
    
        -1,    if  v_i = 0
        ∀ i ∈ I_0(x).

Choose any sequence { t_n }⊂ (0, + ∞) converging to zero and denote x_n = x + t_n y. Then there exists
n_0 ∈ℕ such that for any n ≥ n_0 one has

    ⟨ A_i, x_n ⟩ = ⟨ A_i, x ⟩ + t_n ⟨ A_i, y ⟩
        > b_i,    if  i ∈ I_+(x)  or  (i ∈ I_0(x)  and  v_i = 1),
        
    
        < b_i,    if  i ∈ I_-(x)  or  (i ∈ I_0(x)  and  v_i = 0).

Clearly, for any such n there exists a neighbourhood 𝒰(x_n) of x_n such that

    f(y) = ∑_i ∈ I_+(x) ∪{ i ∈ I_0(x)  v_i = 1 } (⟨ A_i, y ⟩ - b_i)^2 
        ∀ y ∈𝒰(x_n).

Therefore, for any n ≥ n_0 the function f is twice continuously differentiable at x_n and, as is easily seen,
∇^2 f(x_n) = A^T (v) A. Passing to the limit as n →∞ one gets that 
A^T (v) A ∈∂^2 f(x), which completes the proof.






§ ACKNOWLEDGEMENTS




The author is sincerely grateful to professor V.N. Malozemov for drawing the author's attention to paper
<cit.>, during a careful examination of which the author made the observations presented in this note.



abbrv  



