Mathematical Optimization Theory and Operations Research

Let G be a simple graph with vertex set $$V\left( G\right) $$ .A set $$S\subseteq V\left( G\right) $$ is independent if no two vertices from S are adjacent, and by $$\mathrm {Ind}(G)$$ we mean the family of all independent sets of G.The number $$d\left( X\right) =$$ $$\left| X\right| -\left| N(X)\right| $$ is the difference of $$X\subseteq V\left( G\right) $$ , and a set $$A\in \mathrm {Ind}(G)$$ is critical if $$d(A)=\max \{d\left( I\right) :I\in \mathrm {Ind}(G)\}$$ [34].Let us recall the following definitions: $$\mathrm {core}\left( G\right) = {\displaystyle \bigcap } \left\{ S:S\textit{ is a maximum independent set}\right\} $$ [16], $$\mathrm {corona}\left( G\right) = {\displaystyle \bigcup } \left\{ S:S\textit{ is a maximum independent set}\right\} $$ [5], $$\mathrm {\ker }(G)= {\displaystyle \bigcap } \left\{ S:S\textit{ is a critical independent set}\right\} $$ [18], $$\mathrm {nucleus}(G)= {\displaystyle \bigcap } \left\{ S:S\textit{ is a maximum critical independent set}\right\} $$ [12] $$\mathrm {diadem}(G)= {\displaystyle \bigcup } \left\{ S:S\textit{ is a (maximum) critical independent set}\right\} $$ [24]. In this paper we focus on interconnections between $$\ker $$ , core, corona, $$\mathrm {nucleus}$$ , and diadem.

This paper addresses a technique for generating two types of nonconvex test problems. We study quadratic problems with d.c. inequality constraints and sum-of-ratios programs where both numerators and denominators are quadratic functions. Based on the idea of P. Calamai and L. Vicente, we propose the procedures for constructing nonconvex test problems with quadratic functions of any dimension, where global and local solutions are known. The implementation of the procedures does not require any complicated operations and solving auxiliary problems, except for elementary operations with matrices and vectors.

In this paper, we describe a non-convex constrained quadratic programming problem arising in short wave transmitting antenna array synthesis and provide preliminary computational results. We consider problem instances for three different antenna designs including up to 25 radiators. In the computational experiments, BARON package is compared to the gradient optimization method, applied to the unconstrained problem formulation using the penalty function method. Global optimality of the obtained solutions is established using BARON package the smallest instances of 4 radiators. On small instances, both methods have demonstrated similar results, while on larger instances significant difference has been observed. The set of local optima is studied experimentally. It is established that even though the problem instances have numerous local optima, the objective function in many local optima has the same value.

We suggest the modified splitting method for mixed variational inequalities and prove its convergence under rather mild assumptions. This method maintains the basic convergence properties but does not require any iterative step-size search procedure. It involves a simple adaptive step-size choice, which takes into account the problem behavior along the iterative sequence. The key element of this approach is a given majorant step-size sequence converging to zero. The next decreased value of step-size is taken only when the current iterate does not give a sufficient descent of the objective function. This descent value is estimated with the help of an Armijo-type condition, similar to the rule used in the inexact step-size linesearch. If the current iterate gives a sufficient descent, we can even take an increasing step-size value at the next iterate. Preliminary results of computational experiments confirm the efficiency of the proposed modification in comparison with the ordinary splitting method using the inexact step-size linesearch procedure.

We propose a dynamic version of the double description method for generating the extreme rays of a polyhedral cone. The dynamic version of the algorithm supports online input of inequalities. Some modifications of the method were implemented and the results of computational experiments are presented. On a series of problems, our implementation of the algorithm showed higher performance results in comparison with the known analogues.

In this paper popular open-source solvers are compared against Globalizer solver, which is developed at the Lobachevsky State University. The Globalizer is designed to solve problems with black-box objective function satisfying the Lipschitz condition and shows competitive performance with other similar solvers. The comparison is done on several sets of challenging multi-extremal benchmark functions. Also this work considers a method of heuristic hyperparameters control for the Globalizer allowing to reduce amount of initial tuning before optimization. The proposed scheme allows substantially increase convergence speed of the Globalizer by switching between “local” and “global” search phases in runtime.

