arXiv:1611.00507v1 [cs.DS] 2 Nov 2016

Worst Case Competitive Analysis of Online
Algorithms for Conic Optimization

Reza Eghbali
Department of Electrical Engineering
University of Washington
Seattle, WA 98195
eghbali@uw.edu

Maryam Fazel
Department of Electrical Engineering
University of Washington
Seattle, WA 98195
mfazel@uw.edu

Abstract
Online optimization covers problems such as online resource allocation, online
bipartite matching, adwords (a central problem in e-commerce and advertising),
and adwords with separable concave returns. We analyze the worst case competitive
ratio of two primal-dual algorithms for a class of online convex (conic) optimization
problems that contains the previous examples as special cases defined on the
positive orthant. We derive a sufficient condition on the objective function that
guarantees a constant worst case competitive ratio (greater than or equal to 12 ) for
monotone objective functions. We provide new examples of online problems on
the positive orthant and the positive semidefinite cone that satisfy the sufficient
condition. We show how smoothing can improve the competitive ratio of these
algorithms, and in particular for separable functions, we show that the optimal
smoothing can be derived by solving a convex optimization problem. This result
allows us to directly optimize the competitive ratio bound over a class of smoothing
functions, and hence design effective smoothing customized for a given cost
function.

1

Introduction

Given a proper convex cone K ⊂ Rn , let ψ : K 7→ R be an upper semi-continuous concave function.
Consider the optimization problem
!
m
X
maximize ψ
At x t
(1)
t=1

subject to xt ∈ Ft ,

∀t ∈ [m],

where for all t ∈ [m] := {1, 2, . . . , m}, xt ∈ Rk are the optimization variables and Ft are compact
convex constraint sets. We assume At ∈ Rn×k maps Ft to K; for example, when K = Rn+ and
Ft ⊂ Rk+ , this assumption is satisfied if At has nonnegative entries. We consider problem (1) in the
online setting, where it can be viewed as a sequential game between a player (online algorithm) and
an adversary. At each step t, the adversary reveals At , Ft and the algorithm chooses x̂t ∈ Ft . The
performance of the algorithm is measured by its competitive ratio, i.e., the ratio of objective value at
x̂1 , . . . , x̂m to the offline optimum.
Problem (1) covers (convex relaxations of) various online combinatorial problems including online
bipartite matching [25], the “adwords” problem [31], and the secretary problem [27]. More generally,
it covers online linear programming (LP) [9], online packing/covering with convex cost [4, 7, 11],

and generalization of adwords [13]. Online LP is an important example on the positive orthant:
maximize
subject to

m
X

cTt xt

t=1
m
X

Bt xt ≤ b

t=1
T

1 xt ≤ 1, xt ∈ Rk+ ,

∀t ∈ [m].

Here Ft = {x ∈ Rk+ | 1T x ≤ 1}, ATt = [ct , BtT ] and ψ(u, v) = u + I{·≤b} (v) where I{·≤b} (v) is
the concave indicator function of the set {v ≤ b}.
The competitive performance of online algorithms has been studied mainly under the worst-case
model (e.g., in [31]) or stochastic models (e.g., in [27]). In the worst-case model one is interested
in lower bounds on the competitive ratio that hold for any (A1 , F1 ), . . . , (Am , Fm ). In stochastic
models, adversary chooses a probability distribution from a family of distributions to generate
(A1 , F1 ), . . . , (Am , Fm ), and the competitive ratio is calculated using the expected value of the
algorithm’s objective value. The two most studied stochastic models are random permutation and i.i.d.
models. In the random permutation model the adversary is limited to choose distributions that are
invariant under random permutation while in the i.i.d. model (A1 , F1 ), . . . , (Am , Fm ) are required
to be independent and identically distributed. Note that the worst case model can also be viewed as
an stochastic model if one allows distributions with singleton support.
Online bipartite matching, and its generalization the “adwords” problem, are two main examples that
have been studied under the worst case model. The greedy algorithm achieves a competitive ratio of
1/2 while the optimal algorithm achieves a competitive ratio of 1 − 1/e as bid to budget ratio goes
to zero [31, 8, 25, 23]. A more general version of adwords in which each agent (advertiser) has a
concave cost has been studied in [13]. On the other hand, secretary problem and its generalizations are
stated for random permutation model since the worst case competitive ratio of any online algorithm
can be arbitrary small [5, 27]. The convex relaxation of the online secretary problem is a simple linear
program (LP) with one constraint. Therefore, the competitive ratio of online algorithms for LP has
either been analyzed under random permutation or i.i.d models [3, 16, 14, 20, 26] or under the worst
case model with further restrictions on the problem data [9]. Several authors have also proposed
algorithms for adwords and bipartite matching problems under stochastic models which have a better
competitive ratio than the competitive ratio under the worst case model [29, 24, 17, 30, 21, 12].
The majority of algorithms proposed for the problems mentioned above rely on a primal-dual
framework [8, 9, 4, 13, 7]. The differentiating point among the algorithms is the method of updating
the dual variable at each step, since once the dual variable is updated the primal variable can be
assigned using a simple assignment rule based on complementary slackness condition. A simple
and efficient method of updating the dual variable is through a first order online learning step. For
example, the algorithm stated in [14] for online linear programming uses mirror descent with entropy
regularization (multiplicative weight updates algorithm) once written in the primal dual language.
Recently, the work in [14] was independently extended to the random permutation model in [19, 15, 2].
In [2], the authors provide competitive difference bound for online convex optimization under random
permutation model as a function of the regret bound for the online learning algorithm applied to the
dual.
In this paper, we consider two versions of the greedy algorithm for problem (1) The first algorithm,
Algorithm 1, updates the primal and dual variables sequentially. The second algorithm, Algorithm 2,
provides a direct saddle-point representation of what has been described informally in the literature
as “continuous updates” of primal and dual variables. This saddle point representation allows us to
generalize this type of updates to non-smooth function. In section 2, we bound the competitive ratios
of the two algorithms. A sufficient condition on the objective function that guarantees a non-trivial
worst case competitive ratio is introduced. We show that the competitive ratio is at least 12 for a
monotone non-decreasing objective function. Examples that satisfy the sufficient condition (on
the positive orthant and the positive semidefinite cone) are given. In section 3, we derive optimal
algorithms, as variants of greedy algorithm applied to a smoothed version of ψ. For example,
Nesterov smoothing provides optimal algorithm for online LP. The main contribution of this paper
is to show how one can derive the optimal smoothing function (or from the dual point of view the
optimal regularization function) for separable ψ on positive orthant by solving a convex optimization
2

problem. This gives a implementable algorithm that achieves the optimal competitive ratio derived in
[13]. We also show how this convex optimization can be modified for the design of the smoothing
function specifically for the sequential algorithm. In contrast, [13] only considers continuous updates
algorithm.
Notation. We denote the transpose of a matrix A by AT . The inner product on Rn is denoted by
h·, ·i. Given a function ψ : Rn 7→ R, ψ ∗ denotes the concave conjugate of ψ defined as
ψ ∗ (y) = inf hy, ui − ψ(u),
u

for all y ∈ Rn . For a concave function ψ, ∂ψ(u) denotes the set of supergradients of ψ at u, i.e., the
set of all y ∈ Rn such that
∀u0 ∈ Rn : ψ(u0 ) ≤ hy, u0 − ui + ψ(u).
The set ∂ψ is related to the concave conjugate function ψ ∗ as follows. For an upper semi-continuous
concave function ψ we have
∂ψ(u) = argmin hy, ui − ψ ∗ (y).
y

Under this condition, (ψ ∗ )∗ = ψ.
A differentiable function ψ has a Lipschitz continuous gradient with respect to k·k with continuity
parameter µ1 > 0 if for all u, u0 ∈ Rn ,
1
∗
k∇ψ(u0 ) − ∇ψ(u)k ≤ ku − u0 k ,
µ
∗
where k·k is the dual norm to k·k. For an upper semi-continuous concave function ψ, this is
∗
equivalent to ψ ∗ being µ-strongly concave with respect to k·k (see, for example, [36, chapter 12]).
The dual cone K ∗ of a cone K ⊂ Rn is defined as K ∗ = {y | hy, ui ≥ 0 ∀u ∈ K}. Two examples
of self-dual cones are the positive orthant Rn+ and the cone of n × n positive semidefinite matrices
n
S+
. A proper cone (pointed convex cone with nonempty interior) K induces a partial ordering on Rn
which is denoted by ≤K and is defined as
x ≤K y ⇔ y − x ∈ K.
For two sets F, G ⊂ Rn , we write F ≤K G when u ≤K v for all u ∈ F, v ∈ G.
1.1

Two greedy algorithms

The (Fenchel) dual problem for problem (1) is given by
m
X
minimize
σt (ATt y) − ψ ∗ (y),

(2)

t=1

where the optimization variable is y ∈ Rn , and σt denotes the support function for the set Ft defined
as σt (z) = supx∈Ft hx, zi. We denote the optimal dual objective with D? .
A pair (x∗ , y ∗ ) ∈ (F1 × . . . Fm ) × K ∗ is an optimal primal-dual pair if and only if
x∗t ∈ argmax x, ATt y ∗
∀t ∈ [m],
x∈Ft
m
X

