Optimization and Its Applications in Control and Data Sciences

An adaptive conjugate gradient algorithm is presented. The search direction is computed as the sum of the negative gradient and a vector determined by minimizing the quadratic approximation of objective function at the current point. Using a special approximation of the inverse Hessian of the objective function, which depends by a positive parameter, we get the search direction which satisfies both the sufficient descent condition and the Dai-Liao’s conjugacy condition. The parameter in the search direction is determined in an adaptive manner by clustering the eigenvalues of the matrix defining it. The global convergence of the algorithm is proved for uniformly convex functions. Using a set of 800 unconstrained optimization test problems we prove that our algorithm is significantly more efficient and more robust than CG-DESCENT algorithm. By solving five applications from the MINPACK-2 test problem collection, with 10⁶ variables, we show that the suggested adaptive conjugate gradient algorithm is top performer versus CG-DESCENT.

A dynamic model of terminal control with boundary value problems in the form of convex programming is considered. The solutions to these finite-dimensional problems define implicitly initial and terminal conditions at the ends of time interval at which the controlled dynamics develops. The model describes a real situation when an object needs to be transferred from one state to another. Based on the Lagrange formalism, the model is considered as a saddle-point controlled dynamical problem formulated in a Hilbert space. Iterative saddle-point method has been proposed for solving it. We prove the convergence of the method to saddle-point solution in all its components: weak convergence—in controls, strong convergence—in phase and conjugate trajectories, and terminal variables.

The paper proposes two new approaches to designing efficient mathematical tools for quantitatively analyzing decision-making processes that small and medium price-taking traders undergo in forming and managing their portfolios of financial instruments traded in a stock exchange. Two mathematical models underlying these approaches are considered. If the trader can treat price changes for each financial instrument of her interest as those of a random variable with a known (for instance, a uniform) probability distribution, one of these models allows the trader to formulate the problem of finding an optimal composition of her portfolio as an integer programming problem. The other model is suggested to use when the trader does not possess any particular information on the probability distribution of the above-mentioned random variable for financial instruments of her interest while being capable of estimating the areas to which the prices of groups of financial instruments (being components of finite-dimensional vectors for each group) are likely to belong. When each such area is a convex polyhedron described by a finite set of compatible linear equations and inequalities of a balance kind, the use of this model allows one to view the trader’s decision on her portfolio composition as that of a player in an antagonistic game on sets of disjoint player strategies. The payoff function of this game is a sum of a linear and a bilinear function of two vector arguments, and the trader’s guaranteed financial result in playing against the stock exchange equals the exact value of the maximin of this function. This value, along with the vectors at which it is attained, can be found by solving a mixed programming problem. Finding an upper bound for this maximin value (and the vectors at which this upper bound is attained) is reducible to finding saddle points in an auxiliary antagonistic game with the same payoff function on convex polyhedra of disjoint player strategies. These saddle points can be calculated by solving linear programming problems forming a dual pair.

We study maximum likelihood estimators (henceforth MLE) in experiments consisting of two stages, where the first-stage sample is unknown to us, but the second-stage samples are known and depend on the first-stage sample. The setup is similar to that in parametric empirical Bayes models, and arises naturally in numerous applications. However, problems arise when the number of second-level observations is not the same for all first-stage observations. As far as we know, this situation has been discussed in very few cases (see Brandel, Empirical Bayes methods for missing data analysis. Technical Report 2004:11, Department of Mathematics, Uppsala University, Sweden, 2004 and Carlin and Louis, Bayes and Empirical Bayes Methods for Data Analysis, 2nd edn. Chapman & Hall, Boca Raton, 2000) and no analytic expression for the indirect maximum likelihood estimator was derived there. The novelty of our paper is that it details and exemplifies this point. Specifically, we study in detail two situations:

In both cases we discuss the intuitive meaning of our estimator, its properties, and show its advantages vis-\(\grave{\mathrm{a}}\)-vis other natural estimators.