We consider the classical optimization problem of minimizing a strongly convex, non-smooth, Lipschitz-continuous function with one Lipschitz-continuous constraint. We develop the approach in [10] and propose two methods for the considered problem with adaptive stopping rules. The main idea of the methods is using the dichotomy method and solving an auxiliary one-dimensional problem at each iteration. Theoretical estimates for the proposed methods are obtained. Partially, for smooth functions, we prove the linear rate of convergence of the methods. We also consider theoretical estimates in the case of non-smooth functions. The results for some examples of numerical experiments illustrating the advantages of the proposed methods and the comparison with some adaptive optimal method for non-smooth strongly convex functions are also given.

We consider optimization methods for convex minimization problems under inexact information on the objective function. We introduce inexact model of the objective, which as a particular cases includes inexact oracle [16] and relative smoothness condition [36]. We analyze gradient method which uses this inexact model and obtain convergence rates for convex and strongly convex problems. To show potential applications of our general framework we consider three particular problems. The first one is clustering by electorial model introduced in [41]. The second one is approximating optimal transport distance, for which we propose a Proximal Sinkhorn algorithm. The third one is devoted to approximating optimal transport barycenter and we propose a Proximal Iterative Bregman Projections algorithm. We also illustrate the practical performance of our algorithms by numerical experiments.

The linear second-order cone programming problem is considered. For its solution a variant of the primal simplex-type method is proposed. This variant is a generalization on the cone programming of the standard simplex method for linear programming. At each iteration the dual variable and dual slack are defined, and the move from the given extreme point to another one is realized. Finite and infinite convergence of the method to the solution of the problem having a special form is discussed.

Two transportation companies want to enter the market and they are aware of each other. The objective for the both of competitors is to maximize their respective profits by finding the best hub and spoke networks and price structures. One company wants to establish r hubs and the other wants to establish p hubs. It is assumed that the customers choose the route by price and the logistic regression based model is used to estimate how the demand is shared. After setting their networks, the competing companies engage in the price war. We propose a new model for finding a Stackelberg strategy that includes a price game, as bi-level nonlinear mixed-integer program, called the ( $$r{\mid }p$$ ) hub-centroid problem under the price war. It is shown that there is a unique finite Bertrand-Nash price equilibrium. On the basis of this result, we show the solution existence, propose a new equations for the best response pricing, and address the computational complexity of the problem. Finally, we discuss some possible future research directions that concern the solution approach and some other competitive scenarios that involve pricing.

If the lower-level problem in a bilevel optimization problem is replaced by its Karush-Kuhn-Tucker conditions, a mathematical program with complementarity constraints is obtained. Solving this nonconvex optimization problem, locally optimal solutions are computed which do in general not correspond to locally optimal solutions of the bilevel problem. Using a relaxation of this problem in two constraints it can be shown that a sequence of locally optimal solutions of the relaxed problems converges to a point which is related to a locally optimal solution of the bilevel optimization problem. If the lower-level problem is a linear one, relaxation of only the complementarity constraint is sufficient.

A comparative analysis is conducted of the efficiency of different partnership models in the natural resources sector of Russia. The first one is a classic public-private partnership (PPP) model used in developed countries, whereby a private company builds an object of public property and transfers it to the government either immediately after the construction or after a certain period of operation of the object. The second model represents for the government a costly alternative of the former and is used in Russia in underdeveloped regions. This model assumes that the government supports the investor in infrastructure development and, in part, in the implementation of mandatory environmental protection measures and can also provide tax incentives. In practical terms, this work aims to look into possible ways of transforming the current Russian PPP model towards the classic forms of partnership. To conduct the comparative analysis of the PPP models, Stackelberg models are formulated and original iterative algorithms are developed for solving the corresponding bilevel Boolean programming problems based on probabilistic local search. The properties of the equilibrium solutions are studied using real data for the Transbaikal krai. Based on the modeling results, the different partnership models are compared to find out the conditions under which the private investor would choose to invest in publicly owned industrial infrastructure facilities in Russia.

This work addresses the simplest class of the bilevel optimization problems (BOPs) with equilibrium at the lower level. We study linear BOPs with a matrix game at the lower level in their optimistic statement. First, we transform this problem to a single-level nonconvex optimization problem with the help of the optimality conditions for the lower level problem. Then we apply the special Global Search Theory (GST) for general d.c. optimization problems to the reduced problem. Following this theory, the methods of local and global searches in this problem are constructed. These methods take into account the structure of the problem in question.

The routing open shop problem, being a generalization of the metric TSP and the open shop scheduling problem, is known to be NP-hard even in case of two machines with a transportation network consisting of two nodes only. We consider a generalization of this problem with unrelated travel times of each machine. We determine a tight optima localization interval for the two-machine problem in the case when the transportation network consists of at most three nodes. As a byproduct of our research, we present a linear time $$\frac{5}{4}$$ -approximation algorithm for the same problem. We prove that the algorithm has the best theoretically possible approximation ratio with respect to the standard lower bound.

