View: session overviewtalk overview

Session manager Stepan Kochemazov

Session manager Maxim Zharkov

11:40 | One-Point Gradient-Free Methods for Smooth and Non-Smooth Saddle-Point Problems PRESENTER: Aleksandr Beznosikov ABSTRACT. In this paper, we analyze gradient-free methods with one-point feedback for stochastic saddle point problems min_{x}max_{y} phi(x, y). For non-smooth and smooth cases, we present analysis in a general geometric setup with arbitrary Bregman divergence. For problems with higher-order smoothness, the analysis is carried out only in the Euclidean case. The estimates we have obtained repeat the best currently known estimates of gradient-free methods with one-point feedback for problems of imagining a convex or strongly convex function. The paper uses three main approaches to recovering the gradient through finite differences: standard with a random direction, as well as its modifications with kernels and residual feedback. We also provide experiments to compare these approaches for the matrix game. |

12:00 | Library of unimodal optimization algorithms and their comparative testing PRESENTER: Tatiana Zarodnyuk ABSTRACT. It is created a library of efficient numerical algorithms for unimodal optimization, including Newton-type algorithms, the modification of B.T. Polyak's algorithm, the quasi-Newton BFGS algorithm, Hestenes-Stiefel conjugate gradient algorithm, the modification of Barzilai-Borwein algorithm and others. The comparative testing for software implementations of the proposed algorithms have been performed. Computational experiments are carried out using separable and quasi-separable functions, Chebyshev oscillator, and Rosenbrock-Skokov function. |

12:20 | Convex optimization with inexact gradients in Hilbert space and applications to elliptic inverse problems PRESENTER: Vladislav Matyukhin ABSTRACT. In this paper we propose the gradient descent type methods to solve convex optimization problems in Hilbert space. We apply it to solve ill-posed Cauchy problem for Poisson equation and make a comparative analysis with Landweber iteration and steepest descent method. The theoretical novelty of the paper consists in the developing of new stopping rule for accelerated gradient methods with inexact gradient (additive noise). Note that up to the moment of stopping the method ``doesn't feel the noise''. But after this moment the noise start to accumulate and the quality of the solution becomes worse for further iterations. |

12:40 | Zeroth-Order Algorithms for Smooth Stochastic Saddle-Point Problems PRESENTER: Abdurakhmon Sadiev ABSTRACT. Saddle-point problems have recently gained increased attention from the machine learning community, mainly due to applications in training Generative Adversarial Networks using stochastic gradients. At the same time, in some applications only a zeroth-order oracle is available. In this paper, we propose several algorithms to solve stochastic smooth (strongly) convex-concave saddle-point problems using zeroth-order oracles and estimate their convergence rate and its dependence on the dimension $n$ of the variable. In particular, our analysis shows that in the case when the feasible set is a direct product of two simplices, our convergence rate for the stochastic term is only by a log n factor worse than for the first-order methods. We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the minimization part and first-order oracle for the maximization part. Finally, we demonstrate the practical performance of our zeroth-order and 1/2th-order methods on practical problems. |

Session manager Stepan Kochemazov

11:40 | Two-machine routing open shop: how long is the optimal makespan? ABSTRACT. We consider a routing open shop problem being a natural generalization of the metric TSP and the classic open shop scheduling problem. The maximal possible ratio of the optimal makespan and the standard lower bound for the routing open shop has already been investigated in the last few years. The two-machine case is mostly covered. It is constructively proven in 2013 that the above ratio cannot be greater than 4/3, however, we do not know of any problem instance with the value of that ratio greater than 6/5. On the other hand, it is known that optimal makespan is at most 6/5 of the standard lower bound for at least a few special cases of the transportation network: one is with at most three nodes, and another is a tree. In this paper, we introduce an ultimate instance reduction technique, which allows reducing the general problem into a case with at most four nodes and at most six jobs. As a by-product, we propose a new polynomially solvable case of the two-machine routing open shop problem. |