Pose Graph Optimization (PGO) is the problem of estimating a set of poses from pairwise relative measurements. PGO is a nonconvex problem, and currently no known technique can guarantee the efficient computation of a global optimal solution. In this paper, we show that Lagrangian duality allows computing a globally optimal solution, under certain conditions that are satisfied in many practical cases. Our first contribution is to frame the PGO problem in the complex domain. This makes analysis easier and allows drawing connections with the recent literature on unit gain graphs. Exploiting this connection we prove nontrival results about the spectrum of the matrix underlying the problem. The second contribution is to formulate and analyze the properties of the Lagrangian dual problem in the complex domain. The dual problem is a semidefinite program (SDP). Our analysis shows that the duality gap is connected to the number of eigenvalues of the penalized pose graph matrix, which arises from the solution of the SDP. We prove that if this matrix has a single eigenvalue in zero, then (1) the duality gap is zero, (2) the primal PGO problem has a unique solution, and (3) the primal solution can be computed by scaling an eigenvector of the penalized pose graph matrix. The third contribution is algorithmic: we exploit the dual problem and propose an algorithm that computes a guaranteed optimal solution for PGO when the penalized pose graph matrix satisfies the Single Zero Eigenvalue Property (SZEP). We also propose a variant that deals with the case in which the SZEP is not satisfied. This variant, while possibly suboptimal, provides a very good estimate for PGO in practice. The fourth contribution is a numerical analysis. Empirical evidence shows that in the vast majority of cases (100 % of the tests under noise regimes of practical robotics applications) the penalized pose graph matrix does satisfy the SZEP, hence our approach allows computing the global optimal solution. Finally, we report simple counterexamples in which the duality gap is nonzero, and discuss open problems.

This chapter deals with positive linear systems in continuous-time affected by a switching signal representing a disturbance driven by a Markov chain. A state-feedback control law has to be designed in order to ensure mean stability and input–output \(\mathcal{L}_{\infty }\)-induced or \(\mathcal{L}_{1}\)-induced mean performance. The chapter is divided into two parts. In the first, the control action is based on the knowledge of both the state of the system and the sample path of the Markovian process (mode-dependent control). In the second, instead, only the state-variable is known (mode-independent control). In the mode-dependent case, as well as in the single-input mode-independent case, necessary and sufficient conditions for the existence of feasible feedback gains are provided based on linear programming tools, also yielding a full parametrization of feasible solutions. In the multi-input mode-independent case, sufficient conditions are worked out in terms of convex programming. Some numerical examples illustrate the theory.

We introduce a convex optimization modeling framework that transforms a convex optimization problem expressed in a form natural and convenient for the user into an equivalent cone program in a way that preserves fast linear transforms in the original problem. By representing linear functions in the transformation process not as matrices, but as graphs that encode composition of linear operators, we arrive at a matrix-free cone program, i.e., one whose data matrix is represented by a linear operator and its adjoint. This cone program can then be solved by a matrix-free cone solver. By combining the matrix-free modeling framework and cone solver, we obtain a general method for efficiently solving convex optimization problems involving fast linear transforms.

This is a survey of some recent results on the rational circulant covariance extension problem: Given a partial sequence (c ₀, c ₁, …, c _n ) of covariance lags \(c_{k} = \mathbb{E}\{y(t + k)\overline{y(t)}\}\) emanating from a stationary periodic process {y(t)} with period 2N > 2n, find all possible rational spectral functions of {y(t)} of degree at most 2n or, equivalently, all bilateral and unilateral ARMA models of order at most n, having this partial covariance sequence. Each representation is obtained as the solution of a pair of dual convex optimization problems. This theory is then reformulated in terms of circulant matrices and the connections to reciprocal processes and the covariance selection problem is explained. Next it is shown how the theory can be extended to the multivariate case. Finally, an application to image processing is presented.