We address the problem of minimizing the aggregated fuel consumption by the vessels in an inland waterway (a river) with a single lock. The fuel consumption of a vessel depends on its velocity and the slower it moves, the less fuel it consumes. Given entry times of the vessels into the waterway and the deadlines before which they need to leave the waterway, we decide on optimal velocities of the vessels that minimize their private fuel consumption. Presence of the lock and possible congestions on the waterway make the problem computationally challenging. First, we prove that in general Nash equilibria might not exist, i.e., if there is no supervision on the vessels velocities, there might not exist a strategy profile from which no vessel can unilaterally deviate to decrease its private fuel consumption. Next, we introduce simple supervision methods to guarantee existence of Nash equilibria. Unfortunately, though a Nash equilibrium can be computed, the aggregated fuel consumption of such a stable solution is high compared to the consumption in a social optimum, where the total fuel consumption is minimized. Therefore, we propose a mechanism involving payments between vessels, guaranteeing Nash equilibria while minimizing the fuel consumption. This mechanism is studied for both the offline setting, where all information is known beforehand, and online setting, where we only know the entry time and deadline of a vessel when it enters the waterway.

Let $$f : \mathbb {R}^n \rightarrow \mathbb {R}$$ be a conic function and $$x_0 \in \mathbb {R}^n$$ . In this note, we show that the shallow separation oracle for the set $$K = \{x \in \mathbb {R}^n : f(x) \le f(x_0)\}$$ can be polynomially reduced to the comparison oracle of the function f. Combining these results with known results of D. Dadush et al., we give an algorithm with $$(O(n))^n \log R$$ calls to the comparison oracle for checking the non-emptiness of the set $$K \cap \mathbb {Z}^n$$ , where K is included to the Euclidean ball of a radius R. Additionally, we give a randomized algorithm with the expected oracle complexity $$(O(n))^n \log R$$ for the problem to find an integral vector that minimizes values of f on an Euclidean ball of a radius R. It is known that the classes of convex, strictly quasiconvex functions, and quasiconvex polynomials are included into the class of conic functions. Since any system of conic functions can be represented by a single conic function, the last facts give us an opportunity to check the feasibility of any system of convex, strictly quasiconvex functions, and quasiconvex polynomials by an algorithm with $$(O(n))^n \log R$$ calls to the comparison oracle of the functions. It is also possible to solve a constraint minimization problem with the considered classes of functions by a randomized algorithm with $$(O(n))^n \log R$$ expected oracle calls.

We present a framework for optimizing sparse quadratic assignment problems. We propose an iterative algorithm that dynamically generates the quadratic part of the assignment problem and, thus, solves a sparsified linearization of the original problem in every iteration. This procedure results in a hierarchy of lower bounds and, in addition, provides heuristic primal solutions in every iteration. This framework was motivated by the task of the French government to design the French keyboard standard, which included solving sparse quadratic assignment problems with over 100 special characters; a size where many commonly used approaches fail. The design of a new standard often involves conflicting opinions of multiple stakeholders in a committee. Hence, there is no agreement on a single well-defined objective function that can be used for an extensive one-shot optimization. Instead, the process is highly interactive and demands rapid prototyping, e.g., quick primal solutions, on-the-fly evaluation of manual changes, and prompt assessments of solution quality. Particularly concerning the latter aspect, our algorithm is able to provide high-quality lower bounds for these problems in several minutes.

We consider the traveling salesperson problem in a directed graph. The pyramidal tours with step-backs are a special class of Hamiltonian tours for which the traveling salesperson problem is solved by dynamic programming in polynomial time. The polytope of pyramidal tours with step-backs $$\mathrm{{PSB}}(n)$$ is defined as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The skeleton of $${\mathrm{{PSB}}} (n)$$ is the graph whose vertex set is the vertex set of $${\mathrm{{PSB}}} (n)$$ and the edge set is the set of geometric edges or one-dimensional faces of $${\mathrm{{PSB}}} (n)$$ . The main result of the paper is a necessary and sufficient condition for vertex adjacencies in the skeleton of the polytope $${\mathrm{{PSB}}} (n)$$ that can be verified in polynomial time.

