Convergence and Convergence Rate of Stochastic Gradient Search in the Case of Multiple and Non-Isolated Extrema

Categories Control Applications, Stochastic Programming Tags , , , , ,

The asymptotic behavior of stochastic gradient algorithms is studied. Relying on some results of differential geometry (Lojasiewicz gradient inequality), the almost sure point-convergence is demonstrated and relatively tight almost sure bounds on the convergence rate are derived. In sharp contrast to all existing result of this kind, the asymptotic results obtained here do not require … Read more

A Combined Class of Self-Scaling and Modified Quasi-Newton Methods

Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

Techniques for obtaining safely positive definite Hessian approximations with self-scaling and modified quasi-Newton updates are combined to obtain `better’ curvature approximations in line search methods for unconstrained optimization. It is shown that this class of methods, like the BFGS method has global and superlinear convergence for convex functions. Numerical experiments with this class, using the … Read more

On the global convergence of interior-point nonlinear programming algorithms

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

Carathéodory’s lemma states that if we have a linear combination of vectors in R^n, we can rewrite this combination using a linearly independent subset. This result has been successfully applied in nonlinear optimization in many contexts. In this work we present a new version of this celebrated theorem, in which we obtained new bounds for … Read more

About Stationarity and Regularity in Variational Analysis

Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

Stationarity and regularity concepts for the three typical for variational analysis classes of objects — real-valued functions, collections of sets, and multifunctions — are investigated. An attempt is maid to present a classification scheme for such concepts and to show that properties introduced for objects from different classes can be treated in a similar way. … Read more

Nonlinear Integer Programming

Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags

Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic.  The primary goal is … Read more

On Cone of Nonsymmetric Positive Semidefinite Matrices

Categories Linear, Cone and Semidefinite Programming, Other Topics Tags , , , , ,

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of $P_0$-matrix cone which is … Read more

Trace Norm Regularization: Reformulations, Algorithms, and Multi-task Learning

Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , , , , ,

We consider a recently proposed optimization formulation of multi-task learning based on trace norm regularized least squares. While this problem may be formulated as a semidefinite program (SDP), its size is beyond general SDP solvers. Previous solution approaches apply proximal gradient methods to solve the primal problem. We derive new primal and dual reformulations of … Read more

On sequential optimality conditions for smooth constrained optimization

Categories Nonlinear Optimization Tags , , ,

Sequential optimality conditions provide adequate theoretical tools to justify stopping criteria for nonlinear programming solvers. Approximate KKT and Approximate Gradient Projection conditions are analyzed in this work. These conditions are not necessarily equivalent. Implications between different conditions and counter-examples will be shown. Algorithmic consequences will be discussed. ArticleDownload View PDF

A Hierarchy of Near-Optimal Policies for Multi-stage Adaptive Optimization

Categories Robust Optimization, Semi-definite Programming, Supply Chain Management Tags , , ,

In this paper, we propose a new tractable framework for dealing with multi-stage decision problems affected by uncertainty, applicable to robust optimization and stochastic programming. We introduce a hierarchy of polynomial disturbance-feedback control policies, and show how these can be computed by solving a single semidefinite programming problem. The approach yields a hierarchy parameterized by … Read more

A Branch-and-Cut-and-Price Algorithm for Vertex-Biconnectivity Augmentation

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Telecommunications

In this paper, the first approach for solving the vertex-biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge-weighted graph, we search for the cheapest subset of edges to augment this subgraph in order to make it vertex-biconnected. The problem is reduced to the augmentation of the corresponding block-cut tree, … Read more