Introduction

Consider a primal-dual pair of convex optimization problems of the form

(P 0 ) v = inf {(c, x) : g(x) 0},(1)(P * 0 ) v * = sup u 0 inf x {(c, x) + ug(x)},(2)

where c, x ∈ R n , g : R n → R is a convex function, (•, •) denotes the dot product of two vectors, v, v * denote the optimal values of the primal (P 0 ) and dual problems (P * 0 ), respectively. A duality gap plays an important role both in theoretical and numerical analysis of the problems (P 0 ), (P * 0 ). The duality gap is determined by the following formula:

δ = v − v * 0.

Two cases are distinguished: a zero duality gap(δ = 0) and a nonzero duality gap(δ > 0). Traditionally, results are formulated under the assumption that the duality gap is zero. However, it is known that the zero duality gap is satisfied only for limited class of optimization problems, for example, satisfying the Slater condition, and in general the duality gap may turn out to be nonzero. Theoretical approaches to the characterization of duality gap in convex programming are discussed in articles [Chames, 1962], [Champion, 2004], [Ban, 2009], [Borwein, 2014]. It is important to note that the analysis of duality gap in practice with these approaches may be difficult due to the nontriviality of the corresponding characterizations. This circumstance requires new approaches for duality gap analysis in optimization problems.

The aim of this paper is to propose an approach to finding the set of target vectors c with the nonzero duality gap between (P 0 ) and (P * 0 ). We denote this set as

DG = {c ∈ R n : δ > 0}.

A theoretical approach to problem solving was presented in the previous work [Trofimov, 1992]. In this approach, a convex set is constructed for an arbitrary point x 0 from the feasible set of problem (P 0 )

T 1 (x) = lim n→∞ ∂ 1 (n • g(x)),

where ∂ ε f (x 0 ) denotes epsilon-subdifferential of the f at x 0 .

Recall [Rockafellar, 1972] that the gauge γ(•|T ) of set T is defined by

γ(x|T ) = inf{µ > 0|µ −1 • x ∈ T }.

Then by [Trofimov, 1992, Theorem

, Corollary 1] v = (c, x 0 ) − γ(c| − clT 1 (x 0 )), v * = (c, x 0 ) − γ(c| − T 1 (x 0 ))

and consequently

DG = {c : γ(c| − T 1 (x 0 )) − γ(c| − clT 1 (x 0 )) > 0}.

Thus, the set DG of target vectors with nonzero duality gap characterizes the closure property of the surface of some convex set T 1 . At the same time, the vectors c ∈ DG correspond to points from the non-closed part of the boundary T 1 . Applying the described approach for finding the set DG is difficult because the procedure for finding the set T 1 is nontrivial.

Note that the situation is similar for a semi-infinite linear programming problem (SILP). SILP is linear optimization problem in which either the dimension of the decision space or the number of constraints (but not both) is infinite. In particular, SILP deals with problem of the form:

(L) v = inf{(c, x) : (a α , x) ≤ b α , ∀α ∈ Ω}, where Ω is an infinite index set, c ∈ R n , a α ∈ R n , b α ∈ R.

