View: session overviewtalk overview

Session manager Anton Ushakov

Session manager Alexander Stolbov

17:20 | Duality Gap Estimates for a Class of Greedy Optimization Algorithms in Banach Spaces PRESENTER: Kirill Spiridonov ABSTRACT. The paper examines a class of algorithms called Weak Biorthogonal Greedy Algorithms (WBGA) designed for the task of finding the approximate solution to a convex cardinality-constrained optimization problem in a Banach space using linear combinations of some set of "simple" elements of this space (a dictionary), i.e. the problem of finding the infimum of a given convex function over all linear combinations of the dictionary elements with the given cardinality. An important issue when one computationally solves optimization problems is to obtain an estimate of the proximity to an optimal solution, that can be used to effectively check that the approximate solution is with a given accuracy. A similar idea that has already been applied to solving some optimization problems, in which such an estimate of the proximity (certificate) to the optimal solution is called the "duality gap". We introduce the notion of the duality gap for greedy optimization in Banach Spaces and obtain dual convergence estimates for sparse-constrained optimization by means of algorithms from the WBGA class. |

17:40 | Proximal Gradient Methods with Adaptive Subspace Sampling ABSTRACT. Many applications in machine learning or signal processing involve nonsmooth optimization problems. This nonsmoothness brings a low-dimensional structure to the optimal solutions. In this paper, we propose a randomized proximal gradient method harnessing this underlying structure. We introduce two key components: i) a random subspace proximal gradient algorithm; ii) an identification-based sampling of the subspaces. Their interplay brings a significant performance improvement on typical learning problems in terms of dimensions explored. |

18:00 | On the Computational Efficiency of Catalyst Accelerated Coordinate Descent PRESENTER: Dmitry Pasechnyuk ABSTRACT. This article is devoted to one particular case of using universal accelerated proximal envelopes to obtain computationally efficient accelerated versions of methods used to solve various optimization problem setups. We propose a proximally accelerated coordinate descent method that achieves the efficient algorithmic complexity of iteration and allows taking advantage of the data sparseness. It was considered an example of applying the proposed approach to optimizing a SoftMax-like function, for which the described method allowing weaken the dependence of the computational complexity on the dimension in O(sqrt(n)) times and, in practice, demonstrates a faster convergence in comparison with standard methods. As an example of applying the proposed approach, it was shown a variant of obtaining on its basis some efficient methods for optimizing Markov Decision Processes (MDP) in a minimax formulation with a Nesterov smoothed target functional. |

18:20 | A subgradient projection method for set-valued network equilibrium problems PRESENTER: Igor Konnov ABSTRACT. In the present work, we describe a general set-valued variant of the network equilibrium problem with fixed demand. This problem is equivalent to a set-valued variational inequality. Under certain additional assumptions, it can be replaced with a non-smooth convex optimization problem. We propose to apply the subgradient projection method with a special two-speed step-size choice procedure to this problem. Computational experiments on model networks showed that the proposed approach is rather efficient. It gives a more flexible procedure for the choice of parameters. |

18:40 | An Approach for Simultaneous Finding of Multiple Effective Solutions in Multi-objective Optimization Problems PRESENTER: Konstantin Barkalov ABSTRACT. This paper considers computationally intensive multi-objective optimization problems which require computing multiple Pareto-optimal decisions. It is also assumed that efficiency criteria may be multiextremal, and the cost of calculating function values may be quite high. The proposed approach is based on the reduction of multi-objective optimization problems to one-dimensional global optimization problems that can be solved using efficient information-statistical algorithms of global search. One key innovation of the developed approach consists in the possibility of solving several global optimization problems simultaneously, which allows multiple Pareto-optimal decisions to be obtained. Besides, such approach provides for reuse of the computed search information, which considerably reduces computational effort for solving multi-objective optimization problems. Computational experiments confirm the potential of the proposed approach. |

Session manager Maxim Zharkov

