Open Access
Access granted
Subscription Access
Vol 303, No Suppl 1 (2018)
- Year: 2018
- Articles: 25
- URL: https://journals.rcsi.science/0081-5438/issue/view/10771
Article
High Accuracy Algorithms for Approximation of Discontinuity Lines of a Noisy Function
Abstract
We consider the problem of localizing (finding the position of) discontinuity lines of a noisy function of two variables. Such problems arise in image processing, because the boundaries of objects are often discontinuity lines. It is assumed that the function of two variables is smooth in a neighborhood of discontinuity lines and has discontinuity of the first kind at each point of these lines. Instead of the exact function, its approximation in the space L2 and the measurement error level δ are known. In this case, the problem belongs to the class of nonlinear ill-posed problems, and regularization algorithms should be constructed for its solution. We construct and study regularizing discrete algorithms of averaging “with a turn.” New rules are proposed for choosing regularization parameters, and the methods of deriving localization error bounds are improved. Error bounds are found for the localization of singularities of order O(δ4/3) under stricter separability conditions: the separability threshold in the present paper has order O(δ2/3), whereas in the authors’ previous papers devoted to this problem the bounds for the localization error and separability threshold have order O(δ). In addition, the discretization of the algorithms of averaging “with a turn” is investigated theoretically for the first time (conditions for the discretization step are specified).
1-11
Classification of Links of Small Complexity in the Thickened Torus
Abstract
We present a complete table of links in the thickened torus T2 × I of complexity at most 4. The table is constructed by the following method. First, we enumerate all abstract quadrivalent graphs with at most four vertices. Then we consider all inequivalent embeddings of these graphs in the torus. After that each vertex of each of the obtained graphs is replaced by a crossing of one of two possible types specifying the over-strand and the under-strand. The words “over” and “under” are understood in the sense of the coordinate of the corresponding point in the interval I. As a result, we obtain a family of link diagrams in the torus. We propose a number of artificial tricks that essentially reduce the enumeration and help to prove rigorously the completeness of the table. We use a generalized version of the Kauffman polynomial to prove that the obtained links are pairwise inequivalent.
12-24
Three Extremal Problems in the Hardy and Bergman Spaces of Functions Analytic in a Disk
Abstract
Let a nonnegativemeasurable function γ(ρ) be nonzero almost everywhere on (0, 1), and let the product ργ(ρ) be summable on (0, 1). Denote by B = Bγp, q, 1 ≤ p≤ ∞, 1 ≤ q < ∞, the space of functions f analytic in the unit disk for which the function Mpq (f, ρ)ργ(ρ) is summable on (0, 1), where Mp(f, ρ) is the p-mean of f on the circle of radius ρ; this space is equipped with the norm
For a pair of such operators L and G, under some constraints, the following three extremal problems are solved.
The best approximation of the class (1) by the class \(LB_\gamma ^{{p_1},{q_1}}(1)\) by the class \(GB_\gamma^{p_{3}, q_{3}}(N)\) in the norm of the space \(B_\gamma^{p_{2}, q_{2}}\) is found for 2 ≤ p1 ≤ ∞, 1 ≤ p2 ≤ 2, 1 ≤ p3 ≤ 2, 1 ≤ q1 = q2 = q3 ≤ ∞, and qs = 2 or ∞.
The best approximation of the operator L by the set L(N), N > 0, of bounded linear operators from \(B_\gamma ^{{p_1},{q_1}}\) to \(B_\gamma ^{{p_2},{q_2}}\) with the norm not exceeding N on the class \(GB_\gamma ^{{p_3},{q_3}}\) (1) is found for 2 ≤ p1 ≤∞, 1 ≤ p2 ≤ 2, 2 ≤ p3 ≤ ∞, 1 ≤ q1 = q2 = q3 ≤ ∞, and qs = 2 or ∞.
Bounds for the modulus of continuity of the operator L on the class \(GB_\gamma ^{{p_1},{q_1}}\) (1) are obtained, and the exact value of the modulus is found in the Hilbert case.
25-35
Constrained Optimization Methods for the Sensitivity Function
Abstract
We consider a parametric family of convex programs, where the parameter is the vector of the right-hand sides in the functional constraints of the problem. Each vector value of the parameter taken from the nonnegative orthant corresponds to a regular (Slater’s condition) convex program and the minimum value of its objective function. This value depends on the constraint parameter and generates the sensitivity function. We consider the problem of minimizing the implicit sensitivity function on a convex set given geometrically or functionally. This problem can be interpreted as a convex program in which, instead of a given vector of the right-hand sides of functional constraints, only a set to which this vector belongs is specified. As a result, we obtain a two-level problem. In contrast to the classical two-level hierarchical problems with implicitly given constraints, it is objective functions that are given implicitly in our case. There is no hierarchy in this problem. As a rule, sensitivity functions are discussed in the literature in a more general context as functions of the optimum. The author does not know optimization statements of these problems as independent studies or, even more so, solution methods for them. A new saddle approach to the solution of problems with sensitivity functions is proposed. The monotone convergence of the method is proved with respect to the variables of the space in which the problem is considered.
36-44
Modified Bernstein Function and a Uniform Approximation of Some Rational Fractions by Polynomials
Abstract
P. L. Chebyshev posed and solved (1857, 1859) the problem of finding an improper rational fraction least deviating from zero in the uniform metric on a closed interval among rational fractions whose denominator is a fixed polynomial of a given degree m that is positive on the interval and whose numerator is a polynomial of a given degree n ≥ m with unit leading coefficient. In 1884, A.A.Markov solved a similar problem in the case when the denominator is the square root of a given positive polynomial. In the 20th century, this research direction was developed by S.N.Bernstein, N. I.Akhiezer, and other mathematicians. For example, in 1964, G. Szegő extended Chebyshev’s result to the case of trigonometric fractions using the methods of complex analysis. In this paper, using the methods of real analysis and developing Bernstein’s approach, we find the best uniform approximation on the period by trigonometric polynomials of a certain order for an infinite series of proper trigonometric fractions of a special form. It turned out that, in the periodic case, it is natural to formulate some results in terms of the generalized Poisson kernel Πρ,ξ(t) = (cosξ)Pρ(t) + (sinξ)Qρ(t), which is a linear combination of the Poisson kernel Pρ(t) = (1 − ρ2)/[2(1 + ρ2 − 2ρ cos t)] and the conjugate Poisson kernel Qρ(t) = (ρ sin t)/(1 + ρ2 − 2ρ cos t), where ρ ∈ (−1, 1) and ξ ∈ R. We find the best uniform approximation on the period by the subspace Tn of trigonometric polynomials of order at most n for the linear combination Πρ,ξ(t) + (−1)nΠρ,ξ(t + π) of the generalized Poisson kernel and its translation. For ξ = 0, this yields Bernstein’s known results on the best uniform approximation on [−1, 1] of the fractions 1/(x2 − a2) and x/(x2 − a2), |a| > 1, by algebraic polynomials. For ξ = π/2, we obtain the weight analogs (with the weight \(\sqrt {1 - {x^2}} \)x2) of these results. In addition, we find the value of the best uniform approximation on the period by the subspace Tn of a special linear combination of the mentioned Poisson kernel Pρ and the Poisson kernel Kρ for the biharmonic equation in the unit disk.
45-59
Asymptotics of a Solution to a Singularly Perturbed Time-Optimal Control Problem
Abstract
In the study of singularly perturbed optimal control problems, asymptotic solutions of the boundary value problems resulting from the optimality condition for the control are constructed using the well-known and well-developed method of boundary functions. This approach is effective for problems with smooth controls from an open domain. Problems with a closed bounded domain of control have been less thoroughly investigated. The cases usually considered involve situations where the control is a scalar function or a multidimensional function with values in a convex polyhedron. In the latter case, since the optimal control is a piecewise constant function with values at the vertices of the polyhedron, it is important to describe the asymptotic behavior of switching points of the optimal control. In this paper, we investigate a time-optimal control problem for a singularly perturbed linear autonomous system with smooth geometric constraints on the control in the form of a ball. The main difference between this case and the case of systems with fast and slow variables studied earlier is that the matrix at the fast variables is a multidimensional analog of the second-order Jordan cell with zero eigenvalue and, thus, does not satisfy the standard condition of asymptotic stability. The solvability of the problem is proved. Power asymptotic expansions of the optimal time and optimal control in a small parameter at the derivatives in the equations of the system are constructed and justified.
60-69
Preservation of the Coincidence Point Existence Property under Some Discrete Transformations of a Pair of Mappings of Metric Spaces
Abstract
In topology, there are known results on preservation of the fixed point existence property under any homotopy of self-mappings on some spaces in the event that the initial mapping has a nonzero Lefschetz number. For contracting mappings of metric spaces and some of their generalizations, there are known results by M. Frigon on preservation of the contraction property and, consequently, the fixed point existence property under some special homotopies. In 1984, J.W.Walker introduced a discrete counterpart of homotopy for self-mappings of an ordered set, which he called an order isotone homotopy. The naturalness of this notion and its relation to the usual continuous homotopy follow from the work by R. E. Stong (1966). Recently, the author and D. A.Podoprikhin have extended Walker’s notion of an order isotone homotopy and suggested sufficient conditions for preservation of the fixed point (coincidence point) existence property under such discrete homotopy (a pair of homotopies) of a mapping (a pair of mappings) of ordered sets. This paper contains metric counterparts of the obtained results and some corollaries. The method of ordering a metric space proposed by A. Brøndsted in 1974 is used.
79-86
Contact Resistance of a Square Contact
Abstract
We consider a conductive body in the form of a parallelepiped with small square contacts attached to its ends. The potential of the electric current is modeled by a boundary value problem for the Laplace equation in a parallelepiped. The zero normal derivative is assigned on the boundary except for the areas under the contacts, where the derivative is a nonzero constant. Physically, this condition corresponds to the presence of a low-conductivity film on the surface of the contacts. The problem is solved by separation of variables, and then the electrical resistance is found as a functional of the solution in the form of the sum of a double series. Our main aim is to study the dependence of the resistance on a small parameter characterizing the size of the contacts. The leading term of the asymptotics that expresses this dependence is the contact resistance. The mathematical problem is to treat the singular dependence of the sum of the series corresponding to the resistance on the small parameter: the series diverges as the small parameter vanishes. We solve this problem by replacing the series with a two-dimensional integral. We find the leading term of the asymptotics and estimate the remainder. It turns out that the main contribution to the remainder is made by the difference between the two-dimensional integral and the double sum.
70-78
An Optimal Algorithm for an Outerplanar Facility Location Problem with Improved Time Complexity
Abstract
We consider a network facility location problem with unbounded production levels. This problem is NP-hard in the general case and is known to have an optimal solution with quadratic complexity on a tree network. We study the case of a network representable by an outerplanar graph, i.e., by a graph whose vertices belong to one (outer) face. This problem is known to have an optimal algorithm with time complexity O(nm3), where n is the number of vertices and m is the number of possible facility locations. Using some properties of outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally connected service areas, we obtain recurrence relations for the construction of an optimal algorithm with time complexity that is smaller by a factor of \(\sqrt m \) than the time complexity of the earlier algorithm.
87-93
Equivalence of the Existence of Nonconjugate and Nonisomorphic Hall π-Subgroups
Abstract
Let π be some set of primes. A subgroup H of a finite group G is called a Hall π-subgroup if any prime divisor of the order |H| of the subgroup H belongs to π and the index |G: H| is not a multiple of any number in π. The famous Hall theorem states that a solvable finite group always contains a Hall π-subgroup and any two Hall π-subgroups of such group are conjugate. The converse of the Hall theorem is also true: for any nonsolvable group G, there exists a set π such that G does not contain Hall π-subgroups. Nevertheless, Hall π-subgroups may exist in a nonsolvable group. There are examples of sets π such that, in any finite group containing a Hall π-subgroup, all Hall π-subgroups are conjugate (and, as a consequence, are isomorphic). In 1987 F. Gross showed that any set π of odd primes has this property. In addition, in nonsolvable groups for some sets π, Hall π-subgroups can be nonconjugate but isomorphic (say, in PSL2(7) for π = {2, 3}) and even nonisomorphic (in PSL2(11) for π = {2, 3}). We prove that the existence of a finite group with nonconjugate Hall π-subgroups for a set π implies the existence of a group with nonisomorphic Hall π-subgroups. The converse statement is obvious.
94-99
The Direct Theorem of the Theory of Approximation of Periodic Functions with Monotone Fourier Coefficients in Different Metrics
Abstract
In the lower bound in equality (a), the second term nσωl(f; π/n)p generally cannot be omitted. However, if the sequence {ωl(f; π/n)p}n=1∞ or the sequence {En−1(f)p}n=1∞ satisfies Bari’s (Bl(p))-condition, which is equivalent to Stechkin’s (Sl)-condition, then
The upper bound in equality (b), which holds for every function \(f \in L_p(\mathbb{T})\) if the series converges, is a strengthened version of the direct theorem. The order equality (b) shows that the strengthened version is order-optimal on the whole class \(M_p(\mathbb{T})\).
100-114
Sample Average Approximation in a Two-Stage Stochastic Linear Program with Quantile Criterion
Abstract
A two-stage stochastic linear program with quantile criterion is considered. In this problem, the first stage strategy is deterministic and the second stage strategy is chosen when a realization of the random parameters is known. The properties of the problem are studied, a theorem on the existence of its solution is proved, and a sample average approximation of the problem is constructed. The sample average approximation is reduced to a mixed integer linear program, and a theorem on their equivalence is proved. A procedure for finding an optimal solution of the approximating problem is suggested. A theorem on the convergence of discrete approximations with respect to the value of the objective function and to the optimization strategy is given. We also consider some cases not covered in the theorem.
115-123
Painlevé II Equation As a Model of a Resonant Interaction of Oscillators
Abstract
We consider a system of differential equations that describes the interaction of two weakly coupled nonlinear oscillators. The initial data are such that, in the absence of coupling, the first oscillator is far from equilibrium, the second oscillator is near equilibrium, and their natural frequencies are close to each other. We study the resonance capture phenomenon, when the frequencies of the coupled oscillators remain close and the amplitudes of their oscillations undergo significant time variations; in particular, the second oscillator moves far away from the equilibrium. We find that the initial stage of the resonance capture is described by a solution of the second Painlevé equation. The description is obtained under an asymptotic approximation with respect to a small parameter corresponding to the coupling factor.
124-135
Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster
Abstract
We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of a fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm implements a polynomial-time approximation scheme (PTAS).
136-145
Computational Complexity for the Problem of Optimal Intersection of Straight Line Segments by Disks
Abstract
Computational complexity and exact polynomial algorithms are reported for the problem of stabbing a set of straight line segments with a least cardinality set of disks of fixed radii r > 0, where the set of segments forms a straight line drawing G = (V,E) of a plane graph without edge crossings. Similar geometric problems arise in network security applications (Agarwal et al., 2013). We establish the strong NP-hardness of the problem for edge sets of Delaunay triangulations, Gabriel graphs, and other subgraphs (which are often used in network design) for r ∈ [dmin, ηdmax] and some constant η, where dmax and dmin are the Euclidean lengths of the longest and shortest graph edges, respectively.
146-155
Quasoids in Knot Theory
Abstract
This paper is devoted to the definition and construction of quasoids, which are algebraic objects generating invariants of oriented knots and links. Such an invariant can be expressed in terms of the number of proper colorings of the regions into which a knot diagram divides the 2-sphere. A coloring with elements of a set X is proper if the colors of all four regions in a neighborhood of each crossing point of the diagram are matched by means of a function Q: X×X×X → X. This function is called a quasoid over the set X. In this paper,we construct two infinite series of quasoids. The first series is formed by linear quasoids over finite rings. The second series consists of quasoids generated by finite biquasiles. The invariants of knots and links generated by quasoids are nontrivial and can be used to distinguish knots. We show that all knots and links admitting diagrams with at most six crossings are distinguished by linear quasoids over ℤn, where n ≤ 11. We give results of the computer enumeration of all different quasoids over sets whose cardinality does not exceed 4.
156-165
On Automorphisms of a Distance-Regular Graph with Intersection Array {69, 56, 10; 1, 14, 60}
Abstract
Let Γ be a distance-regular graph of diameter 3 with eigenvalues θ0 > θ1 > θ2 > θ3. If θ2 = −1, then the graph Γ3 is strongly regular and the complementary graph \({\bar \Gamma _3}\) is pseudogeometric for pGc3(k, b1/c2). If Γ3 does not contain triangles and the number of its vertices v is less than 800, then Γ has intersection array {69, 56, 10; 1, 14, 60}. In this case Γ3 is a graph with parameters (392, 46, 0, 6) and \({\bar \Gamma _2}\) is a strongly regular graph with parameters (392, 115, 18, 40). Note that the neighborhood of any vertex in a graph with parameters (392, 115, 18, 40) is a strongly regular graph with parameters (115, 18, 1, 3) and its existence is unknown. In this paper, we find possible automorphisms of these strongly regular graphs and automorphisms of a hypothetical distance-regular graph with intersection array {69, 56, 10; 1, 14, 60}. In particular, it is proved that the latter graph is not ar-ctransitive.
166-174
Uniform Approximation by Perfect Splines
Abstract
The problem of uniform approximation of a continuous function on a closed interval is considered. In the case of approximation by the class W(n) of functions whose nth derivative is bounded by 1 almost everywhere, a criterion for a best approximation element is known. This criterion, in particular, requires that the approximating function coincide on some subinterval with a perfect spline of degree n with finitely many knots. Since perfect splines belong to the class W(n), we study the following restriction of the problem: a continuous function is approximated by the set of perfect splines with an arbitrary finite number of knots. We establish the existence of a perfect spline that is a best approximation element both in W(n) and in this set. Therefore, the values of the best approximation in the problems are equal. We also show that the best approximation elements in this set satisfy a criterion similar to the criterion for a best approximation element in W(n). The set of perfect splines is shown to be everywhere dense in W(n).
175-182
On Some Properties of Vector Measures
Abstract
We study the properties of a parameterized sequence of countably additive vector measures with densities defined on a compact space T with a nonnegative nonatomic Radon measure μ and taking values in a separable Banach space. Each vector measure of this sequence depends continuously on a parameter belonging to a metric space. We assume that a countable locally finite open cover and a partition of unity inscribed into this cover are given in the metric space of parameters. We prove that, for each value of the parameter, there exists a sequence of μ-measurable subsets of the space T which is a partition of T. In addition, this sequence depends uniformly continuously on the parameter and, for each value of the parameter and each element of the initial parameterized sequence of vector measures, the relative value of the measure of the corresponding subset in the partition of T can be uniformly approximated by the corresponding value of the corresponding partition of unity function.
183-195
Uniform Lebesgue Constants of Local Spline Approximation
Abstract
Let a function ϕ ∈ C1[−h, h] be such that ϕ(0) = ϕ'(0) = 0, ϕ(−x) = ϕ(x) for x ∈ [0; h], and ϕ(x) is nondecreasing on [0; h]. For any function f: ℝ → ℝ, we consider local splines of the form
196-202
On the Construction of Regularizing Algorithms for the Correction of Improper Convex Programming Problems
Abstract
We consider convex programming problems with a possibly inconsistent constraint system. Such problems constitute an important class of improper models of convex optimization and often arise in the mathematical modeling of real-life operations research statements. Since improper problems arise rather frequently, the theory and methods of their numerical approximation (correction) should be developed, which would allow to design objective procedures that resolve inconsistent constraints, turn an improper model into a family of feasible problems, and choose an optimal correction among them. In the present paper, an approximating problem is constructed by the variation of the right-hand sides of the constraints with respect to the minimum of some vector norm. The type of the norm defines the form of a penalty function, and the minimization of the penalty function together with a stabilizing term is the core of each specific method of optimal correction of improper problems. The Euclidean norm implies the application of a quadratic penalty, whereas a piecewise linear (Chebyshev or octahedral) norm is concerned with the use of an exact penalty function. The proposed algorithms may also be interpreted as (Tikhonov) regularization methods for convex programming problems with inaccurate input information. Convergence conditions are formulated for the methods under consideration and convergence bounds are established.
203-212
Uniform Approximation of the Curvature of Smooth Plane Curves with the Use of Partial Fourier Sums
Abstract
An error bound for the approximation of the curvature of graphs of periodic functions from the class Wr for r ≥ 3 in the uniform metric is obtained with the use of the simplest approximation technique for smooth periodic functions, which is approximation by partial sums of their trigonometric Fourier series. From the mathematical point of view, the interest in this problem is connected with the specific nonlinearity of the graph curvature operator on the class of smooth functions Wr on a period or a closed interval for r ≥ 2. There are several papers on curvature approximation for plane curves in the mean-square and Chebyshev norms. In previous works, the approximation was performed by partial sums of trigonometric series (in the L2 norm), interpolation splines with uniform knots, Fejér means of partial sums of trigonometric series, and orthogonal interpolating wavelets based on Meyer wavelets (in the C∞ norm). The technique of this paper, based on the lemma, can possibly be generalized to the Lp metric and other approximation methods.
213-215
Space of Continuous Set-Valued Mappings with Closed Unbounded Values
Abstract
We consider a space of continuous set-valued mappings defined on a locally compact space T with a countable base. The values of these mappings are closed (not necessarily bounded) sets in a metric space (X, d(·)) whose closed balls are compact. The space (X, d(·)) is locally compact and separable. Let Y be a countable dense set in X. The distance ρ(A,B) between sets A and B belonging to the family CL(X) of all nonempty closed subsets of X is defined as follows:
216-222
Power Weight Integrability for Sums of Moduli of Blocks from Trigonometric Series
Abstract
We study the following problem: find conditions on sequences {γ(r)}, {nj}, and {vj} under which, for any sequence {bk} such that bk → 0 and \({\sum}_{k=r}^\infty|b_k-b_{k+1}|\leq\gamma(r)\) for all r ∈ ℕ, the integral \(\int_0^\pi {{U^p}(x)/{x^q}dx} \) converges, where p > 0, q ∈ [1 − p; 1), and \(U(x):=\sum\nolimits_{j = 1}^\infty {|\sum\nolimits_{k = {n_j}}^{{v_j}} {{b_k}\sin kx|} }\). For γ(r) = B/r with B > 0, this problem was studied and solved by S. A.Telyakovskii. In the case where p ≥ 1, q = 0, vj = nj+1 − 1, and {bk} is monotone, A. S. Belov obtained a criterion for the function U(x) to belong to the space Lp. In Theorem1 of the present paper, we give sufficient conditions for the convergence of the above integral, which coincide with the Telyakovskii sufficient conditions for γ(r) = B/r with B > 0. In the case γ(r) = O(1/r), the Telyakovskii conditions may be violated while the application of Theorem 1 guarantees the convergence of the integral. The corresponding examples are given in the last section of the paper. The question of necessary conditions for the convergence of the integral \(\int_0^\pi {{U^p}(x)/{x^q}dx} \), where p > 0 and q ∈ [1 − p; 1), remains open.
223-230
A Variant of the Affine-Scaling Method for a Second-Order Cone Program
Abstract
A linear cone program in which the cone is the direct product of second-order cones (Lorentz cones) is considered. For its solution, we propose a primal affine-scaling type method generalizing the corresponding method used in linear programming. The method can be considered as a special way to solve a system of necessary and sufficient optimality conditions for a pair of mutually dual cone programs. These conditions are used to derive the dependence of the dual variables on the primal variables, and the dependence is substituted into the complementarity condition. The obtained system of equations is solved with respect to the primal variables by the fixed-point iteration method. The starting points in the method belong to the cone but do not necessarily satisfy the linear equality-type constraints. The local linear convergence of the method is proved under the assumption that the solutions of the primal and dual problems are nondegenerate and strictly complementary.
231-240