BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Guoyin Li

Guoyin Li appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCmath.SPMachine Learningmath.COmath.FAmath.NA

Catalog footprint

What is connected

13works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2021arXiv

Kurdyka-Łojasiewicz exponent via inf-projection

Kurdyka-Lojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of $\frac12$ for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. In this paper, we show under mild assumptions that KL exponent is preserved via inf-projection. Inf-projection is a fundamental operation that is ubiquitous when reformulating optimization problems via the lift-and-project approach. By studying its operation on KL exponent, we show that the KL exponent is $\frac12$ for several important convex optimization models, including some semidefinite-programming-representable functions and some functions that involve $C^2$-cone reducible structures, under conditions such as strict complementarity. Our results are applicable to concrete optimization models such as group fused Lasso and overlapping group Lasso. In addition, for nonconvex models, we show that the KL exponent of many difference-of-convex functions can be derived from that of their natural majorant functions, and the KL exponent of the Bregman envelope of a function is the same as that of the function itself. Finally, we estimate the KL exponent of the sum of the least squares function and the indicator function of the set of matrices of rank at most $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Calculating Radius of Robust Feasibility of Uncertain Linear Conic Programs via Semidefinite Programs

The radius of robust feasibility provides a numerical value for the largest possible uncertainty set that guarantees robust feasibility of an uncertain linear conic program. This determines when the robust feasible set is non-empty. Otherwise the robust counterpart of an uncertain program is not well-defined as a robust optimization problem. In this paper, we address a key fundamental question of robust optimization: How to compute the radius of robust feasibility of uncertain linear conic programs, including linear programs? We first provide computable lower and upper bounds for the radius of robust feasibility for general uncertain linear conic programs under the commonly used ball uncertainty set. We then provide important classes of linear conic programs where the bounds are calculated by finding the optimal values of related semidefinite linear programs (SDPs), among them uncertain SDPs, uncertain second-order cone programs and uncertain support vector machine problems. In the case of an uncertain linear program, the exact formula allows us to calculate the radius by finding the optimal value of an associated second-order cone program.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs

In this paper, we consider a broad class of nonsmooth and nonconvex fractional programs, where the numerator can be written as the sum of a continuously differentiable convex function whose gradient is Lipschitz continuous and a proper lower semicontinuous (possibly nonconvex) function, and the denominator is weakly convex over the constraint set. This model problem includes the composite optimization problems studied extensively lately, and encompasses many important modern fractional optimization problems arising from diverse areas such as the recently proposed scale invariant sparse signal reconstruction problem in signal processing. We propose a proximal subgradient algorithm with extrapolations for solving this optimization model and show that the iterated sequence generated by the algorithm is bounded and any of its limit points is a stationary point of the model problem. The choice of our extrapolation parameter is flexible and includes the popular extrapolation parameter adopted in the restarted Fast Iterative Shrinking-Threshold Algorithm (FISTA). By providing a unified analysis framework of descent methods, we establish the convergence of the full sequence under the assumption that a suitable merit function satisfies the Kurdyka--Łojasiewicz (KL) property. In particular, our algorithm exhibits linear convergence for the scale invariant sparse signal reconstruction problem and the Rayleigh quotient problem over spherical constraint. In the case where the denominator is the maximum of finitely many continuously differentiable weakly convex functions, we also propose an enhanced extrapolated proximal subgradient algorithm with guaranteed convergence to a stronger notion of stationary points of the model problem. Finally, we illustrate the proposed methods by both analytical and simulated numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finding the maximum eigenvalue of a class of tensors with applications in copositivity test and hypergraphs

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. This paper is devoted to a semi-definite program algorithm for computing the maximum $H$-eigenvalue of a class of tensors with sign structure called $W$-tensors. The class of $W$-tensors extends the well-studied nonnegative tensors and essentially nonnegative tensors, and covers some important tensors arising naturally from spectral hypergraph theory. Our algorithm is based on a new structured sums-of-squares (SOS) decomposition result for a nonnegative homogeneous polynomial induced by a $W$-tensor. This SOS decomposition enables us to show that computing the maximum $H$-eigenvalue of an even order symmetric $W$-tensor is equivalent to solving a semi-definite program, and hence can be accomplished in polynomial time. Numerical examples are given to illustrate that the proposed algorithm can be used to find maximum $H$-eigenvalue of an even order symmetric $W$-tensor with dimension up to $10,000$. We present two applications for our proposed algorithm: we first provide a polynomial time algorithm for computing the maximum $H$-eigenvalues of large size Laplacian tensors of hyper-stars and hyper-trees; second, we show that the proposed SOS algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended $Z$-tensors, whose order may be even or odd. Numerical experiments illustrate that our structured semi-definite program algorithm is effective and promising.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Classes of Positive Semi-Definite Hankel Tensors