12:00 | Combining Bit Pattern Tree Optimizations with Graph Test for Double Description Method PRESENTER: Nikolai Zolotykh ABSTRACT. We propose a variation of the Double Description Method based on the use of bit pattern trees, their existing modifications [1] and the graph adjacency test [2]. We describe the implementation details of the algorithm and present the result of computational experiments comparing Double Description Method variations. 1. Genov, B.: The convex hull problem in practice: improving the running time of the double description method. Doctoral dissertation, Universität Bremen (2015). 2. Zolotykh, N. Yu.: New modification of the double description method for constructing the skeleton of a polyhedral cone. Computational mathematics and mathematical physics 52(1), 146–156 (2012) |

12:20 | On complexity of quadratic 2-clustering 1-Mean and 1-Medoid problem with arbitrary clusters sizes ABSTRACT. Given N points in d-dimensional space, the goal is to partition them into two clusters minimizing the sum of squared distances form the elements of the clusters to their centers. The center of one cluster is determined as a centroid (a mean of all cluster points), while the center of the second cluster must be chosen in the initial set of points. It is proved that this problem is NP-hard for arbitrary cluster sizes (not given as a part of input). The paper was supported by Russian Foundation for Basic Research, project 19-01-00308. |

12:40 | Rig Routing with Possible Returns and Stochastic Drilling Times PRESENTER: Anton Eremeev ABSTRACT. We consider a real-world vehicle routing problem with time windows, arising in drilling rigs routing and well servicing on a set of sites with different georgaphical locations. Each site includes a predetermined number of wells which must be processed within a given time window. The same rig can visit a site several times, but the overall number of site visits by rigs is bounded from above. Each well is drilled by one rig without preemptions. It is required to find the routs of the rigs, minimizing the total traveling distance. We also consider a stochastic generalization of the problem, where the drilling times are supposed to be random variables with known discrete distributions. New mixed-integer linear programming models are formulated and tested experimentally. A randomized greedy algorithm is proposed for approximate solving the problem in stochastic formulation, if the number of possible realizations of drilling times is so high that existing MIP solvers are not suitable. |

13:00 | Polynomial 1/2-approximation algorithms for 2-PSP-max and 2-APSP-max with two weight functions PRESENTER: Aleksey Glebov ABSTRACT. The $m$-Peripatetic Salesman Problem ($m$-PSP) is a natural generalization of the classical Travelling Salesman Problem. The task in $m$-PSP is to find $m$ edge disjoint Hamyltonian cycles of maximum or minimum total weight in a complete weighted graph which can be directed (the asymmetric variant of the problem abbreviated as $m$-APSP) or undirected (the symmetric $m$-PSP). Since both problems $m$-PSP and $m$-APSP are known to be NP-hard the important field of research is to elaborate polynomial approximation algorithms with guaranteed accuracy bounds for these problems. Over the past 40 years, many such algorithms have been developed including the 7/9-approximation algorithm for 2-PSP-max by Glebov and Zambalaeva and the polynomial algorithm with the asymptotic approximation ratio 2/3 for $m$-APSP-max by Glebov and Toktokhoeva. All these algorithms are adapted for the case of the problem where we are given only one weight function which is common for all Hamiltonian cycles. In this research we for the first time present two polynomial algorithms with guaranteed approximation ratio 1/2 for the much more complicated variant of both 2-PSP-max and 2-APSP-max where each Hamiltonian cycle is supplied with its own weight function. |

Session manager Alexander Stolbov

11:40 | Dynamic multicriteria games with random horizon ABSTRACT. We consider a dynamic, discrete-time, game model where the payers use a common resource and have different criteria to optimize. Moreover, the planning horizon is assumed to be random. To construct a multicriteria Nash equilibrium the bargaining solution is adopted. To design a multicriteria cooperative equilibrium, a modified bargaining scheme that guarantees the fulfillment of rationality conditions is applied. To illustrate the presented approaches, a dynamic bi-criteria bioresource management problem with many players and random planning horizon is investigated. |

