We are looking for few papers in English (some are translation from Russian). If you have access to the texts, please contact me atremba@ipu.ru (Andrey Tremba)
Poljak BT and Tretjakov NV (1974), "On an Iterative Method for Linear Programming and Its Economical Interpretations", Matekon. Vol. 10(3), pp. 81-100.
Tsypkin JZ and Poliak BT (1974), "Attainable Accuracy of Adaptive Algorithms", Soviet Physics--Doklady. Vol. 19, pp. 562-563.
Poliak BT (1977), "On the Comparison of Gradient Method and Random Search Method", Automatic Control and Computer Sciences. Vol. 11(3), pp. 59-62.
Polyak BT (1977), "Comparison of the Convergence Rate for Single-Step and Multi-Step Optimization Algorithms in the Presence of Noise", Engineering Cybernetics. Vol. 15(1), pp. 6-10.
Tsypkin JZ and Poliak BT (1980), "Optimal Pseudogradient Algorithms for Stochastic Optimization", Soviet Physics--Doklady. Vol. 25, pp. 85-87.
Polyak BT and Tsypkin JZ (1983), "Optimal and Robust Estimation of Autoregression Coefficients", Engineering Cybernetics. Vol. 21(1), pp. 100-109.
Nemirovski AS and Polyak BT (1984), "Iterative Methods for Solution of Linear Ill-Posed Problems under Exact Information. I", Engineering Cybernetics. Vol. 22(3), pp. 1-11.
Nemirovski AS and Polyak BT (1984), "Iterative Methods for Solution of Linear Ill-Posed Problems under Exact Information. II", Engineering Cybernetics. Vol. 22(4), pp. 50-56.
Tsypkin YZ and Polyak BT (1990), "Frequency Criteria for Robust Modality of Linear Discrete Systems", Soviet Journal of Automation and Information Sciences. Vol. 23(4), pp. 1-7.
Polyak BT and Panchenko OB (1997), "Probabilistic Approach to Stability Problem for Interval Matrices", Doklady Mathematics. Vol. 55(2), pp. 309-311 ???.
Polyak BT and Nazin SA (2006), "Estimation of Parameters in Linear Multidimensional Systems under Interval Uncertainty", Journal of Automation and Information Sciences. Vol. 38(2), pp. 19-33.
B. Polyak, P. Shcherbakov Randomization in Robustness, Estimation, and Optimization. Springer International Publishing. 2018, Chapter in book Uncertainty in Complex Networked Systems: In Honor of Roberto Tempo, T. Basar (Ed.), pp. 181-208, pp. 181-208. DOI: 10.1007/978-3-030-04630-9_5, URL: https://doi.org/10.1007/978-3-030-04630-9_5, ISBN: 978-3-030-04630-9
Abstract: This is an attempt to discuss the following question: When is a random choice better than a deterministic one? That is, if we have an original deterministic setup, is it wise to exploit randomization methods for its solution? There exist numerous situations where the positive answer is obvious; e.g., stochastic strategies in games, randomization in experiment design, randomization of inputs in identification. Another type of problems where such approach works successfully relates to treating uncertainty, see Tempo R., Calafiore G., Dabbene F., ``Randomized algorithms for analysis and control of uncertain systems,'' Springer, New York, 2013. We will try to focus on several research directions including optimization problems with no uncertainty and compare known deterministic methods with their stochastic counterparts such as random descent, various versions of Monte Carlo etc., for convex and global optimization. We survey some recent results in the field and ascertain that the situation can be very different.
B. Polyak, E. Gryazina Convexity/Nonconvexity Certificates for Power Flow Analysis. Springer International Publishing. 2017, Chapter in book Advances in Energy System Optimization: Proceedings of the first International Symposium on Energy System Optimization, V. Bertsch, W. Fichtner, V. Heuveline, T. Leibfried (Ed.), pp. 221-230, pp. 221-230. DOI: 10.1007/978-3-319-51795-7_14, URL: http://dx.doi.org/10.1007/978-3-319-51795-7_14
Abstract: Optimal Power Flow problem is considered as minimization of quadratic performance function subject to linear and quadratic equality/inequality constraints, AC power flow equations specify the feasibility domain. Similar quadratic problems arise in discrete optimization, uncertainty analysis, physical applications. In general they are nonconvex, nevertheless, demonstrate hidden convexity structure. We investigate the "image convexity" property. That is, we consider the image of the space of variables under quadratic map defined by power flow equations (the feasibility domain). If the image is convex, then original optimization problem has nice properties, for instance, it admits zero duality gap and convex optimization tools can be applied. There are several classes of quadratic maps representing the image convexity. We aim to discover similar structure and to obtain convexity or nonconvexity certificates for the individual quadratic transformation. We also provide the numerical algorithms exploiting convex relaxation of quadratic mappings for checking convexity. We address such problems as membership oracle and boundary oracle for the quadratic image. Finally the results are illustrated through some examples of 3-bus systems, namely, we detect nonconvexity of them.
B. Polyak, P. Shcherbakov Stability and Performance of Complex Systems Affected by Parametric Uncertainty. Springer. 2014, Chapter in book Encyclopedia of Systems and Control, J. Baillieul, T. Samad (Ed.), pp. 1-10, pp. 1-10. DOI: 10.1007/978-1-4471-5102-9_137-1, URL: http://link.springer.com/referenceworkentry/10.1007/978-1-4471-5102-9_137-1, ISBN: Online: 978-1-4471-5102-9
Abstract: Uncertainty is an inherent feature of all real-life complex systems. It can be described in different forms; we focus on the parametric description. The simplest results on stability of linear systems under parametric uncertainty are the Kharitonov theorem, edge theorem, and graphical tests. More advanced results include sufficient conditions for robust stability with matrix uncertainty, LMI tools, and randomized methods. Similar approaches are used for robust control synthesis, where performance issues are crucial.
O.N. Granichin, B. Polyak Randomized Algorithms of Estimation and Optimization under almost Arbitrary Noise, Nauka, 2003, A.V. Nazin (Ed.). (In Russian) ISBN: 5-02-006525-0
Abstract: The book is devoted to the theory of effective recursive algorithms of multidimensional optimization and estimation which achieve a good performance without standard assumptions on observation noise as zero-mean and independence. The new approach is based on randomized simultaneous perturbations. The offered algorithms are widely used in an identification, recognition, control theory and economics.
B.T. Polyak Optimization problems in the presence of noise. Academie Verlag. 1993, Chapter in book Modern Mathematical Methods of Optimization, K. Elster (Ed.), pp. 53-61, pp. 53-61. (Russian version: in Optimization methods in economic-mathematical modelling, E.G. Gol'shtein (Ed.), Moscow, Nauka, 1991, pp. 86-94) ISBN: 3-05-501452-9, this work in Russian
B.T. Polyak Introduction to Optimization, Optimization Software, 1987, Series: Translations series in mathematics and engineering. ISBN: 0-911575-14-6, this work in Russian
M.V. Balashov, B.T. Polyak, A.A. Tremba Gradient Projection and Conditional Gradient Methods for Constrained Nonconvex Minimization, Numerical Functional Analysis and Optimization, 2020, 41(7), pp. 822-849. DOI: 10.1080/01630563.2019.1704780, URL: https://doi.org/10.1080/01630563.2019.1704780
Abstract: AbstractMinimization of a smooth function on a sphere or, more generally, on a smooth manifold, is the simplest non-convex optimization problem. It has a lot of applications. Our goal is to propose a version of the gradient projection algorithm for its solution and to obtain results that guarantee convergence of the algorithm under some minimal natural assumptions. We use the Ležanski-Polyak-Lojasiewicz condition on a manifold to prove the global linear convergence of the algorithm. Another method well fitted for the problem is the conditional gradient (Frank-Wolfe) algorithm. We examine some conditions which guarantee global convergence of full-step version of the method with linear rate.
M. Danilova, A. Kulakova, B. Polyak Non-monotone Behavior of the Heavy Ball Method, Springer International Publishing, 2020. In Difference Equations and Discrete Dynamical Systems with Applications, volume 312, M. Bohner, S. Siegmund, R. Simon Hilscher, P. Stehlik (Ed.), pp. 213-230. DOI: 10.1007/978-3-030-35502-9_9, URL: https://link.springer.com/chapter/10.1007/978-3-030-35502-9_9, ISBN: 978-3-030-35502-9
Abstract: We focus on the solutions of second-order stable linear difference equations and demonstrate that their behavior can be non-monotone and exhibit peak effects depending on initial conditions. The results are applied to the analysis of the accelerated unconstrained optimization method--the Heavy Ball method. We explain non-standard behavior of the method discovered in practical applications. In addition, such non-monotonicity complicates the correct choice of the parameters in optimization methods. We propose to overcome this difficulty by introducing new Lyapunov function which should decrease monotonically. By use of this function convergence of the method is established under less restrictive assumptions (for instance, with the lack of convexity). We also suggest some restart techniques to speed up the method's convergence.
B. Polyak, I. Fatkhullin Use of Projective Coordinate Descent in the Fekete Problem, Computational Mathematics and Mathematical Physics, 2020, , pp. to appear. (Translated from: Zhurnal Vychislitel'noi Matematiki i Matematichesckoi Fiziki. Vol. 60, No. 5, 815-827, 2020)
Abstract: The problem of minimizing the energy of a system of N points on a sphere in R^3, interacting with the potential U = 1/r^s , s > 0, where r is the Euclidean distance between a pair of points, is considered. A method of projective coordinate descent using a fast calculation of the function and the gradient, as well as a second-order coordinate descent method that rapidly approaches the minimum values known from the literature is proposed.
B. Polyak, A. Tremba Sparse solutions of optimal control via Newton method for under-determined systems, Journal of Global Optimization, 2020, 76(3), pp. 613-623. URL: https://doi.org/10.1007/s10898-019-00784-z
Abstract: We focus on finding sparse and least-ℓ1-norm solutions for unconstrained nonlinear optimal control problems. Such optimization problems are non-convex and non-smooth, nevertheless recent versions of Newton method for under-determined equations can be applied successively for such problems.
B. Polyak, A. Tremba New versions of Newton method: step-size choice, convergence domain and under-determined equations, Optimization Methods and Software, 2019, 0(0), pp. 1-32. DOI: 10.1080/10556788.2019.1669154, URL: https://doi.org/10.1080/10556788.2019.1669154
Abstract: Newton method is one of the most powerful methods for finding solutions of nonlinear equations and for proving their existence. In its ‘pure’ form it has fast convergence near the solution, but small convergence domain. On the other hand damped Newton method has slower convergence rate, but weaker conditions on the initial point. We provide new versions of Newton-like algorithms, resulting in combinations of Newton and damped Newton method with special step-size choice, and estimate its convergence domain. Under some assumptions the convergence is global. Explicit complexity results are also addressed. The adaptive version of the algorithm (with no a priori constants knowledge) is presented. The method is applicable for under-determined equations (with m<n, m being the number of equations and n being the number of variables). The results are specified for systems of quadratic equations, for composite mappings and for one-dimensional equations and inequalities.
B.T. Polyak, L.A. Shalby Minimum Fuel-Consumption Stabilization of a Spacecraft at the Lagrangian Points, Automation and Remote Control, 2019, 80(12), pp. 2217-2228.(Published in Avtomatika i Telemekhanika, 2019, No. 12, pp. 160-172) DOI: 10.1134/S0005117919120105, URL: https://doi.org/10.1134/S0005117919120105, this work in Russian
Abstract: We consider the motion of a spacecraft described by the differential equations of the three-body problem in the Earth-Moon system. The goal is to stabilize the spacecraft in the neighborhood of the collinear Lagrangian points (which are know to be unstable equilibria) via use of minimum fuel-consumption control. The adopted approach is based on l1-optimization of linearized and discretized equations with terminal conditions being the target Lagrangian point. Therefore, the problem reduces to a linear program, and its solution defines pulse controls for the original three-body equations. Upon reaching the desired neighborhood, the spacecraft performs control-free flight until its deviation from the Lagrangian point exceeds certain prespecified threshold. The correction is then applied repeatedly, so that the spacecraft is kept within a small neighborhood of the unstable equilibrium point.
B.T. Polyak, G.V. Smirnov Transient Response in Matrix Discrete-Time Linear Systems, Automation and Remote Control, 2019, 80(9), pp. 1645-1652. (Published in Avtomatika i Telemekhanika, 2019, No. 9, pp. 112-121) DOI: 10.1134/S0005117919090066, URL: https://doi.org/10.1134/S0005117919090066, this work in Russian
Abstract: The behavior of trajectories of multidimensional linear discrete-time systems with nonzero initial conditions is considered in two cases as follows. The first case is the systems with infinite degree of stability (the processes of a finite duration); the second case is the stable systems with a spectral radius close to 1. It is demonstrated that in both cases, large deviations of the trajectories from the equilibrium may occur. These results are applied to accelerated unconstrained optimization methods (such as the Heavy-ball method) for explaining the nonmonotonic behavior of the methods, which is observed in practice.
B.T. Polyak, P.S. Shcherbakov Optimisation and asymptotic stability, International Journal of Control, 2018, 91(11), pp. 2404-2410. DOI: 10.1080/00207179.2016.1257154, URL: https://doi.org/10.1080/00207179.2016.1257154
Abstract: The problems of unconstrained optimisation and establishing asymptotic stability have much in common. Understanding the analogy between these two sheds light on their interconnection and may lead to a number of new results. For instance, in this paper, we provide estimates of the rate of convergence when analysing asymptotic stability of differential equations, rather than just ascertain the very fact of stability. Also, standard methods for the design of Lyapunov functions (e.g. those having the meaning of the full energy of the system) turn out to be unsatisfactory from this point of view and have to be modified. These claims are exemplified in the paper by considering the heavy-ball method for function minimisation ‘in parallel’ with the problem of asymptotic stability for the synchronous motor equation.
B.T. Polyak, P.S. Shcherbakov, G. Smirnov Peak effects in stable linear difference equations, Journal of Difference Equations and Applications, 2018, 24(9), pp. 1488-1502. DOI: 10.1080/10236198.2018.1504930, URL: https://doi.org/10.1080/10236198.2018.1504930
Abstract: We consider asymptotically stable scalar difference equations with unit-norm initial conditions. First, it is shown that the solution may happen to deviate far away from the equilibrium point at finite time instants prior to converging to zero. Second, for a number of root distributions and initial conditions, exact values of deviations or lower bounds are provided. Several specific difference equations known from the literature are also analysed and estimates of deviations are proposed. Third, we consider difference equations with non-random noise (ie bounded-noise autoregression) and provide upper bounds on the solutions. Possible generalizations, eg to the vector case are discussed and directions for future research are outlined.
J.E. Machado, R. Griñó, N. Barabanov, R. Ortega, B. Polyak On Existence of Equilibria of Multi-Port Linear AC Networks With Constant-Power Loads, IEEE Transactions on Circuits and Systems I: Regular Papers, 2017, 64(10), pp. 2772-2782. DOI: 10.1109/TCSI.2017.2697906, URL: https://ieeexplore.ieee.org/document/7926335
Abstract: In this paper we give an answer to the following question. Given a multi-port, linear ac network with instantaneous constant-power loads identify a set of active and reactive load powers for which there is no steady-state operating condition of the network-in this case, we say that the power load is inadmissible. The identification is given in terms of feasibility of simple linear matrix inequalities, and hence it can be easily verified with existing software. For one- or two-port networks, the proposed feasibility test is necessary and sufficient for load power admissibility with the test for the former case depending only on the network data. Two benchmark numerical examples illustrate our results.
B. Polyak, P. Shcherbakov Why Does Monte Carlo Fail to Work Properly in High-Dimensional Optimization Problems?, Journal of Optimization Theory and Applications, 2017, 173(2), pp. 612-627. URL: https://doi.org/10.1007/s10957-016-1045-4
Abstract: The paper presents a quantitative explanation of failure of generic Monte Carlo techniques as applied to optimization problems of high dimensions. Deterministic grids are also discussed.
B.T. Polyak, M.V. Khlebnikov Principle component analysis: Robust versions, Automation and Remote Control, 2017, 78(3), pp. 490-506. (Published in Avtomatika i Telemekhanika, 2017, No. 3, pp. 130-148) DOI: 10.1134/S0005117917030092, URL: http://dx.doi.org/10.1134/S0005117917030092, this work in Russian
Abstract: Modern problems of optimization, estimation, signal and image processing, pattern recognition, etc., deal with huge-dimensional data; this necessitates elaboration of efficient methods of processing such data. The idea of building low-dimensional approximations to huge data arrays is in the heart of the modern data analysis. One of the most appealing methods of compact data representation is the statistical method referred to as the principal component analysis; however, it is sensitive to uncertainties in the available data and to the presence of outliers. In this paper, robust versions of the principle component analysis approach are proposed along with numerical methods for their implementation.
B.T. Polyak, Ya.I. Kvinto Stability and synchronization of oscillators: New Lyapunov functions, Automation and Remote Control, 2017, 78(7), pp. 1234-1242. (Published in Avtomatika i Telemekhanika, 2017, No. 7, pp. 76-85) DOI: 10.1134/S0005117917070050, URL: https://doi.org/10.1134/S0005117917070050, this work in Russian
Abstract: The analysis of asymptotic stability of nonlinear oscillator is one of the classical problems in the theory of oscillations. Usually, it is solved by exploiting Lyapunov functions having the meaning of the full energy of the system. However, the Barbashin-Krasovskii theorem has to be used along this way, and no estimates can be found for the rate of convergence of the trajectories to equilibria points. In this paper we propose a different Lyapunov function which lacks transparent physical meaning. With this function, both the rate of convergence and the domain of attraction of equilibria points can be estimated. This result also enables an efficient analysis of another problem, synchronization of oscillations of two oscillators. We formulate conditions that guarantee frequency synchronization and, on top of that, phase synchronization. Generalizations to the case of arbitrary number of oscillators are also discussed; solution of this problem is crucial in the analysis of power systems.
N. Barabanov, R. Ortega, R. Griñó, B. Polyak On Existence and Stability of Equilibria of Linear Time-Invariant Systems With Constant Power Loads, IEEE Transactions on Circuits and Systems I: Regular Papers, 2016, 63(1), pp. 114-121. DOI: 10.1109/TCSI.2015.2497559, URL: http://ieeexplore.ieee.org/document/7328761/
Abstract: The problem of existence and stability of equilibria of linear systems with constant power loads is addressed in this paper. First, we correct an unfortunate mistake in our recent paper pertaining to the sufficiency of the condition for existence of equilibria in multiport systems given there. Second, we give two necessary conditions for existence of equilibria. The first one is a simple linear matrix inequality hence it can be easily verified with existing software. Third, we prove that the latter condition is also sufficient if a set defined by the problem data is convex, which is the case for single and two-port systems. Finally, sufficient conditions for stability and instability for a given equilibrium point are given. The results are illustrated with two benchmark examples.
B.T. Polyak, O.N. Kuznetsov, V.V. Chumachenko Stability study of a power system with unipolar electromagnetic brake, Automation and Remote Control, 2016, 77(9), pp. 1557-1566. (Published in Avtomatika i Telemekhanika, 2016, No. 9, pp. 58-69) DOI: 10.1134/S0005117916090046, URL: http://dx.doi.org/10.1134/S0005117916090046, this work in Russian
Abstract: Consideration was given to the system of nonlinear differential equations describing a simplest power system with a unipolar installation, the electromagnetic brake (EMB). Behavior of the system was considered with and without EMB. By constructing a special Lyapunov function, local asymptotic stability of the system with EMB was proved.
B.T. Polyak, G. Smirnov Large deviations for non-zero initial conditions in linear systems, Automatica, 2016, 74, pp. 297-307. DOI: https://doi.org/10.1016/j.automatica.2016.07.047, URL: http://www.sciencedirect.com/science/article/pii/S0005109816303156
Abstract: Abstract Transient response of linear systems with non-zero initial conditions was at the center of attention for engineers and researchers at early stages of classical control theory. However this field was not intensively investigated later. For instance, the breakthrough result on unavoidable peaking effect for systems with strong damping factor was obtained by Izmailov in 1987, but it did not attract much attention. We try to continue this line of research and provide explicit worst-case lower bound. Then we exhibit large deviation effects for other pole locations and estimate lower bounds for them. The upper bounds for deviations of trajectories are much better studied; to obtain the smallest deviations by static linear feedback the techniques of linear matrix inequalities can be exploited. We demonstrate that for such closed-loop systems the upper and lower bounds have the same asymptotic behavior.
B.T. Polyak, A.A. Tremba, M.V. Khlebnikov, P.S. Shcherbakov, G.V. Smirnov Large deviations in linear control systems with nonzero initial conditions, Automation and Remote Control, 2015, 76(6), pp. 957-976. (Published in Avtomatika i Telemekhanika, 2015, No. 6, pp. 18-41) DOI: 10.1134/S0005117915060028, URL: http://link.springer.com/article/10.1134/S0005117915060028, this work in Russian
Abstract: Research in the transient response in linear systems with nonzero initial conditions was initiated by A.A. Feldbaum in his pioneering work [1] as early as in 1948. However later, studies in this direction have faded down, and since then, the notion of transient process basically means the response of the system with zero initial conditions to the unit step input. A breakthrough in this direction is associated with the paper [2] by R.N. Izmailov, where large deviations of the trajectories from the origin were shown to be unavoidable if the poles of the closed-loop system are shifted far to the left in the complex plane. In this paper we continue the analysis of this phenomenon for systems with nonzero initial conditions. Namely, we propose a more accurate estimate of the magnitude of the peak and show that the effect of large deviations may be observed for different root locations. We also present an upper bound on deviations by using the linear matrix inequality (LMI) technique. This same approach is then applied to the design of a stabilizing linear feedback aimed at diminishing deviations in the closed-loop system. Related problems are also discussed, e.g., such as analysis of the transient response of systems with zero initial conditions and exogenous disturbances in the form of either unit step function or harmonic signal.
E. Gryazina, B. Polyak Random sampling: Billiard Walk algorithm, European Journal of Operational Research, 2014, 238(2), pp. 497-504. DOI: 10.1016/j.ejor.2014.03.041, URL: http://www.sciencedirect.com/science/article/pii/S037722171400280X
Abstract: Abstract Hit-and-Run is known to be one of the best random sampling algorithms, its mixing time is polynomial in dimension. However in practice, the number of steps required to obtain uniformly distributed samples is rather high. We propose a new random walk algorithm based on billiard trajectories. Numerical experiments demonstrate much faster convergence to the uniform distribution.
B.T. Polyak, M.V. Khlebnikov, P.S. Shcherbakov Sparse feedback in linear control systems, Automation and Remote Control, 2014, 75(12), pp. 2099-2111. (Published in Avtomatika i Telemekhanika, 2014, No. 12, pp. 13-27) DOI: 10.1134/S0005117914120029, URL: http://link.springer.com/article/10.1134/S0005117914120029, this work in Russian
Abstract: We consider a classical problem of linear static state feedback design in the linear system $\dot{x} = Ax + Bu$ subject to a nonstandard constraint that the control vector $u = Kx$ has as many zero components as possible. A simple approach to approximate solutions of such kind of nonconvex problems is proposed, which is based on convexification. The problem reduces to the minimization of special matrix norms subject to the constraints in the form of linear matrix inequalities (LMIs). The approach can be generalized to numerous problems of robust and optimal control that admit a "sparse" reformulation. To the best of our knowledge, both the solution and the problem formulation are new.
B.T. Polyak, P.S. Shcherbakov Why is Monte Carlo inefficient in high-dimensional optimization problems?, St. Petersburg University, 2014. In Stochastic Optimization in Informatics (Stohastičeskaâ optimizaciâ v informatike), volume 10, O.N. Granichin (Ed.), pp. 3-24. (In Russian) URL: http://www.math.spbu.ru/user/gran/soi10_1/sb10_1en.htm, this work in Russian
Abstract: The question formulated in the title is addressed via the example of minimizing linear functions over the n-dimensional ball.
B.T. Polyak, A.A. Tremba Regularization-based Solution of the PageRank Problem for Large Matrices, Automation and Remote Control, 2012, 73(11), pp. 1877-1894. (Published in Avtomatika i Telemekhanika, 2012, No. 11, pp. 144-166) DOI: 10.1134/S0005117912110094, URL: http://link.springer.com/article/10.1134/S0005117912110094, this work in Russian
Abstract: For a column-stochastic matrix, consideration was given to determination of the eigenvector which corresponds to the unit eigenvalue. Such problems are encountered in many applications,-in particular, at ranking the web pages (PageRank). Since the PageRank problem is of special interest for larger matrices, the emphasis was made on the power method for direct iterative calculation of the eigenvector. Several variants of regularization of the power methods were compared, and their relations were considered. The distinctions of their realizations were given.
M.V. Khlebnikov, B.T. Polyak, V.M. Kuntsevich Optimization of Linear Systems Subject to Bounded Exogenous Disturbances: The Invariant Ellipsoid Technique, Automation and Remote Control, 2011, 72(11), pp. 2227-2275. (Published in Avtomatika i Telemekhanika, 2011, No. 11, pp. 9-59) DOI: 10.1134/S0005117911110026, URL: http://link.springer.com/article/10.1134/S0005117911110026, this work in Russian
Abstract: This survey covers a variety of results associated with control of systems subjected to arbitrary bounded exogenous disturbances. The method of invariant ellipsoids reduces the design of optimal controllers to finding the smallest invariant ellipsoid of the closed-loop dynamical system. The main tool of this approach is the linear matrix inequality technique. This simple yet versatile approach has high potential in extensions and generalizations; it is equally applicable to both the continuous and discrete time versions of the problems.
A.V. Nazin, B.T. Polyak Randomized Algorithm to Determine the Eigenvector of a Stochastic Matrix with Application to the PageRank Problem, Automation and Remote Control, 2011, 72(2), pp. 342-352. (Published in Avtomatika i Telemekhanika, 2011, No. 2, pp. 131-141) DOI: 10.1134/S0005117911020111, URL: http://link.springer.com/article/10.1134/S0005117911020111, this work in Russian
Abstract: Consideration was given to estimation of the eigenvector corresponding to the greatest eigenvalue of a stochastic matrix. There exist numerous applications of this problem arising at ranking the results of search, coordination of the multiagent system actions, network control, and data analysis. The standard technique for its solution comes to the power method with an additional regularization of the original matrix. A new randomized algorithm was proposed, and a uniform-over the entire class of the stochastic matrices of a given size-upper boundary of the convergence rate was validated. It is given by $C\sqrt{ln(N)/n}$, where $C$ is an absolute constant, $N$ is size, and $n$ is the number of iterations. This boundary seems promising because $ln(N)$ is smallish even for a very great size. The algorithm relies on the mirror descent method for the problems of convex stochastic optimization. Applicability of the method to the PageRank problem of ranking the Internet pages was discussed.
B.T. Polyak, E.N. Gryazina Randomized methods based on new Monte Carlo schemes for control and optimization, Annals of Operations Research, 2011, 189(1), pp. 343-356. DOI: 10.1007/s10479-009-0585-5, URL: http://link.springer.com/article/10.1007/s10479-009-0585-5
Abstract: We address randomized methods for control and optimization based on generating points uniformly distributed in a set. For control systems this sets are either stability domain in the space of feedback controllers, or quadratic stability domain, or robust stability domain, or level set for a performance specification. By generating random points in the prescribed set one can optimize some additional performance index. To implement such approach we exploit two modern Monte Carlo schemes for generating points which are approximately uniformly distributed in a given convex set. Both methods use boundary oracle to find an intersection of a ray and the set. The first method is Hit-and-Run, the second is sometimes called Shake-and-Bake. We estimate the rate of convergence for such methods and demonstrate the link with the center of gravity method. Numerical simulation results look very promising.
A.V. Nazin, B.T. Polyak The Randomized Algorithm for Finding an Eigenvector of the Stochastic Matrix with Application to PageRank, Doklady Mathematics, 2009, 79(3), pp. 424-427. (Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 6, pp. 734-737) DOI: 10.1134/S1064562409030338, URL: http://link.springer.com/article/10.1134/S1064562409030338, this work in Russian
Abstract: The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is $O(\ln N/n)$, where $N$ is the dimension and $n$ is the number of iterations. The bound looks promising because $\ln N$ is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed.
E.N. Gryazina, B.T. Polyak, A.A. Tremba $D$-decomposition Technique State-of-the-art, Automation and Remote Control, 2008, 69(12), pp. 1991-2026. (Published in Avtomatika i Telemekhanika, 2008, No. 12, pp. 3-40) DOI: 10.1134/S0005117908120011, URL: http://link.springer.com/article/10.1134/S0005117908120011, this work in Russian
Abstract: It is a survey of recent extensions and new applications for the classical $D$-decomposition technique. We investigate the structure of the parameter space decomposition into root invariant regions for single-input single-output systems linear depending on the parameters. The $D$-decomposition for uncertain polynomials is considered as well as the problem of describing all stabilizing controllers of the certain structure (for instance, PID-controllers) that satisfy given $H_\infty$-criterion. It is shown that the $D$-decomposition technique can be naturally linked with $M-\Delta$ framework (a general scheme for analysis of uncertain systems) and it is applicable for describing feasible sets for linear matrix inequalities. The problem of robust synthesis for linear systems can be also treated via $D$-decomposition technique.
Ya. Petrikevich, B. Polyak Monte-Carlo Technique for Stabilization of Linear Discrete-Time Systems via Low-Order Controllers, Nauka, 2008. In Advances in Mechanics: Dynamic and Control, F.L. Chernousko, G.V. Kostin, V.V. Saurin (Ed.), pp. 232-238. (Proceedings of the 14th International Workshop on Dynamics and control, Moscow -Zvenigorod, Russia May 28 - June 2, 2007. Dedicated to Professon Angelo Miele on the occasion of his 85th Birthday) ISBN: 978-5-02-036667-1
Abstract: A novel randomized approach to fixed-order controller design is proposed for discrete-time SISO plants. The algorithm generates stable discrete-time polynomials, and for each of them we find the nearest polynomial in the subspace of characteristic polynomials corresponding to low-order controllers. If this polynomial is stable, the stabilizing controller is found. Otherwise we proceed to generate stable polynomials. If we achieved no success, several "most promising" candidates are found and we try to improve them locally by means of an iterative method of nonsmooth optimization. Numerical simulations demonstrated high efficiency of the approach.
B.T. Polyak, M.V. Khlebnikov, P.S. Shcherbakov Robust Rejection of Exogenous Disturbances via Invariant Ellipsoids Technique, Nauka, 2008. In Advances in Mechanics: Dynamic and Control, F.L. Chernousko, G.V. Kostin, V.V. Saurin (Ed.), pp. 247-254. (Proceedings of the 14th International Workshop on Dynamics and control, Moscow -Zvenigorod, Russia May 28 - June 2, 2007. Dedicated to Professon Angelo Miele on the occasion of his 85th Birthday) ISBN: 978-5-02-036667-1
Abstract: Considered is the problem of optimal rejection of persistent exogenous disturbances in dynamic systems. A robust formulation is given for the case where the matrix coefficients are subjected to norm-bounded uncertainties; the solution technique based on the invariant ellipsoids concept is developed.
B.T. Polyak, S.A. Nazin, M.V. Khlebnikov The Invariant Ellipsoids Technique for Analysis and Design of Linear Control Systems, Nauka, 2008. In Advances in Mechanics: Dynamic and Control, F.L. Chernousko, G.V. Kostin, V.V. Saurin (Ed.), pp. 239-246. (Proceedings of the 14th International Workshop on Dynamics and control, Moscow-Zvenigorod, Russia May 28 - June 2, 2007. Dedicated to Professon Angelo Miele on the occasion of his 85th Birthday) ISBN: 978-5-02-036667-1
Abstract: In this paper an approach based on invariant ellipsoids is applied to the problem of persistent disturbance rejection by means of static state-feedback control. The dynamic system is supposed to be linear time-invariant and affected by unknown-but-bounded exogenous disturbances. Synthesis of an optimal controller that returns a minimum of the size of the corresponding invariant ellipsoid is reduced to one-dimensional convex minimization with LMI constraints.
B.T. Polyak, P.S. Shcherbakov Reachability and Attraction Domains for Linear Systems with Bounded Control: A Characterization via Invariant Ellipsoids, St. Petersburg University, 2008. In Stochastic Optimization in Informatics (Stohastičeskaâ optimizaciâ v informatike), volume 4, O.N. Granichin (Ed.), pp. 3-24. (In Russian) URL: http://www.math.spbu.ru/user/gran/soi4/SOI4.htm, this work in Russian
Abstract: This paper is aimed at efficiently characterizing reachability and attraction domains of linear systems specified in the state space description. We consider bounded controls in the form of the linear static state feedback and saturated control. A description of reachability and attraction domains for such systems is given in terms of invariant ellipsoids using the apparatus of linear matrix inequalities and semidefinite programming formulation. Design of saturated control is based on the ideas of the theory of absolute stability.
B.T. Polyak, M.V. Topunov Filtering under Nonrandom Disturbances: The Method of Invariant Ellipsoids, Doklady Mathematics, 2008, 77(1), pp. 158-162. (Published in Doklady Akademii Nauk, 2008, Vol. 418, No. 6, pp. 749-753) DOI: 10.1134/S1064562408010390, URL: http://link.springer.com/article/10.1134/S1064562408010390, this work in Russian
B.T. Polyak, M.V. Topunov Suppression of Bounded Exogenous Disturbances: Output Feedback, Automation and Remote Control, 2008, 69(5), pp. 801-818. (Published in Avtomatika i Telemekhanika, 2008, No. 5, pp. 72-90) DOI: 10.1134/S000511790805007X, URL: http://link.springer.com/article/10.1134/S000511790805007X, this work in Russian
Abstract: The paper was devoted to rejection of bounded exogenous disturbances and considered design of the static output feedback minimizing the invariant ellipsoids of the dynamic system. The problems of control analysis and design come to the equivalent conditions in the form of linear matrix inequalities and to the problem of semidefinite programming. The state estimate obtained using the Luenberger observer was used at that.
F. Dabbene, B.T. Polyak, R. Tempo On the complete instability of interval polynomials, Systems & Control Letters, 2007, 56(6), pp. 431-438. DOI: 10.1016/j.sysconle.2006.11.002, URL: http://www.sciencedirect.com/science/article/pii/S016769110600212X
Abstract: In this paper, we study "complete instability" of interval polynomials, which is the counterpart of classical robust stability. That is, the objective is to check if all polynomials in the family are unstable. If not, a subsequent goal is to find a stable polynomial. To this end, we first propose a randomized algorithm which is based on a (recursive) necessary condition for Hurwitz stability. The second contribution of this paper is to provide a probability-one estimate of the volume of stable polynomials. These results are based on a combination of deterministic and randomized methods. Finally, we present two numerical examples and simulations showing the efficiency of the proposed methodology for small and medium-size problems.
E.N. Gryazina, B.T. Polyak Multidimensional Stability Domain of Special Polynomial Families, Automation and Remote Control, 2007, 68(12), pp. 2128-2141. (Published in Avtomatika i Telemekhanika, No. 12, 2007, pp. 38-52) DOI: 10.1134/S000511790712003X, URL: http://link.springer.com/article/10.1134/S000511790712003X, this work in Russian
Abstract: Consideration was given to the characteristic polynomials with special affine uncertainty. For this family, the stability domain in the parameter space was shown to be a union of polyhedra. For continuous-time and discrete-time systems, a simple method was proposed to single out the stability domain and determine the stability radius for different norms of uncertainty. Efficiency of this method was corroborated by examples.
E.N. Gryazina, B.T. Polyak, A.A. Tremba Design of the Low-order Controllers by the $H_\infty$ Criterion: A Parametric Approach, Automation and Remote Control, 2007, 68(3), pp. 456-466. (Published in Avtomatika i Telemekhanika, 2007, No. 3, pp. 94-105)
DOI: 10.1134/S0005117907030071, URL: http://link.springer.com/article/10.1134/S0005117907030071, this work in Russian
Abstract: Consideration was given to the problem of describing all stabilizing controllers of a given structure (for example, the the PID-controllers) satisfying the $H_\infty$ criterion. Controllers of a certain family were defined by the parameters $k$, and in the parameter space a domain corresponding to the desired criteria was specified. Two approaches were proposed where (i) the desired domain is represented as an intersection of the admissible sets or (ii) its boundary is determined analytically. The two-parameter case is of special importance because it allows one to make use of the graphical mathematics.
S.A. Nazin, B.T. Polyak Ellipsoid-based Parametric Estimation in the Linear Multidimensional Systems with Uncertain Model Description, Automation and Remote Control, 2007, 68(6), pp. 993-1005. (Published in Avtomatika i Telemekhanika, 2007, No. 6, pp. 67-80) DOI: 10.1134/S0005117907060070, URL: http://link.springer.com/article/10.1134/S0005117907060070, this work in Russian
Abstract: Parametric estimation under uncertainty of the plant model description was considered within the framework of the ellipsoidal approach to the problems of guaranteed estimation. The unknown multidimensional plant whose parameter vector should be estimated was assumed to be linear and static, and uncertainty of its "input-output" model, to have both additive and multiplicative components. The external ellipsoidal approximations of the nonconvex information sets guaranteeing that the vector of possible plant parameters is contained in them were constructed from the results of observations. The method of their construction comes to semidefinite programming, that is, to minimization of the linear function constrained by the linear matrix inequalities which are readily realized by the numerical methods.
S.A. Nazin, B.T. Polyak, M.V. Topunov Rejection of Bounded Exogenous Disturbances by the Method of Invariant Ellipsoids, Automation and Remote Control, 2007, 68(3), pp. 467-486. Published in Avtomatika i Telemekhanika, 2007, No. 3, pp. 106-125) DOI: 10.1134/S0005117907030083, URL: http://link.springer.com/article/10.1134/S0005117907030083, this work in Russian
Abstract: Rejection of the bounded exogenous disturbances was first studied by the $\ell_1$-optimization theory. A new approach to this problem was proposed in the present paper on the basis of the method of invariant ellipsoids where the technique of linear matrix inequalities was the main tool. Consideration was given to the continuous and discrete variants of the problem. Control of the "double pendulum" was studied by way of example.
B.T. Polyak Newton’s method and its use in optimization, European Journal of Operational Research, 2007, 181(3), pp. 1086-1096. DOI: 10.1016/j.ejor.2005.06.076, URL: http://www.sciencedirect.com/science/article/pii/S0377221706001469
Abstract: Newton’s method is a basic tool in numerical analysis and numerous applications, including operations research and data mining. We survey the history of the method, its main ideas, convergence results, modifications, its global behavior. We focus on applications of the method for various classes of optimization problems, such as unconstrained minimization, equality constrained problems, convex programming and interior point methods. Some extensions (non-smooth problems, continuous analog, Smale’s results, etc.) are discussed briefly, while some others (e.g., versions of the method to achieve global convergence) are addressed in more details.
B.T. Polyak, S.A. Nazin Invariant Ellipsoids Technique for Persistent Disturbance Rejection, International Journal of Tomography & Statistics, 2007, 5(W07), pp. 165-170.
Abstract: In this paper an approach based on invariant ellipsoids is applied to the problem of persistent disturbance rejection by means of static state-feedback control. Dynamic system is supposed to be linear time-invariant and affected by unknown-but-bounded exogenous disturbances. Synthesis of an optimal controller that returns a minimum of the size of the corresponding invariant ellipsoid is reduced to the one-dimensional convex minimization with LMI constraints. The problem is considered in continuous and discrete time cases.
E.N. Gryazina, B.T. Polyak Stability regions in the parameter space: $D$-decomposition revisited, Automatica, 2006, 42(1), pp. 13-26. DOI: 10.1016/j.automatica.2005.08.010, URL: http://www.sciencedirect.com/science/article/pii/S0005109805003109
Abstract: The challenging problem in linear control theory is to describe the total set of parameters (controller coefficients or plant characteristics) which provide stability of a system. For the case of one complex or two real parameters and SISO system (with a characteristic polynomial depending linearly on these parameters) the problem can be solved graphically by use of the so-called $D$-decomposition. Our goal is to extend the technique and to link it with general $M - \Delta$ framework. In this way we investigate the geometry of $D$-decomposition for polynomials and estimate the number of root invariant regions. Several examples verify that these estimates are tight. We also extend $D$-decomposition for the matrix case, i.e. for MIMO systems. For instance, we partition real axis or complex plane of the parameter k into regions with invariant number of stable eigenvalues of the matrix $A + kB$. Similar technique can be applied to double-input double-output systems with two parameters.
Yu. Nesterov, B.T. Polyak Cubic regularization of Newton method and its global performance, Mathematical Programming, Series A, 2006, 108(1), pp. 177-205. DOI: 10.1007/s10107-006-0706-8, URL: http://link.springer.com/article/10.1007/s10107-006-0706-8
Abstract: In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.
B. Polyak Early Control Textbooks in Russia (Soviet Union), Elsevier, 2006. In Historic Control Textbooks, J. Gertler (Ed.), pp. 213-232. ISBN: 0-08-045346-5
B. Polyak New Challenges in Nonlinear Control: Stabilization and Synchronization of Chaos, Studentlitteratur, 2006. In Forever Ljung in System Identification, T. Glad, G. Hendeby (Ed.). ISBN: 9789144020518
Abstract: After the pioneering work Ott et al. (1990) the problem of chaos control attracted many researchers, mainly physicists and mathe- maticians. The problem differs dramatically from standard setup of control theory. First, it is essentially nonlinear. Second, goals of control are nonconventional - it may be stabilization of unstable periodic orbits or chaotization of a stable system. Third, the control itself should be small enough. A novel approach to chaos stabilization and synchronization, based on trajectory prediction, will be discussed. It is simple and effective (numerous simulation results demonstrate this); the theoretical validation will be also presented. On the other hand the approach has strong limitations because it is nonrobust with respect to system dynamics.
B. Polyak Controlling chaos with predictive control, Applied and Computational Mathematics, 2006, 5(1), pp. 66-78.
Abstract: A novel approach to controlling chaos in discrete-time nonlinear autonomous systems is proposed. A desired unstable periodic orbit is stabilized by small control using the predicted trajectory of the system. The exact knowledge of the periodic orbit is not assumed, just its existence is required. The method developed is validated for one-dimensional and multidimensional mappings; its efficacy is demonstrated via numerical simulations of the mappings known from the literature, such as logistic, tent, cubic, and the Hénon map. The method is simple in implementation, but its application is limited to systems with no exogenous disturbances and uncertainties in the model description. The approach looks highly promising and may have diverse applications.
B.T. Polyak Newton-Kantorovich method and its global convergence, Journal of Mathematical Sciences, 2006, 133(4), pp. 1513-1523. (Published in Zapiski Nauchnykh Seminarov POMI, Vol. 312, 2004, pp. 256-274) DOI: 10.1007/s10958-006-0066-1, URL: http://link.springer.com/article/10.1007/s10958-006-0066-1
Abstract: In 1948, L. V. Kantorovich extended the Newton method for solving nonlinear equations to functional spaces. This event cannot be overestimated: the Newton-Kantorovich method became a powerful tool in numerical analysis as well as in pure mathematics. We address basic ideas of the method in historical perspective and focus on some recent applications and extensions of the method and some approaches to overcoming its local ture. Bibliography: 56 titles.
B.T. Polyak, S.A. Nazin Estimation of Parameters in Linear Multidimensional Systems under Interval Uncertainty, Journal of Automation and Information Sciences, 2006, 38(2), pp. 19-33. (Translated from Problems of control and informatica, 2006, No. 1-2, 103-115) DOI: 10.1615/J Automat Inf Scien.v38.i2.20, this work in Russian
Abstract: We suggested the method for construction of estimations of parameters in linear multidimensional systems with interval uncertainty in data. Together with additive component because of measuring errors we suggest in the model multiplicative matrix uncertainty, which makes it possible to consider wider class of objects with uncertain structure. For these models external interval approximations of nonconvex information sets are constructed. Method of their construction is based on solving interval systems of linear algebraic equations and promotes construction of parametric estimates for static models with large number of measurements.
B.T. Polyak, P.S. Shcherbakov The $D$-decomposition Technique for Linear Matrix Inequalities, Automation and Remote Control, 2006, 67(11), pp. 1847-1861. (Published in Avtomatika i Telemekhanika, No. 11, 2006, pp. 159-174) DOI: 10.1134/S0005117906110063, URL: http://link.springer.com/article/10.1134/S0005117906110063, this work in Russian
Abstract: In the framework of the theory of linear matrix inequalities, a method is proposed for determining all the domains in the parameter space having the property that an affine family of symmetric matrices has the same fixed number of like-sign eigenvalues inside each of the domains. The approach leans on the ideas of $D$-decomposition; it is particularly efficient in the problems involving few parameters. Generalizations of the method are considered along with its modifications to the presence of uncertainty.
S.E. Efremov, B.T. Polyak Using Predictive Control to Synchronize Chaotic Systems, Automation and Remote Control, 2005, 66(12), pp. 1905-1915. (Translated from Avtomatika i Telemekhanika, No. 12, 2005, pp. 40-50) DOI: 10.1007/s10513-005-0223-x, URL: http://link.springer.com/article/10.1007/s10513-005-0223-x, this work in Russian
Abstract: A method of synchronization of several identical chaotic systems using a new type of control was proposed. It is based on predicting the trajectories of each of the nonlinear systems and correcting them by the deviation of the prediction from the desired value. Three types of control with global interaction between the systems, local interaction between the systems, and one leading oscillator affecting the rest of them were proposed. After synchronization, all systems make identical chaotic motions. This method features low level of the control action; in principle, control may be made arbitrarily small. Numerical modeling bore out efficiency of this method for any number of oscillators.
S.A. Nazin, B.T. Polyak Interval Parameter Estimation under Model Uncertainty, Mathematical and Computer Modelling of Dynamical Systems: Methods, Tools and Applications in Engineering and Related Sciences, 2005, 11(2), pp. 225-237. DOI: 10.1080/138950500069243, URL: http://www.tandfonline.com/doi/abs/10.1080/138950500069243
Abstract: This paper is devoted to the estimation of parameters of linear multi-output models with uncertain regressors and additive noise. The uncertainty is assumed to be described by intervals. Outer-bounding interval approximations of the non-convex feasible parameter set for uncertain systems are obtained. The method is based on the calculation of the interval solution for an interval system of linear algebraic equations and provides parameter estimators for models with a large number of measurements.
B.T. Polyak Stabilizing Chaos with Predictive Control, Automation and Remote Control, 2005, 66(11), pp. 1791-1804. (Translated from Avtomatika i Telemekhanika, No. 11, 2005, pp. 99-112) DOI: 10.1007/s10513-005-0213-z, URL: http://link.springer.com/article/10.1007/s10513-005-0213-z, this work in Russian
Abstract: A novel approach to controlling chaos in discrete-time nonlinear autonomous systems is proposed. A desired unstable periodic orbit is stabilized by small control using the predicted trajectory of the system. The exact knowledge of the periodic orbit is not assumed, just its existence is required. The method developed is validated for one-dimensional and multi-dimensional mappings; its efficacy is demonstrated via numerical simulations of the mappings known from the literature, such as logistic, tent, cubic, and Henon maps. The method is simple in implementation, but its application is limited to systems with no exogenous disturbances and uncertainties in the model description. The approach looks highly promising and may have diverse applications.
B.T. Polyak, P.S. Shcherbakov Hard Problems in Linear Control Theory: Possible Approaches to Solution, Automation and Remote Control, 2005, 66(5), pp. 681-718. (Translated from Avtomatika i Telemekhanika, No. 5, 2005, pp. 7-46) DOI: 10.1007/s10513-005-0115-0, URL: http://link.springer.com/article/10.1007/s10513-005-0115-0, this work in Russian
Abstract: A number of challenging problems in linear control theory are considered which admit simple formulation and yet lack efficient solution methods. These problems relate to the classical theory of linear systems as well as to the robust theory where the system description contains uncertainty. Various solution methods are discussed and the results of numerical simulations are given.
A.V. Nazin, S.A. Nazin, B.T. Polyak On Convergence of External Ellipsoidal Approximations of the Reachability Domains of Discrete Dynamic Linear Systems, Automation and Remote Control, 2004, 65(8), pp. 1210-1230. (Translated from Avtomatika i Telemekhanika, No. 8, 2004, pp. 39-61) DOI: 10.1023/B:AURC.0000038724.88069.21, URL: http://link.springer.com/article/10.1023/B:AURC.0000038724.88069.21, this work in Russian
Abstract: The ellipsoid technique is widely used in the guaranteed estimation for approximation of the reachability domains of dynamic systems. The present paper considered the issues of external ellipsoidal estimation of the current and limiting reachability sets of a stable discrete dynamic linear system. Recurrent estimation algorithms using the criterion of minimum trace of the "weighted" ellipsoid matrix were developed for these systems, and their limiting properties were considered.
B.T. Polyak Extended Superstability in Control Theory, Automation and Remote Control, 2004, 65(4), pp. 567-576. (Translated from Avtomatika i Telemekhanika, No. 4, 2004, pp. 70-80) DOI: 10.1023/B:AURC.0000023533.13882.13, URL: http://link.springer.com/article/10.1023/B:AURC.0000023533.13882.13, this work in Russian
Abstract: The notion of superstability that was recently used to tackle various problems of robustness and the linear control theory was generalized to attain higher flexibility. For the continuous and discrete cases, a class of matrices E was introduced for which the superstability condition is satisfied after the diagonal transformation. Systems with these matrices have piecewise-linear Lyapunov functions $V(x) = \mathop {\max}\limits_i \left| {x_i /d_i} \right|$ . Problems such as verification of the membership $\widetilde{A} \subset E$ for the interval matrices, existence of a feedback $K$ such that $A + BK \in E$, the best componentwise estimation, and disturbance attenuation were all of them reduced to the easily solvable linear programming problems. Efficient numerical methods were proposed to solve the arising linear inequalities.
B.T. Polyak Convexity of the Reachable Set of Nonlinear Systems Under $L_2$ Bounded Controls, Dynamics of Continuous, Discrete and Impulsive Systems, 2004, 11(2-3), pp. 255-267.
Abstract: Recently [7, 8] the new convexity principle has been validated. It states that a nonlinear image of a small ball in a Hilbert space is convex, provided that the map is $C^{1,1}$ and the center of the ball is a regular point of the map. We demonstrate how the result can be exploited to guarantee the convexity of the reachable set for some nonlinear control systems with $L_2$ -bounded control. This provides existence and uniqueness of the solution in some optimal control problems as well as necessary and sufficient optimality conditions and effective iterative methods for finding the solution.
B.T. Polyak, S.A. Nazin Interval solutions for interval algebraic equations, Mathematics and Computers in Simulation, 2004, 66(2-3), pp. 207-217. DOI: 10.1016/j.matcom.2003.11.006, URL: http://www.sciencedirect.com/science/article/pii/S0378475403002052
Abstract: In the framework of interval uncertainty, a well-known classical problem in numerical analysis is considered, namely, to find "the best" interval solution for interval system of linear algebraic equations. This problem is known to be NP-hard and can be solved via multiple linear programming. In present paper, a simple approach is proposed for some particular models of interval uncertainty. This method gives an optimal interval solution without linear programming and is tractable for moderate-size problems. For large-scale problems an effective overbounding technique is developed.
B.T. Polyak, S.A. Nazin, C. Durieu, E. Walter Ellipsoidal parameter or state estimation under model uncertainty, Automatica, 2004, 40(7), pp. 1171-1179. DOI: 10.1016/j.automatica.2004.02.014, URL: http://www.sciencedirect.com/science/article/pii/S0005109804000676
Abstract: Ellipsoidal outer-bounding of the set of all feasible state vectors under model uncertainty is a natural extension of state estimation for deterministic models with unknown-but-bounded state perturbations and measurement noise. The technique described in this paper applies to linear discrete-time dynamic systems; it can also be applied to weakly non-linear systems if non-linearity is replaced by uncertainty. Many difficulties arise because of the non-convexity of feasible sets. Combined quadratic constraints on model uncertainty and additive disturbances are considered in order to simplify the analysis. Analytical optimal or suboptimal solutions of the basic problems involved in parameter or state estimation are presented, which are counterparts in this context of uncertain models to classical approximations of the sum and intersection of ellipsoids. The results obtained for combined quadratic constraints are extended to other types of model uncertainty.
F. Dabbene, P. Gay, B.T. Polyak Recursive algorithms for inner ellipsoidal approximation of convex polytopes, Automatica, 2003, 39(10), pp. 1773-1781. DOI: 10.1016/S0005-1098(03)00180-8, URL: http://www.sciencedirect.com/science/article/pii/S0005109803001808
Abstract: In this paper, fast recursive algorithms for the approximation of an n-dimensional convex polytope by means of an inscribed ellipsoid are presented. These algorithms consider at each step a single inequality describing the polytope and, under mild assumptions, they are guaranteed to converge in a finite number of steps. For their recursive nature, the proposed algorithms are better suited to treat a quite large number of constraints than standard off-line solutions, and have their natural application to problems where the set of constraints is iteratively updated, as on-line estimation problems, nonlinear convex optimization procedures and set membership identification.
B.T. Polyak Robust Linear Algebra and Robust Aperiodicity, Springer-Verlag, 2003. In Directions in Mathematical Systems Theory and Optimization, volume 286, A. Rantzer, C.I. Byrnes (Ed.), pp. 249-260. DOI: 10.1007/3-540-36106-5_19, URL: http://link.springer.com/chapter/10.1007/3-540-36106-5_19, ISBN: Print 978-3-540-00065-5, Online 978-3-540-36106-0
Abstract: We consider some simple robust linear algebra problems which provide new insight for the robust stability and aperiodicity. Uncertainties are defined via various matrix norms, which include vector-induced and component-wise norms. First, the solution set of uncertain systems of linear algebraic equations is described. Second, the radius of nonsingularity of a matrix family is calculated. Third, these results are applied for estimation of aperiodicity radius.
B.T. Polyak The convexity principle and its applications, Bulletin of the Brazilian Mathematical Society, 2003, 34(1), pp. 59-75. DOI: 10.1007/s00574-003-0003-6, URL: http://link.springer.com/article/10.1007/s00574-003-0003-6
Abstract: Recently [1, 2] the new convexity principle has been validated. It states that a nonlinear image of a small ball in a Hilbert space is convex, provided that the map is $C^{1,1}$ and the center of the ball is a regular point of the map. This result has numerous applications in linear algebra, optimization and control.
M.E. Halpern, B.T. Polyak Optimization-based design of fixed-order controllers for command following, Automatica, 2002, 38(9), pp. 1615-1619. DOI: 10.1016/S0005-1098(02)00045-6, URL: http://www.sciencedirect.com/science/article/pii/S0005109802000456
Abstract: For discrete-time scalar systems, we propose an approach for designing feedback controllers of fixed order to minimize an upper bound on the peak magnitude of the tracking error to a given command input. The work makes use of linear programming to design over a class of closed-loop systems recently proposed for the rejection of non-zero initial conditions and bounded disturbances. We incorporate performance robustness in the form of a guaranteed upper bound on the peak magnitude of the tracking error under plant coprime factor uncertainty.
B.T. Polyak History of mathematical programming in the USSR: analyzing the phenomenon, Mathematical Programming, Series B, 2002, 91(3), pp. 401-416. (Has translation in Proceedings of XIV Baikal International School Seminar "Optimization Methods and their Applications", 2008) DOI: 10.1007/s101070100258, URL: http://link.springer.com/article/10.1007/s101070100258, this work in Russian
Abstract: I am not a historian; these are just reminiscences of a person involved in the development of optimization theory and methods in the former USSR. I realize that my point of view may be very personal; however, I am trying to present as broad and unbiased picture as I can.
B.T. Polyak, S.A. Nazin Limiting Behaviour of Bounding Ellipsoids for State Estimation, Pergamon, 2002. In Nonlinear Control Systems 2001, volume 2, A.B. Kurzhanski, A.L. Fradkov (Ed.), pp. 553-558. (A Proceedings Volume from the 5th Ifac Symposium, St. Petersburg, Russia, 4-6 July 2001) ISBN: 0080435602
Abstract: Ellipsoidal technique is an advantageous and helpful tool in state estimation of dynamic systems with bounded disturbances; it gives a reliable outer approximations on reachable sets. In this paper the problem concerning asymptotic behaviour of ellipsoidal estimates is considered for linear discrete-time systems without measurements. At the core of that question, some benefits and useful properties were noted using the trace criterion in ellipsoidal calculus algorithms - specically the boundedness and convergence of approximations. The minimal ellipsoid that contains the limiting reachable set is compared with the recursive algorithm of state estimation.
B.T. Polyak, P.S. Shcherbakov Superstable Linear Control Systems. I. Analysis, Automation and Remote Control, 2002, 63(8), pp. 1239-1254. (Translated from Avtomatika i Telemekhanika, No. 8, 2002, pp. 37-53) DOI: 10.1023/A:1019823208592, URL: http://link.springer.com/article/10.1023/A:1019823208592, this work in Russian
Abstract: The notion of superstability of linear control systems was introduced. Superstability which is a sufficient condition for stability was formulated in terms of linear constraints on the entries of a matrix or the coefficients of a characteristic polynomial. In the first part of the paper, the properties of superstable systems were studied. The norms of solutions were proved to decrease exponentially monotonically in the absence of perturbations, and the solutions were proved to be uniformly bounded in the presence of bounded perturbations. A generalization to nonlinear and time varying systems was discussed. Spectral properties of superstable systems were studied. For interval matrices, a complete solution was given to the problem of robust superstability.
B.T. Polyak, P.S. Shcherbakov Superstable Linear Control Systems. II. Design, Automation and Remote Control, 2002, 63(11), pp. 1745-1763. (Translated from Avtomatika i Telemekhanika, No. 11, 2002, pp. 56-75) DOI: 10.1023/A:1020999113912, URL: http://link.springer.com/article/10.1023/A:1020999113912, this work in Russian
Abstract: The notion of superstability introduced in [1] is applied to the design of stabilizing and optimal controllers. It is shown that a static output feedback controller which ensures superstability of the closed-loop system can be found (provided it exists) by means of linear programming (LP) techniques; finding a superstable matrix in the given affine family is a generalization of this problem. The ideology of superstability is also shown to be fruitful in optimal and robust control. This is exemplified by the problems of rejection of bounded disturbances, optimization of the integral performance index which involves absolute values (rather than squares) of the control and state, and by stabilization of an interval matrix family and simultaneous stabilization.
G. Calafiore, B.T. Polyak Stochastic Agorithms for Exact and Approximate Feasibility of Robust LMIs, Automatic Control, IEEE Transactions on, 2001, 46(11), pp. 1755-1759. DOI: 10.1109/9.964685, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=964685
Abstract: In this note, we discuss fast randomized algorithms for determining an admissible solution for robust linear matrix inequalities (LMIs) of the form $F(x, \Delta) \preccurlyeq 0$, where $x$ is the optimization variable and $\Delta$ is the uncertainty, which belongs to a given set $\mathbf{\Delta}$. The proposed algorithms are based on uncertainty randomization: the first algorithm finds a robust solution in a finite number of iterations with probability one, if a strong feasibility condition holds. In case no robust solution exists, the second algorithm computes an approximate solution which minimizes the expected value of a suitably selected feasibility indicator function. The theory is illustrated by examples of application to uncertain linear inequalities and quadratic stability of interval matrices
C. Durieu, É. Walter, B. Polyak Multi-Input Multi-Output Ellipsoidal State Bounding, Journal of Optimization Theory and Applications, 2001, 111(2), pp. 273-303. DOI: 10.1023/A:1011978200643, URL: http://link.springer.com/article/10.1023/A:1011978200643
Abstract: Ellipsoidal state outer bounding has been considered in the literature since the late sixties. As in the Kalman filtering, two basic steps are alternated: a prediction phase, based on the approximation of the sum of ellipsoids, and a correction phase, involving the approximation of the intersection of ellipsoids. The present paper considers the general case where $K$ ellipsoids are involved at each step. Two measures of the size of an ellipsoid are employed to characterize uncertainty, namely, its volume and the sum of the squares of its semiaxes. In the case of multi-input multi-output state bounding, the algorithms presented lead to less pessimistic ellipsoids than the usual approaches incorporating ellipsoids one by one.
O.N. Kiselev, B.T. Polyak Minimization of Overshoot in Linear Discrete-Time Systems via Low-Order Controllers, Automation and Remote Control, 2001, 62(4), pp. 597-606. (Translated from Avtomatika i Telemekhanika, No. 4, 2001, pp. 98-108) DOI: 10.1023/A:1010285629098, URL: http://link.springer.com/article/10.1023/A:1010285629098, this work in Russian
Abstract: For the SISO linear discrete-time control systems, a technique of response optimization was proposed. It is based on introducing a performance function which is the upper bound of the maximum of error magnitude. Its minimization leads to a linear programming problem in the controller coefficients. Importantly, a low-order controller can be designed in this manner. Various generalizations of the problem, including the robust variant, were considered.
B. Polyak, M. Halpern Optimal design for discrete-time linear systems via new performance index, International Journal of Adaptive Control and Signal Processing, 2001, 15(2), pp. 129-152. DOI: 10.1002/acs.647, URL: http://dx.doi.org/10.1002/acs.647
Abstract: We introduce a class of linear discrete-time systems called ‘superstable’. For the SISO case this means that the absolute value of the constant term of the characteristic polynomial is greater than the sum of absolute values of all other coefficients, while superstable MIMO systems have a state matrix with l1 norm less than one. Such systems have many special features. First, non-asymptotic bounds for the output of such systems with bounded input can be easily obtained. In particular, for small enough initial conditions, we get the equalized performance property, recently introduced for the SISO case by Blanchini and Sznaier (36th CDC, San Diego, 1997, pp. 1540-1545). Second, the same bounds can be obtained for LTV systems, provided all the frozen LTI systems are super stable. This makes the notion well suited for adaptive control.These bounds can be used as the performance index for optimal controller design, as proposed by Blanchini and Sznaier for the SISO case. Then to obtain disturbance rejection in SISO or MIMO systems, we design a controller which guarantees super stability of the closed-loop system and minimizes the proposed performance index ($\gamma$-optimality). This problem happens to be quasiconvex with respect to the controller coefficients and can be solved via parametric linear programming. Compared with the well-known $l_1$ optimization-based design technique, the approach allows low-order controllers to be designed (while $l_1$ optimal controllers may have high order) and can take into account non-asymptotic time-domain behaviour of the system with non-zero initial conditions. For unbounded controller orders we prove the existence and finite dimensionality of $\gamma$-optimal designs. We also address the robustness issues for transfer functions with coprime factor uncertainty bounded in $l_1$ norm. A robust performance problem can be formulated and similarly solved via linear programming. Numerous examples are provided to compare the proposed design with optimal $l_1$ and $H_\infty$ controllers.
B.T. Polyak Random algorithms for solving convex inequalities, Elsevier Science, 2001. In Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, volume 8, D. Butnariu, S. Reich, Y. Censor (Ed.), pp. 409-422. DOI: 10.1016/S1570-579X(01)80024-0, URL: http://www.sciencedirect.com/science/article/pii/S1570579X01800240, ISBN: 0-444-50595-4
Abstract: A random subgradient method is proposed for the general convex feasibility problemwith very large (or infinite) number of inequalities. Under the strong feasibility assumption the method terminates in a finite number of iterations with probability one. A convergent version of the method for infeasible case is also provided. The algorithm can be applied for solving linear matrix inequalities arising in control. Numerical simulation demonstrates high efficiency of the approach for large dimensional problems.
B.T. Polyak Local programming, Computational Mathematics and Mathematical Physics, 2001, 41(9), pp. 1259-1266. (Translated from: Zhurnal Vychislitel'noi Matematiki i Matematichesckoi Fiziki. Vol. 41, No. 9, 1324-1331, 2001) this work in Russian
Abstract: Local programming is the class of mathematical programming problems with the additional constraint $\|x - a\| \leq \epsilon$. It turns out that if $a$ is a regular point of the original problem and $\epsilon > 0$ is sufficiently small, these problems behave as convex ones, even though neither the objective function nor the constraints are assumed to be convex. This phenomenon is based on the general principle of the convexity of the image of a small ball under a nonlinear mapping. The duality theory for local programming problems is developed. Special methods with high convergence rate for solving these problems are constructed.
B.T. Polyak Convexity of Nonlinear Image of a Small Ball with Applications to Optimization, Set-Valued Analysis, 2001, 9(1-2), pp. 159-168. DOI: 10.1023/A:1011287523150, URL: http://link.springer.com/article/10.1023/A:1011287523150
Abstract: Let $f: X \rightarrow Y$ be a nonlinear differentiable map, $X, Y$ are Hilbert spaces, $B(a, r)$ is a ball in $X$ with a center $a$ and radius $r$. Suppose $f'(x)$ is Lipschitz in $B(a, r)$ with Lipschitz constant $L$ and $f'(a)$ is a surjection: $f'(a) X = Y$; this implies the existence of $v > 0$ such that $\|f'(a)^* y\| \geq v\|y\|, \forall y \in Y$. Then, if $arepsilon < min\{r, v/(2L)\}$, the image $F = f(B(a, arepsilon))$ of the ball $B(a, arepsilon)$ is convex. This result has numerous applications in optimization and control. First, duality theory holds for nonconvex mathematical programming problems with extra constraint $\|x - a\| \leq arepsilon$. Special effective algorithms for such optimization problems can be constructed as well. Second, the reachability set for ‘small power control’ is convex. This leads to various results in optimal control.
B.T. Polyak, R. Tempo Probabilistic robust design with linear quadratic regulators, Systems & Control Letters, 2001, 43(5), pp. 343-353. DOI: 10.1016/S0167-6911(01)00117-7, URL: http://www.sciencedirect.com/science/article/pii/S0167691101001177
Abstract: In this paper, we study robust design of uncertain systems in a probabilistic setting by means of linear quadratic regulators (LQR). We consider systems affected by random bounded nonlinear uncertainty so that classical optimization methods based on linear matrix inequalities cannot be used without conservatism. The approach followed here is a blend of randomization techniques for the uncertainty together with convex optimization for the controller parameters. In particular, we propose an iterative algorithm for designing a controller which is based upon subgradient iterations. At each step of the sequence, we first generate a random sample and then we perform a subgradient step for a convex constraint defined by the LQR problem. The main result of the paper is to prove that this iterative algorithm provides a controller which quadratically stabilizes the uncertain system with probability one in a finite number of steps. In addition, at a fixed step, we compute a lower bound of the probability that a quadratically stabilizing controller is found.
B.T. Polyak, W.M. Haddad, V. Chellaboina, R. Kumar Discussion on: ‘Multiobjective $L_1/H_\infty$ Controller Design for Systems with Frequency and Time Domain Constraints’, European Journal of Control, 2000, 6(2), pp. 184-185. DOI: 10.1016/S0947-3580(00)70926-5, URL: http://www.sciencedirect.com/science/article/pii/S0947358000709265
B.T. Polyak, P.S. Shcherbakov Random Spherical Uncertainty in Estimation and Robustness, Automatic Control, IEEE Transactions on, 2000, 45(11), pp. 2145-2150. DOI: 10.1109/9.887645, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=887645
Abstract: A theorem is formulated that gives an exact probability distribution for a linear function of a random vector uniformly distributed over a ball in $n$-dimensional space. This mathematical result is illustrated via applications to a number of important problems of estimation and robustness under spherical uncertainty. These include parameter estimation, characterization of attainability sets of dynamical systems, and robust stability of affine polynomial families.
A.N. Vishnyakov, B.T. Polyak Low-Order Controllers for Discrete Control Systems under Nonrandom Disturbances: A Synthesis Method, Automation and Remote Control, 2000, 61(9, part 2), pp. 1515-1521. (Translated from Avtomatika i Telemekhanika, No. 9, 2000, pp. 112-119) this work in Russian
Abstract: In modern literature, great attention is paid to the design of optimal controllers for systems under nonstochastic disturbances bounded in $\ell_\infty$ norm [1-9]. Standard approaches, such as the $\ell^1$-optimization [4, 5], only produce controllers of unduly high order that are unwieldy in practical implementation. Other optimal design procedures [8, 9] employ a special criterion to generate uniformly time-bounded output of a system. In this paper we develop a new procedure to synthesis modal control systems with predefined order of the optimal controller. The main idea, due to Tsypkin [1, 2], is that the quality functional for systems with a fixed characteristic polynomial is a convex function of the parameter of a family of stabilizing controllers. A similar approach can also be developed for nonrandom disturbances that are bounded in a norm other than the $\ell_\infty$-norm. An interesting case of pulse disturbances bounded in $\ell_1$-norm is also given.
O.N. Kiselev, B.T. Polyak Design of Low-Order Controllers by the $H^\infty$ and Maximal-Robustness Performance Indices, Automation and Remote Control, 1999, 60(3, part 2), pp. 393-402. (Translated from Avtomatika i Telemekhanika, No. 3, pp. 119-130, March, 1999) this work in Russian
Abstract: ???
B.T. Polyak, M.E. Halpern Robust Stability and Design of Linear Discrete-Time SISO Systems Under $l_1$ Uncertainties, Automatic Control, IEEE Transactions on, 1999, 44(11), pp. 2076-2080. DOI: 10.1109/9.802919, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=802919
Abstract: Shows how value sets and the zero exclusion principle can be used to obtain results on the robust stability and design of controllers against a special infinite-dimensional $l_1$ norm bounded parametric uncertainty in both numerator and denominator of scalar discrete-time plants. This parametric uncertainty has properties of both parametric and unstructured uncertainty and allows standard $H^\infty$ design tools to be used without conservatism.
B.T. Polyak, P.S. Shcherbakov Numerical Search of Stable or Unstable Element in Matrix or Polynomial Families: A Unified Approach to Robustness Analysis and Stabilization, Springer, 1999. In Robustness in Identification and Control, volume 245, A. Garilli, A. Tesi, A. Vicino (Ed.), pp. 344-358. DOI: 10.1007/BFb0109879, URL: http://link.springer.com/chapter/10.1007/BFb0109879, ISBN: Print 978-1-85233-179-5, Online 978-1-84628-538-7
Abstract: In this paper, we develop a new approach to robustness analysis and design under parametric uncertainty. The heart of the approach is an iterative procedure of non-smooth optimization, which is aimed at moving the zeros of a parameter-dependent polynomial toward a prescribed domain. The method is based on the first-order and second-order formulae for zeros of perturbed polynomials and, hence, deals directly with perturbed zeros rather than coefficients. The salient feature of the method is that it applies to a broad class of problems involving any differentiable dependence of the coefficients of polynomials on the vector of parameters. A similar method based on the same ideas is developed for families of matrices. An immediate application to the control theory leads to solution of a number of fundamental problems: Robust stability of polynomial and matrix families; Maximal degree of stability; Stabilization via low-order controllers; Simultaneous stabilization; Robust stabilization. We illustrate the efficacy of the approach by several numerical examples.
Ya.Z. Tsypkin, B.T. Polyak High-Gain Robust Control, European Journal of Control, 1999, 5(1), pp. 3-9. DOI: 10.1016/S0947-3580(99)70132-9, URL: http://www.sciencedirect.com/science/article/pii/S0947358099701329
Abstract: We consider linear time-invariant SISO systems with parametric or non-parametric uncertainty in the transfer function. It is assumed that the system is robustly minimum-phase; we obtain necessary and sufficient conditions for the system to be robustly stabilisable by a high-gain controller and explicitly calculate the gain margin for interval systems. Thus, such systems need neither identification nor adaptation to be robustly stabilised and to attenuate disturbances. The case of unmodelled dynamics is more sophisticated; some models admit high-gain stabilisation while others do not.
B.T. Polyak Robust Stability of Interval Matrices: a Stochastic Approach, Springer, 1998. In Stochastic Programming Methods and Technical Applications, volume 458, K. Marti, P. Kall (Ed.), pp. 202-207. DOI: 10.1007/978-3-642-45767-8_12, URL: http://link.springer.com/chapter/10.1007/978-3-642-45767-8_12, ISBN: Print 978-3-540-63924-4, Online 978-3-642-45767-8
Abstract: The problem of checking robust stability of interval matrices has been proved to be NP-hard. However a closely related problem can be effectively solved in the framework of the stochastic approach [1]. Moreover the deterministic interval robust stability radius happens to be very conservative for large dimensions from the probabilistic point of view.
B.T. Polyak Convexity of Quadratic Transformations and Its Use in Control and Optimization, Journal of Optimization Theory and Applications, 1998, 99(3), pp. 553-583. DOI: 10.1023/A:1021798932766, URL: http://link.springer.com/article/10.1023/A:1021798932766
Abstract: Quadratic transformations have the hidden convexity property which allows one to deal with them as if they were convex functions. This phenomenon was encountered in various optimization and control problems, but it was not always recognized as consequence of some general property. We present a theory on convexity and closedness of a 3D quadratic image of $\mathbb{R}^n, n \geq 3$, which explains many disjoint known results and provides some new ones.
Ya.Z. Tsypkin, B.T. Polyak Stability of linear difference equations with unmodelled higher order terms, Journal of Difference Equations and Applications, 1998, 3(5-6), pp. 539-546. (Dedicated to Gerry Ladas on his sixtieth birthday) DOI: 10.1080/10236199708808119, URL: http://www.tandfonline.com/doi/pdf/10.1080/10236199708808119
Abstract: We consder the case when the tru linear difference equation may difer from the nominal one. Neither higher order coefficients nor the order of the true equation are known: the only information available is that these higher order coefficients ae bounded in $l_1$ norm. We obtain necessary and sufficient conditionsfor stability of the entire family of such equations.
O.N. Kiselev, L.H. Lan, B.T. Polyak Frequency Responses under Parameteric Uncertainty, Automation and Remote Control, 1997, 58(4, part 2), pp. 645-661. (Translated from Avtomatika i Telemekhanika, No. 4, pp. 155-174, April, 1997) this work in Russian
Abstract: ???
B.T. Polyak, O.B. Panchenko Probabilistic Approach to Stability Problem for Interval Matrices, Doklady Mathematics, 1997, 55(2), pp. 309-311 ???. (Published in Russian in Doklady Rossiiskoy Akademii Nauk, 1997, Vol. 353, No. 4, pp. 456-458) this work in Russian
B.T. Polyak, Ya.Z. Tsypkin Optimal and Robust Methods for Stochastic Optimization, Nova Journal of Mathematics, Game Theory, and Algebra, 1997, 6(2/3), pp. 163-176.
Abstract: The problems of stochastic optimization arise in statistics, identification, numerical analysis. Recurrent algorithms of stochastic approximation type are the popular tools for solving such problems. The aim of the paper is to describe the algorithms with the highest rate of convergence. Another class of methods are minimax optimal methods which are robust under some prior uncertainty.
B.T. Polyak, P.S. Shcherbakov A Probabilistic Approach to Robust Stability of Time Delay Systems, Automation and Remote Control, 1996, 57(12, part 1), pp. 1770-1779. (Translated from Avtomatika i Telemekhanika, No. 12, pp. 97-108, December, 1996) this work in Russian
Abstract: ???
B.T. Polyak, P.S. Shcherbakov Robust Stability of Systems with Uncertain Delays, Mathematics Today, 1996, 32(7-8), pp. 118-121.
Abstract: The issue of robust stability of a family of quasipolynomials containing several interval delays is considered. The approach taken is the probabilistic approximation of the value set as a confidence ellipse on the complex plane.
B.T. Polyak, Ya.Z. Tsypkin Stability and Robust Stability of Uniform Systems, Automation and Remote Control, 1996, 57(11, part 1), pp. 1606-1617. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 91-104, November, 1996) this work in Russian
Abstract: ???
B.T. Polyak, A.N. Vishnyakov Multiplying Disks: Robust Stability of a Cascade Connection, European Journal of Control, 1996, 2(2), pp. 101-111. DOI: 10.1016/S0947-3580(96)70034-1, URL: http://www.sciencedirect.com/science/article/pii/S0947358096700341
Abstract: An explicit formula for a product of n disks in the complex plane is obtained. It completes the circular arithmetic technique and yields numerous applications in robust stability analysis. One of them, namely the Nyquist test (or a small gain theorem) for a cascade connection of uncertain SISO blocks, is considered in more detail.
O.N. Kiselev, B.T. Polyak Robust gain margin for a cascade of uncertain links, International Journal of Systems Science, 1995, 26(4), pp. 965-974. DOI: 10.1080/00207729508929079, URL: http://www.tandfonline.com/doi/abs/10.1080/00207729508929079
Abstract: We study the robust gain margin for a cascade of first-order links with interval time constants. It is proved to be equal to the minimal gain margin for the one-parameter family of plants. In particular cases it suffices to find the gain margin of the single system. Numerical examples with ten and more links can easily be treated.
O.N. Kiselev, B.T. Polyak Gain Margin for a Cascade of Uncertain Components, Automation and Remote Control, 1995, 56(9, part 2), pp. 1278-1286. (Translated from Avtomatika i Telemekhanika, No. 9, pp. 93-103, September, 1995) this work in Russian
Abstract: ???
O.B. Panchenko, B.T. Polyak Estimation of the Measure of Stable Polynomials in an Interval Family, Automation and Remote Control, 1995, 56(7, part 2), pp. 997-1003. (Translated from Avtomatika i Telemekhanika, No. 7, pp. 108-115, July, 1995) this work in Russian
Abstract: ???
B.T. Polyak, J. Kogan Necessary and Sufficient Conditions for Robust Stability of Linear Systems with Multiaffine uncertainty Structure, Automatic Control, IEEE Transactions on, 1995, 40(7), pp. 1255-1260. DOI: 10.1109/9.400482, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=400482
Abstract: This correspondence is concerned with an image $f(B^m)$ of a box $B^m \subset \mathbb{R}^m$ under a multiaffine transformation $f : \mathbb{R}^m \rightarrow C$. The authors introduce a notion of a principal point of $B^m$ and prove that the boundary of $f(B^m)$ is covered by images of principal points. The authors exploit this result to provide necessary and sufficient robust stability conditions for polynomials whose coefficients are multiaffine functions of parameters. An application of the general criterion obtained in the correspondence to the particular case of systems with a cascade of first-order uncertain blocks leads to a computationally tractable procedure that verifies stability of the systems
B.T. Polyak, P.S. Shcherbakov Algorithms of Matrix Estimation, Automation and Remote Control, 1995, 56(11, part 2), pp. 1605-1619. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 122-139, November, 1995) this work in Russian
Abstract: ???
Ya.Z. Tsypkin, B.T. Polyak Robust Stability of a Class of Distributed-Parameter Systems, Doklady Mathematics, 1995, 51(2), pp. 304-306. (Translated from: Doklady Akademii Nauk, 1995, Vol. 341, No. 4, pp. 463-465) this work in Russian
Ya.Z. Tsypkin, B.T. Polyak Frequency Domain Criteria for Robust Stability of a Family of Linear Difference Equations, Journal of Difference Equations and Applications, 1995, 1(2), pp. 137-149. DOI: 10.1080/10236199508808015, URL: http://www.tandfonline.com/doi/pdf/10.1080/10236199508808015
Abstract: We provide necessary and sufficient conditions for stability of solutions to linear difference equations with coefficients in a prescribed set. The conditions encompass classes of uncertainty such as interval families, $l^p$ families, affine families.
A.S. Nemirovskii, B.T. Polyak Necessary Conditions for the Stability of Polynomials and Their Use, Automation and Remote Control, 1994, 55(11, part 2), pp. 1644-1649. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 113-119, November, 1994) this work in Russian
Abstract: a unified approach based on the results of Gauss anil Newton is proposed for deriving lhe necessary conditions of stability of polynomials. It yields criteria for tesling whether a polynomial with real or complex coefficients is Hurwitz, aperiodic, and sector stable. These conditions are useful in estimating the probability that random polynomial is a Hurwitz polynomiaI and in solving certain problems of robust stability.
B. Polyak, P. Scherbakov, S. Shmulyian Circular Arithmetic and its Applications to Robustness Analysis, Birkhäuser, 1994. In Modeling Techniques for Uncertain Systems, volume 18, A.B. Kurzhanski, V.M. Veliov (Ed.), pp. 229-243. ISBN: 0-8176-3746-X, 3-7643-7346-X
Abstract: Interval analysis is a common tool in dealing with uncertain real numbers. Its complex analog is called circular arithmetic. A circular number is a circle on the complex plane. Arithmetic operations with such numbers are rather simple; the only exception is multiplication. Explicit and approximate formulae for product of circular numbers are given. Numerous applications of this technique to robust stability problems are presented.
B.T. Polyak Frequency domain criteria for robust stability of bivariate polynomials, Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on, 1994, 41(2), pp. 161-167. DOI: 10.1109/81.269052, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=269052
Abstract: The problem of robust strict-sense Hurwitz stability for bivariate polynomials is considered. A general criterion is formulated as a zero exclusion principle. Attempts are made to construct a value set for a wide class of coefficient perturbations. Interval, disc and linear families for both continuous time and discrete time cases are studied. All conditions for robust stability are written in two-dimensional or one-dimensional frequency domain form. One of examples is a bivariate version of the Nyquist test.
B.T. Polyak, P.S. Scherbakov, S.B. Shmulyian Construction of value set for robustness analysis via circular arithmetic, International Journal of Robust and Nonlinear Control, 1994, 4(3), pp. 371-385. DOI: 10.1002/rnc.4590040305, URL: http://onlinelibrary.wiley.com/doi/10.1002/rnc.4590040305/abstract
Abstract: Circular arithmetic technique is developed for constructing value set of a characteristic polynomial. It provides necessary and sufficient conditions for robust stability of disk polynomials and their simple combinations. In more complicated cases sufficient conditions can be obtained. Various examples including multilinear (real or complex) parameter perturbations are considered.
B.T. Polyak, Ya.Z. Tsypkin Robust Aperiodicity, Physics - Doklady, 1994, 39(3), pp. 149-152. (Translated from: Doklady Akademii Nauk, 1994, Vol. 335, No. 3, pp. 304-307) this work in Russian
B.T. Polyak, Ya.Z. Tsypkin, Y.Q. Shi, K.K. Yen, C.M. Chen Comments on "Two necessary conditions for a complex polynomial to be strictly Hurwitz and their applications in robust stability analysis" (with reply), Automatic Control, IEEE Transactions on, 1994, 39(5), pp. 1147-1148. DOI: 10.1109/9.284913, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=284913
Abstract: In the note,$^1$ the authors present two simple necessary conditions for a polynomial with complex coefficients to be strictly Hurwitz. They claim that this is an extension and refinement of a recent result [1]. We comment that the second condition is well known and that the first one is a direct corollary of Newton's test for a polynomial to have only real roots.
Ya.Z. Tsypkin, B.T. Polyak, A. Katbab, E.I. Jury On the strict- and wide-sense stability robustness of uncertain systems: application of a new frequency criterion, Systems & Control Letters, 1994, 22(5), pp. 377-383. DOI: 10.1016/0167-6911(94)90035-3, URL: http://www.sciencedirect.com/science/article/pii/0167691194900353
Abstract: In this paper, we discuss a new frequency-domain graphical approach for robust stability of uncertain systems. This method is based on Mikhailov's criterion and it requires the plotting of only one Hodograph and evaluation of two boundary conditions. Moreover, this approach is extended to a more general robust stability sense, i.e., extended and wide-sense Hurwitz stability, which may be applied to a number of robustness problems such as positivity, nonnegativity, spectral analysis, and array processing.
A.V. Goldenshluger, B.T. Polyak Estimation of regression parameters with arbitrary noise, Mathematical Methods of Statistics, 1993, 2(1), pp. 18-29. (Two pages, including references are missing!)
O.N. Kiselyov, B.T. Polyak Robust Stability of a Chain of Simple Links, Automation and Remote Control, 1993, 54(12, part 2), pp. 1824-1834. (Translated from Avtomatika i Telemekhanika, No. 12, pp. 115-127, December, 1993) this work in Russian
Abstract: We consider the problem of stabili|y of a closed system containing a chain of simple links with an interval uncertainty for the time constant of each link. In this case the characteristic equation is nonlinear with respect to undetermined parameters and the problem cannot be covered by the existing criteria of robust stability of linear families. A general necessary and sufficient condition of the robust stability is sugested. It is also specified for a number of particular cases; it becomes especially simple for the non-overlapped uncertainty intervals. A convenient sufficient condition of the robust stability is also derived.
B.T. Polyak, A.B. Tsybakov A Family of Asymptotically Optimal Methods for Choosing the Order of a Projective Regression Estimate, Theory of Probability & Its Applications, 1993, 37(3), pp. 471-481. (Translated from Russian Journal by V. Kotov) DOI: 10.1137/1137097, URL: http://epubs.siam.org/doi/pdf/10.1137/1137097, this work in Russian
Ya.Z. Tsypkin, B.T. Polyak Robust Stability of Discrete-Time Systems: Frequency Domain Approach, TSI Press, 1993. In Fundamentals of Discrete-Time Systems: A Tribute to Professor Eliahu I. Jury, M. Jamshidi, M. Mansour, B.D.O. Anderson, N.K. Bose (Ed.), pp. 163-169. ISBN: 0-9627451-9-7
Abstract: This paper presents frequency criteria formulations of discrete-time systems robust stability. These criteria are useful for various admissible disturbances sets of systems parameterss.
Ya.Z. Tsypkin, B.T. Polyak Robust absolute stability of continuous systems, International Journal of Robust and Nonlinear Control, 1993, 3(3), pp. 231-239. DOI: 10.1002/rnc.4590030304, URL: http://onlinelibrary.wiley.com/doi/10.1002/rnc.4590030304/abstract
Abstract: The problem of stability of continuous-time nonlinear systems with nonparametric uncertainty of a linear part and sector uncertainty of its nonlinear part is considered. The proposed robust stability criterion is a natural extension of the circle criterion for absolute stability. The situation with the Popov criterion is also discussed; it is demonstrated to be nonrobust for perturbations of a linear part, bounded in $H^\infty$ norm.
A.V. Nazin, B.T. Polyak, A.B. Tsybakov Optimal and robust kernel algorithms for passive stochastic approximation, Information Theory, IEEE Transactions on, 1992, 38(5), pp. 1577-1583. DOI: 10.1109/18.149511, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=149511
Abstract: The problem of estimating a root of an equation $f(x) = 0$ is considered in the situation where the values of $f(x)$ are measured with random errors at random points and the choice of these points cannot be controlled. Nonlinear modification of the recursive Hardle-Nixdorf method is studied. Almost sure and mean square convergence is proved, and the rate of convergence is estimated. The optimal choice of parameters and of a kernel is presented; it is shown that for the optimal procedure the lower bound for the accuracy of arbitrary methods of solving the problem is attained
B.T. Polyak Robustness Analysis for Multilinear Perturbations, Birkhäuser, 1992. In Robustness of Dynamic Systems with Parameter Uncertainties, M. Mansour, S. Balemi, W. Truöl (Ed.), pp. 93-104. DOI: 10.1007/978-3-0348-7268-3_10, URL: http://link.springer.com/chapter/10.1007/978-3-0348-7268-3_10, ISBN: Print 978-3-0348-7270-6, Online 978-3-0348-7268-3
Abstract: An image $f(K)$ of a box $K \subset R^m$ under multilinear transformation $f: R^m \rightarrow G$ is studied. For a class of functions called $D$ - functions it is proved to be a convex polygon with $2m$ edges. Under less restrictive assumptions $f(K)$ is a noncovex polygon. In the most general case $f(K)$ has curvilinear parts of the boundary. This result has numerous applications in robustness analysis. Edge and Kharitonovlike theorems as well as frequency criteria for polytopes of polynomials can be extended to multilinear families of polynomials. Systems with a cascade of uncertain blocks or with uncertain plant and controller are considered as examples.
B.T. Polyak Rantzer-Doyle's Problem Revisited, Birkhäuser, 1992. In Robustness of Dynamic Systems with Parameter Uncertainties, M. Mansour, S. Balemi, W. Truöl (Ed.), pp. 314-315. DOI: 10.1007/978-3-0348-7268-3_30, URL: http://link.springer.com/chapter/10.1007/978-3-0348-7268-3_30, ISBN: Print 978-3-0348-7270-6, Online 978-3-0348-7268-3
B.T. Polyak Frequency Methods in the Theory of Robust Stability, Automation and Remote Control, 1992, 53(1, part 2), pp. 140-142. (Part of the paper Discussion on Robustness Problems in Control Systems, Automation and Remote Control, Vol. 53, No. 1, Part 2, 1992, 134-142. Translated from Avtomatika i Telemekhanika, No. 1, pp. 172-175, July, 1992) this work in Russian
B.T. Polyak, A.B. Juditsky Acceleration of Stochastic Approximation by Averaging, SIAM Journal on Control and Optimization, 1992, 30(4), pp. 838-855. DOI: 10.1137/0330046, URL: http://epubs.siam.org/doi/pdf/10.1137/0330046
Abstract: A new recursive algorithm of stochastic approximation type with the averaging of trajectories is investigated. Convergence with probability one is proved for a variety of classical optimization and identification problems. It is also demonstrated for these problems that the proposed algorithm achieves the highest possible rate of convergence.
B.T. Polyak, A.B. Tsybakov On Stochastic Approximation with Arbitrary Noise (the KW-case), AMS, 1992. In Topics in Nonparametric Estimation, volume 12, R.Z. Khasminskii (Ed.). ISBN: 0-8218-4111-4
B.T. Polyak, Ya.Z. Tsypkin Robust Nyquist Test, Automation and Remote Control, 1992, 53(7, part 1), pp. 972-977. (Translated from Avtomatika i Telemekhanika, No. 7, pp. 25-31, July, 1992) this work in Russian
Abstract: A graphic test is proposed for deciding the stability, of a family of closed-loop linear systems in terms of the frequency characteristic of the nominal open-loop system and the width of the band around the frequency characteristic describing the family. Two types o.f uncertainty are considared: additive and multiplicative. The proposed tests are close to the Nyquist test for the nominal system. The only difference is that the Nyquist hodograph is replaced with a modified hodograph and the point -1 is replaced with a circle. Similar tests are applied to problems with parametric uncenainty.
Ya.Z. Tsypkin, B.T. Polyak Robust Absolute Stability of Continuous Systems, Birkhäuser, 1992. In Robustness of Dynamic Systems with Parameter Uncertainties, M. Mansour, S. Balemi, Truöl W. (Ed.), pp. 113-121. DOI: 10.1007/978-3-0348-7268-3_12, URL: http://link.springer.com/chapter/10.1007/978-3-0348-7268-3_12, ISBN: Print 978-3-0348-7270-6, Online 978-3-0348-7268-3
Abstract: The problem of stability of continuous-time nonlinear systems with non-parametric uncertainty of a linear part and sector uncertainty of its nonlinear part is considered. The proposed robust stability criterion is a natural extension of the circle criterion for absolute stability. The situation with Popov criterion is also discussed; it is demonstrated to be nonrobust for perturbations of a linear part, bounded in $H^\infty$ norm.
Ya.Z. Tsypkin, B.T. Polyak Optimal recurrent algorithms for identification of nonstationary plants, Computers & Electrical Engineering, 1992, 18(5), pp. 365-371. DOI: 10.1016/0045-7906(92)90044-E, URL: http://www.sciencedirect.com/science/article/pii/004579069290044E
Abstract: Identification of static or dynamic linear plants with time-varying parameters is considered. The drift of parameters is described by difference equations. A recurrent identification algorithm having an asymptotically optimal rate of convergence is obtained. The algorithm is nonlinear if noises are non-Gaussian. Particular cases and extensions are discussed.
O.N. Kiselev, B.T. Polyak Ellipsoidal Estimation with respect to a Generalized Criterion, Automation and Remote Control, 1991, 52(9, part 2), pp. 1281-1292. (Translated from Avtomatika i Telemekhanika, No. 9, pp. 133-145, September, 1991) this work in Russian
Abstract: It is proposed to apply ellipsoidal estimates that are optimal with respect to a generalized criterion (previously the volume of an ellipsoid was used as the criterion) for problems of estimating parameters and states of systems with deterministic bounded disfurbances. Such an approach allows us to simpe calculation of explicit estimates and obtain less "elongated" ellipsoids. Methods for constructing an approximation for the union and intersection of ellipsoids are presented. A technique for transition from ellipsoidal estimators to the inteval ones and vice versa is described.
N.P. Petrov, B.T. Polyak Robust $D$-Partition, Automation and Remote Control, 1991, 52(11, part 1), pp. 1513-1523. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 41-53, November, 1991) this work in Russian
Abstract: The idea of D-partltlon (construction of a two-dimensional stability region) is combined with the robust approach (testing the stability of systems from a given region in the parameter space). Techniques are suggested for constructing robust stabillty regions by two parameters when the other parameters fall inslde given perturbation ranges. Continuous and discrete systems with real and complex parameters are considered. Cases when the coefflcients of the characteristic equation are nonlinear in the parameters are also examined.
B.T. Polyak, A.B. Tsybakov Asymptotic Optimality of the $C_p$-Test for the Orthogonal Series Estimation of Regression, Theory of Probability & Its Applications, 1991, 35(2), pp. 293-306. (Translated from Russian Journal by V. V. Slavova) DOI: 10.1137/1135037, URL: http://epubs.siam.org/doi/pdf/10.1137/1135037, this work in Russian
B.T. Polyak, Ya.Z. Tsypkin Robust Stability of Discrete Linear Systems, Soviet Physics-Doklady, 1991, 36(2), pp. 111-113. (Translated by Zvi Lerman from: Doklady Akademii Nauk SSSR, 1991, Vol. 316, No. 4, pp. 842-846) this work in Russian
B.T. Polyak, Ya.Z. Tsypkin Robust Stability under Complex Perturbations of the Parameters, Automation and Remote Control, 1991, 52(8, part 1), pp. 1069-1077. (Translated from Avtomatika i Telemekhanika, No. 8, pp. 45-55, August, 1991) this work in Russian
Abstract: Questions of stability of an incompletely determined system which corresponds to a family of characteristic equations with coefficients varying in a disk in the complex plane are considered. Necessary and sufficient conditions for the robust stability of continuous and discrete linear systems are given. The same questions are studied for closed systems (with fixed regulator and indefinite object). Tests are formulated for testing the robust degree of stability and positive reality. conditions for robust absolute stability, of nonlinear systems are found.
Ya.Z. Tsypkin, B.T. Polyak Frequency Domain Criterion for Robust Stability of Polytope of Polynomials, CRC Press, 1991. In Control of Uncertain Dynamic Systems, S.P. Bhattacharyya, L.H. Keel (Ed.), pp. 491-499. (A collection of papers presented at the International Workshop on Robust Control, San Antonio, Texas, March 1991) ISBN: 0-8493-0195-5
Abstract: This paper provides a new necessary and sufficient condition for Hurwitz robust stability of polynomial family $\sum_{i=1}^m A_i(s) B_i(s)$, where $B_i$ are fixed polynomials and $A_i$ are interval ones. The condition is given in graphical form; it is based on the frequency domain approach. Some examples and extensions are considered.
Ya.Z. Tsypkin, B.T. Polyak Frequency Domain Approach to Robust Stability of Continuous Systems, Mita Press, 1991. In Systems and Control: Topics in Theory and Applications, T. Ono, F. Kozin (Ed.), pp. 389-399. URL: http://ci.nii.ac.jp/ncid/BA13093198, ISBN: 4-89583-085-3
Abstract: The general frequency domain criteria for robust stability of uncertain linear continuous systems are proposed. For the case of interval uncertainty the criterion is formulated in graphical form which differs from Kharitonov's test. Other types of constraints for perturbations are considered (e.g. $l^p$-constraints). The case of structured uncertainties connected with closed loop systems is also studied.
Ya.Z. Tsypkin, B.T. Polyak Frequency Domain Criteria for $l^p$-Robust Stability of Continuous Linear Systems, Automatic Control, IEEE Transactions on, 1991, 36(12), pp. 1464-1469. DOI: 10.1109/9.106161, URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=106161
Abstract: Necessary and sufficient criteria in the frequency domain for robust stability are given under the assumption that coefficients of a characteristic polynomial belong to a transformed $l^p$-ball. Three cases are considered in detail: $p =\infty$ (interval uncertainty), $p = 2$ (ellipsoidal uncertainty), and $p = 1$ (octahedral uncertainty). It is shown that frequency-domain-stability criteria are efficient when one deals with robust stability problems. The frequency-domain approach considered can be extended to various problems of robust stability
B.T. Polyak Variational Problems Arising in Statistics, Birkhäuser, 1990. In Perspectives in Control Theory, volume 2, B. Jakubczyk, K. Malanowski, W. Respondek (Ed.), pp. 277-285. (Proceedings of the Sielpia Conference, Sielpia, Poland, 1988) DOI: 10.1007/978-1-4757-2105-8_17, URL: http://link.springer.com/chapter/10.1007/978-1-4757-2105-8_17, ISBN: Print 978-1-4757-2107-2, Online 978-1-4757-2105-8
Abstract: Mathematical statistics is a nice source of nonstandard variational problems. As an example we can mention the famous Neyman-Pearson lemma on hypothesis testing: in optimization language it is a variational problem with integral type functional (not including derivatives) subject to specific constraints. In this paper we deal with variational problems of another kind arising in such areas of statistics as parameter estimation and nonparametric regression. Among them there are such nonstandard problems as minimization of a functional which is a ratio of two integrals, minimization of a matrix-valued criteria, finding a saddle point of a functional over some classes of functions etc. Some of these problems can be solved in explicit form by use of a technique which is untypical for the classical calculus of variations.
B.T. Polyak New Method of Stochastic Approximation Type, Automation and Remote Control, 1990, 51(7, part 2), pp. 937-946. (Translated from Avtomatika i Telemekhanika, No. 7, pp. 98-107, July, 1990) this work in Russian
Abstract: An iterative method of solutlon of problems of stochastic optimization and parameter estimation is considered that combines two processes. The first is a stochastic approximation process with a constant or slowly decreasing step. The second involves averaging this process, so that it is possible to obtain the asyrnptotically highest feasible convergence rate. The advantage of this method over conventional methods consists in the low a priori information requirements and the absence of operations with matrices.
B.T. Polyak, A.B. Tsybakov Optimal Order of Accuracy for Search Algorithms in Stochastic Optimization, Problems of Information Transmission, 1990, 26(2), pp. 126-133. (Translated from Problemy Peredachi Informatsii, 1990, Vol. 26, No. 2, 45-53) this work in Russian
Abstract: A new optimum-seeking method is proposed and its asymptotic optimality is proved.
B.T. Polyak, Ya. Z. Tsypkin Frequency Criteria of Robust Stability and Aperiodicity of Linear Systems, Automation and Remote Control, 1990, 51(9, part 1), pp. 1192-1201. (Translated from Avtomatika i Telemekhanika, No. 9, pp. 45-54, September, 1990) this work in Russian
Abstract: Frequency criteria of stability are formulated for linear systems with perturbed coefficients of their characteristic polynomials. The cases are examined of interval-constrained perturbatlons and ellipsoidally constrained perturbations. The largest possible range of perturbations is obtained, and conditions of robust aperiodicity are presented.
Ya.Z. Tsypkin, B.T. Polyak Frequency Criteria for Robust Modality of Linear Discrete Systems, Soviet Journal of Automation and Information Sciences, 1990, 23(4), pp. 1-7. (Translated from Russian journal Avtomatika (Kiev), 1990, No. 5, pp. 3-9) this work in Russian
A.V. Nazin, B.T. Polyak, A.B. Tsybakov Passive Stochastic Approximation, Automation and Remote Control, 1989, 50(11, part 2), pp. 1563-1569. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 127-134, November, 1989) this work in Russian
Abstract: A root of the equation f(x) = 0 is sought in the case that the values of f(x) are measured with a random error at random Points whose choice cannot be controlled. The recursive Hardle-Nixdorf method of solution of this problem is studied. Its convergence almost surely and in the mean square is proved, and the convergence rate is estimated. A technique of selection of the optlmal parameters of this method is described, and lt ls proved that this yields a lower bound (in order of magnitude) for the accuracy of any methods of solution of the oroblem.
B.T. Polyak, A.B. Tsybakov Optimal Projection Estimators for a Regression Function of Unknown Smoothness, Soviet Mathematics-Doklady, 1989, 39(1), pp. 73-77. (Translated by H. H. McFaden from: Doklady Akademii Nauk USSR, 1989, Vol. 304, No. 2, pp. 297-301) this work in Russian
Yu.Sh. Verulava, B.T. Polyak Selection of the Regression Model Order, Automation and Remote Control, 1988, 49(11, part 2), pp. 1482-1494. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 113-129, November, 1988) this work in Russian
Abstract: We consider the problem of fitting a function from observations with a random error. The approximation is sought as a finite series in a given system of functions; the main issue is the determination of the number of terms in this expansion. The approximation aceuracy is estlmated by the mean-square prediction error over the entire interval or on the given system of points. Exact and aymptotic expressions are derived for the mean-square error under various assumptions. We give criteria for model order selection using prior information of different kinds and consider some numerical examples.
A.S. Nemirovskii, B.T. Polyak, A.B. Tsybakov Rate of Convergence of Nonparametric Estimates of Maximum-Likelihood Type, Problems of Information Transmission, 1985, 21(4), pp. 258-272. (Translated from Problems of Information Transmission, 1985, Vol. 21, No. 4, 17-33) this work in Russian
Abstract: The authors obtain the rate of convergence of $M$-estimates of nonparametric regression in the $L_2$ metric. It is shown that, for classes of smooth, monotonic, and convex functions, this rate cannot be improved (to within a constant). It is established that in a number of cases, particularly for the class of mono-tonic functions, nonlinear $M$-estimates are better than any linear estimates in terms of the order of the rate of convergence.
A.S. Nemirovskii, B.T. Polyak, Ya.Z. Tsypkin Optimum algorithms of stochastic optimization with multiplicative error, Soviet Physics-Doklady, 1985, 30(9), pp. 744-745. (Translated by Zvi Lerman from: Doklady Akademii Nauk SSSR, 1985, Vol. 284, No. 3, pp. 554-567) this work in Russian
A.S. Nemirovski, B.T. Polyak Iterative Methods for Solution of Linear Ill-Posed Problems under Exact Information. I, Engineering Cybernetics, 1984, 22(3), pp. 1-11. (Translated from Izvestia AN USSR, Tekhnicheskay Kibernetika, 1984, No. 2, pp. 13-25) this work in Russian
A.S. Nemirovski, B.T. Polyak Iterative Methods for Solution of Linear Ill-Posed Problems under Exact Information. II, Engineering Cybernetics, 1984, 22(4), pp. 50-56. (Translated from Izvestia AN USSR, Tekhnicheskay Kibernetika, 1984, No. 3, pp. 18-25) this work in Russian
A.S. Nemirovskii, B.T. Polyak, A.B. Tsybakov Signal Processing by the Nonparametric Maximum-Likelihood Method, Problems of Information Transmission, 1984, 20(3), pp. 177-192. (Translated from Problems of Information Transmission, Vol. 20, No. 3, 29-46) this work in Russian
Abstract: The authors propose a class of estimates that are a generalization of maximum-likelihood and $M$-estimates in the nonparametric regression problem. Existence conditions and calculation methods for such estimates are considered, and it is shown that they are consistent.
A.S. Nemirovskii, B.T. Polyak, A.B. Tsybakov The maximum likelihood method in nonparametric regression, Theory of Probability & Its Applications, 1984, 28(4), pp. 830-831. (Part of the article: Summary of reports presented at sessions of the probability and mathematical statistics seminar at the Leningrad section of the Mathematical institute of the USSR Academy of Sciences, 1982, Theory of Probability and Its Applications, 1984, No. 4, 830-840. Translated from Russian Journal by W. U. Sirk) DOI: 10.1137/1128084, URL: http://epubs.siam.org/doi/pdf/10.1137/1128084, this work in Russian
B.T. Polyak, Ya.Z. Tsypkin Criterion Algorithms of Stochastic Optimization, Automation and Remote Control, 1984, 45(6, part 2), pp. 766-774. (Translated from Avtomatika i Telemekhanika, No. 6, pp. 95-104, June, 1984) this work in Russian
Abstract: Criterion optimization problems are considered in which it is important to estimate the optimum value of the performance criterion, whereas the coordinates of the extremum point are not of interest. Algorithms are proposed for solving criterion problems in the presence of random errors of measurement of the gradient; they are optimal in the sense of the criterion rate of convergence.
Yu.Sh. Verulava, Z.N. Gorgadze, B.T. Polyak Algorithms for Estimation of Autoregression Coefficients, Automation and Remote Control, 1984, 45(11, part 1), pp. 1428-1434. (Translated from Avtomatika i Telemekhanika, No. 11, pp. 49-57, November, 1984) this work in Russian
Abstract: The recurslve algorithms of estimation of autoregression coefficients proposed in [1] are studied with the aid of simulation. Their convergence rate depends on various factors. Theoretical and numerical results are compared, and it is found by experiment that the algorithms are convergent in the case of unstable models and noise with infinite variance.
A.S. Nemirovskii, B.T. Polyak, A.B. Tsybakov Estimators of Maximum Likelihood Type for Nonparametric Regression, Soviet Mathematics-Doklady, 1983, 28(3), pp. 788-792. (Translated by L. Rosenblatt from: Doklady Akademii Nauk USSR, 1983, Vol. 273, No. 6, pp. 1310-1314) this work in Russian
B.T. Polyak, J.Z. Tsypkin Optimal and Robust Estimation of Autoregression Coefficients, Engineering Cybernetics, 1983, 21(1), pp. 100-109. (Translated from Izvestia AN USSR, Tekhnicheskay Kibernetika, 1983, No. 1, pp. 118-126) this work in Russian
B.T. Polyak, Ya.Z. Tsypkin Optimal algorithms of criterial optimization under conditions of uncertainty, Soviet Physics-Doklady, 1983, 28(11), pp. 919-920. (Translated by Zvi Lerman from: Doklady Akademii Nauk SSSR, 1983, Vol. 273, No. 2, pp. 315-318) this work in Russian
B.T. Poljak Iterative algorithms for singular minimization problems, Academic Press, 1981. In Nonlinear Programming 4, O.L. Mangasarian, R.R. Meyer, S.M. Robinson (Ed.), pp. 147-166. DOI: 10.1016/B978-0-12-468662-5.50011-2, URL: http://www.sciencedirect.com/science/article/pii/B9780124686625500112, ISBN: 978-0-12-468662-5
Abstract: The principal purpose of this paper is to treat the convergence and the rate of convergence of gradient and conjugate gradient methods in the solution of unconstrained minimization problems when the Hessian of the objective function is singular at a solution point.
B.T. Poljak, J.Z. Tsypkin Robust Identification, Automatica, 1980, 16(1), pp. 53-63. DOI: 10.1016/0005-1098(80)90086-2, URL: http://www.sciencedirect.com/science/article/pii/0005109880900862
Abstract: Convenient identification techniques based on maximum likelihood estimators (MLE) are very sensitive to deviations from assumed distributions of observations. Huber's approach to robust estimation is highly fruitful for solving identification problems under incomplete information. In the paper some robust estimators for nonlinear regression problems are proposed and their features are discussed.
B.T. Polyak, Ya.Z. Tsypkin Optimal Pseudogradient Adaptation Algorithms, Automation and Remote Control, 1980, 41(8, part 1), pp. 1101-1110. (Translated from Avtomatika i Telemekhanika, No. 8, pp. 74-84, August, 1980) this work in Russian
Abstract: The authors investigate the asymptotic rate of convergence of arbitrary pseudogradient algorithms for determining an unconditional extremum of a function when there is random nolse in the calculation of its gradient. Optimal pseudogradient algorithms for which this rate is maximal are established. Optimal pseudogradient algorithms require nonlinear transformation of the gradient; the form of this transformation is determined entirely by the distribution law of the noise.
B.T. Polyak, Ya.Z. Tsypkin Robust Pseudogradient Adaptation Algorithms, Automation and Remote Control, 1980, 41(10, part 1), pp. 1404-1409. (Translated from Avtomatika i Telemekhanika, No. 10, pp. 91-97, October, 1980) this work in Russian
Abstract: A recursive algorithm is proposed for seeking the unconstrained extremum of a function in the presence of random noise in the computation of its gradient, which does not require exact knowledge of the probability distribution of noise. The algorithm is proved to be asymptotically minimal optimal for the given class of noise. The relation to robust statistical procedures is discussed.
J.Z. Tsypkin, B.T. Poliak Optimal Pseudogradient Algorithms for Stochastic Optimization, Soviet Physics-Doklady, 1980, 25, pp. 85-87. (Published in Russian in Doklady Akademii Nauk USSR, 1980, Vol. 250, No. 5, pp. 1084-1087) this work in Russian
B.T. Poljak On the Bertsekas' method for minimization of composite functions, Springer, 1979. In International Symposium on Systems Optimization and Analysis, volume 14, A. Bensoussan, J.L. Lions (Ed.), pp. 176-184. DOI: 10.1007/BFb0002653, URL: http://link.springer.com/chapter/10.1007/BFb0002653, ISBN: Print 978-3-540-09447-0, Online 978-3-540-35232-7
B.T. Polyak Methods for solving constrained extremum problems in the presence of random noise, USSR Computational Mathematics and Mathematical Physics, 1979, 19(1), pp. 72-81. (Translated from: Zh. vȳchisl. Mat. mat. Fiz., 19, 1, 70-78, 1979) DOI: 10.1016/0041-5553(79)90067-3, URL: http://www.sciencedirect.com/science/article/pii/0041555379900673, this work in Russian
Abstract: The extremum problem with equation-type constraints is considered, when the measurements of all functions and their gradients are subject to noise. Three methods of solution are described: they are modifications of the method of Lagrange multipliers, the method of penalty functions, and the method of penalty estimates respectively. The methods are shown to be convergent in a specific probability sense.
B.T. Polyak, Ya.Z. Tsypkin Adaptive Estimation Algorithms (Convergence, Optimality, Stability), Automation and Remote Control, 1979, 40(3, part 1), pp. 378-389. (Translated from Avtomatika i Telemekhanika, No. 3, pp. 71-84, April, 1979) this work in Russian
Abstract: Adaptive estimation algorithms for the computation of recursive estimates in a standard regression problem are considered. The convergence of these algorithms is proved and the rate of convergence is investigated. A method is indicated for determining the nonlinear transformation of mismatch and choice of the gain matrix in an adaptive algorithm which ensure its asymptotic optimality. Such an asymptotically optimal algorithm corresponds to the recursive version of the method of maximum likelihood. With incomplete a priori information about noise, asymptotically optimal, in the minimal sense, algorithms are found and the connection with stable (robust) estimation is shown.
B.T. Poljak Subgradient Methods: A Survey of Soviet Research, Pergamon Press, 1978. In Nonsmooth Optimization, volume 3, C. Lemarechal, R. Mifflin (Ed.), pp. 5-29. (Proceedings of a IIASA Workshop, March 28 - April 8, 1977) URL: http://webarchive.iiasa.ac.at/Admin/PUB/Documents/XB-78-504.pdf, ISBN: 0 08 023428 3
B.T. Poljak Nonlinear programming methods in the presence of noise, Mathematical Programming, Series B, 1978, 14(1), pp. 87-97. DOI: 10.1007/BF01588952, URL: http://link.springer.com/article/10.1007/BF01588952
Abstract: The problem of minimizing a nonlinear function with nonlinear constraints when the values of the objective, the constraints and their gradients have errors, is studied. This noise may be due to the stochastic nature of the problem or to numerical error. Various previously proposed methods are reviewed. Generally, the minimization algorithms involve methods of subgradient optimization, with the constraints introduced through penalty, Lagrange, or extended Lagrange functions. Probabilistic convergence theorems are obtained. Finally, an algorithm to solve the general convex (nondifferentiable) programming problem with noise is proposed.
B.T. Polyak Minimization of composite regression functions, Cybernetics, 1978, 14(4), pp. 642-644. (Translated from Kibernetika, No. 4, pp. 148-149, July-August, 1978) DOI: 10.1007/bf01069853, URL: http://dx.doi.org/10.1007/BF01069853, this work in Russian
Abstract: In the theory of learning systems with complex objectives of learning [1], and also in reducing stochastic problems of mathematical programming to problems of unconstrained minimization with the aid of the method of penalty functions [2], it is often necessary to minimize functions that are nonlinearly dependent on regression functions. A method of solution of such problems of minimization has been proposed in [1], and its proof for the convex case can be found in [2-5]. Below we shall describe the case of nonconvex functions.
B.T. Poliak On the Comparison of Gradient Method and Random Search Method, Automatic Control and Computer Sciences, 1977, 11(3), pp. 59-62. (Translated from: Poljak B.T. Concerning the comparison of gradient method and random search method, Avtomatika i vych. tekhnika, 1977, No. 3, 194-197) this work in Russian
B.T. Polyak Comparison of the Convergence Rate for Single-Step and Multi-Step Optimization Algorithms in the Presence of Noise, Engineering Cybernetics, 1977, 15(1), pp. 6-10. (Translated from Izvestia AN USSR, Tekhnicheskay Kibernetika, 1977, No. 1, pp. 9-12) this work in Russian
B.T. Polyak Convergence and Convergence Rate of Iterative Stochastic Algorithms. II. The Linear Case, Automation and Remote Control, 1977, 38(4, part 2), pp. 537-542. (Translated from Avtomatika i Telemekhanika, No. 4, pp. 101-107, April, 1977) this work in Russian
Abstract: Iterative stochastic algorithms are examined in which the deterministic component is linear. Estimates are given of the matrix of the process' second-order moments for various methods of choosing the step length. The general results are applied to the investigation of the gradient method of minimizlng a quadratic function in the presence of noise.
B.T. Polyak Minimization methods with constraints, Journal of Soviet Mathematics, 1976, 5(1), pp. 97-128. (Translated from Itogi Nauki i Tekhniki (Matematicheskii Analiz), Vol. 12, Part 1, pp. 147-197, 1974) DOI: 10.1007/bf01091662, URL: http://dx.doi.org/10.1007/BF01091662, this work in Russian
Abstract: The present survey deals with numerical methods of solving extremum problems with constraints, i.e., mathematical programming problems. The survey encompasses the period beginning with the discovery of the theory of the theory of mathematical programming (early 1950's) to the present day.
B.T. Polyak Convergence and Convergence Rate of Iterative Stochastic Algorithms. I. General case, Automation and Remote Control, 1976, 37(12, part 1), pp. 1858-1868. (Translated from Avtomatika i Telemekhanika, No. 12, pp. 83-94, December, 1976) this work in Russian
Abstract: We examine iterative stochastic algorithms applicable in extremal regulation, statistics, in solving problems of optimization, adaptation, learning, and image recognition. In terms of Lyapunov functions we formulate general results on convergence in some probabilistic sense or other (in the mean, almost surely, with probability $1 - \delta$). We have obtained estimates of convergence rate.
A.B. Bakushinskii, B.T. Poljak On the Solution of Variational Inequalities, Soviet Mathematics-Doklady, 1974, 15(6), pp. 1705-1710. (Translated by M. Lopez-Morillas from: Doklady Akademii Nauk USSR, 1974, Vol. 219, No. 5, pp. 1038-1041) this work in Russian
B.T. Poljak, N.V. Tretjakov On an Iterative Method for Linear Programming and Its Economical Interpretations, Matekon, 1974, 10(3), pp. 81-100. (Translation from Russian in Economics and Mathematical Methods, 1972, Vol. 8, No. 5, 740-751) this work in Russian
B.T. Polyak, N.V. Tret'yakov The method of penalty estimates for conditional extremum problems, USSR Computational Mathematics and Mathematical Physics, 1974, 13(1), pp. 42-58. (Translated from: Zh. vȳchisl. Mat. mat. Fiz., 13, 1, 34-46, 1973) DOI: 10.1016/0041-5553(74)90004-4, URL: http://www.sciencedirect.com/science/article/pii/0041555374900044, this work in Russian
Abstract: We consider a method of solving problems on extrema with constraints of the equality type, at each step of which a Lagrange function modified by the addition of a penalty function is minimized. It is proved that this method converges locally at the rate of a geometrical progression whose denominator is smaller, the greater the penalty coefficient.
J.Z. Tsypkin, B.T. Poliak Attainable Accuracy of Adaptive Algorithms, Soviet Physics-Doklady, 1974, 19, pp. 562-563. (Published in Russian in Doklady Akademii Nauk USSR, 1974, Vol. 218, No. 3, pp. 532-535) this work in Russian
B.T. Polyak, Ya.Z. Tsypkin Pseudogradient Adaptation and Training Algorithms, Automation and Remote Control, 1973, 34(3, part 1), pp. 377-397. (Translated from Avtomatika i Telemekhanika, No. 3, pp. 45-68, March, 1973) this work in Russian
Abstract: The authors propose a unified approagh, based on the notion of the pseudogradient, to the analysis of various stochastic algorithms for minimizing functionals. A general theorem regarding convergence is proved; this is used to substantiate stochastic approximation algorithms (regular and search), random-search algorithms, generalized stochastic gradient algorithms, and various particular algorithms for identification and pattern-recognition problems.
B.T. Polyak The convergence rate of the penalty function method, USSR Computational Mathematics and Mathematical Physics, 1971, 11(1), pp. 1-12. (Translated from: Zh. vychisl. Mat. mat. fiz., 11, 1, 3-11, 1971) DOI: 10.1016/0041-5553(71)90094-2, URL: http://www.sciencedirect.com/science/article/pii/0041555371900942, this work in Russian
Abstract: The closeness of the solution of the problem with a penalty to the solution of the original problem is estimated at a conditional minimum. It is shown how to match the accuracy of the discovery of the minimum in the problem with a penalty function with the value of the coefficient of the penalty function.
B.T. Polyak Convergence of methods of feasible directions in extremal problems, USSR Computational Mathematics and Mathematical Physics, 1971, 11(4), pp. 53-70. (Translated from: Zh. vȳchisl. Mat. mat. Fiz., 11, 4, 855-869, 1971) DOI: 10.1016/0041-5553(71)90004-8, URL: http://www.sciencedirect.com/science/article/pii/0041555371900048, this work in Russian
Abstract: General theorems on the convergence conditions of one-step iteration methods for minimization problems with constraints are presented. These theorems are applied for the uniform derivation of both previously known and also new results on the convergence of specific methods.
B.T. Polyak Iterative methods using Lagrange multipliers for solving extremal problems with constraints of the equation type, USSR Computational Mathematics and Mathematical Physics, 1970, 10(5), pp. 42-52. (Translated from: Zh. vȳchisl. Mat. mat. Fiz., 10, 5, 1098-1106, 1970) DOI: 10.1016/0041-5553(70)90036-4, URL: http://www.sciencedirect.com/science/article/pii/0041555370900364, this work in Russian
Abstract: Some methods of minimization under constraints of the equation type will be discussed, in which the iterative process is based both on the initial variables and on dual variables (Lagrange multipliers). In the classification given in [1], these methods are of the duality type. Alternatively, they may be interpreted as iterative methods for finding the stationary (in particular, saddle) points of the Lagrange function. We assume that both the functional to be minimized, and the constraints, are reasonably smooth. In Section 1 we describe the methods, prove their local convergence, and estimate the rate of convergence. In Section 2 we consider the merits and drawbacks of the methods from the computational point of view, and outline a means for selecting the initial approximation.
B.T. Poljak Semicontinuity of integral functionals and existence theorems on extremal problems, Mathematics of the USSR-Sbornik, 1969, 7(1), pp. 59-77. (Translated from: Mat. Sbornik Tom 78 (120) (1969), No. 1) DOI: 10.1070/SM1969v007n01ABEH001078, URL: http://iopscience.iop.org/0025-5734/7/1/A03, this work in Russian
Abstract: In this paper we consider integral functionals of the form $f(x) = \int_G F(x(s), s) ds$ (in p. 2), $f(x, y) = \int_G F(x(s), y(s), s) ds$ (in p. 3), $f(x) = \int_G F(x(s), Dx(s), s)ds$ (in p. 4). We present sufficient (and in some cases also necessary) conditions for their semicontinuity and continuity with respect to various types of convergence (viz. strong and weak in the spaces $L_p, (1 \leq p \leq \infty)$, and $W_p^1 (1 \leq p \leq \infty)$). These results are applied in p. 5 to obtain existence theorems in extremal problems containing such functionals.
B.T. Poljak Correction to the paper Semicontinuity of integral functionals and existence theorems in extremal problems, Mat. Sb. 78 (120) (1969), 65-84, Mathematics of the USSR-Sbornik, 1969, 9(4), pp. 570. (Translated from: Mat. Sbornik Tom 80 (122) (1969), No. 4) DOI: 10.1070/sm1969v009n04abeh003731, URL: http://dx.doi.org/10.1070/SM1969v009n04ABEH003731, this work in Russian
Abstract: This is an Erratum for the article 1969 Math. USSR Sb. Vol. 7, P. 59.
B.T. Polyak Minimization of unsmooth functionals, USSR Computational Mathematics and Mathematical Physics, 1969, 9(3), pp. 14-29. (Translated from: Zh. vȳchisl. Mat. mat. Fiz. 9, 3, 509-521, 1969) DOI: 10.1016/0041-5553(69)90061-5, URL: http://www.sciencedirect.com/science/article/pii/0041555369900615, this work in Russian
Abstract: We consider the minimization of a convex, but but necessarily differentiable, functional in a convex set of Hilbert space. The minimization method amounts to movement along a reference functional. The step length is evaluated here, not assigned; all we require for its evaluation is a knowledge of the minimum value of the functional. Under some natural assumptions, this method proves to be convergent both for smooth and non-differentiable functionals, at the rate of a geometric progression. We show how the method may be modified if the minimum of the functional is unknown. We also consider another minimization method, whereby the convergence rate can be increased considerably; this is based on approximation of the functional close to its minimum by a piecewise linear functional. Finally, we quote examples of problems to which our methods are applicable, and examine the computational aspects of the methods.
B.T. Polyak The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 1969, 9(4), pp. 94-112. (Translated from: Zh. vȳchisl. Mat. mat. Fiz., 9, 4, 807-821, 1969) DOI: 10.1016/0041-5553(69)90035-4, URL: http://www.sciencedirect.com/science/article/pii/0041555369900354, this work in Russian
Abstract: The conjugate gradient method was first described in [1, 2] for solving sets of linear algebraic equations. The method, being iterative in form, has all the merits of iterative methods, and enables a set of linear equations to be solved (or what amounts to the same thing, the minimum of a quadratic functional in finite-dimensional space to be found) after a finite number of steps. The method was later extended to the case of Hilbert space [3-5], and to the case of non-quadratic functionals [6, 7]. The present paper proves the convergence of the method as applied to non-quadratic functionals, describes its extension to constrained problems, considers means for further accelerating the convergence, and describes experience in the practical application of the method for solving a variety of extremal problems.
L.G. Gubin, B.T. Polyak, E.V. Raik The method of projections for finding the common point of convex sets, USSR Computational Mathematics and Mathematical Physics, 1967, 7(6), pp. 1-24. (Translated from: Zh. vȳchisl. Mat. mat. Fiz. 7, 6, 1211-1228, 1967) DOI: 10.1016/0041-5553(67)90113-9, URL: http://www.sciencedirect.com/science/article/pii/0041555367901139, this work in Russian
Abstract: Many mathematical and applied problems can be reduced to finding some common point of a system (finite or infinite) of convex sets. Usually each of the sets is such that it is not difficult to find the projection of any point on to this set. In this paper we shall consider various methods of finding points from the intersection of sets, using projection on to a separate set as an elementary operation. The strong convergence of the sequences obtained in this way is proved. Applications are given to various problems, including the problem of best approximation and problems of optimal control. Particular attention is paid in the latter case to problems with restrictions on the phase coordinates.
B.T. Poljak A General Method of Solving Extremum Problems, Soviet Mathematics-Doklady, 1967, 8(3), pp. 593-597. (Translated by P. Flor from: Doklady Akademii Nauk USSR, 1967, Vol. 174, No. 1, pp. 33-36) this work in Russian
B.T. Poljak, Ju.A. Schreider Application of Walsh Polynomials in Approximate Calculation, AMS, 1967. In Nine papers on foundations, measure theory and analysis, volume 57, pp. 171-189. (Translated by R. P. Boas from: B.T. Polyak, Yu. A. Shreider, Application of Walsh Polynomials in Approximate Calculation, Voprosy teorii matematicheskih mashin, Fizmatlit, 1962, 2, 174-190) ISBN: 0821817574, this work in Russian
Abstract: One of the important problems of numerical analysis is to find methods for the approximate representation of functions. The problem arises both when the calculations involve the standard analytic functions (sine, cosine, logarithm, exponential, error funcnion, Bessel functions, etc.) and when we have to approximate or smooth empirical functions.
E.S. Levitin, B.T. Poljak Convergence of Minimizing Sequences in Conditional Extremum Problems, Soviet Mathematics-Doklady, 1966, 7, pp. 764-767. (Translated by C. O. Wilde from: Doklady Akademii Nauk USSR, 1966, Vol. 168, No. 5, pp. 997-1000) this work in Russian
E.S. Levitin, B.T. Polyak Constrained minimization methods, USSR Computational Mathematics and Mathematical Physics, 1966, 6(5), pp. 1-50. (Translated from: Zh. vȳchisl. Mat. mat. Fiz. 6, 5, 787-823, 1966) DOI: 10.1016/0041-5553(66)90114-5, URL: http://www.sciencedirect.com/science/article/pii/0041555366901145, this work in Russian
B.T. Poljak Existence theorems and convergence of minimizing sequences in extremum problems with restrictions, Soviet Mathematics-Doklady, 1966, 7, pp. 72-75. (Translated by L. Ebner from: Doklady Akademii Nauk USSR, 1966, Vol. 166, No. 2, pp. 287-290) this work in Russian
B.T. Polyak Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics, 1964, 4(5), pp. 1-17. (Translated from: Zh. Vych. Mat. 4, No. 5, 791-803, 1964) DOI: 10.1016/0041-5553(64)90137-5, URL: http://www.sciencedirect.com/science/article/pii/0041555364901375, this work in Russian
Abstract: For the solution of the functional equation $P(x) = 0$ (where $P$ is an operator, usually linear, from $B$ into $B$, and $B$ is a Banach space) iteration methods are generally used. These consist of the construction of a series $x^0, \ldots, x^n, \ldots$, which converges to the solution (see, for example [1]). Continuous analogues of these methods are also known, in which a trajectory $x(t), 0 \leq t \leq \infty$ is constructed, which satisfies the ordinary differential equation in B and is such that $x(t)$ approaches the solution of (1) as $t \rightarrow \infty$ (see [2]). We shall call the method a $k$-step method if for the construction of each successive iteration $x^{n+1}$ we use $k$ previous iterations $x^n, \ldots, x^{n-k+1}$. The same term will also be used for continuous methods if $x(t)$ satisfies a differential equation of the $k$-th order or $k$-th degree. Iteration methods which are more widely used are one-step (e.g. methods of successive approximations). They are generally simple from the calculation point of view but often converge very slowly. This is confirmed both by the evaluation of the speed of convergence and by calculation in practice (for more details see below). Therefore the question of the rate of convergence is most important. Some multistep methods, which we shall consider further, which are only slightly more complicated than the corresponding one-step methods, make it possible to speed up the convergence substantially. Note that all the methods mentioned below are applicable also to the problem of minimizing the differentiable functional $f(x)$ in Hilbert space, so long as this problem reduces to the solution of the equation grad $f(x) = 0$.
B.T. Polyak Gradient methods for solving equations and inequalities, USSR Computational Mathematics and Mathematical Physics, 1964, 4(6), pp. 17-32. (Translated from: Zh. Vych. Mat. 4, No. 6, 995-1005, 1964) DOI: 10.1016/0041-5553(64)90079-5, URL: http://www.sciencedirect.com/science/article/pii/0041555364900795, this work in Russian
Abstract: In this paper we consider some iteration methods for solving nonlinear operator equations and linear inequalities. These methods are naturally called gradient methods because they are at the same time methods of minimizing some auxiliary functional which is used as a proof of their convergence.
B.T. Polyak Gradient methods for the minimisation of functionals, USSR Computational Mathematics and Mathematical Physics, 1963, 3(4), pp. 864-878. (Translated from: Zh. Vych. Mat. 3, No. 4, 643-653, 1963) DOI: 10.1016/0041-5553(63)90382-3, URL: http://www.sciencedirect.com/science/article/pii/0041555363903823, this work in Russian
Abstract: Let $f(t)$ be a functional defined in the (real) Hubert space $H$. The problem consists in finding its minimum value $f^* = \inf f(x)$ and some minimum point $x^*$ (if such exists).