17:20 | Exact algorithms for various graph clustering problems PRESENTER: Alexander Morshinin ABSTRACT. Clustering problems form an important section of data analysis. In the machine learning clustering problems are usually classified as unsupervised or as semi-supervised learning. We consider a family of clustering problems which are formalized by graph clustering. The aim of these problems is to split the vertex set of a given graph into pairwise disjoint groups (clusters) minimizing the number of edges between clusters and the number of missing edges inside clusters. The problems under consideration are NP-hard. We present exact algorithms for these problems. Firstly, we introduce a universal branch and bounds algorithm which is suitable for any graph clustering problem. Secondly, we present linear integer programming models for some graph clustering problems. |

17:40 | A new approximation algorithm for graph clustering with constraints on cluster sizes PRESENTER: Nikita Gorbunov ABSTRACT. A version of the graph clustering problem is considered. In this version sizes of all clusters don't exceed a given positive integer p. This problem is NP-hard for every fixed p. A new approximation algorithm is presented and a bound on worst-case behaviour of this algorithm is obtained. This bound is better than performance guarantees of earlier presented approximation algorithms. |

18:00 | Solving Irregular Polyomino Tiling Problem Using Simulated Annealing and Integer Programming PRESENTER: Aigul Fabarisova ABSTRACT. This paper addresses a problem of irregularity in polyomino tiling arising in phased array design. Such important parameter of antennas as the sidelobe level implicitly depends on the irregularity of array structure. It is complex and can be calculated only by modeling the entire system. We introduce an integer programming model for tiling with L-tromino and L-tetromino and the heuristic approach based on the Simulated Annealing. To implement irregularity measurement, the evaluation function based on the entropy concept was proposed. |

18:20 | A heuristic approach in solving the optimal seating chart problem PRESENTER: Milan Tomić ABSTRACT. The optimal seating chart problem is a graph partitioning problem with a very practical use. It is the problem of finding an optimal seating arrangement on a wedding or a gala dinner. Given the number of tables available and the number of seats per table, the optimal seating arrangement is determined based on the guests' preferences to seat or not to seat together with other guests at the same table. The problem is easily translated to finding a m-partitioning of a graph of n nodes, such that the number of nodes in each partition is less than or equal to the given upper limit c, and that the sum of edge weights in all partitions is maximized. Although it can be easily formulated as MILP, the problem is extremely difficult to solve even with relatively small instances, which makes it perfect to apply a heuristic method. In this paper we present a research of a novel descent-ascent method for the solution, with comparison to some of the already proposed techniques from the earlier works. |

18:40 | A feature based solution approach for the flying sidekick traveling salesman problem PRESENTER: Adriano Masone ABSTRACT. The integration of new distribution technologies in the delivery systems, specifically drones, has been investigated by several companies to reduce the last mile logistic costs. The most promising delivery system, in terms of emissions and completion time reduction, consists of a truck and a drone operating in tandem for the parcel delivery to the customers. This has led to the definition of new and complex routing problems that have received great attention by the operations research community. Several contributions have appeared in the last years providing ILP and MILP formulation for these kinds of problems. Nevertheless, due to complexity, their solutions is impracticable even on small instances. In particular, the synchronization and the coordination of the two vehicles represent critical issues. In this work, we investigate the possibility of using customer characterizing features which allow to determine a priori promising customer-to-vehicle assignments. This information can be used to perform several variable fixing in the FS-TSP formulation, so reducing the size and the complexity of the instances to be solved. Thus, the final aim is to determine optimal or sub-optimal solutions using state-of-the-art solver on a reduced FS-TSP. To this aim, we provide a computational study proving the quality of the chosen features and their effectiveness in the solution of new and literature instances. |

Session manager Maxim Staritsyn

17:20 | Identification of the thermal conductivity coefficient of a substance from a temperature field in a three-dimensional domain PRESENTER: Vladimir Zubov ABSTRACT. The inverse problem of determining the temperature-dependent thermal conductivity coefficient of a substance in a parallelepiped is considered and investigated. The consideration is carried out on the basis of the first boundary value problem for a three-dimensional non-stationary heat conduction equation. The inverse coefficient problem is reduced to a variational problem and is solved numerically using gradient methods for minimizing the cost functional. In this work, special attention is paid to the practically important cases when the experimental field is specified only in the subdomain of the object under consideration. The working capacity and effectiveness of the proposed approach are demonstrated by solving a number of nonlinear inverse problems. |