We propose a new iterative two-step proximal algorithm for solving the problem of equilibrium programming in a Hilbert space. This method is a result of extension of L.D. Popov’s modification of Arrow-Hurwicz scheme for approximation of saddle points of convex-concave functions. The convergence of the algorithm is proved under the assumption that the solution exists and the bifunction is pseudo-monotone and Lipschitz-type.

One of the main problems of stochastic control theory is the estimation of attainability sets, or information sets. The most popular and natural approximations of such sets are ellipsoids. B.T. Polyak and his disciples use two kinds of ellipsoids covering a set of points—minimal volume ellipsoids and minimal trace ellipsoids. We propose a way to construct an ellipsoidal approximation of an attainability set using nonparametric estimations. These ellipsoids can be considered as an approximation of minimal volume ellipsoids and minimal trace ellipsoids. Their significance level depends only on the number of points and only one point from the set lays on a bound of such ellipsoid. This unique feature allows to construct a statistical depth function, rank multivariate samples and identify extreme points. Such ellipsoids in combination with traditional methods of estimation allow to increase accuracy of outer ellipsoidal approximations and estimate the probability of attaining a target set of states.

This chapter explores some important characteristics of algebraic linear systems containing interval parameters. Applying the Cramer’s rule, a parametrized solution of a linear system can be expressed as the ratio of two determinants. We show that these determinants can be expanded as multivariate polynomial functions of the parameters. In many practical problems, the parameters in the system characteristic matrix appear with rank one, resulting in a rational multilinear form for the parametrized solutions. These rational multilinear functions are monotonic with respect to each parameter. This monotonic characteristic plays an important role in the analysis and design of algebraic linear interval systems in which the parameters appear with rank one. In particular, the extremal values of the parametrized solutions over the box of interval parameters occur at the vertices of the box.

This paper presents a fuzzy proportional membership model for clustering (FCPM). Unlike the other clustering models, FCPM requires that each entity may express an extent of each prototype, which makes its criterion to loose the conventional prototype-additive structure. The methods for fitting the model at different fuzziness parameter values are presented. Because of the complexity of the clustering criterion, minimization of the errors requires the gradient projection method (GPM). We discuss how to find the projection of a vector on the simplex of the fuzzy membership vectors and how the stepsize length of the GPM had been fixed. The properties of the clusters found with the FCPM are discussed. Especially appealing seems the property to keep the extremal cluster prototypes stable even after addition of many entities around the grand mean.

In analogy to extremal principles in physics, we introduce the Principle of Least Revenue for treating market equilibria. It postulates that equilibrium prices minimize the total excessive revenue of market’s participants. As a consequence, the necessary optimality conditions describe the clearance of markets, i.e. at equilibrium prices supply meets demand. It is crucial for our approach that the potential function of total excessive revenue be convex. This facilitates structural and algorithmic analysis of market equilibria by using convex optimization techniques. In particular, results on existence, uniqueness, and efficiency of market equilibria follow easily. The market decentralization fits into our approach by the introduction of trades or auctions. For that, Duality Theory of convex optimization applies. The computability of market equilibria is ensured by applying quasi-monotone subgradient methods for minimizing nonsmooth convex objective—total excessive revenue of the market’s participants. We give an explicit implementable algorithm for finding market equilibria which corresponds to real-life activities of market’s participants.

The Legendre transform (LET) is a product of a general duality principle: any smooth curve is, on the one hand, a locus of pairs, which satisfy the given equation and, on the other hand, an envelope of a family of its tangent lines.

An application of the LET to a strictly convex and smooth function leads to the Legendre identity (LEID). For strictly convex and three times differentiable function the LET leads to the Legendre invariant (LEINV).

Although the LET has been known for more then 200 years both the LEID and the LEINV are critical in modern optimization theory and methods.

The purpose of the paper is to show the role of the LEID and the LEINV play in both constrained and unconstrained optimization.