A Hankel tensor is called a strong Hankel tensor if the Hankel matrix generated by its generating vector is positive semi-definite. It is known that an even order strong Hankel tensor is a sum-of-squares tensor, and thus a positive semi-definite tensor. The SOS decomposition of strong Hankel tensors has been well-studied by Ding, Qi and Wei \cite{DQW1}. On the other hand, very little is known for positive semi-definite Hankel tensors which are not strong Hankel tensors. In this paper, we study some classes of positive semi-definite Hankel tensors which are not strong Hankel tensors. These include truncated Hankel tensors and quasi-truncated Hankel tensors. Then we show that a strong Hankel tensor generated by an absoluate integrable function is always completely decomposable, and give a class of SOS Hankel tensors which are not completely decomposable.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems

We adapt the Douglas-Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method to minimize the sum of a proper closed function $g$ and a smooth function $f$ with a Lipschitz continuous gradient, we show that if the step-size parameter is smaller than a computable threshold and the sequence generated has a cluster point, then it gives a stationary point of the optimization problem. Convergence of the whole sequence and a local convergence rate are also established under the additional assumption that $f$ and $g$ are semi-algebraic. We also give simple sufficient conditions guaranteeing the boundedness of the sequence generated. We then apply our nonconvex DR splitting method to finding a point in the intersection of a closed convex set $C$ and a general closed set $D$ by minimizing the squared distance to $C$ subject to $D$. We show that if either set is bounded and the step-size parameter is smaller than a computable threshold, then the sequence generated from the DR splitting method is actually bounded. Consequently, the sequence generated will have cluster points that are stationary for an optimization problem, and the whole sequence is convergent under an additional assumption that $C$ and $D$ are semi-algebraic. We achieve these results based on a new merit function constructed particularly for the DR splitting method. Our preliminary numerical results indicate that our DR splitting method usually outperforms the alternating projection method in finding a sparse solution of a linear system, in terms of both the solution quality and the number of iterations taken.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Further Results on Cauchy Tensors and Hankel Tensors

In this article, we present various new results on Cauchy tensors and Hankel tensors. { We first introduce the concept of generalized Cauchy tensors which extends Cauchy tensors in the current literature, and provide several conditions characterizing positive semi-definiteness of generalized Cauchy tensors with nonzero entries.} As a consequence, we show that Cauchy tensors are positive semi-definite if and only if they are SOS (Sum-of-squares) tensors.} Furthermore, we prove that all positive semi-definite Cauchy tensors are completely positive tensors, which means every positive semi-definite Cauchy tensor can be decomposed { as} the sum of nonnegative rank-1 tensors. We also establish that all the H-eigenvalues of nonnegative Cauchy tensors are nonnegative. Secondly, we present new mathematical properties of Hankel tensors. { We prove that an even order Hankel tensor is Vandermonde positive semi-definite if and only if its associated plane tensor is positive semi-definite. We also show that, if the Vandermonde rank of a Hankel tensor $\mathcal{A}$ is less than the dimension of the underlying space, then positive semi-definiteness of $\mathcal{A}$ is equivalent to the fact that $\mathcal{A}$ is a complete Hankel tensor, and so, is further equivalent to the SOS property of $\mathcal{A}$. Lastly, we introduce a new structured tensor called Cauchy-Hankel tensors, which is a special case of Cauchy tensors and Hankel tensors simultaneously.} Sufficient and necessary conditions are established for an even order Cauchy-Hankel tensor to be positive definite. Final remarks are listed at the end of the paper.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Global convergence of splitting methods for nonconvex composite optimization

We consider the problem of minimizing the sum of a smooth function $h$ with a bounded Hessian, and a nonsmooth function. We assume that the latter function is a composition of a proper closed function $P$ and a surjective linear map $\cal M$, with the proximal mappings of $τP$, $τ> 0$, simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: alternating direction method of multipliers and proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that, if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions $h$ and $P$ are semi-algebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the $\ell_{1/2}$ regularization. Finally, when $\cal M$ is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex $h$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

SOS Tensor Decomposition: Theory and Applications