y ∗ ∈ ∂ψ(

At x∗t ).

(3)
(4)

t=1

Based on these optimality conditions, we consider two algorithms. Algorithm 1 updates the primal
and dual variables sequentially, by maintaining a dual variable ŷt and using it to assign x̂t ∈
argmaxx∈Ft x, ATt ŷt . The algorithm then updates the dual variable based on the second optimality
condition (4) 1 . By the assignment rule, we have At x̂t ∈ ∂σt (ŷt ), and the dual variable update can
be viewed as
* t
+
X
ŷt+1 ∈ argmin
As x̂s , y − ψ ∗ (y).
y

s=1

Therefore, the dual update is the same as the update in dual averaging [34] or Follow The Regularized
Leader (FTRL) [39, 1][37, section 2.3] algorithm with regularization −ψ ∗ (y).
1

we assume that ∂ψ nonempty on the boundary of K, otherwise, we can modify the algorithm to start from a
point in the interior of the cone very close to zero.

3

Algorithm 1 Sequential Update
Initialize ŷ1 ∈ ∂ψ(0)
for t ← 1 to m do
Receive At , Ft
x̂t ∈ argmaxx∈Ft x, ATt ŷt
Pt
ŷt+1 ∈ ∂ψ( s=1 As x̂s )
end for
Algorithm 2 updates the primal and dual variables simultaneously, ensuring that
x̃t ∈ argmax
x∈Ft

x, ATt ỹt

,

ỹt ∈ ∂ψ(

t
X

As x̃s ).

s=1

This algorithm is inherently more complicated than algorithm 1, since finding x̃t involves solving a
saddle-point problem. This can be solved by a first order method like the mirror descent algorithm
for saddle point problems. In contrast, the primal and dual updates in algorithm 1 solve two separate
maximization and minimization problems 2
Algorithm 2 Simultaneous Update
for t ← 1 to m do
Receive At , Ft
(ỹt , x̃t ) ∈ arg miny maxx∈Ft

D
E
Pt−1
y, At x + s=1 As x̃s − ψ ∗ (y)

end for
For a reader more accustomed to optimization algorithms, we would like to point to alternative
views on these algorithms. If 0 ∈ Ft for all t, then an alternative view on Algorithm 2 is coordinate
minimization. Initially, all the coordinates are set to zero, then at step t
!
t
X
x̃t ∈ argmax ψ
At x̃s + At x .
(5)
x∈Ft

s=1

If in addition ψ is differentiable, Algorithm 1, at each time step t, applies one iteration of Frank-Wolfe
algorithm [18] for solving (5).

2

Competitive ratio bounds and examples for ψ

In this section, we derive bounds on the competitive ratios of Algorithms
P1mand 2 by bounding their
respective duality gaps. Let ỹm+1 to be the minimum element in ∂ψ( t=1 At x̃t ) with respect to
ordering ≤K ∗ (such an element exists in the superdifferential by Assumption (1),
which appears
Pm
later in this section). We also choose ŷm+1 to be the minimum element in ∂ψ( t=1 At x̂t ) with
respect to ≤K ∗ . Note that ŷm+1 is used for analysis and does not play a role in the assignments of
Algorithm 1. Let Pseq and Psim denote the primal objective values for the primal solution produced
by the algorithms 1 and 2, and Dseq and Dsim denote the corresponding dual objective values,
!
!
m
m
X
X
Pseq = ψ
At x̂t ,
Psim = ψ
At x̃t ,
t=1

Dseq =

m
X

t=1

σt (ATt ŷt ) − ψ ∗ (ŷm+1 ),

Dsim =

t=1

m
X

σt (ATt ỹt ) − ψ ∗ (ỹm+1 ).

t=1

2
Also if the original problem is a convex relaxation of an integer program, meaning that each Ft = convFt
where Ft ⊂ Zl , then x̂t can always be chosen to be integral while integrality may not hold for the solution of
the second algorithm.

4

The next lemma provides a lower bound on the duality gaps of both algorithms.
Lemma 1 The duality gap for Algorithm 2 is lower bounded as
Psim − Dsim ≥ ψ ∗ (ỹm+1 ) + ψ(0),
and the duality gap for Algorithm 1 is lower bounded as
Pseq − Dseq ≥ ψ ∗ (ŷm+1 ) + ψ(0) +

m
X

hAt x̂t , ŷt+1 − ŷt i .

t=1

Furthermore, if ψ has a Lipschitz continuous gradient with parameter 1/µ with respect to k·k, then
Pseq − Dseq ≥ ψ ∗ (ŷm+1 ) + ψ(0) −

m
X
1
2
kAt x̂t k .
2µ
t=1

(6)

Note that right hand side of (6) is exactly the regret bound of the FTRL algorithm (with a negative
sign) [38]. The proof is given in Appendix A. To simplify the notation in the rest of the paper, we
assume ψ(0) = 0.
Now we state a sufficient condition on ψ that leads to non-trivial competitive ratios, and we assume
this condition holds in the rest of the paper. One can interpret this assumption as having “diminishing
returns” with respect to the ordering induced by a cone. Examples of functions that satisfy this
assumption will appear later in this section.
Assumption 1 Whenever u ≥K v, there exists y ∈ ∂ψ(u) that satisfies
y ≤K ∗ z,
for all z ∈ ∂ψ(v).
When ψ is differentiable, Assumption 1 simplifies to
u ≥K v ⇒ ∇ψ(u) ≤K ∗ ∇ψ(v).
That is, the gradient, as a map from Rn (equipped with ≤K ) to Rn (equipped with ≤K ∗ ), is orderreversing (also known as antitone). If ψ satisfies Assumption 1, then so does ψ ◦ A, when A is a linear
map such that hy, Avi ≥ 0, for all v ∈ K and y ∈ K ∗ . When ψ is twice differentiable, Assumption
1 is equivalent to w, ∇2 ψ(u)v ≤ 0, for all u, v, w ∈ K. For example, this is equivalent to Hessian
being element-wise non-positive when K = Rn+ .
Competitive ratio for non-decreasing ψ

2.1

To quantify the competitive ratio of the algorithms, we define αψ : K 7→ R as
αψ (u) = sup {c | ψ ∗ (y) ≥ cψ(u), ∀y ∈ ∂ψ(u)},

(7)

which for u 6= 0 can also be written as
αψ (u) =

ψ ∗ (y)
.
y∈∂ψ(u) ψ(u)
inf

Since ψ ∗ (y) + ψ(u) = hy, ui for all y ∈ ∂ψ(u), αψ is equivalent to3
αψ (u) = sup{c | hy, ui ≥ (c + 1)ψ(u), ∀y ∈ ∂ψ(u)}

(8)

= sup{c | ψ 0 (u; u) ≥ (c + 1)ψ(u)},
where ψ 0 (u, v) is the directional derivative of ψ at u in the direction of v. Note that for any u ∈ K,
we have −1 ≤ αψ (u) ≤ 0 since for any y ∈ ∂ψ(u), by concavity of ψ and the fact that y ∈ K ∗ ,
we have 0 ≤ hy, ui ≤ ψ(u) − ψ(0). If ψ is a linear function then αψ = 0, while if 0 ∈ ∂ψ(u) for
some u ∈ K, then αψ (u) = −1. Figure 1 shows a differentiable function ψ : R+ 7→ R. The value of
α(u0 ) is the ratio of ψ ∗ (ψ 0 (u0 )) to ψ(u0 ) as shown.
The next theorem provides lower bounds on the competitive ratio of the two algorithms.
3

If ψ(0) 6= 0, then the definition of αψ should be modified to αψ (u) = sup{c | hy, ui ≥ (c + 1)(ψ(u) −
ψ(0)), y ∈ ∂ψ(u)}.

5

ψ(u0 )
−ψ ∗ (ψ 0 (u0 ))
u0

u

Figure 1: ψ 0 is the derivative of ψ and −ψ ∗ (ψ 0 (u0 )) is the y-intercept of the tangent to the function
graph at u0 . αψ (u0 ) is the ratio of ψ ∗ (ψ 0 (u0 )) to ψ(u0 ).
Theorem 1 If Assumption 1 holds, then for the simultaneous update algorithm we have 4 :
Psim ≥

1
D? .
1 − ᾱψ

where D∗ is the dual optimal objective and
ᾱψ = inf{αψ (u) | u ∈ K}.

(9)

For the sequential update algorithm,
Pseq ≥

m
X
1
(D? +
hAt x̂t , ŷt+1 − ŷt i).
1 − ᾱψ
t=1

Further, if ψ is differentiable with gradient Lipschitz continuity parameter
Pseq ≥
Proof:

1
µ

with respect to k·k,