In the Routing Open Shop problem n jobs are located in the nodes of an edge-weighted graph $$G=(V,E)$$ and m machines must process all jobs in such a way that each machine processes only one job at a time and each job is processed by only one machine at a time. The goal is to minimize the makespan, i. e. the time when the last machine comes back to the initial node called a depot (at the beginning all machines are in the depot). This problem is NP-hard even when the graph contains only two nodes. In this paper we consider the case of $$G=K_2$$ when all processing times and travel times are unit. We pose the conjecture that the problem is polynomially solvable in this case, i. e. that the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time $$O(\log mn)$$ . We provide some bounds on the makespan for the case of $$m=n$$ depending on the loads distribution.

Given a graph $$G=(V,E)$$ with edge weights and a subset $$R\subseteq E$$ of required edges, the NP-hard Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. The number b of vertices incident to an odd number of edges of R and the number c of connected components formed by the edges in R are both bounded from above by the number of edges that has to be traversed additionally to the required ones. We show how to reduce any RPP instance I to an RPP instance $$I'$$ with $$2b+O(c/\varepsilon )$$ vertices in $$O(n^3)$$ time so that any $$\alpha $$ -approximate solution for $$I'$$ gives an $$\alpha (1+\varepsilon )$$ -approximate solution for I, for any $$\alpha \ge 1$$ and $$\varepsilon >0$$ . That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We make first steps towards a PSAKS with respect to the parameter c.

We study a version of the graph 2-clustering problem. In this version, for a given undirected graph, one has to find a nearest 2-cluster graph, i.e., the graph on the same vertex set with exactly 2 nonempty connected components each of which is a complete graph. The distance between two graphs is the number of noncoinciding edges.The problem under consideration is NP-hard. In 2004, Bansal, Blum, and Chawla presented a simple polynomial time 3-approximation algorithm for the similar correlation clustering problem in which the number of clusters doesn’t exceed 2. In 2008, Coleman, Saunderson, and Wirth presented a 2-approximation algorithm for this problem applying local search to every feasible solution obtained by the 3-approximation algorithm of Bansal, Blum, and Chawla.Unfortunately, the method of proving the performance guarantee of the Coleman, Saunderson, and Wirth’s algorithm is not suitable for the graph 2-clustering. Coleman, Saunderson, and Wirth used switching technique that allows to reduce clustering any graph to the equivalent problem whose optimal solution is the complete graph, i.e., the cluster graph consisting of the single cluster.In the graph 2-clustering problem any optimal solution has to consist of exactly 2 clusters, so we need another approximation algorithm and another method of proving a bound on its worst-case behaviour. We present a polynomial time 2-approximation algorithm for the 2-clustering problem on general graphs. In contrast to the proof of Coleman, Saunderson, and Wirth, our proof of the performance guarantee of this algorithm doesn’t use switchings.

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is the well-known combinatorial optimization problem having numerous valuable applications in operations research. Unlike the classic CVRP (without time windows constraints), approximation algorithms with theoretical guarantees for the CVRPTW are still developed much less, even for the Euclidean plane. In this paper, perhaps for the first time, we propose an approximation scheme for the planar CVRPTW with non-uniform splittable demand combining the well-known instance decomposition framework by A. Adamaszek et al. and Quasi-Polynomial Time Approximation Scheme (QPTAS) by L. Song et al. Actually, for any $$\varepsilon \in (0,1)$$ the scheme proposed finds a $$(1+\varepsilon )$$ -approximate solution of the problem in polynomial time provided the capacity q and the number p of time windows does not exceed $$2^{\log ^\delta n}$$ for some $$\delta =O(\varepsilon )$$ . For any fixed p and q the scheme is Efficient Polynomial Time Approximation Scheme (EPTAS) with subquadratic time complexity.

We consider a modification to the classic medianoid problem, where facilities of different types are present on the market. A newcomer firm opens facilities providing a specific type of products and competes with existing facilities of that type. Each customer requires multiple products of different types and chooses the shortest route visiting facilities providing the needed types of products. A local search approach to maximize the market share of the newcomer firm is proposed, utilizing upper and lower bounds for the customers’ trip lengths to avoid time-consuming computations.

The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job’s first operation. The goal is to minimise the time needed for the completion of all jobs. This scheduling problem is NP-hard in the strong sense even for very restricted cases such as the case with a given order of jobs processing on one of the machines. The paper contributes to the efforts of establishing the borderline between the NP-hard and polynomial-time solvable cases by proving that there exists a polynomial-time algorithm which constructs an optimal schedule if the duration of each operation does not exceed one-fifth of the buffer capacity. The presented polynomial-time algorithm is used as a basis for a heuristic for the general case. This heuristic is complemented by a Lagrangian relaxation based heuristic and a bin-packing based constructive heuristic. The heuristics are tested by computational experiments.