In this paper, we examine structured tensors which have sum-of-squares (SOS) tensor decomposition, and study the SOS-rank of SOS tensor decomposition. We first show that several classes of even order symmetric structured tensors available in the literature have SOS tensor decomposition. These include positive Cauchy tensors, weakly diagonally dominated tensors, $B_0$-tensors, double $B$-tensors, quasi-double $B_0$-tensors, $MB_0$-tensors, $H$-tensors, absolute tensors of positive semi-definite $Z$-tensors and extended $Z$-tensors. We also examine the SOS-rank of SOS tensor decomposition and the SOS-width for SOS tensor cones. The SOS-rank provides the minimal number of squares in the SOS tensor decomposition, and, for a given SOS tensor cone, its SOS-width is the maximum possible SOS-rank for all the tensors in this cone. We first deduce an upper bound for general tensors that have SOS decomposition and the SOS-width for general SOS tensor cone using the known results in the literature of polynomial theory. Then, we provide an explicit sharper estimate for the SOS-rank of SOS tensor decomposition with bounded exponent and identify the SOS-width for the tensor cone consisting of all tensors with bounded exponent that have SOS decompositions. Finally, as applications, we show how the SOS tensor decomposition can be used to compute the minimum $H$-eigenvalue of an even order symmetric extended $Z$-tensor and test the positive definiteness of an associated multivariate form. Numerical experiments are also provided to show the efficiency of the proposed numerical methods ranging from small size to large size numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Tensor Analogy of Yuan's Theorem of the Alternative and Polynomial Optimization with Sign structure

Yuan's theorem of the alternative is an important theoretical tool in optimization, which provides a checkable certificate for the infeasibility of a strict inequality system involving two homogeneous quadratic functions. In this paper, we provide a tractable extension of Yuan's theorem of the alternative to the symmetric tensor setting. As an application, we establish that the optimal value of a class of nonconvex polynomial optimization problems with suitable sign structure (or more explicitly, with essentially non-positive coefficients) can be computed by a related convex conic programming problem, and the optimal solution of these nonconvex polynomial optimization problems can be recovered from the corresponding solution of the convex conic programming problem. Moreover, we obtain that this class of nonconvex polynomial optimization problems enjoy exact sum-of-squares relaxation, and so, can be solved via a single semidefinite programming problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Positive Semi-Definiteness of Generalized Anti-Circulant Tensors

Anti-circulant tensors have applications in exponential data fitting. They are special Hankel tensors. In this paper, we extend the definition of anti-circulant tensors to generalized anti-circulant tensors by introducing a circulant index $r$ such that the entries of the generating vector of a Hankel tensor are circulant with module $r$. In the special case when $r =n$, where $n$ is the dimension of the Hankel tensor, the generalized anticirculant tensor reduces to the anti-circulant tensor. Hence, generalized anti-circulant tensors are still special Hankel tensors. For the cases that $GCD(m, r) =1$, $GCD(m, r) = 2$ and some other cases, including the matrix case that $m=2$, we give necessary and sufficient conditions for positive semi-definiteness of even order generalized anti-circulant tensors, and show that in these cases, they are SOS tensors. This shows that, in these cases, there are no PNS (positive semidefinite tensors which are not sum of squares) Hankel tensors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

SOS-Hankel Tensors: Theory and Application

Hankel tensors arise from signal processing and some other applications. SOS (sum-of-squares) tensors are positive semi-definite symmetric tensors, but not vice versa. The problem for determining an even order symmetric tensor is an SOS tensor or not is equivalent to solving a semi-infinite linear programming problem, which can be done in polynomial time. On the other hand, the problem for determining an even order symmetric tensor is positive semi-definite or not is NP-hard. In this paper, we study SOS-Hankel tensors. Currently, there are two known positive semi-definite Hankel tensor classes: even order complete Hankel tensors and even order strong Hankel tensors. We show complete Hankel tensors are strong Hankel tensors, and even order strong Hankel tensors are SOS-Hankel tensors. We give several examples of positive semi-definite Hankel tensors, which are not strong Hankel tensors. However, all of them are still SOS-Hankel tensors. Does there exist a positive semi-definite non-SOS-Hankel tensor? The answer to this question remains open. If the answer to this question is no, then the problem for determining an even order Hankel tensor is positive semi-definite or not is solvable in polynomial-time. An application of SOS-Hankel tensors to the positive semi-definite tensor completion problem is discussed. We present an ADMM algorithm for solving this problem. Some preliminary numerical results on this algorithm are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Analysis of the convergence rate for the cyclic projection algorithm applied to basic semi-algebraic convex sets

In this paper, we study the rate of convergence of the cyclic projection algorithm applied to finitely many basic semi-algebraic convex sets. We establish an explicit convergence rate estimate which relies on the maximum degree of the polynomials that generate the basic semi-algebraic convex sets and the dimension of the underlying space. We achieve our results by exploiting the algebraic structure of the basic semi-algebraic convex sets.

0 citations0 reviewsNo code linkedOpen access