ABSTRACT. In many optimization problems, nonsmoothness appears in a structured manner. Composite structures are found in LASSO-type problems arising in machine learning. Separable structures result from applying some decomposition technique to problems that cannot be solved directly. This context is frequent in stochastic programming, bilevel optimization, equilibrium problems.

The talk will give a panorama of techniques that have proven successful in exploiting structural properties that are somewhat hidden behind nonsmoothness. Throughout the presentation, the emphasis is put on transmitting the main ideas and concepts, illustrating with examples the presented material.

ABSTRACT. We discuss state-of-the-art results on local convergence and the rate of convergence of the classical augmented Lagrangian algorithm. The local primal-dual linear/superlinear convergence is obtained under the sole assumption that the dual starting point is close to a multiplier satisfying the second-order sufficient optimality condition. In fact, in the equality-constrained case, even the weaker noncriticality assumption is enough. In particular, no constraint qualifications of any kind are needed. Classical literature on the subject required the linear independence constraint qualification (in addition to other things). In addition to the most standard form of the augmented Lagrangian algorithm, the general lines of analysis apply also to its variant with partial penalization of the constraints, to the proximal-point version, and to the modification with smoothing of the max-function. Moreover, we show that to compute suitable approximate solutions of augmented Lagrangian subproblems which ensure the superlinear convergence of the algorithm, it is enough to make just two Newtonian steps (i.e., solve two quadratic programs, or two linear systems in the equality-constrained case). The two quadratic programs are related to stabilized sequential quadratic programming, and to second-order corrections, respectively.

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.

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.

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.

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.

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.

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)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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".

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.

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].

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.

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

ABSTRACT. Today urban road network of a modern city can include several subnets. Indeed, bus lanes form a transit subnet available only for public vehicles. Toll roads form a subnet, available only for drivers who ready to pay fees for passage. The common aim of developing such subnets is to provide better urban travel conditions for public vehicles and toll-paying drivers. The present paper is devoted to the equilibrium traffic flow assignment problem in a multi-subnet urban road network. We formulate this problem as a non-linear optimization program and prove that its solution corresponds to the equilibrium traffic assignment pattern in a multi-subnet road network. Moreover, we prove that obtained equilibrium traffic assignment pattern guarantees less or equal travel time for public vehicles and toll-paying drivers than experienced by all other vehicles. The findings of the paper contribute to the traffic theory and give fresh managerial insights for traffic engineers.

ABSTRACT. We first present a review of local search methods that are usually used to solve the minimum sum-of-square clustering (MSSC) problem. We then present some their combinations within the Variable neighbourhood descent (VND) scheme. They combine k-means, h-means and j-means heuristics in a nested and sequential way. To show how these local searches can be implemented within a metaheuristic framework, we apply the VND heuristics in the local improvement step of the variable neighbourhood search (VNS) procedure. Computational experiments are carried out which suggest that this new and simple application of VNS is comparable to the state of the art. Then we discuss some decomposition and aggregation strategies for solving MSSC problem with huge data sets. Following the recent Less is more approach, the data set is divided randomly into a few smaller subproblems and after solving, the centroids of each subproblem are chosen to represent its cluster for a new aggregation stage. Encouraging computational results on instances of several million entities are presented.

ABSTRACT. Approximate techniques for solving combinatorial optimization problems, such as metaheuristics, often make use of learning. Examples include evolutionary algorithms and ant colony optimization. On the other side, matheuristics - that is, heuristic techniques making use of mathematical programming - rarely include a learning component. Most variants of large neighbourhood search, for instance, do not take profit from learning. In this talk I will present examples of our recent work in which we design matheuristics that make successful use of learning, considering both positive and negative feedback.