12:00 | Altruistic-like equilibrium in a differential game of renewable resource extraction PRESENTER: Vladimir Mazalov ABSTRACT. We consider a model of renewable resource extraction described by a differential game with infinite horizon. The environmental problems are often considered from cooperative prospective as the selfish behavior of a player may negatively affects not only on other players' profits, but also on the environment. The reason is the joint stock of resource which is influenced by all players. We characterize the Berge and altruistic equilibrium in a differential game of renewable resource extraction and compare them with the Nash equilibrium. According to the concept of altruistic equilibrium players can choose the part of the other players' payoffs they support and summarize with the part of their own profit. This equilibrium can be considered as an intermediate between Berge and Nash equilibria. We make numerical simulations and demonstrate theoretical results for the case of n symmetric players. |

12:20 | Data-driven combinatorial optimization with incomplete information: a distributionally robust optimization approach ABSTRACT. In this study, we analyze linear combinatorial optimization problems where the cost vector is not known a priori but is only observable through a finite data set. In contrast to the related studies, we presume that the number of observations with respect to particular components of the cost vector may vary. The goal is to find a procedure that transforms the data set into an estimate of the expected value of the objective function (which is referred to as a prediction rule) and a procedure that retrieves a candidate decision (which is referred to as a prescription rule). We aim at finding the least conservative prediction and prescription rules, which satisfy some specified asymptotic guarantees. We demonstrate that the resulting vector optimization problems admit a weakly optimal solution, which can be obtained by solving a particular distributionally robust optimization problem. Specifically, the decision-maker may optimize the worst-case expected loss across all probability distributions with given component-wise relative entropy distances from the empirical marginal distributions. Finally, we perform numerical experiments to analyze the out-of-sample performance of the proposed solution approach. |

12:40 | Opinion dynamics in social networks: from competition to bargaining PRESENTER: Artem Sedakov ABSTRACT. The literature on game theoretic models of opinion dynamics in social networks mainly focuses on Nash equilibrium, which reflects a competitive situation between influencing agents called players. In some real-world situations, however, the players can negotiate with each other; therefore, a different type of solution should be considered to address such behavior. In this talk, we examine an opinion dynamics game based on the Friedkin-Johnsen model, for which we characterize the Pareto frontier including the Nash bargaining solution. Next, we will analyze the behavior of this solution when the susceptibility of non-influencing agents to their initial opinions changes. We will also demonstrate how the Nash equilibrium outcome differs from the outcome prescribed by the Nash bargaining solution. |

Session manager Maxim Zharkov

15:00 | Sample Approximations of Bilevel Stochastic Programming Problems with Probabilistic and Quantile Criteria ABSTRACT. We consider bilevel stochastic programming problems with probabilistic and quantile criteria. The lower level problems is assumed to be linear for fixed leader's (upper level) variables and fixed realizations of the random parameters. The objective function and the constraints of the lower level problem depend on the leader's strategy and random parameters. The objective function of the upper level problem is defined as the value of the probabilistic or quantile functional of the random losses on the upper level. We suggest conditions guaranteeing that the objective function of the upper level is a normal integrand. It is shown that these conditions are satisfied for a class of problems with positive coefficients of the lower level problem. This allows us to suggest sufficient conditions of the existence of a solution to the considered problem. We construct sample approximations of these problems. These approximations reduce to mixed integer nonlinear programming problems. We describe sufficient conditions of the convergence of the sample approximations to the original problems. |

15:20 | Optimal (in the sense of the minimum of the polyhedral norm) matrix correction of inconsistent systems of linear algebraic equations and improper linear programming problems in interval constraints PRESENTER: Vladimir Erokhin ABSTRACT. The report deals with the problems of multiparameter (matrix) correction of inconsistent systems of linear algebraic equations and improper linear programming problems written in canonical form. The optimal criteria specified in these problems are the weighted minimax criterion and the minimum of the considered sum of the absolute values of the elements of the matrix correction requirements. The considered correction problems are supplemented by interval constraints imposed on the corrected elements of the matrix system and its right-hand side. The analyzed systems of linear algebraic equations can contain fixed (not subject to correction) rows and columns. The calculation schemes for solving the set tasks of matrix correction are presented and substantiated. Calculation schemes require a minimum of scalar positive parameters at the upper (external) level and are reduced to solving systems of linear algebraic equations and inequalities depending on the declared parameter, as well as linear programming problems at a internal level. |