We consider the bicriteria asymmetric travelling salesman problem (bi-ATSP): Given a complete directed graph where each arc is associated to a couple of positive weights, the aim is to find the Pareto set, consisting of all non-dominated Hamiltonian circuits. We propose new hybrid algorithms for the bi-ATSP using the adjacency-based representation of solutions and the operators that use the Pareto relation. Our algorithms are based on local search and evolutionary methods. The local search combines principles of the well-known Pareto Local Search procedures and Variable Neighborhood Search approach, realizing the search in width and depth. A genetic algorithm with NSGA-II scheme is applied to improve and extend a set of Pareto local optima by means of evolutionary processes. The experimental evaluation shows applicability of the algorithms to various structures of the bi-ATSP instances generated randomly and constructed from benchmark asymmetric instances with single objective.

We consider 1-skeletons of the symmetric and asymmetric traveling salesperson polytopes whose vertices are all possible Hamiltonian tours in the complete directed or undirected graph, and the edges are geometric edges or one-dimensional faces of the polytope. It is known that the question whether two vertices of the symmetric or asymmetric traveling salesperson polytopes are nonadjacent is NP-complete. A sufficient condition for nonadjacency can be formulated as a combinatorial problem: if from the edges of two Hamiltonian tours we can construct two complementary Hamiltonian tours, then the corresponding vertices of the traveling salesperson polytope are not adjacent. We consider a heuristic simulated annealing approach to solve this problem. It is based on finding a vertex-disjoint cycle cover and a perfect matching. The algorithm has a one-sided error: the answer “not adjacent” is always correct, and was tested on random and pyramidal Hamiltonian tours.

Having defined a complete bipartite graph G, with weights associated with both vertices and edges, the Bipartite Quadratic Programming problem (BQP) consists in selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. Applications of the BQP arise in mining discrete patterns from binary data, approximation of matrices by rank-one binary matrices, computation of the cut-norm of a matrix, etc. In addition, BQP is also known in the literature under different names such as maximum weighted induced subgraph, maximum weight bi-clique and maximum cut on bipartite graphs. Since the problem is NP-hard, many heuristic methods have been proposed in the literature to solve it. In this paper, we apply the recent Less is more approach, whose basic idea is to design a heuristic as simple as possible, i.e., a method that uses a minimum number of ingredients but provides solutions of better quality than the current state-of-the-art. To reach that goal, we propose a simple hybrid heuristic based on Tabu search, that uses two neighborhood structures and relatively simple rule for implementation of short-term memory operation. In addition, a simple rule for calculation of tabu list length is introduced. Computational results were compared favorably with the current state-of-the-art heuristics. Despite its simplicity, our heuristic was able to find 6 new best known solutions on very well studied test instances.

The Divide-and-Conquer approach is often used to solve hard instances of the Boolean satisfiability problem (SAT). In particular, it implies splitting an original SAT instance into a series of simpler subproblems. If this split satisfies certain conditions, then it is possible to use a stochastic pseudo-Boolean black-box function to estimate the time required for solving an original SAT instance with the chosen decomposition. One can use black-box optimization methods to minimize the function over the space of all possible decompositions. In the present study, we make use of peculiar features which stem from the NP-completeness of the Boolean satisfiability problem to improve this general approach. In particular, we show that the search space over which the black-box function is minimized can be extended by adding solver parameters and the SAT encoding parameters into it. In the computational experiments, we use the SMAC algorithm to optimize such black-box functions for hard SAT instances encoding the problems of cryptanalysis of several stream ciphers. The results show that the proposed approach outperforms the competition.

In this paper, abstract parabolic control systems in Hilbert space are considered. The state of the system is unknown, but there is an equation of measurement in discrete times. The initial state and disturbances are restricted by joint integral constraints. According to measurements, the information set is introduced that contains the true state of the system. This set includes all the states of the system that are compatible with the measurements. The preliminary aim of control consists in minimization of the terminal criterion depending of the information set. We suggest some statements of the problem based on the separation of control and observation processes. The optimal instants of transition from estimation to control are looked for as well. The approach is applied to distributed systems with partial derivatives and to systems with the deviation of time of retarded and neutral types. The approximation scheme are suggested and examples are considered.