The model (L) naturally arises in an abundant number of applications in different fields of mathematics and engineering [Goberna, 2002]. It is known that convex problem can be reformulated as SILP.In SILP the duality gap is characterized by the nonclosed boundary of the conic hull K = cone{[a α ; b α ], [0 n ; 1] : α ∈ Ω} of the coefficients of the semi-infinite constraint system. The sets T 1 and K have similar properties: they allow us to find the optimal values of v and v * , determine the attainability of these values and in some cases find optimal solutions for dual problems. However, the convex and possibly nonclosed cone K ⊂ R n+1 in SILP corresponds to the set T 1 ⊂ R n . The set DG may have a complex structure: the DG is not convex or closed, and there may be very many target vectors with nonzero duality gap. In [Astaf'ev, 2017], an example is given where the dimension of the relative interior of DG is only one less than the number of variables (n).

On the other hand, it is well known that the existence of duality gap is closely related to the study of the ε-perturbed problems (P ε ) given by

(P ε ) v(ε) = inf {(c, x) : g(x) ε} ,

where ε is a positive parameter, v(ε) denotes perturbation function of problem (P 0 ). The existence of nonzero duality gap is equivalent to the fact that v(ε) is not lower semi-continuous at the origin [Rockafellar, 1970].

In this work, we propose a new approach for finding the set DG, which is based on an infinitesimal analysis of the perturbation function v(ε). The approach presupposes finding the order of smallness and the proportionality coefficient of an infinitely small quantity (ISQ), which represents the difference between the perturbation function v(ε) and the optimal value v = v(0) of the original problem (P 0 ).

The optimal value of the dual problem and the duality gap are determined by the limit of the optimal values of the ε-perturbed primal problem. It is clear that the ε-perturbed constraints lead to an extension of the feasible set of the primal problem. The degree of expansion of the feasible set can be study in several ways: by a given target direction c (point approach) and by the shift value of the supporting plane v = (c, x) (integral approach). We consider the second method, which leads to the optimal value of the dual problem. This method generates infinitesimals. As a rule, ISQs have the integer orders of smallness, i.e. have the corresponding integer derivatives. In some cases, infinitesimals appear in which the exponents of the power series form arithmetic progression. We propose a method for study the duality gap, in which the ISQ with the highest monomial with a fractional exponent appears.

We also apply the method to study the quality of a geometric domain, considered as the feasible set F of problem (P 0 ). The quality of the geometric domain is determined by the existence of duality gap on certain target directions c. If the geometric domain is unbounded, then we are dealing with the classical problem of convex nonlinear programming with duality gap. In the case of boundedness of the geometric domain, we propose to determine the quality by the order of smallness of the perturbation function v(ε) for small perturbations ε. If the orders of smallness for all directions are the same, the geometric domain quality is good. Thus, the duality gap is generalized from the case of an unbounded feasible set to the case of a bounded feasible set. In the paper, we apply the method for study the quality of the geometric domain

F = {x ∈ R 2 : −x 1 + √ x 2 1 + x 2 2 0}.

The paper is organized as follows. In Section 2 we introduce the notion of log-image and define an analytical representation of the log-image. Section 3 is devoted to an exposition of the method of finding the ISQ characteristics using the asymptotic properties of the logarithm of given function. In Section 4 we present an algorithm for computing the above ISQ characteristics. The algorithm is based on the procedure of identifying the asymptote coefficients of the ISQ logarithmic characteristic. The algorithm uses processing of points of the logarithmic characteristic with a sliding window and subsequent clustering. The main result on the connection between the duality gap and ISQ characteristics (theorem 2) is given in Section 5. In Section 6 the proposed approach is applied for numerical example. We end the paper with conclusions and an outlook on future work.

Analytical Representation of Log-Images

Let us remind that the function f (x) is called infinitely small quantity or infinitesimal as

x → +0 if lim x→0 f (x) = 0.

For a given infinitesimal y = f (x), we call function g(x) the log-image (name by analogy, for example, with Laplace image): ỹ = g(x), where x = lg x, ỹ = lg |y|.

Note the following simple properties of log-images:

i) Cg 1 (x) ↔ f 1 (x) C , C = const. ii) C + g 1 (x) ↔ 10 C f 1 (x), C = const. iii) g 1 (x) + g 2 (x) ↔ f 1 (x)f 2 (x). iiii) g 1 (x)g 2 (x) ↔ f 2 (x) lg f1(x) = f 1 (x) lg f2(x) .

The property i) follows from obvious relation

Cg 1 (x) = Clg f 1 (x) = lgf 1 (x) C .

Properties ii)-iiii) are proved similarly. Note that the operations of the sum and the product of log-images are commutative.

Thus, the arithmetic operations on the ISQ log-images correspond to certain operations on the ISQ originals.

The log-image is the main tool in our approach to find ISQ characteristics. Later we will show that the log-image can be constructed numerically using a table-defined function. In this case, the use of numerical logimage for finding ISQ characteristics can lead to significant errors. We show that the log-image can be obtained analytically. This makes it possible to avoid numerical errors in determining ISQ characteristics.

Let φ(x) be a continuous monotone function defined on the set X ∈ R with the range

Y ∈ R. It has the inverse function φ −1 , i. e. φ ( φ −1 (x) ) = ( φ • φ −1 ) (x) = x for every x ∈ X.

We take an arbitrary function f (x) : X → X and for f (x) construct a functional Φ(f ) as follows:

g = Φ(f ), if g = φ • f • φ −1 .

(3)

The function g is defined on the set Y with the range Y . From definition (3) it follows that f = φ −1 • g • φ. Take for the function φ(x) the decimal logarithm: φ(x) = lg x. Then

φ −1 (x) = 10 x , X = R + = {x : x > 0} , Y = R.

Suppose that the function g(x) is a log-image of the function f (x). Then for all x ∈ X we have lg f

(x) = g (lg x), Φ • f = g • φ.

Hence, we obtain an analytic representation of the log-image g of the function f :

g = φ • f • φ −1 = Φ(f ), g (x) = lg f ( 10 x)