15:40 | Application of smooth approximation in stochastic optimization problems with a polyhedral loss function and probability criterion. PRESENTER: Roman Torishnyi ABSTRACT. In this paper, we consider a stochastic optimization problem with a convex piecewise linear (polyhedral) loss function, polyhedral constraints, and continuous random vector distribution. The objective is to maximize the probability that the loss function value does not exceed the specified level when constraints are satisfied. We use an approximation of polyhedral function and probability criterion, replacing maximum with smooth maximum transform and Heaviside function with sigmoid function. This replacement leads to the approximation of their gradients. Next, the problem solved using modified gradient descent. The accuracy and effectiveness of this method are shown in two examples. Also, we discuss some aspects of such approximations in the case of discrete random distribution. |

16:00 | Algorithms for solving variational inequalities and saddle-point problems with some generalizations of Lipschitz property for operators PRESENTER: Alexander Titov ABSTRACT. The article is devoted to the development of numerical methods for solving saddle-point problems and variational inequalities with simplified requirements for the smoothness conditions of functionals. Recently there were proposed some notable methods for problems with strongly monotone operators. Our focus here is on newly proposed [1] techniques for solving strongly convex-concave saddle-point problems. One of the goals of the article is to improve the obtained estimates of the complexity of introduced algorithms by using accelerated methods for solving auxiliary problems. In addition, we introduce an analogue of the boundedness condition for the operator in the case of arbitrary (not necessarily Euclidian) prox structure. We propose an analogue of the mirror descent method for solving variational inequalities with such operators, which is optimal in the considered class of problems. [1] Alkousa, M.S., Gasnikov, A.V., Dvinskikh, D.M., Kovalev, D.A., & Stonyakin, F.S. (2020). Accelerated methods for saddle-point problems. Journal of Computational Mathematics and Mathematical Physics, 60 (11), 1843-1866. |

16:20 | A new appoach to linear programs with many two-sided constraints PRESENTER: Oksana Pichugina ABSTRACT. The paper focuses on linear programming problems (LP) with two-sided constraints whose number is much larger than the number of variables. The new solution approach uses a non-smooth penalty function in the form of a maximum function. The choice of the penalty parameter ensures the equivalence between the original LP and the problem of minimizing the penalty function. The latter problem is tackled by means of a modification of the r-algorithm, i.e., of an iterative subgradient method with an adaptive step adjustment and a constant coefficient of space dilation towards the difference of two successive subgradients. Based on an implementation of this LPralg algorithm with GNU Octave, computational results on randomly generated LP-instances with 50.000 to 150.000 two-sided constraints and 100 to 300 variables are presented. The results demonstrate the advantage of this approach in comparison to well-known linear programming software, such as the GLPK package as well as CPLEX and Gurobi solvers. Among other problems, the new approach can be applied to robust linear programs with a finite uncertainty domain. |

Session manager Stepan Kochemazov

15:00 | Simultaneous detection and discrimination of subsequences which are nonlinearly extended elements of the given sequence alphabet in a quasiperiodic sequence ABSTRACT. The subject of the study is one unexplored discrete optimization problem. This problem arises in the framework of a posteriori approach when solving the following problem of simultaneous detection and discrimination of pulses an a quasiperiodic pulse-train. We assume that 1) we have the quantity of pulses in the pulse train and a finite alphabet of reference pulses as a part of the input, 2) every pulse in the pulse train coincides with some non-linearly stretched (by duplicating its components) alphabet element, 3) all pulses are included in the pulse train entirely, 4) the difference between the initial indices of two neighboring pulses is limited from above by the given value (the pulse train is a quasiperiodic one). We have to detect every pulse and set a match between the pulse and some alphabet element. We show that the considered discrete optimization problem is polynomial-time solvable and construct the algorithm that guarantees the optimal solution to this problem. The results of the numerical simulation are presented. |

15:20 | On data reduction for the Graphic TSP PRESENTER: Daniel Skachkov ABSTRACT. The Graphic TSP is finding a minimum-cost tour containing all vertices of a given graph. Herein, the input graph is not necessarily complete and visiting vertices several times is allowed. We present first results on provably effective polynomial-time data reduction for this NP-hard problem. In particular, we study the existence of problem kernels of size polynomial in the feedback edge set number or the vertex cover number of the input graph. |