Let $$Y^n,$$ , be the set of continuous bounded functions on the numerical axis with the following two properties: (1) the Fourier transform of a function is a function of bounded variation on the axis (in particular, a summable function); (2) a function is $$n-1$$ times continuously differentiable, its derivative of order $$n-1$$ is locally absolutely continuous, and the nth order derivative is bounded, more exactly, belongs to the space $$L_\infty $$ . In the space $$Y^n,$$ consider the class $$\mathcal {Q}^n$$ of functions, for which the $$L_\infty $$ -norm of the nth order derivative is bounded by a constant, for example, by 1. The following two approximation problems are discussed: the best approximation of the differentiation operator $$D^k$$ of order k, , by bounded operators on the class $$\mathcal {Q}^n$$ and the optimal calculation of the differentiation operator $$D^k$$ on functions from the class $$\mathcal {Q}^n$$ under the assumption that their Fourier transform is given with a known error in the space of functions of bounded variation, in particular, in the space L of functions summable on the axis. In interrelation with these two problems, we discuss the exact Kolmogorov type inequality in the space $$Y^n$$ between the uniform norm of the kth order derivative of a function, the variation of the Fourier transform of the function, and the $$L_\infty $$ -norm of its derivative of order n.

The paper is devoted to a generalization of a necessary optimality condition in the form of the Feedback Minimum Principle for a nonconvex discrete-time free-endpoint control problem. The approach is based on an exact formula for the increment of the cost functional. This formula is completely defined through a solution of the adjoint system corresponding to a reference process. By minimizing that increment in control variable for a fixed adjoint state, we define a multivalued map, whose selections are feedback controls with the property of potential “improvement” of the reference process. As a result, we derive a necessary optimality condition (optimal process does not admit feedback controls of a “potential descent” in the cost functional). In the case when the well-known Discrete Maximum Principle holds, our condition can be further strengthened. Note that obtained optimality condition is quite constructive and may lead to an iterative algorithm for discrete-time optimal control problems. Finally, we present sufficient optimality conditions for problems, where Discrete Maximum Principle does not make sense.

We consider a linear time-invariant control system with right-hand side depending on a small parameter. Assuming that the system is controllable, we study the asymptotics of the minimal eigenvalue of a system’s controllability Gramian and provide some bounds for the eigenvalue. These estimates are applied to the study of convexity properties of reachable sets for nonlinear control systems with integral constraints on control variables.

For an optimal control problem with intermediate state constraints, we construct an iterative descent algorithm and prove a related necessary optimality condition. Finally, we show how these results can be applied to measure-driven multiprocesses.

The problem of the ellipsoidal estimation of the reachable set of the control system under uncertainties is considered. The matrix included in the differential equations of the system dynamics is uncertain and only bounds on admissible values of this matrix coefficients are known. It is assumed that the initial states of the system are unknown but belong to a given star-shaped symmetric nondegenerate polytope. This polytope may be a non-convex set. Under such conditions, the dynamical system is a nonlinear and reachable set loses convexity property. A Minkowski function is used in the investigation to describe the trajectory tubes and their set-valued estimates. The step by step algorithm for constructing external and internal ellipsoidal estimates of reachable sets for such bilinear control systems is proposed. Numerical experiments were performed. The results of these numerical experiments are included.

We find conditions of unique strong solution existence for the generalized Showalter—Sidorov problem to semilinear evolution equations with a degenerate operator at the highest fractional Gerasimov—Caputo derivative and with some constraint on the image of the nonlinear operator. Then we consider a class of optimal control problems for systems, whose dynamics is described by such equations endowed with the respective initial value conditions. Target functional is assumed not to take into account control costs. In such situation we used the additional condition of the admissible controls set boundedness. The obtained result of the initial problem unique solvability and properties of some functions spaces are applied to the proof of optimal control existence for such class of problems. Abstract results are applied to study of a control problem for a system, which is described by an initial-boundary value problem to a nonlinear partial differential equation, not solvable with respect to the highest time fractional derivative.

We consider a broad class of optimal control problems for nonlinear measure-driven equations. For such problems, we propose necessary optimality conditions, which are based on a specific procedure of “feedback variation” of a given, reference impulsive control. The approach is based on using impulsive feedback controls designed by means of “weakly invariant functions”. The concept of weakly invariant function generalizes the notion of weakly monotone function. In the paper, we discuss the advantages of this approach and some perspectives of designing, on its base, nonlocal numeric algorithms for optimal impulsive control.

This paper proposes a semi-supervised classification method which combines machine learning regularization framework and cluster ensemble approach. We use the low-rank decomposition of the co-association matrix of the ensemble to significantly speed up calculations and save memory. Numerical experiments using Monte Carlo approach demonstrate the efficiency of the proposed method.

