Optimization and Applications

In the paper, we investigate the problem of optimal control for a linear system of ordinary differential equations with linear boundary conditions. The boundary conditions include, as terms, the values of the phase variable both at separate intermediate points and their integral values over individual intervals of the independent variable. The values of the right sides of unseparated boundary conditions are optimizing in the problem. In the paper the necessary conditions for the existence and uniqueness of the solution to the boundary value problem, the convexity of the target functional, the necessary optimality conditions for the optimized parameters are obtained. Conditions contain constructive formulas of the gradient components of the functional. The numerical solution of an illustrative problem is considered.

A new approach to solving terminal control problems with phase constraints, based on saddle-point sufficient optimality conditions, is considered. The basis of the approach is Lagrangian formalism and duality theory. We study linear controlled dynamics in the presence of phase constraints. The cross section of phase constraints at certain points in time leads to the appearance of new intermediate finite-dimensional convex programming problems. In fact, the optimal control problem, defined over the entire time interval, is split into a number of independent intermediate subproblems, each of which is defined in its own sub-segment. Combining the solutions of these subproblems together, we can obtain solutions5 to the original problem on the entire time interval. To this end, a gradient flow is launched to solve all intermediate problems at the same time. The convergence of computing technology to the solution of the optimal control problem in all variables is proved.

We consider a stylized distribution channel, where a manufacturer sells a single kind of good to a retailer. In classical setting, the profit of manufacturer is quadratic w.r.t. wholesales discount, while the profit of retailer is quadratic w.r.t. retail discount (pass-through). Thus, the wholesale prices and the retail prices are continuous. These results are elegant mathematically but not adequate economically. Therefore, we assume that wholesale discount and retail discounts are piece-wise constant. We show the strict concavity of retailer’s profits w.r.t. retail discount levels. As for the manufacturer’s profits w.r.t. wholesale discount levels, we show that strict concavity can be guaranteed only in the case when retail discount is constant and sufficiently large.

We consider the issue of synthesis and analysis of multidimensional controlled model with consideration of predator-prey interaction and taking into account migration flows, and propose new formulations of corresponding optimal control problems. In search for optimal trajectories, we develop a generalized algorithm of global parametric optimization, which is based on the development of algorithm for generating control function and on modifications of classical numerical methods for solving differential equations. We present the results of the search for optimal trajectories and control functions generation. Additionally, we propose an algorithm for the transition to stochastic controlled models based on the development of a method for constructing self-consistent stochastic models. The tool software as a part of a software package for modeling controlled dynamical systems has been developed. We have also carried out a computer study of the constructed models. The results can be used in the problems of modeling dynamics processes, taking into account the requirements of control and optimization.

Given a set of two input strings and a pattern string, the constrained longest common subsequence problem deals with finding a longest string that is a subsequence of both input strings and that contains the given pattern string as a subsequence. This problem has various applications, especially in computational biology. In this work we consider the \(\mathcal {NP}\)–hard case of the problem in which more than two input strings are given. First, we adapt an existing A\(^*\) search from two input strings to an arbitrary number m of input strings (\(m \ge 2\)). With the aim of tackling large problem instances approximately, we additionally propose a greedy heuristic and a beam search. All three algorithms are compared to an existing approximation algorithm from the literature. Beam search turns out to be the best heuristic approach, matching almost all optimal solutions obtained by A\(^*\) search for rather small instances.

The nonlinear trajectory tracking control problem for underactuated mechanical systems is considered on the example of a ship motion model. The control that implements the goal should be designed taking into account feedback delay as well as state and control constraints. The purpose is to propose a control law such that, on the one hand, it has the form of explicit feedback, on the other hand, its parameters can be found using standard software tools, provided that the numerical characteristics of the system are specified. In this case, uniform asymptotic stability of the desired motion of the system should be ensured.

The problem is solved by reducing to the stabilization problem for a triangular LPV system with the subsequent transformation into several optimization problems with standard numerical procedures for solving. The domain of attraction that fit into the prescribed region is estimated via sublevel sets of quadratic Lyapunov functions using the Razumikhin conditions and stability properties of cascaded systems. The developed algorithms are implemented based on standard procedures of computational software. The results obtained can be applied to other control problems.

A new elementary proof of Farkas’ theorem is proposed. The proof is based on the consideration of the always solvable problem of minimizing the residual of a system of linear equations/inequalities and the necessary and sufficient conditions for the minimum of this problem. Minimizing the residuals of an inconsistent system makes it easy to calculate the normal solution to a consistent system. The connection between Farkas’ theorem and linear and quadratic programming is shown. A new version of the theorem on alternatives is proposed.

We present recent advances in the analysis of nonlinear structures and their applications to nonlinear optimization problems with constraints given by nonregular mappings or other singularities obtained within the framework of the p-regularity theory developed over the last twenty years. In particular, we address the problem of description of the tangent cone to the solution set of the operator equation, optimality conditions, and solution methods for optimization problems.