.

(4)

For the original f (x), we similarly obtain

f = φ −1 • g • φ = Φ −1 (g), f (x) = 10 g(lg (x)) .

Applying (4), one can obtain ISQs with infinitely small and infinitely large order of smallness. An example of ISQ with infinitely small order of smallness is the function:

f (x) = 10 − √ −lg x , 0 < x < 1, g(x) = − √ −x, x < 0.

An example of ISQ with infinitely large order of smallness is the function:

f (x) = 10 −lg 2 x , 0 < x < 1, g(x) = −x 2 , x < 0.

Asymptotic Method for Determining the Characteristics of Infinitesimals

Recall that an order of smallness of ISQ is a minimal positive number p (if it exists) for which there exists a finite limit

b = lim x→0 f (x) x p , b ̸ = 0.

(5) Definition (5) does not provide a constructive way of finding p, since p is not known in advance. We give a numerical method for calculation the order of smallness.

Without loss of generality, we assume that the ISQ f (x) > 0 for x > 0.

Suppose that the ISQ log-image ỹ = g(x) has a slant asymptote ỹ = a + kx, (

where a and k are asymptote coefficients.

It is known that these coefficients are determined by the formulas

a = lim x→−∞ [g(x) − kx], (7) k = lim x→−∞ g(x) x , (8)

if these limits exist.

The following theorem is valid Theorem 1 ([Trofimov, 2015, p. 14]). ISQ f (x) has the order of smallness p if and only if the ISQ log-image has a left slant asymptote ỹ = a + kx, where a and k are asymptote coefficients, wherein p = k, a = lg b.

Proof. The theorem follows from the representation of the ISQ f (x) in the form

f (x) ≈ Cx p + o(x p ). Then lg f (x) ≈ lg C + plg x,

or making the substitution x = lg x, ỹ = lg f (x), a = lg C, k = p, we obtain ỹ ≈ a + kx.

It follows from Theorem 1 that ISQ characteristics can be found from the analytical formulas ( 7)-( 8) if the function g is given analytically(see ( 4)).

The main disadvantage of the asymptotic method is that it is necessary to analytically calculate the limits ( 7)-( 8) for finding ISQ characteristics. In the next section, we will consider a numerical method for identifying the coefficients of the logarithmic asymptote (6).

Clustering Method for Finding Characteristics of Infinitesimals

As follows from Theorem 1, the order of smallness and the proportionality coefficient of the ISQ are determined by the parameters k and a of the asymptote (6) of the ISQ log-image. The linear nature of the dependence ỹ(x) allows us to reduce the problem of finding the parameters k and a to estimate the linear regression parameters. To solve the latter problem, the ordinary least squares method (OLS) can be used. The classical version of OLS reduces to the solution of a certain system of linear algebraic equations ( ( X, 1) m ( X, X) ( X, 1)

) ( a k ) = ( ( Ỹ , 1) ( X, Ỹ ) ) , (9)

where m denotes the number of variable values pairs (x i , ỹi ), i = 1, 2, . . . , m, X = (x 1 , x2 , . . . , xm ), Ỹ = (ỹ 1 , ỹ2 , . . . , ỹm ). However, applying the OLS method to a real data set ( X, Ỹ ) can lead to significant errors in the estimates of a and k. First of all, this is due to the errors in setting the initial ISQ, and hence the ISQ log-image. In our case, the errors arise in the numerical solution of ε-perturbed problems P ε , i.e. when the perturbation function v(ε) is calculated. In connection with this, it is required to develop other methods of reliable determination of the coefficients a and k.

In this section, we propose an approach to constructing a numerical method that approximately finds the coefficients a and k of the logarithmic asymptote (6). This approach consists of two steps. The first step is to divide points of the logarithmic characteristic with windows of predefined size and calculate linear approximations of a and k on each window. The second step is to cluster result approximations {a, k} with k-means clustering method. As estimates of a and k we take the centers of these clusters.

The outline of the algorithm can be summarized as follows Algorithm 1 Clustering Algorithm for Finding Characteristics of Infinitesimals

1: procedure Clustering(X, Y , w) Input : A sequence of n numbers X = [x 1 , . . . , x n ]; A sequence of n numbers Y = [y 1 , . .

. , y n ];

A value w is slice window width; Output :

A coefficient of proportionality b; An order of smallness p; Initialization

2:

Let n is the number elements of input array X Ỹi ← (ỹ i , ỹi+1 , . . . , ỹi+w−1 ) 12:

for i ← 1, n do 5: X[i] ← lg X[i] 6: Ỹ [i] ← lg Y [i](a i , k i ) ← OLS( Xi , Ỹi )

◃ Call Ordinary Least Square Procedure return (b, p) ◃ The Characteristics of Infinitesimal 19: end procedure When we have two clusters it means that the logarithmic characteristics has two asymptotes: the main and secondary. So that the next order of smallness comes out. For example, for infinitesimal y(x) = 1 2 x

1 3 + 1 2 x 1 2

method finds a ≈ −0.25 and k ≈ 0.34. So b ≈ 0.55 and p ≈ 0.34.

Connection Between the Duality Gap and Infinitesimals

We now formulate a theorem relating the duality gap to the order of smallness of the perturbation function v(ε) of the convex problem. Further, without loss of generality, we assume that v = v(0) = 0. Denote primal problem (P 0 ) with the target vector c m by P 0,m and the dual problem (P * 0 ) with the target vector c m by P * 0,m Consider the sequence of target vectors {c m }, for which the duality relation v m = Inf(P 0,m ) = Sup(P * 0,m ) = v * m holds, i.e. c m / ∈ DG. For example, we can take c m from the relative interior of the cone T 1 [Trofimov, 1992, Corollary 3]. We denote by p m and b m the order of smallness and the coefficient of proportionality of the perturbed function of (P 0,m ) with the target vector c m .

Let p and b be analogous parameters of the perturbed function v(ε) of (P 0 ) for the target vector c with nonzero duality gap. The following theorem is valid Theorem 2. Let {c m } → c ∈ DG. Suppose that the duality relation holds for the vectors {c m }. Suppose also that for every m dual problems (P 0,m ) and (P * 0,m ) with target vector c m have unique solutions. Then starting with a certain number, the sequence {p m } is constant and equal to 1, and the sequence {b m } → +∞ and p = 0.

Proof. By [Rockafellar, 1972, Theorem 29.1], we have u

* m = −v ′ m (ε) | ε=0 . Hence v m (ε) = v m (0) − u m (ε) * • ε + o(ε). (10) and, consequently p m = 1. Since c ∈ DG, then 0 = v(0) > v * (0). Hence v(ε) is not ISQ, since lim ε→0 v(ε) = v * (0) < v(0) = 0,(11)

and, consequently p = 0. Since

lim ε→0 v(ε) ε 0 = lim ε→0 v(ε) = v * , then b = v * ̸ = 0.

Since the perturbation function v c (ε) is continuous with respect to the vector c for any ε 0, then we have

lim m→∞ v m (ε) = v(ε) (12)

and lim

m→∞ v m (0) = v(0). (13)

It follows from ( 10), ( 12), ( 13), ( 11) that ∀ε > 0

lim m→∞ u * m (ε) • ε = ε • lim m→∞ u * m (ε) = −v(ε) > 0.

Then we have

lim m→∞ u * m (ε) = − v(ε) ε > 0.

and consequently lim

b m = lim m→∞ [ lim ε→0 u * m (ε) ] = lim ε→0 [ lim m→∞ u * m (ε) ] = +∞.

Theorem 2 allows us to construct a numerical algorithm for finding the target vectors c, for which a nonzero duality gap exists in the convex optimization problem.

Numerical Example

Consider the following convex optimization problem

f (x 1 , x 2 ) = c 1 x 1 + c 2 x 2 → min subject to g(x 1 , x 2 ) = −x 1 + √ x 2 1 + x 2 2 0.

Problem with similar constraint is considered in the papers [Karney, 1982], [Champion, 2004].

The feasible set of the unperturbed problem is a ray F = {x : x = (t, 0), t 0} .

For the target vectors c 1 = (1, 1), c 2 = (0, ±1) and c 3 = (−1, −1), we have the following duality relations:

v c 1 = v * c 1 = 0; v c 2 = 0, v * c 2 = −∞; v c 3 = −∞, v * c 3 = − ∞.

Along with this problem, we consider the ε-perturbed problem for ε > 0

f (x 1 , x 2 ) = c 1 x 1 + c 2 x 2 → min (= v(ε)) subject to g(x 1 , x 2 ) = −x 1 + √ x 2 1 + x 2 2 ε,

and additional constraints that ensure the compactness of feasible set

x 1 5, x 2 5.

It is known that optimal value v(ε) is finite for convex optimization problem with bounded feasible set. Then [Eremin, 1976, p. 100] For the case of the classical duality gap (the vector c 2 ), we obtain p = 0.5. Thus, the difference in the order of smallness of the perturbation function for different target directions is directly related to the duality gap and the quality of the constraints of a compact feasible set.