15:40 | Maximising the total weight of on-time jobs on parallel machines subject to a conflict graph PRESENTER: Joanna Berlińska ABSTRACT. The paper considers scheduling on parallel machines under the constraint that some pairs of jobs cannot be processed concurrently. Each job has an associated weight, and all jobs have the same deadline. The objective is to maximise the total weight of on-time jobs. The problem is known to be strongly NP-hard in general. A polynomial-time algorithm for scheduling unit execution time jobs on two machines is proposed. The performance of a broad family of approximation algorithms for scheduling unit execution time jobs on more than two machines is analysed. For the case of arbitrary job processing times, two integer linear programming formulations are proposed and compared with two formulations known from the earlier literature. An iterated variable neighborhood search algorithm is also proposed and evaluated by means of computational experiments. |

16:00 | Local search algorithm for problem of helicopter people transportation in offshore projects of oil and gas development PRESENTER: Elena Lubnina ABSTRACT. In recent years, the instability of the oil price on the world market has been encouraging oil companies to reduce operating costs. This is especially important for offshore field development projects. One of the potential ways to increase the profitability of offshore projects is to optimize people and cargo transportation costs during servicing offshore oil and gas platforms. In this paper, we solve the optimization problem of helicopter people transportation. This task can be classified as a Capacitated Vehicle Routing problem with Split Delivery and PickUp (CVRPSDP). It is known this problem belongs to the class of NP-hard problems, so a local search algorithm is considered for its solution. The effectiveness of the algorithm depends, among other things, on the method of choosing the initial solution and the system of neighborhoods. The paper presents the results obtained for the company JV "Vietsovpetro". |

16:20 | Efficient PTAS for the Maximum Traveling Salesman Problem in a Metric Space of Fixed Doubling Dimension ABSTRACT. The maximum traveling salesman problem (Max TSP) is one of the intensively researched combinatorial optimization problems. It consists of finding a maximum-weight Hamiltonian cycle in a given complete weighted graph. This problem is APX-hard in the general and metric cases but admits approximation schemes in the geometric setting, when the distances between vertices are induced by some vector norm in fixed-dimensional real space. We propose the first polynomial-time approximation scheme for Max TSP in any metric space of fixed doubling dimension. The proposed algorithm implements a scheme EPTAS which, for any fixed ε∈(0,1), finds a (1-ε)-approximate solution of the considered problem in cubic time. Also, we suggest a polynomial-time algorithm which computes asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions. |

Session manager Alexander Stolbov

15:00 | Simplified model of rational development of an economic entity ABSTRACT. The object of the study is a model of dynamic management of an economic entity, namely a household, an investor (enterprise) or the state as a whole. The development strategy of a subject is called rational if its welfare exceeds a given level during each interval of the period under consideration. In [1], based on the Solow equation [2], a model combining discrete and continuous specificity was proposed for finding rational strategies In this paper, we study a simplified version of this model in order to compare the strategies obtained in it with the strategies developed by the classical Ramsey-Kass-Koopmans model [3,4]. The comparison criteria are an integral indicator of well-being and local indicators. The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314-2019-0018). The work was supported in part by the Russian Foundation for Basic Research, projects 19-010-00910 and 20-010-00151. [1] Sergey M. Antsyz On Models of Economic Development, Taking into Account Lending // Proceedings 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems (OPCS 2019). Novosibirsk Akademgorodok, Russia: Publisher IEEE Catalog Number: CFP19U46-ART, 2019, pp. 4-7. [2] R. M. Solow A Contribution to the Theory of Economic Growth // The Quarterly Journal of Economics, vol. 70, issue 1, pp. 65--94, February 1956. [3] David H. Romer Advanced macroeconomics, 4th ed. p. cm. University of California. Berkeley: McGraw-Hill, 2012. [4] S. A. Ashmanov Introduction to Mathematical Economics. Moscow: Nauka, 1984 [in Russian]. |

