Optimization and Applications

The object of investigation is the routing open shop problem, in which a fleet of machines have to visit all the nodes of a given transportation network to perform operations on some jobs located at those nodes. Each machine has to visit each node, to process each job and to return back to the common initial location—the depot. Operations of each job can be processed in an arbitrary sequence, any machine may perform at most one operation at a time. The goal is to construct a feasible schedule to minimize the makespan. The routing open shop problem is known to be NP-hard even in the simplest two-machine case with the transportation network consisting of just two nodes (including the depot). We consider a certain generalization of this problem in which travel times are individual for each of the two machines and the structure of the transportation network is an arbitrary cactus. We generalize an instance reduction algorithm known for the problem on a tree with identical travel times, and use it to describe new polynomially solvable cases for the problem, as well as an efficient approximation algorithm for another special case with a tight approximation ratio guarantee.

A metric projection from the real Hilbert space onto a subset of the boundary of a closed convex (not necessary bounded) set is considered. We show a connection between Lipschitz continuity on some subset of the Hilbert space of operator of metric projection with the Lipschitz constant strictly less than 1 and local strong convexity of the set (in terms of modulus of convexity for intersection of a set and a ball with a small radius).

In this paper we consider the problem of the sign-definiteness of a quadratic form (QF) in the domain defined by quadratic constraints under quadratic constraints. Each constraint is determined by an inequality on a QF. Well known and widely applicable in the control theory approach consists of using so called S–procedure. The semidefinite relaxation approach investigated in this paper allows us to derive an S–procedure from duality conditions. However, the S–procedure, which gives necessary and sufficient conditions for sign-definiteness for the relaxed problem, gives only sufficient conditions for sign-definiteness for the initial problem if the number of quadratic constraints is two or more. In this paper the new approach is proposed, allowing establishment of conditional sign definiteness in some cases, when the S–procedure doesn’t give an answer. The results are illustrated by an example.

On the plane, the barrier is a line segment, and the mobile sensors are initially located at some points (depots). Each sensor can travel a limited-length path, starting and ending at its depot. That part of the barrier, along which sensor moved, is covered by this sensor. It is required to find a min-power subset of sensors covering the entire barrier. The complexity of this problem is not known. In this paper, we have found the special cases of polynomial solvability and state some necessary and sufficient conditions for the existence of the solution. An efficient (polynomial) algorithm for checking the existence of the solution is proposed. Moreover, we have developed some approximation algorithms. In particular, an efficient implementation of the dynamic programming algorithm, which in some special cases yields an optimal solution, is proposed.

The designing of multidimensional deterministic and stochastic models of populations dynamics with regard to the relations of competition and mutualism, and migration is described. The model examples in three-dimensional and four-dimensional cases are considered, qualitative and numerical investigation of models is carried out. The transition to the corresponding multidimensional nondeterministic models defined by stochastic differential equations is made. The stability analysis of stationary states is performed. The structure of multidimensional models with competition and mutualism is described with regard to the properties of the Fokker–Planck equations and the formulated rules for the transition to stochastic differential equations in the Langevin form. Numerical experiments for the studied models are carried out using the developed software package. Algorithms for generating trajectories of the Wiener process and multipoint distributions, as well as modifications of the Runge–Kutta method, are used. The comparative analysis of deterministic and stochastic models is carried out. The conditions under which stochastization has a little effect on the stability of the system are studied. Some formulations of population dynamics optimal control problems in models are proposed. The results can be applied in problems of synthesis, optimal control and stability analysis of generalized models of interconnected communities dynamics.

We consider a parametrized constrained optimization problem, which can be represented as the Moreau-type infimal convolution of the norm and some (nonconvex in general) function f. This problem arises particularly in optimal control and approximation theory. We assume that the admissible set A is weakly convex and function f is Lipschitz continuous and weakly convex on the convex hull of A. We show that the problem is Tykhonov well-posed and the solution of the problem is unique and Lipschitz continuous in some neighbourhood of A. Exact estimates for the size of the neighbourhood and for the Lipschitz constant are obtained. Based on these results we prove lower regularity of the optimal value (marginal) function of this problem in some neighbourhood of A.