m
X
1
1
2
kAt x̂t k ).
(D? −
1 − ᾱψ
2µ
t=1

(10)

We first show that Assumption 1 implies that
m
X

σt (ATt ỹt ) ≥

t=1
m
X

m
X

σt (At ŷt ) ≥

σt (ATt ỹm+1 ),

t=1
m
X

t=1

(11)

σt (At ŷm+1 ),

t=1

To do so, we prove that for all t, σt (ATt ỹt ) ≥ σt (ATt ỹm+1 ). The proof for σt (ATt ŷt ) ≥ σt (ATt ŷm+1 )
follows the same steps.
Pt
Pm
For any t, we have
for all s. Since ỹt ∈
s=1 As x̃s ≤K
s=1 As x̃s since As Fs ⊂ KP
Pt
m
∂ψ( s=1 As x̃s ) and ỹm+1 was chosen to be the minimum element in ∂ψ( s=1 As x̃s ) with respect
to ≤K ∗ , by the Assumption 1, we have
ỹt ≥K ∗ ỹm+1 .
Since At x ∈ K for all x ∈ Ft , we get hAt x, yt i ≥ hAt x, ym i . Therefore, σt (ATt ỹt ) ≥ σt (ATt ỹm+1 ).
Now by (11)
Dsim =

m
X

σt (ATt ỹt )

∗

− ψ (ỹm+1 ) ≥

m
X

t=1

σt (ATt ỹm+1 ) − ψ ∗ (ỹm+1 ) ≥ D? .

t=1

?

Similarly, Dseq ≥ D . Lemma 1 and definition of ᾱψ give the desired result.
4

If ψ(0) 6= 0, then the conclusion becomes Psim − ψ(0) ≥

6

1
1−αψ

(D? − ψ(0)).



Competitive ratio for non-monotone ψ

2.2

If ψ is not non-decreasing with respect to K, the algorithms are not guaranteed to increase the
objective at each step; therefore, Pseq and Psim are not guaranteed to be non-negative. However, if we
add the assumption that 0 ∈ Ft for all t, then Algorithm 2 will not decrease the objective at any step,
t
t−1
X
X
ψ(
As x̃s ) − ψ(
As x̃s ) ≥ x̃t , ATt ỹt = max x, ATt ỹt ≥ 0,
s=1

x∈Ft

s=1

(12)

which follows from concavity of ψ.
In other words, the algorithm simply assigns 0 to xt if any other feasible point in Ft reduces the
objective value. Define
m
X
ũ =
At x̃t ,
t=1

and note that under the assumption 0 ∈ Ft , we have ψ(ũ) ≥ 0. Further, we have:
1
Psim ≥
D? .
1 − αψ (ũ)

(13)

We provide examples of non-monotone ψ and their competitive ratio analysis in this section and
section 3.1. Given appropriate conditions on Ft and At , in order to find a lower bound on the
competitive ratio independent of ũ, we only need to lower bound αψ over a subset of K. Note that
when ψ is not non-decreasing, then there exists a supergradient that is not in K ∗ . Therefore, αψ (ũ)
for general ψ can be less than −1. In this case, the lower bound for the competitive ratio of Algorithm
(2) is less than 12 .
We now consider examples of ψ that satisfy Assumption 1 and derive lower bound on αψ for those
examples.
2.3

Examples on the positive orthant.

Let K = Rn+ and note that K ∗ = K. To simplify the notation we use ≤ instead of ≤Rn+ . When ψ has
continuous partial second derivatives with respect to all the variables, Assumption 1 is equivalent to the
Hessian being element-wise non-positive over Rn+ . Assumption 1 is closely related to submodularity.
In fact, on the positive orthant this assumption is sufficient for submodularity of ψ on the lattice
defined by ≤. However, this assumption is not necessary for submodularity. When ψ has continuous
partial second derivatives with respect to all the variables, the necessary and sufficient condition only
requires the off-diagonal elements of the Hessian to be non-positive [28].
If ψ is separable, i.e.,
ψ(u) =

n
X

ψi (ui ),

(14)

i=1

Assumption 1 is satisfied since by concavity for each ψi we have ∂ψi (ui ) ≤ ∂ψi (vi ) when ui ≤ vi .
If ψ satisfies the Assumption 1, then so does ψ(Au), where A is an element-wise non-negative
matrix.
Adwords In the basic adwords problem, for all t, Ft = {x ∈ Rl+ | 1T x ≤ 1}, At is a diagonal
matrix with non-negative entries, and
n
n
X
X
ψ(u) =
ui −
(ui − 1)+ ,
(15)
i=1
∗

i=1
T

where (·)+ = max{·, 0}. In this problem, ψ (y) = 1 (y − 1). Since 0 ∈ ∂ψ(1) we have αψ = −1
by (8); therefore, the competitive ratio of algorithm 2 is 12 . Let r = maxt,i,j At,ij , then we have
Pm
1
t=1 hAt x̂t , ŷt+1 − ŷt i ≤ nr. Therefore, the competitive ratio of algorithm 1 goes to 2 as r (bid to
budget ratio) goes to zero. In adwords with concave returns studied in [13], At is diagonal for all t
and ψ is separable 5 .
5

Note that in this case one can remove the assumption that ∂ψi ⊂ R+ since if ỹt,i = 0 for some t and i,
then x̃s,i = 0 for all s ≥ t.

7

Online linear program and non-separable budget Recall that online LP is given by
!
m
m
X
X
T
maximize
ct xt + I{·≤1}
Bt xt
t=1

t=1

x t ∈ Ft ,

∀t ∈ [m].

where Ft = {x ∈ Rk+ | 1T x ≤ 1} is the simplex. If a lower bound on the optimal dual variable
mini yi∗ ≥ −l is given, then the LP can be written in the exact penalty form [6]:
!
m
m
X
X
T
maximizext ∈Ft
ct x t + G
Bt xt .
(16)
t=1

t=1

where G is an l-Lipschitz continuous function with respect to l1 norm given by
n
X
G(u) = −l
(ui − 1)+ .
i=1

−l is a lower bound on dual variable if


ct,j
l > max
| Bt,ij > 0, j ∈ [k], i ∈ [n] .
Bt,ij

(17)

To prove this, by way of contradiction, we assume that yi∗ ≤ −l for some i ∈ [n]. Now by the
definition of l, we have ct,j + (BtT y ∗ )j < 0 for all j such that Bt,ij > 0. On the other hand by the
optimality condition (3), ct + BtT y ∗ ∈ NFt (x∗t ) where NFt (x∗t ) is the normal cone of the simplex at
x∗t . Therefore, we should have x∗t,j = 0 for all j such that Bt,ij > 0. This results in (Bt x∗t )i = 0
Pm
which yield ( t=1 Bt x∗t )i = 0. This means that the corresponding variable yi∗ = 0 which is a
contradiction. With this choice of l, Algorithm 2 always maintains a feasible solution for the original
problem when applied to (16). This follows from the fact that if ỹt,i = −l for some t and i, then
(Bt x̃t )i = 0. Note that in the adwords problem Bt = diag(ct ) and l = 1.
For any p ≥ 1 let Bp be
Pnthe lp -norm ball. In order to provide examples of non-separable G,
we rewrite the function i=1 (ui − 1)+ using the distance from B∞ . For any set C ⊂ Rn+ , let
d1 (u, C) = inf ū∈C ku − ūk1 and note that d1 (u, C) is 1-Lipschitz continuous with respect to l1
norm. We have:
n
X
(1 − ui )+ = d1 (u, B∞ ).
(18)
i=1

Pm
Consider a problem with constraint k t=1 Bt xt kp ≤ 1. Given the bound on dual variable in (17),
this problem can be equivalently written in the form of (16) with the exact penalty [10, Theorem 5.5]
G(u) = −ld1 (u, Bp ).
When p = ∞, we get back (18).
For p ≥ 1, although not separable, the function G(u) = −d1 (u, Bp ) satisfies Assumption 1. For B1 ,
that follows from the fact that d1 (u, B1 ) = (1T u − 1)+ ; therefore, ∂d1 (u, B1 ) = 1∂f (1T u), where
f (x) = (x − 1)+ . The proof for p > 1 is given in Appendix B.
When ψ is given by 16 with G(u) = −ld1 (u, Bp ), we have αψ (ũ) ≥ − θl , where θ =
mint minx∈Ft
2.4

cT
t x
.
1T Bt x

The derivation of this bound is also given in Appendix B.

Examples on the positive semidefinite cone.

n
Let K = S+
and note that K ∗ = K. An interesting example that satisfies Assumption 1 is
p
ψ(U ) = trU with p ∈ (0, 1), where ∇ψ(U ) = pU p−1 and ᾱψ = p − 1. This objective function is
used in pth mean optimal experiment design. Another example is ψ(U ) = log det(U + A0 ), where
∇ψ(U ) = (U + A0 )−1 and ᾱψ = −1 since

h∇ψ(U ), U i
n − tr(A0 + U )−1 A0
=
→ 0 as trU → ∞.
ψ(U ) − ψ(0)
log det((A0 + U )A−1
0 )
8

Maximizing log det arises in several offline applications including D-optimal experiment design
[35], maximizing the Kirchhoff complexity of a graph [41], Optimal sensor selection [22, 40]. An
example of applications for maximizing the logdet of a projected Laplacian, as a function of graph
edge weights, appears in connectivity control of mobile networks [41]. We derive the competitive
ratio of the greedy algorithm with smoothing for online experiment design and Kirchhoff complexity
maximization of a graph in section 3.

3

Smoothing of ψ for improved competitive ratio

The technique of “smoothing” an objective function, or equivalently adding a strongly convex
regularization term to its conjugate function, has been used in several areas. In convex optimization,
a general version of this is due to Nesterov [32], and has led to faster convergence rates of first order
methods for non-smooth problems. In this section, we study how replacing ψ with a appropriately
smoothed function ψS helps improve the performance of the two algorithms discussed in section 1.1,
and show that it provides optimal competitive ratio for two of the problems mentioned in section 2,
adwords and online LP. We then show how to maximize the competitive ratio of Algorithm 2 for a
separable ψ and compute the optimal smoothing by solving a convex optimization problem. This
allows us to design the most effective smoothing customized for a given ψ: we maximize the bound
on the competitive ratio over the set of smooth functions.(see subsection 3.2 for details).
Let ψS denote an upper semi-continuous concave function (a smoothed version of ψ), and suppose
ψS satisfies Assumption 1. The algorithms we consider in this section are the same as Algorithms
1 and 2, but with ψ replacing ψS . Note that the competitive ratio is computed with respect to the
original problem, that is the offline primal and dual optimal values are still the same P ? and D? as
before. If we replace ψ with ψS in algorithms 1 and 2, the dual updates are modified to
* t
+
X
ŷt+1 ∈ argmin
As x̂s , y − ψS ∗ (y),
y

s=1

*
(x̃t , ỹt ) ∈ arg min max
y

x∈Ft

y, At x +

t−1
X

+
As x s

− ψS ∗ (y).

s=1

From Lemma 1, we have that
Dsim ≤ ψS
Dseq ≤ ψS

m
X
t=1
m
X

!
At x̃t

− ψ ∗ (ỹm+1 )

!
At x̂t

− ψ ∗ (ŷm+1 ) −

t=1

(19)
m
X

hAt x̂t , ŷt+1 − ŷt i .

(20)

t=1

Similar to our assumption on ψ(0), to simplify the notation, by replacing ψS (·) with ψS (·) − ψS (0),
we assume ψS (0) = 0. Define
αψ,ψS (u) = sup{c |ψ ∗ (y) ≥ ψS (u) + (c − 1)ψ(u), ∀y ∈ ∂ψS (u)},
and
ᾱψ,ψS = inf{αψ,ψS (u) | u ∈ K}.
Now the conclusion of Theorem 1 holds with ᾱψ replaced by ᾱψ,ψS . Similarly, when ψS is nonmonotone, inequality (13) holds with αψ replaced by αψ,ψS .
3.1

Nesterov Smoothing

We first consider Nesterov smoothing [32], and apply it to examples on non-negative orthant. Given a
proper upper semi-continuous concave function φ : Rn 7→ R ∪ {−∞}, let
ψS = (ψ ∗ + φ∗ )∗ .
Note that ψS is the hypo-sum (sup-convolution) of ψ and φ.
ψS = ψφ(u) = sup ψ(v) + φ(u − v).
v

9

This is called hypo-sum of ψ and φ since the hypo-graph of ψS is the Minkowski sum of hypo-graphs
of ψ and φ.
If ψ and φ are separable, then ψφ satisfies Assumption 1 for K = Rn+ . Here we provide example
of Nesterov smoothing for functions on non-negative orthant.
Adwords and Online LP: Consider the problem (16) with G(u) = −l
problem we smooth G with:

Pn

i=1 (ui

− 1)+ . For this

m

1 X
(e − 1)
θ
φ∗ (y) = ( ((yi −
) log(1 −
yi )) − (1 + γ)1T y),
γ i=1
(e − 1)
θ
where γ = log(1 +

l(e−1)
),
θ

cTt x
T
x∈Ft 1 Bt x

θ = min min
t

and l is defined as in (17). In this case, we have;
1
)γ.
e−1