We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that it turned out to be well suited for finding several edge-disjoint MST of a given diameter. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an segment \([a_n; b_n]\), \(a_n>0\). Sufficient conditions of asymptotic optimality are presented. It is also noteworthy that the new algorithmic approach to solve the problem of finding a given-diameter MST both on directed and undirected graphs.

The linear regression analysis problems are considered under the assumption of the presence of noise in the output and input variables. To estimate the measure of approximation of the initial data, the \(l_1\) metric is used, which has a probabilistic rationale as a maximum likelihood method for two-sided exponential noise distribution. This approximation problem can also be interpreted as an improper (has no solution) interpolation problem, for which it is required to change (correct) optimally the positions of the points so that they all lie on the same hyperplane. In addition, the case of preliminary linear data transformation is considered, while the original information matrix is subject to correction. Therefore, the arising problems belong to the new class of parametric correction. It is shown that these approximation (corrections) problems can be reduced to a set of a finite number of linear programming problems.

We consider the repetition-free longest common subsequence (RFLCS) problem, where the goal is to find a longest sequence that appears as subsequence in two input strings and in which each character appears at most once. Our approach is to transform a RFLCS instance to an instance of the maximum independent set (MIS) problem which is subsequently solved by a mixed integer linear programming solver. To reduce the size of the underlying conflict graph of the MIS problem, a relaxed decision diagram is utilized. An experimental evaluation on two benchmark instance sets shows the advantages of the reduction of the conflict graphs in terms of shorter total computation times and the number of instances solved to proven optimality. A further advantage of the created relaxed decision diagrams is that heuristic solutions can be effectively derived. For some instances that could not be solved to proven optimality, new state-of-the-art results were obtained in this way.

We investigate the problem of setting up battery swapping stations for electric scooters in an urban area from a computational optimization point of view. For the considered electric scooters batteries can be swapped quickly in a few simple steps. Depleted batteries are recharged at these swapping stations and provided again to customers once fully charged. Our goal is to identify optimal battery swapping station locations as well as to determine their capacities appropriately in order to cover a specified level of assumed demand at minimum cost. We propose a Mixed Integer Linear Programming (MILP) formulation that models the customer demand over time in a discretized fashion and also considers battery charging times. Moreover, we propose a Large Neighborhood Search (LNS) heuristic for addressing larger problem instances for which the MILP model cannot practically be solved anymore. Prototype implementations are experimentally evaluated on artificial benchmark scenarios. Moreover, we also consider an instance derived from real-world taxi and bus stop shelter data of Manhattan. With the MILP model, instances with up to 1000 potential station locations and up to 2000 origin/destination demand pairs can be solved to near optimality, while for larger instances the LNS is a highly promising choice.

Nonlinear least squares iterative solver developed earlier by the author is applied for numerical solution of special system of multilinear equations arising in the problem of canonical tensor decomposition. The proposed algorithm is based on easily parallelizable computational kernels such as matrix-vector multiplications and elementary vector operations and therefore has a potential for a quite efficient implementation on modern high-performance computers. The results of numerical testing presented for certain examples of large scale dense and medium size sparse 3D tensors found in existing literature seem very competitive with respect to computational costs involved.

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is a specialized version of the well-known Generalized Traveling Salesman Problem (GTSP) having a lot of valuable applications in operations research. Despite the practical significance, results in the field of design, implementation, and numerical evaluation the algorithms for this problem remain still rare. In this paper, to the best of our knowledge, we propose the first heuristic solver for this problem augmented by numerical evaluation results of its performance against the public test instances library PCGTSPLIB. Our algorithm is an extension of the recent Large Neighborhood Search (GLNS) heuristic GTSP solver designed to take into account additional precedence constraints. Similarly to GLNS, the source code of all our algorithms is open, and the executables are freely accessible, which ensures the reproducibility of the reported numerical results.

We consider a posteriori approach to the problem of noise-proof simultaneous detection and discrimination of subsequences-fragments having some given properties in a quasiperiodic sequence. The solution to the problem is stated for the case when the quantity of sought subsequences is unknown. We assume that 1) a finite alphabet of reference sequences is given; 2) a set of permissible deformations is defined for the alphabet, this set gathers all possible extensions of its elements (by duplicating their components); 3) every subsequence-fragment in the quasiperiodic sequence belongs to the set of permissible deformations; 4) subsequences-fragments do not intersect each other, and the difference between the initial positions of two neighboring fragments is limited from above by a given value.

We show that in the framework of a posteriori approach, the problem of simultaneous detection and discrimination reduces to solving an unexplored discrete optimization problem. A polynomial-time algorithm that guarantees the optimal solution to this optimization problem is proposed. The results of the numerical simulation are presented.