This paper is devoted to an unexplored discrete optimization problem, which can be interpreted as a problem of least mean squares approximation of some observed discrete-time signal (a numerical time series) by an unobservable quasiperiodic (almost periodic) pulse signal generated by a pulse with a given pattern (reference) shape. Quasiperiodicity is understood, first, in the sense of admissible fluctuations of the interval between repetitions of the reference pulse, and second, in the sense of admissible nonlinear time expansions of its reference shape. Such problems are common in biomedical applications related to monitoring and analyzing electrocardiogram (ECG), photoplethysmogram (PPG), and several other signals. In the optimization model, the number of generated (admissible or approximating) quasiperiodic pulse sequences grows exponentially with the duration of the discrete-time signal (i.e., with the number of points in the time series). The size of the admissible solutions set also grows exponentially. However, despite that exponential growth, we have constructively proved the optimization problem polynomial-time solvability. Namely, we propose an algorithm that finds an optimal solution to the problem in $$\mathcal {O} (T_{\max }^{3}N)$$ time; where N is the duration of the observed signal (the number of points in the time series), $$ T_{\max } \le N $$ is a positive integer number which bounds the fluctuations of the repetition period. If $$T_{\max }$$ is a part of the input, then the algorithm’s running time is $$ \mathcal {O} (N^{4}) $$, i.e., the algorithm is polynomial. If $$T_{\max }$$ is a fixed parameter (that is typical for applications), then the running-time of the algorithm is $$ \mathcal {O} (N) $$, i.e., the algorithm is linear in time. Numerical simulation examples demonstrate the robustness of the algorithm in the presence of additive noise.

This paper considers pricing equity-linked notes (ELN) portfolio and related portfolio optimization. ELNs are the derivative instruments which can be viewed as bonds with floating coupons. The floating coupon is represented in terms of an embedded option that depends on the behavior of a certain underlying asset or a basket of them. We provide the new optimization problem by hyperbolic absolute risk aversion (HARA) utility function approach. We obtain the solution of this problem in terms of a dynamic programming equation.

Gradient optimization methods are often used to solve problems of computer simulation of the crystal structures of materials. In this case it becomes necessary to calculate the partial derivatives of the total atoms’ system energy according to different parameters. Frequently the calculation of these derivatives is an extremely time-consuming and difficult problem. When describing and modeling the crystal structure of a material characterized by chemical composition, geometry, and type of chemical bond, interatomic interaction potentials are used. In this paper a special multi-step process is constructed to calculate the energy of the atoms’ system in the case when the interaction of atoms is described by the Tersoff Potential. On the basis of the constructed multi-step process an algorithm for calculation the second derivatives (Hessian) of the atoms’ system energy with respect to the coordinates of the atoms is presented. The above-mentioned second derivatives are provided both for the case when the material under study has a three-dimensional structure, and for the case when a two-dimensional model of a multilayer piecewise-homogeneous material is considered.

We consider three problems of partitioning a finite set of N points in the d-dimensional Euclidean space into two clusters balancing the value of (1) the normalized by a cluster size sum of squared deviations from the mean, (2) the sum of squared deviations from the mean, and (3) the size-weighted sum of squared deviations from the mean. We have proved the NP-completeness of all these problems.