αψ,ψφ (ũ) ≥ 1 − (1 +

(see the Appendix C for the derivation). This gives the competitive ratio of γ1 (1 − 1/e). In the case of
adwords where θ = l, this yield the optimal competitive ratio of 1 − e−1 and the smoothed function
coincides with the one derived in the previous paragraph. For a general LP, this approach provides
the optimal competitive ratio, which is known to be O(γ −1 ) [9].
Online experiment design and online graph formation: As pointed in section 2.4, maximizing
the determinant arises in graph formation, sensor selection and optimal experiment design. In the
offline form, these problems can be cast into maximizing log det subject to linear constraints as
follows:
m
X
maximize log det(A0 +
at aTt xt )
(21)
t=1

subject to

m
X

xt ≤ b,

t=1

xt ∈ [0, 1],

∀t,

where A0  0 and at ∈ Rn . We describe the online version of this problem for graph formation
and experiment design case. Consider the following online problem on a graph: given an underlying
connected graph with the Laplacian matrix L0 , at round t, the online algorithm is presented with
an edge and should decide whether to pick or drop theP
edge by choosing xt ∈ {0, 1}. There is a
n
bound on the number of the edges that can be picked, t=1 xt ≤ b. The goal is to maximize the
Kirchhoff complexity of the graph. The convex relaxation of the optimization problem is given by
21 where A0 = L0 + 11T and at is the incidence vector of the edge presented at round t. The
online experiment design or sensor selection is the same as (21). In that problem the vectors at are
experiment or measurement vectors.
The dual to 21 is as follows
maximize

m
X

(aTt Y at + y)+ + n − log det(Y ) + trA0 Y − by

t=1

subject to y ≤ 0, Y ≥ 0.
The hard budget constraint in problem 21 can be replaced by the exact penalty function G(u) =
−l(u − b)+ when −l is a given lower bound on the optimal dual variable corresponding to the
constraint. −l is a lower bound on the optimal dual variable corresponding to the constraint if
l>

2
.
λmin (A0 )
10

(22)

Pn
This follows from the fact that by the optimality condition (4), Y ∗ = (A0 + t=1 at aTt x∗t )−1 . If
y ∗ ≤ −l, then aTt Y ∗ at + y ∗ < 0 for all t. ThisP
combined with the the primal optimality condition
m
(3) forces x∗t = 0 for all t. Therefore, we get t=1 x∗t = 0 and y ∗ = 0, which is a contradiction.
Similar to the previous problems, we smooth G with:
b
θ
e−1
((y −
) log(1 −
y) − (1 + γ)y).
γ
e−1
θ

φ∗ (y) =

Here γ = log(1 + θl ) and θ = log(1 + 1/n). For this problem we have:
αψ,ψφ (ũ) ≥ 1 − (1 +

1
1
)γ + ᾱlog det ≥ −(1 +
)γ.
e−1
e−1

This results in the following competitive ratio bound
1

Psim − log det(A0 ) ≥



1+ 1+

1
e−1

 (D? − log det(A0 )).
γ

The proof is included in the Appendix C. In the graph formation problem, λmin (A0 ) = λ2 (L0 ), that
is the second smallest eigenvalue of L0 . For a connected graph λ2 (L0 ) ∈ [1/n, n] with lower bound
achieved by the path graph and the upper bound achieved by the complete graph. Therefore, the
competitive ratio in this case is Ω( log1 n ).
3.2

Computing optimal smoothing for separable functions on Rn+

We now tackle the problem of finding the optimal smoothing for separable functions on the positive
orthant, which as we show in an example at the endP
of this section is not necessarily
Pn given by Nesterov
n
smoothing. Given a separable monotone ψ(u) = i=1 ψi (ui ) and ψS (u) = i=1 ψS i (ui ) on Rn+
we have that ᾱψ,ψS ≥ mini ᾱψi ,ψS i .
To simplify the notation, drop the index i and consider ψ : R+ 7→ R. We formulate the problem
of finding ψS to maximize αψ,ψS as an optimization problem. In section 4 we discuss the relation
between
this optimization method and the optimal algorithm presented in [13]. We set ψM (u) =
Ru
y(s)ds
with y a continuous function, and state the infinite dimensional convex optimization
0
problem with y as a variable,
minimize β
Z
subject to

(23)
u

y(s)ds − ψ ∗ (y(u)) ≤ βψ(u),

∀u ∈ [0, ∞)

0

y ∈ C[0, ∞).
where β = 1− ᾱψ,ψS (theorem 1 describes the dependence of the competitive ratios on this parameter).
Note that we have not imposed any condition on y to be non-increasing (i.e., the corresponding ψS
to be concave). The next lemma establishes that every feasible solution to the problem (23) can be
turned into a non-increasing solution.
Lemma 2 Let (y, β) be a feasible solution for problem (23) and define ȳ(u) = inf s≤u y(s). Then
(ȳ, β) is also a feasible solution for problem (23).
In particular if (y, β) is an optimal solution, then so is (ȳ, β). The proof is given in the supplement.

Re-

visiting the adwords problem, we observe that the optimal solution is given by y(u) =

e−exp(u)
e−1

+

,

which is the derivative of the smooth function we derived using Nesterov smoothing in section
3.1. The optimality of this y can be established by providing a dual certificate, a measure ν corresponding to the inequality constraint, that together with y satisfies the optimality condition. If we
set dν = f (u) du with f (u) = exp (1 − u)/(e − 1), the optimality conditions are satisfied with
11

β = (1 − 1/e)−1 .
Z

∞

f (u)ψ(u) du = 1, f  0,
Zu=0
∞

f (s) ds ∈ f (u)∂ψ ∗ (y(u)),

∀u ≥ 0,

Zs=u
u

y(s)ds − ψ ∗ (y(u)) ≤ βψ(u),
∀u ≥ 0,
0
Z u
f (u)(
y(s)ds − ψ ∗ (y(u)) − βψ(u)) = 0,

∀u ≥ 0.

0

Also note that if ψ plateaus (e.g., as in the adwords objective), then one can replace problem (23)
with a problem over a finite horizon.
Theorem 2 Suppose ψ(u) = c on [u0 , ∞). Then problem (23) is equivalent to the following problem,
minimize β
(24)
Z u
subject to
y(s)ds − ψ ∗ (y(u)) ≤ βψ(u),
∀u ∈ [0, u0 ]
0

y(u0 ) = 0,

y ∈ C[0, u0 ].

So for a function ψ with a plateau, one can discretize problem (24) to get a finite dimensional
problem,
minimize β
subject to h

(25)
t
X

y[s] − ψ ∗ (y[t]) ≤ βψ(ht),

∀t ∈ [d]

s=1

y[d] = 0,
where h = u0 /d is the discretization step. Figure 2a shows the optimal smoothing for the piecewise
linear function ψ(u) = min(.75, u, .5u + .25) by solving problem (25). We point out that the
optimal smoothing for this function is not given by Nesterov’s smoothing (even though the optimal
smoothing can be derived by Nesterov’s smoothing for a piecewise linear function with only two
pieces, like the adwords cost function). Figure 2d shows the difference between the conjugate of
the optimal smoothing function and ψ ∗ for the piecewise linear function, which we can see is not
concave.
Pm
In cases where a bound umax on t=1 At Ft is known, we can restrict t to [0, umax ] and discretize
problem (23) over this interval. However, the conclusion of Lemma 2 does not hold for a finite
horizon and we need to impose additional linear constraints y[t] ≤ y[t − 1] to ensure the monotonicity
of y. We find the optimal √
smoothing for two examples of this kind: ψ(u) = log(1 + u) over [0, 100]
(Figure 2b), and ψ(u) = u over [0, 100] (Figure 2c). In Figure 2e, we show the competitive ratio
achieved with the optimal smoothing of ψ(u)
√ = log(1 + u) over [0, umax ] as a function of umax .
Figure 2f depicts this quantity for ψ(u) = u.
3.3

Bounds for the sequential algorithm

In this section we provide a lower-bound on the competitive ratio of the sequential algorithm
(Algorithm 1). Based on this competitive ratio bound we modify Problem (23) for designing the
smoothing function for the sequential algorithm.
Theorem 3 Suppose ψS is differentiable on an open set containing K and satisfies Assumption 1. In
addition suppose there exists c ∈ K is such that At Ft ≤K c for all t, then
1
Pseq ≥
D? ,
1 − ᾱψ,ψS + κc,ψ,ψS
where κ is given by
κc,ψ,ψS = inf{r | hc, ∇ψS (0) − ∇ψS (u)i ≤ rψ(u), u ∈ K}
(26)
12

0.8

0.6

5

25

4

20

3

15

2

10

0.4

0.2

ψS
ψ

1

ψS
ψ

0

0

0
0

0.5

1

1.5

2

0

20

40

u

60

80

0

100

0.9

0.2
0.1

0.4

0.6

0.8

1

0.85
0.8

0.9
0.85
0.8
0.75

0

1

100

0.95

0.7

-0.1

80

(c)

0.75

0

60

u

comp. ratio

0.3

comp. ratio

0.95

0.2

40

(b)

0.4

0

20

u

(a)

ψS∗ (y) − ψ∗ (y)

ψS
ψ

5

500

0.7

1000

0

200

400

umax

y

(e)

(d)

600

800

1000

umax

(f)

Figure 2: Optimal√smoothing for ψ(u) = min(.75, u, .5u+.25) (a), ψ(u) = log(1+u) over [0, 100]
(b), and ψ(u) = u over [0, 100] (c). The competitive ratio
√ achieved by the optimal smoothing as a
function of umax for ψ(u) = log(1 + u) (e) and ψ(u) = u (f). ψS ∗ − ψ ∗ for the piecewise linear
function (d).
Proof:

Since ψS satisfies Assumption 1, we have ŷt+1 ≤K ∗ ŷt . Therefore, we can write:
m
X

hAt x̂t , ŷt − ŷt+1 i ≤

t=1

m
X

hc, ŷt − ŷt+1 i

t=1

= hc, ŷ0 − ŷm+1 i

(27)

Now by combining 20 with 27, we get
Dseq ≤ ψS

m
X

!
At x̂t

*
+

c, ∇ψS (0) − ∇ψS

t=1

m
X

!+
At x̂t

.

t=1

The conclusion of the theorem follows from the definition of ᾱψ,ψS , κc,ψ,ψS and the fact that
D̂ ≥ D? .

Based on the result of the previous theorem we can modify the optimization problem set up in
Section 3.2 for separable functions on Rn+ to maximize the lower bound on the competitive ratio of
the sequential algorithm. Note that in this case we have κc,ψ,ψS ≤ maxi κci ,ψi ,ψS i . Similar to the
previous section to simplify the notation we drop the index i and assume ψ is a function of a scalar
variable. The optimization problem for finding ψS that minimizes κc,ψ,ψS − ᾱψ,ψS is as follows:
minimize β
Z
subject to

(28)
u

y(s)ds + c(ψ 0 (0) − y(u)) − ψ ∗ (y(u)) ≤ βψ(u),

∀u ∈ [0, ∞)

0

y ∈ C[0, ∞).
In the case of Adwords, the optimal solution is given by



u−1
1
β=
y(u) = β 1 − exp
,
−1 ,
1+c
1 − exp( c+1
)
+


−1
which gives a competitive ratio of 1 − exp c+1
. In Figure 3b we have plotted the competitive
ratio achieved by solving problem 28 for ψ(u) = log det(1 + u) with umax = 100 as a function
13

0.8

Competitive ratio

Competitive ratio

0.7

0.6

0.5

0.4

0.3

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

0

20

40

60

c

c

(a)

(b)

80

100

Figure 3: The competitive ratio achieved by the optimal smoothing for the sequential algorithm as a
function of c for ψ(u) = min(.75, u, .5u + .25) (a) and ψ(u) = log(1 + u) with umax = 100 (b).
of c. Figure 3a shows the competitive ratio as a function of c for the piecewise linear function
ψ(u) = min(.75, u, .5u + .25).

4

Discussion and related work

We discuss results and papers from two communities, computer science theory and machine learning,
related to this work.
Online convex optimization. In [13], the authors proposed an optimal algorithm for adwords with
differentiable concave returns (see examples in section 2). Here, “optimal” means that they construct
an instance of the problem for which competitive ratio bound cannot be improved, hence showing
the bound is tight. The algorithm is stated and analyzed for a twice differentiable, separable ψ(u).
The assignment rule for primal variables in their proposed algorithm is explained as a continuous
process. A closer look reveals that this algorithm falls in the framework of algorithm 2, with the
only difference being that at each step, (x̃t , ỹt ) are chosen such that where vi : R+ 7→ R+ is an
increasing differentiable function given as a solution of a nonlinear differential equation that involves
ψi and may not necessarily have a closed form. The competitive ratio is also given based on the
differential equation. They prove that this gives the optimal competitive ratio for the instances where
ψ1 = ψ2 = . . . = ψn .
Note that this is equivalent of setting ψS i (ui ) = ψ(vi (ui ))). Since vi is nondecreasing ψS i is a
concave function. On the other hand, given a concave function ψS i (R+ ) ⊂ ψi (R+ ), we can set
vi : R+ 7→ R+ as vi (u) = inf{z | ψi (z) ≥ ψS i (u)}. Our formulation in section 3.2 provides a
constructive way of finding the optimal smoothing. It also applies to non-smooth ψ.
Recently, authors in [4, 7, 11] have provided a primal-dual onlineP
algorithm for the
Pmdual probm
lemP
(2) that corresponds to the non-monotone primal objective ψ ( t=1 At xt ) = t=1 cTt xt +
m
G ( t=1 Bt xt ).The primal and dual updates in their algorithm are presented as a continuous update
based on a differential equation. They assume that G∗ is differentiable and that ∇G∗ is monotone
on Rn+ , i.e., If y ≥ y 0 , then ∇G∗ (y) ≤ ∇G∗ (y 0 ). In contrast, our assumption written in terms of
G∗ for a differentiable function will become: If ∇G∗ (y) < ∇G∗ (y 0 ), then y ≥ y 0 , which is not
equivalent to the assumption in [7]. When G is separable the two assumptions coincide and this
algorithm is similar
Pn Rtoy algorithm 2 applied to the smooth function GM whose conjugate is given by
G∗M (y) = γ1 i=1 0 i G∗i 0 (z) log(1 − z/θ) dz. This smoothing coincides with Nesterov smoothing
in the case of LP.
Online learning. As mentioned before, the dual update in Algorithm 1 is the same as in Follow-theRegularized-Leader (FTRL) algorithm with −ψ ∗ as the regularization. This primal dual perspective
has been used in [39] for design and analysis of online learning algorithms. In the online learning
literature, the goal is to derive a bound on regret that optimally depends on the horizon, m. The goal
in the current paper is to provide competitive ratio for the algorithm that depends on the function ψ.
Regret provides a bound on the duality gap, and in order to get a competitive ratio the regularization
14

