1,721,028 research outputs found
Finding the stationary states of Markov chains by iterative methods
No full textIn this paper, we develop new methods for approximating dominant eigenvector of column-stochastic matrices. We analyze the Google matrix, and present an averaging scheme with linear rate of convergence in terms of 1-norm distance. For extending this convergence result onto general case, we assume existence of a positive row in the matrix. Our new numerical scheme, the Reduced Power Method (RPM), can be seen as a proper averaging of the power iterates of a reduced stochastic matrix. We analyze also the usual Power Method (PM) and obtain convenient conditions for its linear rate of convergence with respect to 1-norm
Optimal Methods of Convex Programming and Application Thereof
No full textAvailable from VNTIC / VNTIC - Scientific & Technical Information Centre of RussiaSIGLERURussian Federatio
On well-structured convex–concave saddle point problems and variational inequalities with monotone operators
No full textInternational audienceFor those acquainted with CVX (aka disciplined convex programming) of Grant and Boyd (Matlab software for disciplined convex programming, version 2.2, CVX Research, Inc., 2020. http://cvxr.com/cvx/doc/), the motivation of this work is the desire to extend the scope of CVX beyond convex minimization – to convex–concave saddle point problems and variational inequalities with monotone operators. To attain this goal, given a family of cones (e.g. Lorentz, semidefinite, geometric, etc.), we introduce the notions of -conic representation of a convex–concave saddle point problem and of variational inequality with monotone operator. We demonstrate that given such a representation of the problem of interest, the latter can be reduced straightforwardly to a conic problem on a cone from and thus can be solved by (any) solver capable to handle conic problems on cones from (e.g. Mosek or SDPT3 in the case of semidefinite cones). We also show that -representations of convex–concave functions and monotone vector fields admit a fully algorithmic calculus which helps to recognize the cases when a saddle point problem or variational inequality can be converted into a conic problem on a cone from and to carry out such conversion
On complexity of matrix scaling
No full textAbstractLine Sun Scaling problem for a nonnegative matrix A is to find positive definite diagonal matrices Y, Z which result in prescribed row and column sums of the scaled matrix YAZ. The Matrix Balancing problem for a nonnegative square matrix A is to find a positive definite diagonal matrix X such that the row sums in the scaled matrix XAX are equal to the corresponding column sums. We demonstrate that ϵ-versions of both these problems, same as those of other scaling problems for non-negative multiindex arrays, can be reduced to a specific Geometric Programming problem. For the latter problem, we develop a polynomial-time algorithm, thus deriving polynomial time solvability of a number of generic scaling problems for nonnegative multiindex arrays. Our results extend those previously known for the problems of matrix balancing [3] and of double-stochastic scaling of a square nonnegative matrix [2]
The Projective Method for solving linear matrix inequalities
No full textNumerous problems in control and systems theory can be formulated in terms of linear matrix inequalities (LMI). Since solving an LMI amounts to a convex optimization problem, such formulations are known to be numerically tractable. However, the interest in LMI-based design techniques has really surged with the introduction of efficient interior-point methods for solving LMIs with a polynomial-time complexity. This paper describes one particular method called the Projective Method. Simple geometrical arguments are used to clarify the strategy and convergence mechanism of the Projective algorithm. A complexity analysis is provided, and applications to two generic LMI problems (feasibility and linear objective minimization) are discussed.
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Aggregating regular norms
No full textThe subject of this paper is regularity-preserving aggregation of regular norms on finite-dimensional linear spaces. Regular norms were introduced in [5] and are closely related to ``type 2'' spaces [9, Chapter 9] playing important role in 1) high-dimensional convex geometry and probability in Banach spaces [0.this http URL], and in 2) design of proximal first-order algorithms for large-scale convex optimization with dimension-independent, or nearly so, complexity. Regularity, with moderate parameters, of a norm makes applicable, in a dimension-independent fashion, numerous geometric, probabilistic, and optimization-related results, which motivates our interest in aggregating regular norms with controlled (and moderate) inflation of regularity parameters
Theory and applications of first-order methods for convex optimization with function constraints
No full textThis dissertation focuses on the development of efficient first-order methods for function constrained convex optimization and their applications in a few different areas, including healthcare, finance and machine learning. The thesis consists of three major studies.
The first part of the thesis considers the problem of minimizing an expectation function over a closed convex set, coupled with a functional or expectation constraint on either
decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the constraint on devision variables. We show that this algorithm exhibits
the optimal rate of convergence, in terms of both optimality gap and constraint violation, when the objective and constraint functions are generally convex, where denotes the optimality gap and infeasibility. Moreover, we show that
this rate of convergence can be improved to if the objective and constraint functions are strongly convex. We then present a variant of CSA, namely the cooperative stochastic parameter approximation (CSPA) algorithm, to deal with
the situation when the constraint is defined over problem parameters and show that it exhibits similar optimal rate of convergence to CSA. It is worth noting that CSA and CSPA are primal methods which do not require the iterations on the dual space and/or
the estimation on the size of the dual variables. To the best of our knowledge, this is the first time that such optimal SA methods for solving functional or expectation constrained stochastic optimization are presented in the literature. In addition, we apply the CSA and CSPA methods to an asset allocation problem, and a combined classification and metric learning problem, respectively.
The second part of the thesis is devoted to conditional gradient methods which have attracted much attention in both machine learning and optimization communities recently. These simple methods can guarantee the generation of sparse solutions. In addition, without the computation of full gradients, they can handle huge-scale problems sometimes even with an exponentially increasing number of decision variables. This study aims to significantly expand the application areas of these methods by presenting new conditional gradient methods for solving convex optimization problems with general affine and nonlinear constraints. More specifically, we first present a new constraint extrapolated condition gradient (CoexCG) method
that can achieve an iteration complexity for both smooth and structured nonsmooth function constrained convex optimization. We further develop novel variants of CoexCG, namely constraint extrapolated and dual regularized conditional gradient (CoexDurCG) methods, that can achieve similar iteration complexity to CoexCG but allow adaptive selection for algorithmic parameters. We illustrate the effectiveness of these methods for solving an important class of radiation therapy treatment planning problems arising from healthcare industry.
In the third part of the thesis, we extend the convex function constrained optimization to the multi-stage setting, i.e., multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal rate of convergence in terms of the total number of required scenarios when applied to a three-stage stochastic optimization problem.
We further show that this rate of convergence can be improved to when the objective function is strongly convex. We also discuss variants of DSA for solving more general multi-stage stochastic optimization problems with the number of stages . The developed DSA algorithms only need to go through the scenario tree once in order to compute an -solution of the multi-stage stochastic optimization problem. As a result, the memory required by DSA only grows linearly with respect to the number of stages. To the best of our knowledge, this is the first time that stochastic approximation type methods are generalized for multi-stage stochastic optimization with T \gep 3. We apply the DSA method for solving a class of multi-stage asset allocation problem and demonstrate its potential advantages over existing methods, especially when the planning horizon is relatively short but the number of assets is large.Ph.D
- …