17:40 | Optimization of regulation and infrastructure of the electricity market PRESENTER: Alexander Vasin ABSTRACT. This research examines a model of a wholesale electricity market including consumers and producers located at several nodes, transmitting lines, and energy storages. Tariff regulation aimed at shift- ing some part of consumption from peak zones of the schedule to off-peak time of the day is considered. Among producers, we distinguish renew- able energy sources with stochastic production volumes. They can be used to replace more expensive energy sources, but under adverse con- ditions should be replaced by reserve capacities with conventional tech- nologies or energy storages. Problems of optimal regulation aimed at maximizing the expected social welfare are studied. We prove that op- timal tariffs for consumers at every node and each time interval should correspond to average marginal supply costs for the node and the time. Optimal control strategies for energy storages are determined with ac- count of their total charge volumes and maximum charging rates. We prove that, for every storage, the strategy corresponds to maximization of its profit from energy resale at the competitive market. A problem of the market infrastructure optimization is also studied. Proceeding from Lagrange theorem, we obtain the system of equations for determination of optimal parameters of the storages. |

18:00 | The Research of Mathematical Models for Forecasting Covid-19 Cases PRESENTER: Mostafa Abotaleb ABSTRACT. The world is currently facing a Covid-19 pandemic and that virus is spreading rapidly among people, which leads to an increase in the the number of infection cases and also an increase in the number of deaths cases. This is a huge challenge as this pandemic affected all sectors, and therefore there was important for mathematicians in modelling this epidemic spread in the world in order to reduce the damage caused by this pandemic and also discovering the pattern of that virus spreading. In our report, time series models are used to obtain estimates of the number of cases of infection and numbers of deaths using ARIMA, Holt's Linear Trend, BATS, TBATS, and SIR Models. We have developed a new algorithm in order to use these models and choose the best model for forecasting the number of infections and deaths in terms of the least error of MAPE as standard. We have observed in most of the data that were used in this algorithm that the best models that achieve the least forecast errors are BATS, TBATS, and ARIMA respectively. The experiment was hold for the ten countries most affected by the Covid-19, this algorithm was able to detect the data pattern of the virus spreading for every country, in addition it is interested in more research and studies on other models. |

18:20 | On the speed-in-action problem for the class of linear non-stationary infinite-dimensional discrete-time systems with bounded control and degenerate operator PRESENTER: Danis Ibragimov ABSTRACT. An infinite-dimensional non-stationary linear control system with discrete time and bounded control is considered. It is assumed that the set of admissible values of the control is convex and weakly compact, the phase space is normalized, and the system operator is linear and bounded. For a given system, the speed-in-action problem is solved: it is required to construct an admissible process that transfers the system in the minimum number of steps from a given initial state to the origin. The speed-in-action problem for discrete systems is characterized by the difficulty of applying classical methods: the irregularity of the extremum of the Lagrange function generally leads to the degenerate nature of the maximum principle; in turn, Bellman's dynamic programming method is reduced to an exhaustive search. There is a known approach to solving the problem on the basis of 0-controllability sets, the construction of which turns out to be difficult to implement in the case of an irreversible system operator, which makes the development of alternative methods urgent. In this paper, we propose an approach based on the use of the apparatus of reachable sets, which allows us to generalize the known results to the case of a degenerate operator of the system. An analytical description of the reachable sets is presented, the optimality criterion for the boundary points of the reachable set is formulated and proved in the form of the maximum principle, its degeneracy is demonstrated for interior points, the method is developed for reducing the case of interior points to the case of boundary points. Examples are considered. |

18:40 | Optimal boundary control of string vibrations by displacement of one end with the other end fixed and with a given shape of deflection at some instant PRESENTER: Vanya Barseghyan ABSTRACT. We consider the problem of optimal boundary control of string vibrations with given initial and final conditions and a given value of the string deflection function at some intermediate instant. Also, the quality criterion is set for the entire time interval. Control is realized by the displacement of one end while the other end is fixed. A constructive approach to constructing the optimal boundary control action is proposed. A computational experiment is carried out with the construction of the corresponding graphs and their comparative analysis, which confirm the results obtained. |