function should be crafted based on ψ. A general choice of regularization which yields an optimal
regret bound in terms of m is not enough for a competitive ratio argument, therefore existing results
in online learning do not address our aim.
Acknowledgments
The authors would like to thank James Saunderson, Ting Kei Pong, Palma London, and Amin Jalali
for their helpful comments and discussions.
References

[1] Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient
algorithm for bandit linear optimization. In COLT, pages 263–274, 2008.
[2] Shipra Agrawal and Nikhil R Devanur. Fast algorithms for online stochastic convex programming. arXiv preprint arXiv:1410.7596, 2014.
[3] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online
linear programming. arXiv preprint arXiv:0911.2974, 2009.
[4] Yossi Azar, Ilan Reuven Cohen, and Debmalya Panigrahi. Online covering with convex
objectives and applications. arXiv preprint arXiv:1412.3507, 2014.
[5] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online auctions and
generalized secretary problems. SIGecom Exch., 7(2):7:1–7:11, June 2008.
[6] Dimitri P Bertsekas. Necessary and sufficient conditions for a penalty method to be exact.
Mathematical programming, 9(1):87–99, 1975.
[7] Niv Buchbinder, Shahar Chen, Anupam Gupta, Viswanath Nagarajan, et al. Online packing and
covering framework with convex objectives. arXiv preprint arXiv:1412.8347, 2014.
[8] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Algorithms–ESA 2007, pages 253–264. Springer, 2007.
[9] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing.
Mathematics of Operations Research, 34(2):270–286, 2009.
[10] James V Burke. An exact penalization viewpoint of constrained optimization. SIAM Journal on
control and optimization, 29(4):968–998, 1991.
[11] TH Chan, Zhiyi Huang, and Ning Kang. Online convex covering and packing problems. arXiv
preprint arXiv:1502.01802, 2015.
[12] Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: Online keyword matching
with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference
on Electronic Commerce, EC ’09, pages 71–78, New York, NY, USA, 2009. ACM.
[13] Nikhil R Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of
the forty-fourth annual ACM symposium on Theory of computing, pages 137–144. ACM, 2012.
[14] Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near
optimal online algorithms and fast approximation algorithms for resource allocation problems.
In Proceedings of the 12th ACM conference on Electronic commerce, pages 29–38. ACM, 2011.
[15] Reza Eghbali, Jon Swenson, and Maryam Fazel. Exponentiated subgradient algorithm for
online optimization under the random permutation model. arXiv preprint arXiv:1410.7171,
2014.
[16] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. Online
stochastic packing applied to display ad allocation. In Proceedings of the 18th Annual European
Conference on Algorithms: Part I, ESA’10, pages 182–194, Berlin, Heidelberg, 2010. SpringerVerlag.
[17] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S Muthukrishnan. Online stochastic
matching: Beating 1-1/e. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual
IEEE Symposium on, pages 117–126. IEEE, 2009.
15

