Study notes for “A constructive approach to strengthen algebraic descriptions of function and
operator classes” by Rubbens, Hendrickx, and Taylor
Shuvomoy Das Gupta
May 30, 2025
Study notes for the recent paper [
1
], which I really enjoyed reading. The study note here works out couple of examples in the paper to
1
Anne Rubbens, Julien M. Hendrickx, and
Adrien Taylor. "A constructive approach
to strengthen algebraic descriptions of
function and operator classes." arXiv
preprint arXiv:2504.14377 (2025).
get a feel for the core methodology. I highly recommend the paper anyone interested in this area.
Contents
1 Smooth convex functions 1
2 Smooth functions satisfying a Lojasiewicz condition 1
1 Smooth convex functions
Three alternative characterizations. Three alternative characterizations of smooth convex functions are:
1.
(1)
2.
(2)
3.
(3)
One-point strengthening of an inequality. Let
and R
. Let us denote the pairwise
one-point strengthening of
in (2) with respect to R
, by
, which satisfies
where
maximize
R
minimize
R
R
R
subject to
▷ now drop the scond and third cosntraints of the inne problem
maximize
R
minimize
R
R
R
subject to
▷ dual
▷ dual
▷ note that the relaxation does not contain any term containing
so one less variable
(A)
Construct the Lagrangian of the inner minimization problem:
and the associated dual function:
inf
if
and
else
Hence, we have the following dual problem to the relaxed inner minimization problem:
maximize
subject to
using which and weak duality (dual maximization problem is a lower bound to primal minimization problem) we have the
following:
maximize
R
maximize
subject to
(B)
Next note that any feasible solution to the inner maximization problem will be its lower bound (by definition any feasible
solution to a maximization problem will lead to an objective value that is less than or equal to its maximum objective value).
We consider the following feasible solution
and
which satisfies both the equality constraints and
also the sign constraints in the last inner maximization problem. For this feasible solution, the objective then becomes:
and putting this lower bound in (B) we get:
maximize
R
now notice this last maximization problem is maximizing a concave function, which would have the optimal at:
with the optimal value being
maximize
R
C
From (A), (B), and (C) we have the following (relaxed) one-point strengthening of
:
To write it more cleanly:
2 Smooth functions satisfying a Lojasiewicz condition
We consider -smooth functions satisfying quadratic Lojasiewicz condition characterized by following inequalities:
Loja
(4)
▷ without loss of generality we can set
Let
and R
. Let us denote the pairwise one-point strengthening of
Loja
in 4
with respect to the set R
, by
Loja
which satisfies
Loja
and
Loja
maximize
R
minimize
R
R
R
subject to
maximize
R
minimize
R
R
R
subject to
▷ dual
▷ dual
▷ dual
▷ dual
(5)
Here the simplifications for the first two constraints of the inner minimization problem can also be verified using Mathematica
as follows.
1
2 (*Constraint 1*)
3 term1 = fz -
4 fi + (1/2)*(gz + gi) (xi - z) - (L/
5 4)*(z - xi)^2 + (1/(4 L))*(gz - gi)^2 - τ;
6
7 term1Simp = Collect[Expand[term1], {τ, gz, fz}, FullSimplify]
8
9 (*Output of term1Simp
10 fz + gz^2/(4 L) + (gi^2 - L (4 fi + L (xi - z)^2) + 2 gi L (xi - z))/(
11 4 L) - (gz (gi - L xi + L z))/(2 L) - τ
12 *)
13
14 (*Constraint 2*)
15
16 term2 = fi -
17 fz + (1/2)*(gi + gz) (z - xi) - (L/
18 4)*(z - xi)^2 + (1/(4 L))*(gz - gi)^2 - τ;
19
20
21 term2Simp = Collect[Expand[term2], {τ, gz, fz}, Simplify]
22
23 (*Output of term2Simp
24 -fz + gz^2/(4 L) - (gz (gi + L xi - L z))/(2 L) + (
25 gi^2 - L (-4 fi + L (xi - z)^2) + 2 gi L (-xi + z))/(4 L) - τ
26 *)
The Lagrangian of the inner minimization problem of (5) is as follows:
/* free terms */
/* terms containing */
/* terms contianing
*/
/* terms contaianing
*/
which will be convex in
if we have the condition
which will become a constraint in the dual. Now, the dual function of the inner minimization problem will be:
inf
which will be achieved at:
/* otherwise we can jut minimize to by minimizing */
and
/* otherwise we can jut minimize to by minimizing
*/
and Recall that the minimizer of
is
with
.
with the optimal value being:
and the condition to prevent division by zero:
Thus the dual to the inner maximization problem is:
maximize
subject to
Thus assuming strong duality and using the dual problem above, we can write (5) as:
maximize
R
subject to
using which and weak duality (dual maximization problem is a lower bound to primal minimization problem) we have the
following for (5) :
Loja
maximize
R
maximize
R
subject to
maximize
R
subject to
(6)
So, any feasible solution to (6) would correspond to a relaxed 2-point strengthening (4). To that goal, we can proceed in the
same manner as in the previous section, though there does not seem to be one simple feasible analytical solution in this case.