In this paper we consider the following Maximum Diversity Subset problem. Given a set of points in Euclidean space, find a subset of size M maximizing the squared Euclidean distances between the chosen points. We propose an exact dynamic programming algorithm for the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, the algorithm has a pseudo-polynomial time complexity. Using this algorithm, we develop an FPTAS for the special case where the dimension of the Euclidean space is bounded by a constant. We also propose a new proof of strong NP-hardness of the problem in the general case.

Stochastic optimization problems with probabilistic and quantile objective functions are considered. The probability objective function is defined as the probability that the value of losses does not exceed a fixed level. The quantile function is defined as the minimal value of losses that cannot be exceeded with a fixed probability. Sample approximations of the considered problems are formulated. A method to estimate the accuracy of the approximation of the probability maximization and quantile minimization is described for the case of a finite set of feasible strategies. Based on this method, we estimate the necessary sample size to obtain (with a given probability) an epsilon-optimal strategy to the original problems by solving their approximations in the cases of finite set of feasible strategies. Also, the necessary sample size is obtained for the probability maximization in the case of a bounded infinite set of feasible strategies and a Lipschitz continuous probability function.

Polynomial time approximation algorithms are proposed with constant approximation factors for a problem of computing the smallest cardinality set of identical disks whose union intersects each segment from a given set E of n straight line segments on the plane. This problem has important applications in operations research, namely in wireless and road network analysis. It is equivalent to finding the least cardinality piercing (or hitting) set for the corresponding family of n Euclidean r-neighborhoods of straight line segments of E on the plane, which are called r-hippodromes in the literature. When the number of distinct orientations is upper bounded by k of segments from E, a simple $$O(n\log n)$$ -time 4k-approximate algorithm is known for this problem. Besides, when E contains arbitrary straight line segments, overlapping at most at their endpoints, $$O(n^4\log n)$$ -time 100-approximate algorithm is given recently. In the present paper, simple approximation algorithms are proposed with small approximation factors for E, being edge set of some special plane graphs of interest in road network applications; here the number of distinct orientations of straight line segments from E can be arbitrarily large. More precisely, $$O(n^2)$$ -time approximation algorithms are constructed for edge sets of either Gabriel or relative neighborhood graphs or of Euclidean minimum spanning trees with factors of 14, 12 and 10 respectively. These algorithms are much faster, more accurate and conceptually much simpler than the aforementioned 100-approximate algorithm for the general case of the problem on edge sets of arbitrary plane graphs.

We consider one strongly NP-hard problem of clustering a finite set of points in Euclidean space. In this problem, we need to partition a finite set of points into two clusters minimizing the sum over both clusters of the weighted intracluster sums. Each of these sums is the sum of squared distances between the elements of the cluster and their center. The center of the one cluster is unknown and determined as the centroid, while the center of the other one is fixed at the origin. The weight factors for both intracluster sums are the given sizes of the clusters. In this paper, we present an approximation algorithm for the problem and prove that it is a polynomial-time approximation scheme (PTAS).

We consider the problem of controlling a rod attached to a rotor. A rotating flywheel is attached to one end of the rod. The rotor is controlled by the first player. The flywheel is controlled by the second player. The goal of the first player is to bring the rotor to a vertical position at a given time. The goal of the second player is the opposite. This problem is an example of a more general linear differential game with a one-dimensional aim. Using a linear change of variables, this problem is reduced to a single-type one-dimensional differential game with a non-convex terminal set, for which we have found the necessary and sufficient conditions of termination and constructed the corresponding controls of the players.

We analyze the uniform asymptotics of the equilibrium value (as a function of initial state) in the case when its payoffs are averaged with respect to a density that depends on some scale parameter and this parameter tends to zero; for example, the Cesàro and Abel averages as payoffs for the uniform and the exponential densities, respectively. We also investigate the robustness of this asymptotics of the equilibrium value with respect to the choice of distribution when its scale parameter is small enough. We establish the class of densities such that the existence of the asymptotics of the equilibrium value for some density guarantees the same asymptotics for a piecewise-continuous density; in particular, this class includes the uniform, exponential, and rational densities. By reducing the general n-person dynamic games to mappings that assigns to each payoff its corresponding equilibrium value, we gain an ability to consider dynamic games in continuous and discrete time, both in deterministic and stochastic settings.