[18] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research
logistics quarterly, 3(1-2):95–110, 1956.
[19] Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online.
arXiv preprint arXiv:1407.5298, 2014.
[20] Patrick Jaillet and Xin Lu. Near-optimal online algorithms for dynamic resource allocation
problems. arXiv preprint arXiv:1208.2596, 2012.
[21] Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds.
Mathematics of Operations Research, 2013.
[22] Siddharth Joshi and Stephen Boyd. Sensor Selection via Convex Optimization. IEEE TRANSACTIONS ON SIGNAL PROCESSING, 57(2), 2009.
[23] Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online
b-matching. Theoretical Computer Science, 233(1):319–325, 2000.
[24] Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with
unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of
computing, pages 587–596. ACM, 2011.
[25] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line
bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of
computing, pages 352–358. ACM, 1990.
[26] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual
on online packing lps in the random-order model. In Proceedings of the 46th Annual ACM
Symposium on Theory of Computing, STOC ’14, pages 303–312, New York, NY, USA, 2014.
ACM.
[27] Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions.
In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages
630–631. Society for Industrial and Applied Mathematics, 2005.
[28] GG Lorentz. An inequality for rearrangements. The American Mathematical Monthly, 60(3):176–
179, 1953.
[29] Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an
approach based on strongly factor-revealing lps. In Proceedings of the forty-third annual ACM
symposium on Theory of computing, pages 597–606. ACM, 2011.
[30] Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching:
Online actions based on offline statistics. Mathematics of Operations Research, 37(4):559–573,
2012.
[31] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized
online matching. Journal of the ACM (JACM), 54(5):22, 2007.
[32] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming,
103(1):127–152, 2005.
[33] Yurii Nesterov. Introductory lectures on convex optimization, volume 87. Springer Science &
Business Media, 2004.
[34] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221–259, 2009.
[35] Friedrich Pukelsheim. Optimal design of experiments, volume 50. siam, 1993.
[36] R Tyrrell Rockafellar, Roger J-B Wets, and Maria Wets. Variational analysis, volume 317.
Springer, 1998.
[37] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends
in Machine Learning, 4(2):107–194, 2011.
[38] Shai Shalev-Shwartz and Yoram Singer. Online learning: Theory, algorithms, and applications.
2007.
[39] Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms.
Machine Learning, 69(2-3):115–142, 2007.
16

[40] Manohar Shamaiah, Siddhartha Banerjee, and Haris Vikalo. Greedy sensor selection: Leveraging submodularity. In 49th IEEE Conference on Decision and Control (CDC), pages 2572–2577.
IEEE, dec 2010.
[41] Michael M Zavlanos and George J Pappas. Distributed connectivity control of mobile networks.
Robotics, IEEE Transactions on, 24(6):1416–1428, 2008.

Appendix
A

Proofs

Proof of Lemma 1: Using the definition of Dsim , we can write:

Dsim =

m
X

σt (ATt ỹt ) − ψ ∗ (ỹm+1 )

t=1

=

m
X

hAt x̃t , ỹt i − ψ ∗ (ỹm+1 )

t=1

≤

m
X

t
t−1
X
X
(ψ(
As x̃s ) − ψ(
As x̃s )) − ψ ∗ (ỹm+1 )

t=1

= ψ(

m
X

s=1

s=1

As x̃s ) − ψ(0) − ψ ∗ (ỹm+1 ),

s=1

where in the inequality follows from concavity of ψ, and the last line results from the sum telescoping.
Similarly, we can bound Dseq :
Dseq =
=

m
X
t=1
m
X

σt (ATt ŷt ) − ψ ∗ (ŷm+1 )

(29)

hAt x̂t , ŷt i − ψ ∗ (ŷm+1 )

t=1

=

m
X

hAt x̂t , −ŷt+1 + ŷt i +

t=1

≤

m
X
t=1

=

m
X
t=1

m
X

hAt x̂t , ŷt+1 i − ψ ∗ (ŷm+1 )

t=1

hAt x̂t , −ŷt+1 + ŷt i +

m
X

t
t−1
X
X
(ψ(
As x̂s ) − ψ(
As x̂s )) − ψ ∗ (ŷm+1 )

t=1

s=1

s=1

m
X
hAt x̂t , −ŷt+1 + ŷt i + ψ(
As x̂s ) − ψ(0) − ψ ∗ (ŷm+1 ).
s=1

To provide intuition about the above inequalities
Pm we have plotted the derivative of a concave function
ψ defined on R+ in Figure 4. The quantity t=1 hAt x̃t , ỹt i is a right Riemann
Pm sum approximation
of the integral of ψ 0 and lower bounds the integral (Figure 4a). The quantity t=1 hAt x̂t , ŷt i is a left
Riemann sum approximation of the integral and upper bounds the integral (Figure 4b). The area of
hatched rectangle bounds the error of the left Riemann sum and is equal to hAt x̂t , −ŷt+1 + ŷt i.
When ψ is differentiable with Lipschitz gradient, we can use the following inequality that is equivalent
to Lipschitz continuity of the gradient:

ψ(u0 ) ≥ ψ(u) + h∇ψ(u), u0 − ui −

17

1
2
ku − u0 k
2µ

u, u0 ∈ K

ψ 0 (u)

ψ 0 (u)

ŷ1
ỹ1

ŷt

ỹ2

ŷ3

ỹ3
A1 x̃1 A2 x̃2

u

A3 x̃3

A1 x̂1

(a)

Figure 4: Interpretation of

At x̂t At x̂3

u

(b)

Pm

t=1

σt (ATt ỹt ) and

Pm

t=1

σt (ATt ŷt ) as Riemann sums.

(see, for example, [33, section 2.1.1]) to get
Dseq =
=

m
X
t=1
m
X

σt (ATt ŷt ) − ψ ∗ (ŷm+1 )

(30)

hAt x̂t , ŷt i − ψ ∗ (ŷm+1 )

t=1

≤