When processing multiple navigation satellite systems, including GPS, GLONASS, Galileo, Beidou, QZSS, the overall number of the pseudorange and carrier phase signals can exceed several tens. On the other hand, a much smaller number of them is usually sufficient to achieve necessary precision of positioning. Also, some parts of precise positioning algorithms, like carrier phase ambiguity resolution, are very sensitive to the problem dimension as they include the integer search. To reduce computational cost of positioning, the optimal choice of signals involved in computations should be performed. Optimization is constrained by a given number of satellite signals to be chosen for processing. This optimization problem falls into the class of binary optimization problems which are hard for precise solution. In this paper, we present approaches to an approximate solution of the optimal selection problem. After the linear relaxation of binary constraints, the relaxed problem is convex and can be transformed to semidefinite programming or second-order cone programming problems. The optimal solution of the relaxed problem can be considered as a lower bound of a combinatorial optimization problem. After rounding non-integer variables the approximate solution is obtained. As a result, two-sided bounds of the optimum are obtained. In practice, the approximate solution is very close to precise solution for most real world cases. Because the relaxed problem is convex, it can be solved efficiently.

We study a stylized vertical distribution channel where a representative manufacturer sells a single kind of good to a representative retailer. The control of the manufacturer is the price discounts, while the control of the retailer is pass-through. In the classical setting, the arising problem is quadratic with respect to wholesale price discount and pass-through. Thus, the optimal sale price is continuous. It seems elegant mathematically but not adequate economically. Therefore we assume that the controls are constant or piece-wise constant. This way, the optimal control problem reduces to the mathematical programming problem where the profit of the manufacturer is quadratic with respect to price discount level(s), while the profit of the retailer is quadratic with respect to pass-through level(s). We study the concavity property of the profits. This allows getting the optimal behavior strategies of the manufacturer and the retailer.

Nonlinear least squares type iterative solver for f(x) = 0 is considered based on successive solution of orthogonal projections of the linearized equation on a sequence of appropriately chosen low-dimensional subspaces. The bases of the latter are constructed using only the first-order derivatives of the function. The techniques based on the concept of the limiting stepsize along normalized direction (developed earlier by the author) is used to guarantee the monotone decrease of the nonlinear residual norm. The results of numerical testing are presented, including not only small-sized standard test problems, but also larger and harder examples, such as algebraic problems associated with canonical decomposition of dense and sparse 3D tensors as well as finite-difference discretizations of 2D nonlinear boundary problems for 2nd order partial differential equations.

The optimal control problem with phase constraints is considered. A new indirect approach of synthesized optimal control is proposed as an alternative to direct methods. A comparative study of direct and indirect approaches is carried out on the problem of optimal control for a small group of mobile robots in the complex environment with phase constraints by evolutionary algorithms. With a direct approach to the numerical solution of the optimal control problem, the control function is searched in the form of piece-wise functional approximation. The indirect approach of synthesized optimal control comes from the engineering practice. Instead of reducing the optimal control problem to the problem of finite-dimensional optimization, we firstly make the object stable relative to some point in the state space by solving an additional task of synthesis of stabilizing control and then we find the coordinates of stabilization points as the desired parameters of optimal control.

We consider the Connected k-factor problem (k-CFP): given a complete edge-weighted n-vertex graph, the goal is to find a connected k-regular spanning subgraph of maximum or minimum total weight. The problem is called geometric, if the vertices of a graph correspond to a set of points in a normed space $$\mathbb R^d$$ and the weight of an edge is the distance between its endpoints. The k-CFP is a natural generalization of the well-known Traveling Salesman Problem, which is equivalent to the 2-CFP. In this paper we complement the known $$(1-1/ k^2)$$-approximation algorithm for the maximum k-CFP from [Baburin et al., 2007] with an approximation algorithm for the geometric k-CFP, that guarantees a relative error $$\varepsilon = O\left( (k/n)^{1/(d+2)}\right) $$. Together these two algorithms form an asymptotically optimal algorithm for the geometric k-CFP with an arbitrary value of k in an arbitrary normed space of fixed dimension d. Finally, the asymptotically optimal algorithm can be easily transformed into a PTAS for the considered geometric problem.

