In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such … Read more
A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers … Read more
In Riemannian optimization problems, commonly encountered manifolds are $d$-dimensional matrix manifolds whose tangent spaces can be represented by $d$-dimensional linear subspaces of a $w$-dimensional Euclidean space, where $w > d$. Therefore, representing tangent vectors by $w$-dimensional vectors has been commonly used in practice. However, using $w$-dimensional vectors may be the most natural but may not … Read more
We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, … Read more
Distributionally robust optimization (DRO) is widely used, because it offers a way to overcome the conservativeness of robust optimization without requiring the specificity of stochastic optimization. On the computational side, many practical DRO instances can be equivalently (or approximately) formulated as semidefinite programming (SDP) problems via conic duality of the moment problem. However, despite being … Read more
In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. … Read more
In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ($w^p$ with $0
We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer … Read more
In this paper, I view and present the multiobjective discrete optimisation problem as a particular case of disjunctive programming where one seeks to identify efficient solutions from within a disjunction formed by a set of systems. The proposed approach lends itself to a simple yet effective iterative algorithm that is able to yield the set … Read more
A real symmetric matrix M is completely positive semidefinite if it admits a Gram representation by positive semidefinite matrices (of any size d). The smallest such d is called the completely positive semidefinite rank of M, and it is an open question whether there exists an upper bound on this number as a function of … Read more