t−1
t
m
m
X
X
X
X
1
2
As x̂s )) − ψ ∗ (ŷm+1 )
As x̂s ) − ψ(
(ψ(
kAt x̂t k +
2µ
s=1
s=1
t=1
t=1

=

m
m
X
X
1
2
kAt x̂t k + ψ(
As x̂s ) − ψ(0) − ψ ∗ (ŷm+1 ).
2µ
t=1
s=1


Proof of Lemma 2: Let (y, β) be a feasible solution for problem (23). Note that y ≥ 0 since
dom ψ ∗ ⊂ R+ by the fact that ψ is non-decreasing. Let ȳ(u) = inf s≤u y(s). Note that ȳ is
continuous. Define
Ru
Ru
y(s) ds − ψ ∗ (y(u))
ȳ(s) ds − ψ ∗ (ȳ(u))
s=0
β(u) =
,
β̄(u) = s=0
,
ψ(u)
ψ(u)
with the definition modified with the right limit at u = 0. For any u such that ȳ(u) = y(u), we have:
Ru
Ru
y(s) ds − ψ ∗ (y(u))
ȳ(s) ds − ψ ∗ (ȳ(u))
s=0
β(u) =
≥ s=0
= β̄(u).
ψ(u)
ψ(u)
Now, we consider the set {u | ȳ(u) 6= y(u)}. By the definition of ȳ, we have ȳ(0) = y(0). Since
both functions are continuous, the set {u | ȳ(u) 6= y(u)} is an open subset of R and hence can be
written as a countable union of disjoint open intervals. Specifically, we can define the end points of
the intervals as:
a0 = b0 = 0,
ai = inf{u > bi−1 | y(u) > ȳ(u)}, ∀i ∈ {1, 2, . . .}
bi = inf{u > ai | y(u) = ȳ(u)}, ∀i ∈ {1, 2, . . .}.
S
then {u | ȳ(u) 6= y(u)} = i∈{1,2,...} (ai , bi ).(See Figure 5)
For any i ∈ {1, 2, . . .}, we show that β(u) ≥ β̄(u) on (ai , bi ). If ai = ∞, then bi = ∞, so we
assume that ai < ∞. By the definition of ai and bi , ȳ(u) is constant on (ai , bi ). Also, we have
y(ai ) = ȳ(ai ). Similarly, we have y(bi ) = ȳ(bi ) whenever bi < ∞.
18

a1

b1 a2

b2 u

Figure 5: An example of y(u) (solid blue) and ȳ(u) (dashed red).
Since ȳ(u) ≤ y(u) for all u and y(ai ) = ȳ(ai ), we have
β(ai ) ≥ β̄(ai ).

(31)

If bi < ∞, similarly by the fact that y(bi ) = ȳ(ai ) = ȳ(bi ), we have
β(bi ) ≥ β̄(bi ).

(32)

Now we consider the case where bi = ∞. In this case we have ȳ(u) = ȳ(ai ) on (ai , ∞). We
consider two cases based on the asymptotic behavior of ψ. If limu→∞ ψ(u) = +∞ (ψ is unbounded),
then we have
Ru
Ru
y(s) ds
ȳ(ai ) ds
s=0
lim sup β(u) = lim sup
≥ lim sup s=0
= lim β̄(u).
(33)
u→∞
ψ(u)
ψ(u)
u→∞
u→∞
u→∞
Here we used the fact that −ψ ∗ (y(u)) is bounded. This follows from the fact ψ ∗ is monotone thus:
−ψ ∗ (y(u)) ≤ −ψ ∗ (ȳ(ai )),
and −ψ ∗ (ȳ(ai )) < ∞ because if −ψ ∗ (ȳ(ai )) = ∞, then β(ai ) ≥ β̄(ai ) = ∞ which contradicts the
feasibility of (y, β).
Now consider the case when limu→∞ ψ(u) = M for some positive constant M . In this case,
−ψ ∗ ≤ M . We claim that y(ai ) = 0 and lim inf t→∞ y(u) = 0. Suppose lim inf u→∞ y(u) > 0,
then lim supu→∞ β(u) = ∞ since the numerator in the definition of β tends to infinity while
the denominator is bounded. But this contradicts feasibility of (y, β). On the other hand, by the
definition of ai and bi we should have y(ai ) = ȳ(ai ) ≤ lim inf u→∞ y(u). Combining this with
the fact that ȳ(ai ) ∈ dom ψ ∗ ⊂ R+ , we conclude that y(ai ) = 0. Using that y(ai ) = 0 and
lim inf u→∞ y(u) = 0, we get:
Ru
y(s) ds − ψ ∗ (y(u))
lim sup β(u) = lim sup s=0
ψ(u)
u→∞
u→∞
Ru
y(s) ds − ψ ∗ (0)
≥ lim s=0
u→∞
M
R ai
ȳ(s)
ds
−
ψ ∗ (0)
≥ s=0
= lim β̄(u),
(34)
u→∞
M
where in the last inequality we used the fact that ȳ(u) = 0 for u ≥ ai .
Let ψ 0 be the right derivative of ψ. Since ψ is concave, ψ 0 is non-increasing. Therefore, the interval
(ai , bi ) can be written as (ai , u0 ] ∪ [u0 , bi ) such that ψ 0 (u) ≥ ȳ(ai ) on (ai , u0 ] and ψ 0 (u) ≤ ȳ(ai ) on
[u0 , bi ). Since ψ 0 (u) ≥ ȳ(ai ) on (ai , u0 ] we have:
Z u
Z u
ȳ(s) ds =
ȳ(ai ) ds
ai
ai
Z u
≤
ψ 0 (s) ds = ψ(u) − ψ(ai ),
ai

19

for all u ∈ (ai , u0 ]. This yields:
R ai
β̄(ai ) =
≥

ȳ(s) ds − ψ ∗ (ȳ(ai ))
ψ(u)
Ru
R ai
ȳ(s) ds + ai ȳ(s) ds − ψ ∗ (ȳ(ai ))
s=0
s=0

ψ(ai ) + ψ(u) − ψ(ai )

= β̄(u).

for all u ∈ (ai , u0 ]. Here we used the fact that if c1 ≥ c2 > 0 and d2 ≥ d1 ≥ 0, then
c1
c1 + d1
≥
.
c2
c2 + d2
Similarly, we have β̄(bi ) ≥ β̄(u) for any u ∈ [u0 , bi ). Combining this with (31),(32),(33), and (34),
we get:
sup β̄(u) = max(β̄(ai ), β̄(bi ))
ai ≤u≤bi

≤ max(β(ai ), β(bi )) ≤

sup β(u).
ai ≤u≤bi

We conclude that β̄(u) ≤ β(u) for all t ≥ 0 hence (ȳ, β) is a feasible solution for the problem.
Proof of Theorem 2: Let (y, β) be a feasible solution for problem (23). By Lemma 2, we can
assume that y is non-increasing. First, note that y ≥ 0 since dom ψ ∗ = [0, ∞). Define ȳ(u) = y(u)
for u ≤ u0 and ȳ(u) = 0 for u > u0 . We show that (ȳ, β) is also a feasible solution for (23) modulo
the continuity condition. Define
Ru
Ru
y(s) ds − ψ ∗ (y(u))
ȳ(s) ds − ψ ∗ (ȳ(u))
s=0
β(u) =
,
β̄(u) = s=0
.
ψ(u)
ψ(u)
By the definition of ȳ, for all u, we have:
Z u
Z
y(s) ds ≥
0

u

ȳ(s) ds,

(35)

0

and β(u) = β̄(u) for u ∈ [0, u0 ]. Since y(u) is non-increasing and y(u) ≥ 0, limu→∞ y(u) exists.
We claim that limu→∞ y(u) = 0. To see this note that if limu→∞ y(u) > 0, then
Z u
y(s) ds = ∞,
lim
u→∞

s=0

which contradicts the fact that β(u) ≤ β for all u. For all u ≥ u0 , now we have:
Ru
limu→∞ s=0 y(s) ds − ψ ∗ (0)
sup β(u) ≥ lim β(u) =
u→∞
ψ(u0 )
u≥u0
Ru
limu→∞ s=0 ȳ(s) ds − ψ ∗ (0)
= β̄(u0 ),
≥
ψ(u0 )
where the equality follows from the fact that limu→∞ y(u) = 0, and in the last inequality, we used
(35). Since ȳ(u) = 0 for u > u0 , β(u) is constant on [u0 ∞). Therefore, supu≥u0 β̄(u) = β̄(u0 ).
Combining this with the previous inequality we get:
sup β(u) ≥ sup β̄(u0 ).
u≥u0

u≥u0

Therefore, we conclude that β̄(u) ≤ β for all u. Thus (ȳ, β) is also a feasible solution for (23)
modulo the continuity condition. Note that ȳ(u) may not be continuous at u0 . However, we can find
a sequence of continuous functions z (j) that converge pointwise to y and z (i) (u) = 0 for all i and
u ≥ u0 . To do so we consider a sequence of real number i → 0. We define z (i) (u) = ȳ(u) for
u ∈ [0, u0 − i ) ∪ [u0 , ∞). On [u0 − i , u0 ] we define z (i) (u) to be a linear function that take values
y(u0 − ) and 0 on the endpoints. Define
R u (i)
z (s) ds − ψ ∗ (z (i) (u))
βz(i) = sup s=0
.
ψ(u)
u>0
20

By upper semi-continuity of ψ ∗ , βz(i) converges to β̄.
Let β ∗ be the optimal solution for problem (23). By the definition, there exits a feasible sequence
(y (j) , β (j) ) such that β (j) converges to β ∗ . Let ȳ (j) (u) = y (j) (u) for t ≤ u0 and ȳ (j) (u) = 0 for
t > u0 . Note that ȳ (j) (u) may not be continuous at u0 . However, we can find a sequence of continuous
functions (z (ji) , βz(ji) ) as in above. Now βz(jj) converges to β ∗ .

Distance from lp norm ball

B

In this section we prove that the function:
G(u) = −d1 (u, Bp )
satisfies Assumption 1 and find a lower bound on ᾱψ when ψ is given by 16 with G(u) =
−ld1 (u, Bp ).
For any u ∈ Rn+ , there exists ū ∈ Bp such that d1 (u, Bp ) = ku − ūk1 . the subdifferential of distance
function is6 :
∂d1 (u, Bp ) = ∂ ku − ūk1 ∩ NBp (ū),
where NBp (u) = {ξ | hξ, v − ui ≥ 0, ∀v ∈ Bp } is the normal cone of Bp at u. In fact d1 (u, Bp ) =
ku − ūk1 if and only if ∂ ku − ūk1 ∩ NBp (ū) 6= ∅. When u ∈ intBp , ū = u and ∂d1 (u, Bp ) = {0}.
In order to find ∂d1 (u, Bp ) when u ∈
/ intBp , we first find ū in this case. For any r ≥ 0, define
u ∧ r ∈ Rn+ to be:
(u ∧ r)i = min(ui , r) ∀i.
Note that ku ∧ 0kp = 0 and ku ∧ (maxi ui )kp = kukp ≥ 1. Since ku ∧ rkp is a continuous function
of r, by the intermediate value theorem, there exists ru ∈ (0, maxi ui ] such that ku ∧ ru kp = 1.
Now ū = u ∧ r. To see this note that:

∂ ku − ūk1 ∩ NBp (ū) =

∂ ku − ūk1 ∩ NBp (ū) =

1

◦(p−1)



(u ∧ ru )
for ru < max ui ;
i
rup−1

z
◦(p−1)
|0≤z≤1
for ru = max ui ;
p−1 (u ∧ ru )
i
ru

(36)
(37)

where ◦(p−1) denotes element-wise exponentiation. Now if u0 ≤ u, then ru ≤ ru0 since ku ∧ rkp ≥
ku0 ∧ rkp for all r. Thus by (36) and (37), there exists y ∈ ∂d1 (u, Bp ) such that y ≥ ∂d1 (u0 , Bp ).
Now
bound αψ when ψ is given by 16 with G(u) = −ld1 (u, Bp ). Let (v, u) =
Pm we canPlower
m
( t=1 ct x̃t , t=1 Bt x̃t ). Note that by (36) when y ∈ ∂ψ(u) with u ∈
/ Bp , then mini yi = −l. Now
by the definition of l in (17) and the explanation that followed it, we must have u ∈ Bp . If u ∈ intBp ,
then G is differentiable at u and ∇G(u) = 0 which yields αψ (v, u) = 0. Now suppose u ∈ bdBp .
In this case we have:
− kykq
− kykq
G∗ (y)
Pm
αψ (v, u) = min
= min Pn
≥ min
.
y∈∂G(u)
y∈∂G(u) ψ (
y∈∂G(u) θ1T u
t=1 At xt )
t=1 ct x̄t
Recall that θ = mint minx∈Ft

cT
t x
.
1T Bt x

By (37), we have:

min − kykq = −

y∈∂G(u)

l
.
(maxi ui )p−1

Therefore,
αψ (v, u) ≥ −

l
1
.
θ (1T u)(maxi ui )p−1

As u varies on the bdBp , the right hand side is lower bounded by
6

For convex function we use ∂ to denote subdifferential.

21

−l
θ .

This yields αψ ≥ − θl .

C

Derivation of lower bounds on αψ,ψφ

We first derive a general inequality which will be specialized to different examples for bounding
αψ,ψφ . Let K = K1 × K2 , with K1 and K2 two proper cones. Suppose ψ(v, u) = H(v) + G(u),
where H : K1 7→ R is a non-decreasing, and G : K
P2m7→ R is non-increasing and l Lipschitz
continuous. We assume H(v) ≥ θu for all (v, u) ∈ t=1 At Ft . Note that ψ ∗ (z, y) = H ∗ (z) +
G∗ (y). We set





m
X
θ
(e − 1)
1
∗
yi −
log 1 −
yi − (1 + γ)yi ,
φ (y) =
γ
(e − 1)
θ
i=1
Pm
where γ = log(1 + l(e−1)
). We let ψφ(v, u) = H(v) + Gφ(u). Let (v, u) ∈ t=1 At x̃t . Since
θ
ψφ(0) = 0, and the simultaneous algorithm does not decrease the objective,
H(v) + Gφ(u) ≥ ψφ(0) = 0.

(38)

Let (z, y) ∈ ∂ψφ(u), then we have:
˜ i G∗ (y)
ui = ∇i φ∗ (y) + ∇
1
(e − 1)yi
˜ i G∗ (y),
= log(1 −
)−1+∇
γ
θ

(39)

˜ ∗ (y) ∈ ∂G∗ (y). Using the previous identity, we can derive the following upper bound
for some ∇G
for Gφ(u):
Gφ(u) = hy, ui − G∗ (y) − φ∗ (y)
D
E
˜ ∗ (y) − G∗ (y) + hy, ∇φ∗ (y)i − φ∗ (y)
= y, ∇G
˜ ∗ (y)) + φ(∇φ∗ (y))
= G(∇G
m
X
θ
˜ ∗ (y)) +
˜ i G∗ (y) + 1) + 1 1T y
= G(∇G
(ui − ∇
(e − 1) i=1
γ
m

X
1
θ
˜ i G∗ (y)) + 1 1T y.
H(v) +
(1 − ∇
(40)
(e − 1)
(e − 1) i=1
γ
Pm
Now we specialize the bound to the case where G : Rm
+ 7→ R and G(u) = −l
i=1 (ui − 1)+ . We
∗
˜
lower bound αψ,ψφ (v, u) when u ≤ 1. In that case, (39) is satisfied with ∇i G (y) = 1. Thus from
(40) simplifies to:
1
1
Gφ(u) ≤
H(v) + 1T y.
(41)
(e − 1)
γ
˜ ∗ (y)) +
≤ G(∇G

Combining this with (38), we get:
H(v) + G(u) = H(v) ≥

(1/e − 1) T
1 y.
γ

(42)

In the view of definition of αψ,ψφ , by using (41) and the fact that G∗ (y) = 1T y, we derive the
following inequality:
1
1
H(v) + Gφ(u) − G∗ (y) ≤ (1 +
)H(v) + ( − 1)1T y.
(43)
e−1
γ
Combining (42) and (43), we get the following lower bound on αψ,ψφ :
αψ,ψφ (v, u) ≥ 1 − (1 +

1
)γ + ᾱH .
e−1

(44)

Online LP: In this problem,
ψ

m
X
t=1

!
At x t

=

m
X

cTt xt

t=1

+G

m
X
t=1

22

!
Bt xt

,

(45)

Pn
with G(u) = −l i=1 (ui − 1)+ . In this problem H(v) = v is the identity function.
Pm
Pm
Let (ṽ, ũ) = ( t=1 cTt x̃t , t=1 Bt x̃t ). If ỹt,i ≤ −l for some t and i, then by the definition of l
in (17) and the explanation that followed it, we have (Bt x̃t )i = 0. On the other hand, we have
∇i Gφ(u) ≤ −l when ũi ≥ 1. Therefore, we conclude that ũ ≤ 1. Also, by the definition of θ, we
have H(ṽ) ≥ θ1T ũ. Since H is a linear function, αH = 0. Thus (44) yields
αψ,ψφ (ṽ, ũ) ≥ 1 − (1 +

1
)γ.
e−1

(46)

Online graph formation and online Experiment design : In this problem, H(U ) = log det(U +
A0 ) − log det(A0 ), G(u) = −l(b − u)+ and At x = (aTt at x, x).
We can use the following identity for determinant of rank one update of a matrix
det(A + vv T ) = det(A)(1 + v T A−1 v T ),
to derive a lower bound on log det(U + A0 ) − log det(A0 ),
H(U ) = log det(U + A0 ) − log det(A0 )
=

m
X

log det(A0 +

s=1

=

m
X

s
X

at aTt x̃t )

− log det(A0 +

t=1

s−1
X

at aTt x̃t )

t=1

log(1 + aTt Ỹt at x̃t )

t=1

≥ log(1 +

m
1 X
)
x̃t = θu.
n t=1

Pm
Pm
Let (Ũ , ũ) = ( t=1 at aTt x̃t , t=1 x̃t ). If ỹt ≤ −l for some t, then by the definition of l in (22),
aTt Ỹt at + ỹt < 0 which results in x̃t = 0. Given the fact that Gφ0 (u) = −l when u ≥ b, we
conclude that ũ ≤ b. Therefore, by (44), we get
αψ,ψφ (Ũ , ũ) ≥ −(1 +

23

1
)γ.
e−1