Considered is the problem of the attraction domain estimation in the space “distance to the trajectory – orientation” for the problem of the planar motion control of a wheeled robot. This problem has received much attention in connection with precision farming applications  [11]. The mathematical model of the robot takes into account kinematic relationships between velocity of a given target point, orientation of the platform, and control. It is supposed that the four wheels platform moves without slipping. The rear wheels are assumed to be driving while the front wheels are responsible for the rotation of the platform. The control goal is to drive the target point to the desired trajectory and to stabilize its motion. The case of the straight line trajectory is considered in the paper. The control was obtained using the feedback linearization approach  [5] and is subject to the two-sided constraints. The system is then rewritten in the so called Lurie form  [1, 12] and embedded in the class of systems with nonlinearities constrained by the sector condition. Based on this, the method of attraction domain estimation in the state space of the system is proposed. The negativity condition for the derivative of the Lyapunov function with respect to the system’s dynamics under sector conditions is formulated in terms of solvability of the linear matrix inequality (LMI)  [2]. To take into account quadratic constraints the S-procedure  [12] is applied. The Lyapunov function is supposed to be a quadratic form with addition of an integral over nonlinearity (so called Lurie-Postnikov function). Earlier, other classes of Lyapunov functions were used for this problem, see for example  [8]. The optimization problem was formulated as a semidefinite programming (SDP) problem with LMI constraints. Numerical results are presented. The estimates achieved show less conservativeness in comparison with ellipsoidal ones.

Decentralized distributed optimization over time-varying graphs (networks) is nowadays a very popular branch of research in optimization theory and consensus theory. Applications of this field include drone or satellite networks, as well as distributed machine learning. However, the first theoretical results in this branch appeared only a few years ago. In this paper, we propose a simple method which alternates making gradient steps and special communication procedures. Our approach is based on reformulation of the distributed optimization problem as a problem with linear constraints and then replacing linear constraints with a penalty term.

The simulation of the airframe assembly process implies the modelling of contact interaction of compliant parts. As every item in mass production deviates from the nominal, the analysis of the assembly process involves the massive solving of contact problems with varying input data. The contact problem may be formulated in terms of quadratic programming. The bottleneck is the computation time that may be reduced by the use of specially adapted optimization methods. The considered problems have an ill-conditioned Hessian and a sparse matrix of constraints. It is necessary to solve a large number of problems with the same constraint matrix and Hessian. This work considers the primal-dual interior-point method (IPM) and proposes its adaptation to the solving of assembly problems. A method is proposed for choosing a feasible starting point based on a physical interpretation for reducing the number of IPM iterations. The numerical comparison of the approaches to solve a system of linear equations at each iteration of IPM is presented, i.e. an augmented system and a normal equation (its reduction) using various preconditioners. Finally, IPM is compared by computation time with an active-set method, a Newton projection method and Lemke’s method on a number of aircraft assembly problems.

Electric energy generation is an important sector of Russian economy. Its optimizing is an important measure for increasing the social welfare and the GDP. This study aims to propose a mathematical model for optimizing a wholesale electricity market’s performance by means of modern economic and technical tools: consumption tariffs with multiple rates that aim to shift daily consumption from the pike times, renewable energy generators, energy storages.

In this paper, we consider equilibrium problems in Hadamard metric spaces. For an approximate solution of problems, a new iterative adaptive extra-proximal algorithm is proposed and studied. In contrast to the previously used rules for choosing the step size, the proposed algorithm does not calculate bifunction values at additional points and does not require knowledge of information on of bifunction’s Lipschitz constants. For pseudo-monotone bifunctions of Lipschitz type, the theorem on weak convergence of sequences generated by the algorithm is proved. The proof is based on the use of the Fejer property of the algorithm with respect to the set of solutions of problem. It is shown that the proposed algorithm is applicable to pseudo-monotone variational inequalities in Hilbert spaces.

The linear second-order cone programming problem is considered. For its solution, the dual simplex-type method is proposed. The method is the generalization of the standard dual simplex method for linear programming for cone programming. At each iteration the primal variable is defined, and pivoting of the dual variable is carried out. The proof of the local convergence is given.

The investigation deals with the choice of a finite-difference scheme for approximating the heat diffusion equation when solving the inverse coefficient problem in a three-dimensional formulation. Using the examples of a number of nonlinear problems for a three-dimensional heat equation whose coefficients depend on temperature, a comparative analysis of several schemes of alternating directions was performed. The following schemes were examined: a locally one-dimensional scheme, a Douglas-Reckford scheme, and a Pisman-Reckford scheme. Each numerical method was used to obtain the temperature distribution inside the parallelepiped. When comparing methods, the accuracy of the obtained solution and the computer time to achieve the required accuracy were taken into account. The inverse coefficient problem was reduced to the variational problem. Based on the carried out research, recommendations were made regarding the choice of a finite-difference scheme for the discretization of the primal problem when solving the inverse coefficient problem.