The paper is concerned with the construction of open-loop strategies for the n-person nonzero-sum differential game with multilevel hierarchy. The dynamics of the first player (leader) is defined by its own position and control. The player of further levels of hierarchy knows the position and control of the players of the upper hierarchical levels. At the same time the dynamics and payoff functional of the player do not depend on the position and control of lower hierarchical levels.We solve this problem with the help of consequent solutions of optimal control problems for each player. Using the solution of Hamilton—Jacobi equation and the results of optimal control theory we construct the open-loop controls of the players. The specifics of this problem is the construction of solution for the Hamilton—Jacobi equation with the Hamiltonian discontinuous w.r.t. phase variable. In this case we use the notion of multivalued solution proposed by Subbotin. We show that the open-loop controls provide a Nash equilibrium in the differential game with multilevel hierarchy and the set of payoffs of the players is described by the multivalued solution of the corresponding Hamilton—Jacobi equation.

The subject of this paper is a linear quadratic case of a differential game model with continuous updating. This class of differential games is essentially new, there it is assumed that at each time instant, players have or use information about the game structure defined on a closed time interval with a fixed duration. As time goes on, information about the game structure updates. Under the information about the game structure we understand information about motion equations and payoff functions of players. A linear quadratic case for this class of games is particularly important for practical problems arising in the engineering of human-machine interaction. The notion of Nash equilibrium as an optimality principle is defined and the explicit form of Nash equilibrium for the linear quadratic case is presented. Also, the case of dynamic updating for the linear quadratic differential game is studied and uniform convergence of Nash equilibrium strategies and corresponding trajectory for a case of continuous updating and dynamic updating is demonstrated.

It studies the problem of immigration proof partition for communities (countries) in a multidimensional space. This is an existence problem of Tiebout type equilibrium, where migration stability suggests that every inhabitant has no incentives to change current jurisdiction. In particular, an inhabitant at every frontier point has equal costs for all available jurisdictions. It is required that the inter-country border is represented by a continuous curve.The paper presents the solution for the case of the costs described as the sum of the two values: the ratio of total costs on the total weight of the population plus transportation costs to the center presented as a barycenter of the state. In the literature, this setting is considered as a case of especial theoretical interest and difficulty. The existence of equilibrium division is stated via an approximation reducing the problem to the earlier studied case, in which centers of the states never can coincide: to do this an earlier proved a generalization of conic Krasnosel’skii fixed point theorem is applied.

The paper considers the model of opinion dynamics in the network having a star structure. An opinion about an event is distributed among network agents restricted by the network structure. The agent in the center of the star is influenced by all other agents with equal intensity. The agents located in non-center nodes are influenced only by the agent located in the center of the star. Additionally, it is assumed that there are two players who are not located in the considered network but they influence the agents’ opinions with some intensities which are strategies of the players. The goal of any player is to make opinions of the network agents be closer to the initially given value as much as possible in a finite time interval. The game of competition for opinion is linear-quadratic and is solved using the Euler-equation approach. The Nash equilibrium in open-loop strategies is found. A numerical simulation demonstrates theoretical results.

In the paper a two-level infinitely repeated hierarchical game with one player (center) $$C_0$$ on the first level and $$S_1,\ldots , S_n$$ subordinate players on the second is considered. On each stage of the game player $$C_0$$ selects vector $$x=(x_1, \ldots ,x_n)$$ from a given set X, in which each component represents vector of resources delivered by $$C_0$$ to one of subordinate players, i.e. $$x_i =(x_{i1},\ldots ,x_{im})$$ . At the second level, $$S_i$$ , $$i=1,2,\ldots , n$$ , choose the controls $$y_i\in Y_i (x_i)$$ , where $$Y_i (x_i)$$ depends upon the choice of player $$C_0$$ .In this game, a set of different Nash equilibrium also based on threat and punishment strategies is obtained.In one case, the center enforces special behavior of subordinate firms (vector of manufactured goods), threatening to deprive them of resources on the next steps if the subordinate firms refuse to implement the prescribed behavior.In another case, the subordinate firms can force the center to use a certain resource allocation threatening to stop production.Using different combinations of such behaviors on different stages of the game, we obtain a wide class of Nash equilibrium in the game under consideration.The cooperative version of the game is also considered. The conditions are derived under which the cooperative behavior can be supported by Nash Equilibrium or Strong Nash Equilibrium (Nash Equilibrium stable against deviations of coalitions).

We consider a dynamic, discrete-time, game model where the players use a common resource and have different criteria to optimize. The coalition formation process in dynamic multicriteria games is considered. The characteristic function is constructed in two unusual forms under the assumption of informed players: all players decide simultaneously or members of coalitions are assumed to be the leaders and players decide sequentially. Internal and external stability concepts are adopted for dynamic multicriteria games to obtain new stability conditions. To illustrate the presented approaches a multicriteria bioresource management problem with a finite horizon is investigated.