15:20 | Strong stability in finite games with perturbed payoffs PRESENTER: Yury Nikulin ABSTRACT. We consider a finite cooperative game of several players in a normal form with perturbed linear payoffs where perturbations formed by a set of additive matrices, with two arbitrary Hölder norms specified independently in the outcome and criterion spaces. The concept of equilibrium is generalized using the coalitional profile, i.e. by partitioning the players of the game into coalitions. In this situation, two extreme cases of this partitioning correspond to the Pareto optimal outcome and the Nash equilibrium outcome, respectively. We analyze such type of stability, called strong stability, that is under any small admissible perturbations the efficiency of at least one optimal outcome of the game is preserved. The limiting attainable upper and lower bounds of such perturbations have been specified. The obtained result generalizes some previously known facts and sheds more light on the combinatorial specific of the problem considered. Possible applications of the obtained theoretical results are mentioned. |

15:40 | Inverse Optimal Control with Continuous Updating for Steering Behavior Model with Reference Trajectory PRESENTER: Ovanes Petrosian ABSTRACT. Most real control processes continuously evolve in time, and a person may not have all the information about the process at the initial moment of time. For example, the driver only has local information about the curvature of the road or any obstacles that might cause a lane change. The continuous updating approach allows modeling the limited information available to subjects during decision making. Previously, the authors considered many variations and methods of applying the approach with continuous information updating: optimality conditions for equilibrium and cooperative strategies were constructed for the linear-quadratic case [2,4], the Hamilton-Jacobi-Belman equation [1,5], Pontryagin's maximum principle [3, 7] and more [6, 8]. In this paper, we apply a continuous updating approach to the inverse optimal control problem for motion along a given trajectory. The application is an inverse problem for determining the behavior of a driver while driving along a target trajectory. The real motion data from the driving simulator is used and the conclusion is drawn. [1] Petrosian O., Tur A. (2019) Hamilton-Jacobi-Bellman Equations for Non-cooperative Differential Games with Continuous Updating. In: Bykadorov I., Strusevich V., Tchemisova T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Communications in Computer and Information Science, vol 1090. Springer, Cham. https://doi.org/10.1007/978-3-030-33394-2_14 [2] Kuchkarov I., Petrosian O. (2019) On Class of Linear Quadratic Non-cooperative Differential Games with Continuous Updating. In: Khachay M., Kochetov Y., Pardalos P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science, vol 11548. Springer, Cham. https://doi.org/10.1007/978-3-030-22629-9_45 [3] Petrosian O., Tur A., Zhou J. (2020) Pontryagin’s Maximum Principle for Non-cooperative Differential Games with Continuous Updating. In: Kochetov Y., Bykadorov I., Gruzdeva T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2020. Communications in Computer and Information Science, vol 1275. Springer, Cham. [4] Kuchkarov I., Petrosian O. (2020) Open-Loop Based Strategies for Autonomous Linear Quadratic Game Models with Continuous Updating. In: Kononov A., Khachay M., Kalyagin V., Pardalos P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2020. Lecture Notes in Computer Science, vol 12095. Springer, Cham. https://doi.org/10.1007/978-3-030-49988-4_15 [5] Ovanes Petrosian, Anna Tur, Zeyang Wang, Hongwei Gao (2020), Cooperative differential games with continuous updating using Hamilton–Jacobi–Bellman equation, https://doi.org/10.1080/10556788.2020.1802456 [6] Zeyang Wang, Ovanes Petrosian (2020), On class of non-transferable utility cooperative differential games with continuous updating, Journal of Dynamics and Games, October 2020, 7(4): 291-302, 10.3934/jdg.2020020 [7] Jiangjing Zhou, Anna Tur, Ovanes Petrosian, Hongwei Gao (2020) On the Class of Cooperative Differential Games with Continuous Updating using Pontryagin Maximum Principle, Mathematics (to be published) [8] Ovanes Petrosian, Jairo Inga, Ildus Kuchkarov, Michael Flad, Soren Hohmann (2020), Optimal Control and Inverse Optimal Control with Continuous Updating for Human Behavior Modeling, IFAC-PapersOnLine (to be published, IFAC2020) https://www.researchgate.net/publication/344344967_Optimal_Control_and_Inverse_Optimal_Control_with_Continuous_Updating_for_Human_Behavior_Modeling |

Session manager Stepan Kochemazov