The problem of optimal exploitation of an ecological population with a binary structure is considered (there is an additional criterion for population structuring in addition to age or developmental stage). It is assumed that population state dynamics is described by a nonlinear generalization of the Leslie model. We prove a criterion for the existence of so-called quasi-preserving controls that support the sustainable population dynamics. Moreover, optimal quasi-preserving controls with a minimum number of nonzero coordinates (i.e., controls that preserve unchanged the largest number of structural units of a population) are found explicitly. The proposition about the minimum possible number of nonzero coordinates for optimal vectors is also proved. This proposition is a generalization to the case of a binary population structure of well-known bimodality property of optimal strategies for populations with one-dimensional structure.

This paper addresses the nonconvex optimization problem with the cost function and equality and inequality constraints given by d.c. functions. The original problem is reduced to a problem without constraints by means of the exact penalization techniques. Furthermore, the penalized problem is presented as a d.c. minimization problem. For the latter problem, we apply the global optimality conditions (GOCs), which possess the so-called constructive (algorithmic) property. These new GOCs are generalized for the minimizing sequences, and a theoretical method is developed. Based on this theoretical foundation, a new global search scheme is designed for the auxiliary (penalized) and original problems, the convergence of which is one of the new results of the work.

The paper studies the nonlinear optimization problem in the form of optimal control problem subject to irregular constraints for which the multiplier of the objective function in Pontryagin’s function may vanish. It turns out that in case of p-regularity constraints this drawback can be overcome. But for this it necessary to prove continuous dependence solution of differential equation with respect to the boundary conditions. We give a new approach to the existence of such solutions via p-regularity theory.

The constructive kernel algorithm for approximation of probability densities using the given sample values is proposed. This algorithm is based on the approaches of the theory of the numerical functional approximation. The critical analysis of the optimization criterion for the kernel density estimators (based on decrease of upper boundary of mean square error) is conducted. It is shown that the constructive kernel algorithm is nearly equal to the randomized projection-mesh functional numerical algorithm for approximation of the solution of the Fredholm integral equation of the second kind. In connection with this it is proposed to use the criterion of conditional optimization of functional algorithms for the kernel algorithm for approximation of probability densities. This criterion is based on minimization of the algorithm’s cost for the fixed level of error. The corresponding formulae for the conditionally optimal parameters of the kernel algorithm are derived.

The paper considers the classical problem of optimal saving rate (golden rule) for an endogenous production function built on the basis of a micro-description of the dynamics of production capacity. The production capacities are distributed according to the moments of creation (vintage capacity model) and are limited by the age of their possible use. The main hypothesis of the model is that the number of workplaces on a production unit is fixed, and the capacity decreases with a constant pace. The resulting production function reflects explicitly the mechanisms for control of the production system. The average labor intensity is a short-term control, while the share of new capacities and their age limit are long-term controls. The golden rule for the Solow model is formulated in terms of capacity and labor intensity. The new endogenous production function gives new effects. The optimal level of accumulation rate does not depend on the choice of output elasticity by a production factor. The age limit of production capacity is a new production factor of the endogenous production function. It affects the value of effective labor per unit of capacity stock.

Traffic assignment problem is one of the central problems in transportation science. Various model assumptions lead to different setups corresponding to nonlinear optimization problems.In this work, we focus on the stable dynamic model and its generalizations. We propose new equivalent representation for stable dynamic model [Nesterov and de Palma, 2003]. We use smoothing technique to derive new model, which can be interpreted as a stochastic equilibrium model.

The linear second-order cone programming problem is considered. For its solution the dual multiplicative barrier methods are proposed. The methods are generalizations on the cone programming the corresponding methods for linear programming. They belong to the class of dual affine-scaling methods and can be treated as a special way for solving the optimality conditions for primal and dual problems. The local convergence of the methods with linear rate is proved.

In this article, we consider the problem of planning maintenance operations at a locomotive maintenance depot. There are three types of tracks at the depot: buffer tracks, access tracks and service tracks. A depot consists of up to one buffer track and a number of access tracks, each of them ending with one service track. Each of these tracks has a limited capacity measured in locomotive sections. We present a constraint programming model and a greedy algorithm for solving the problem of planning maintenance operations. Using lifelike data based on the operation of several locomotive maintenance depots in Eastern polygon of Russian Railways, we carry out numerical experiments to compare the presented approaches.

In this contribution, an interpolation problem using radial basis functions is considered. A recently proposed approach for the search of the optimal value of the shape parameter is studied. The approach consists of using global optimization algorithms to minimize the error function obtained using a leave-one-out cross validation (LOOCV) technique, which is commonly used for solving machine learning problems. In this paper, the proposed approach is studied experimentally on classes of randomly generated test problems using the GKLS-generator, which is widely used for testing global optimization algorithms. The experimental study on classes of randomly generated test problems is very important from the practical point of view, since results show the behavior of the algorithms for solving not a single test problem, but the whole class with controllable difficulty, which is the main property of the GKLS-generator. The obtained results are relevant, since the experiments have been carried out on 200 randomized test problems, and show that the algorithms are efficient for solving difficult real-life problems demonstrating a promising behavior.

The following time-optimal control problem is solved numerically: compute the fastest trajectory joining two given (initial and final) points of a dynamic control system in a time-periodic flow field subject to state constraints. The considered problem mimics the real-life task of path-planning of a ship in a flow with tidal variations. The considered problem is solved using the maximum principle in Gamkrelidze’s form. Under reasonable assumptions on the flow field, it is proved, that the problem is regular and the measure Lagrange multiplier, associated with the state constraint, is continuous. These properties (regularity and continuity) play a critical role in computing the field of extremals by solving the two-point boundary value problem given by the maximum principle. Some examples of time-periodic fluid flows are considered and the corresponding optimal solutions are found.

We consider an algorithm with space dilation. For a certain choice of the dilation coefficient, this is a method of outer approximation of semi-ellipsoids by ellipsoids with monotonous decrease in their volume. It is shown that the Yudin-Nemirovski-Shor ellipsoid method is a specific case. Two forms of the algorithm are dealt with: the B-form, where the inverse space transformation matrix B is updated, and the H-form, where the symmetric matrix $$H=BB^{\top }$$ is updated. Our test results show that the B-form of the algorithm is computationally more robust to error accumulation than the H-form. The application of the algorithm for finding a minimizer of a convex function, for solving convex programming problems, and for determining a saddle point of a convex-concave function is described. Possible ways of accelerating the algorithm by deeper ellipsoid approximations are discussed as well.

The paper investigates the problem of optimal control by the systems of ODE of block-structure with unseparated boundary conditions between blocks. The considered complex object consists of blocks. The state of each of them is described by the system of ordinary differential equations. The blocks are interconnected in an arbitrary order only by the initial and/or final (boundary) state values. The necessary optimality conditions for the considered optimal control problem are obtained.Note that, the obtained adjoint problem has the same specifics as the direct problem. For the numerical solution of optimal control problem, it is proposed to apply first-order optimization methods using the formulas for the functional gradient that participate in the necessary optimality conditions. To solve the direct and adjoint initial boundary-value problems of a block structure and with unseparated nonlocal boundary conditions with sparse (arbitrary filled) matrix, special schemes of the sweep method are proposed that take into account the specifics of the systems of differential equations and boundary conditions that allow the transfer of boundary conditions for each block separately.

A Generalized Coordinate Method (GCM) for linear permutation-based optimization is presented as a generalization of the Modified Coordinate Localization Method and Modified Coordinate Method is presented, and its applications to multiobjective linear optimization on permutations are outlined. The method is based on properties of linear function on a transposition graph, a decomposition of the graph, and extracting from it a multidimensional grid graph, where a directed search of an optimal solution is performed. Depending on the search parameters, GCM yields an exact or approximate solution to the original problem. An illustrative example is given for the method.

For semicoercive contact elastic problem with friction the smooth duality scheme is investigated, which allows on each step of successive approximation method to define simultaneously the displacement vector of elastic body points and normal contact stress defining the friction force on the next step of successive approximation method.

The Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem that has numerous valuable practical applications. It is known, that CVRP is strongly NP-hard even on the Euclidean plane and APX-hard in its metric setting even for any fixed capacity $$q\ge 3$$. For the Euclidean setting, there are known several approximation schemes. But, to the best of our knowledge, polynomial bounds for their time complexity were proved either for a fixed capacity q or under the restriction $$q\ll n$$. Moreover, most of these schemes were developed for the simplest case, where each customer has a unit demand, and cannot be extended to the general case of a non-uniform demand (both splittable or not) directly.In this paper, we are managed to significantly relax the restriction on capacity admitting the existence of PTAS for this problem and propose the first approximation scheme for the CVRP on the Euclidean plane with non-uniform non-splittable demand parameterized by an upper bound for the size of an optimum solution. Time complexity of the proposed scheme is polynomial for any fixed parameter values if $$q=poly(n)$$.

Some adaptive analogue of the Mirror Prox method for variational inequalities is proposed. In this work we consider the adaptation not only to the value of the Lipschitz constant, but also to the magnitude of the oracle error. This approach, in particular, allows us to prove a complexity near $$O\left( \frac{1}{\varepsilon }\right) $$ for variational inequalities for a special class of monotone bounded operators. This estimate is optimal for variational inequalities with monotone Lipschitz-continuous operators. However, there exists some error, which may be insignificant. The results of experiments on the comparison of the proposed approach with some known analogues are presented. Also, we discuss the results of the experiments for matrix games in the case of using non-Euclidean proximal setup.

This paper considers implementable versions of a conceptual convex optimization algorithm which provides a high-speed (super-linear, quadratic and finite) convergence for broad classes of convex optimization problems. The algorithm can be best viewed in the space of conjugate variables and as such it implicitly solves optimality conditions by sequential projection on the epigraph of conjugate function. The implementable version of this algorithm tries to solve projection problems approximately by construction of the inner approximations of the epigraph up to sufficient accuracy.This paper suggests also a version of the algorithm with additional linear cuts imposed on the epigraph which requires solution of an non-traditional auxiliary one-dimensional optimization problem. We derive an explicit form of this subproblem and provide convergence theorem for the resulting algorithm.

The backtracking is a basic combinatorial search algorithm. As many other deterministic methods it suffers from the high complexity. Fortunately the high performance computing can efficiently cope with this issue. It was observed that the structure of the search tree can dramatically affect the efficiency of a parallel search. We study the complexity of a frontal autonomous scheme for the backtrack search parallelization. In this approach several independent cores perform a number of first steps of the backtrack search. After that each core takes one sub-problem and solves it completely. Then the results are merged to select the best solution. To study the impact of the tree structure on the performance of the frontal autonomous scheme we formalize the notion of a perfectly scalable problem and prove a criterion for a search tree to fit to this class.

In this paper we consider spaces with an asymmetric seminorm and continue to study weakly convex sets. If we consider the Minkowski functional of the epigraph of some convex function as a seminorm, then the results obtained for weakly convex sets can be applied to weakly convex functions whose epigraphs are weakly convex sets with respect to this seminorm. We consider two sets in an asymmetric seminormed space, one of which is weakly convex with respect to an asymmetric seminorm, and the other one is strongly convex with respect to the asymmetric seminorm. We study the nearest points (in the sense of seminorm) problem and prove that this problem is well posed. Well posedness is an important property in the optimization theory. If a minimization problem is well posed, then one can build stable numerical algorithms, used for finding the solution of the problem.

We discuss two optimization problems: minimization of time and minimization of energy – for a material point, controlled by a limited force, moving along a straight line in the presence of friction and under limitation on the velocity. In the second problem, the time interval is fixed, and the recuperation of energy is taken into account. We describe extremals of these problems, satisfying the maximum principle for problems with state constraints in the Dubovitskii – Milyutin form.