We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a(probably nonconvex)smooth function and a(probably nonsmooth)convex functi...We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a(probably nonconvex)smooth function and a(probably nonsmooth)convex function.The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions.Therefore,the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods.When the accuracy of the model function at the solution of the subproblem is not sufficient,we add a safeguard on the stepsizes for improving the accuracy.For a class of functions that can be“truncated”,an additional truncation step is defined and a stepsize modification strategy is designed.The overall scheme converges globally and we establish fast local convergence under suitable assumptions.In particular,using a connection with a smooth Riemannian trust-region method,we prove local quadratic convergence for partly smooth functions under a strict complementary condition.Preliminary numerical results on a family of Ei-optimization problems are reported and demonstrate the eficiency of our approach.展开更多
In the past several centuries,there have been two major different paradigms for doing scientific research:the Keplerian paradigm and the Newtonian paradigm.In the Keplerian paradigm,natural laws are discovered through...In the past several centuries,there have been two major different paradigms for doing scientific research:the Keplerian paradigm and the Newtonian paradigm.In the Keplerian paradigm,natural laws are discovered through the analysis of data while in the Newtonian paradigm,one focuses on pursuing fundamental principles that govern Nature.展开更多
This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matri...This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where non- negativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on tile classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspeetral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.展开更多
In this work,we present probabilistic local convergence results for a stochastic semismooth Newton method for a class of stochastic composite optimization problems involving the sum of smooth nonconvex and nonsmooth c...In this work,we present probabilistic local convergence results for a stochastic semismooth Newton method for a class of stochastic composite optimization problems involving the sum of smooth nonconvex and nonsmooth convex terms in the objective function.We assume that the gradient and Hessian information of the smooth part of the objective function can only be approximated and accessed via calling stochastic firstand second-order oracles.The approach combines stochastic semismooth Newton steps,stochastic proximal gradient steps and a globalization strategy based on growth conditions.We present tail bounds and matrix concentration inequalities for the stochastic oracles that can be utilized to control the approximation errors via appropriately adjusting or increasing the sampling rates.Under standard local assumptions,we prove that the proposed algorithm locally turns into a pure stochastic semismooth Newton method and converges r-linearly or r-superlinearly with high probability.展开更多
In this paper,we study a few challenging theoretical and numerical issues on the well known trust region policy optimization for deep reinforcement learning.The goal is to find a policy that maximizes the total expect...In this paper,we study a few challenging theoretical and numerical issues on the well known trust region policy optimization for deep reinforcement learning.The goal is to find a policy that maximizes the total expected reward when the agent acts according to the policy.The trust region subproblem is constructed with a surrogate function coherent to the total expected reward and a general distance constraint around the latest policy.We solve the subproblem using a preconditioned stochastic gradient method with a line search scheme to ensure that each step promotes the model function and stays in the trust region.To overcome the bias caused by sampling to the function estimations under the random settings,we add the empirical standard deviation of the total expected reward to the predicted increase in a ratio in order to update the trust region radius and decide whether the trial point is accepted.Moreover,for a Gaussian policy which is commonly used for continuous action space,the maximization with respect to the mean and covariance is performed separately to control the entropy loss.Our theoretical analysis shows that the deterministic version of the proposed algorithm tends to generate a monotonic improvement of the total expected reward and the global convergence is guaranteed under moderate assumptions.Comparisons with the state-of-the–art methods demonstrate the effectiveness and robustness of our method over robotic controls and game playings from OpenAI Gym.展开更多
Most iterative algorithms for eigenpair computation consist of two main steps:a subspace update(SU)step that generates bases for approximate eigenspaces,followed by a Rayleigh-Ritz(RR)projection step that extracts app...Most iterative algorithms for eigenpair computation consist of two main steps:a subspace update(SU)step that generates bases for approximate eigenspaces,followed by a Rayleigh-Ritz(RR)projection step that extracts approximate eigenpairs.So far the predominant methodology for the SU step is based on Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner.In this work,we investigate block methods in the SU step that allow a higher level of concurrency than what is reachable by Krylov subspace methods.To achieve a competitive speed,we propose an augmented Rayleigh-Ritz(ARR)procedure.Combining this ARR procedure with a set of polynomial accelerators,as well as utilizing a few other techniques such as continuation and deflation,we construet a block algorithm designed to reduce the number of RR steps and elevate concurrency in the SU steps.Extensive computational experiments are conducted in C on a representative set of test problems to evaluate the performance of two variants of our algorithm.Numerical results,obtained on a many-core computer without explicit code parallelization,show that when computing a relatively large number of eigenpairs,the performance of our algorithms is competitive with that of several state-of-the-art eigensolvers.展开更多
A new two-level subspace method is proposed for solving the general unconstrained minimization formulations discretized from infinite-dimensional optimization problems. At each iteration, the algorithm executes either...A new two-level subspace method is proposed for solving the general unconstrained minimization formulations discretized from infinite-dimensional optimization problems. At each iteration, the algorithm executes either a direct step on the current level or a coarse subspace correction step. In the coarse subspace correction step, we augment the traditional coarse grid space by a two-dimensional subspace spanned by the coordinate direction and the gradient direction at the current point. Global convergence is proved and convergence rate is studied under some mild conditions on the discretized functions. Preliminary numerical experiments on a few variational problems show that our two-level subspace method is promising.展开更多
In this paper, we consider two different formulations (one is smooth and the other one is nonsmooth) for solving linear matrix inequalities (LMIs), an important class of semidefinite programming (SDP), under a c...In this paper, we consider two different formulations (one is smooth and the other one is nonsmooth) for solving linear matrix inequalities (LMIs), an important class of semidefinite programming (SDP), under a certain Slater constraint qualification assumption. We then propose two first-order methods, one based on subgradient method and the other based on Nesterov's optimal method, and show that they converge linearly for solving these formulations. Moreover, we introduce an accelerated prox-level method which converges linearly uniformly for both smooth and non-smooth problems without requiring the input of any problem parameters. Finally, we consider a special case of LMIs, i.e., linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a much weaker assumption.展开更多
In this paper, we propose an extended Levenberg-Marquardt (ELM) framework that generalizes the classic Levenberg-Marquardt (LM) method to solve the unconstrained minimization problem min ρ(r(x)), where r : R...In this paper, we propose an extended Levenberg-Marquardt (ELM) framework that generalizes the classic Levenberg-Marquardt (LM) method to solve the unconstrained minimization problem min ρ(r(x)), where r : Rn→ Rm and ρ : Rm → R. We also develop a few inexact variants which generalize ELM to the cases where the inner subproblem is not solved exactly and the Jaeobian is simplified, or perturbed. Global convergence and local superlinear convergence are established under certain suitable conditions. Numerical results show that our methods are promising.展开更多
In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem unde...In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem under path cardinality constraints.Specifically,such a problem formulation captures various types of objectives including proportional fairness,average delay,as well as load balancing.In addition,in order to handle the"unsplittable flows",path cardinality constraints are added,making the resulting optimization problem quite challenging to solve due to intrinsic nonsmoothness and nonconvexity.Almost all existing works deal with such a problem using relaxation techniques to transform it into a convex optimization problem.However,we provide a novel solution framework based on the linearized alternating direction method of multipliers(LADMM)to split the original problem with coupling terms into several subproblems.We then derive that these subproblems,albeit nonconvex nonsmooth,are actually simple to solve and easy to implement,which can be of independent interest.Under some mild assumptions,we prove that any limiting point of the generated sequence of the proposed algorithm is a stationary point.Numerical simulations are performed to demonstrate the advantages of our proposed algorithm compared with various baselines.展开更多
基金partly supported by the Fundamental Research Fund-Shenzhen Research Institute for Big Data(SRIBD)Startup Fund JCYJ-AM20190601partly supported by the NSFC grant 11831002the Beijing Academy of Artificial Intelligence.
文摘We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a(probably nonconvex)smooth function and a(probably nonsmooth)convex function.The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions.Therefore,the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods.When the accuracy of the model function at the solution of the subproblem is not sufficient,we add a safeguard on the stepsizes for improving the accuracy.For a class of functions that can be“truncated”,an additional truncation step is defined and a stepsize modification strategy is designed.The overall scheme converges globally and we establish fast local convergence under suitable assumptions.In particular,using a connection with a smooth Riemannian trust-region method,we prove local quadratic convergence for partly smooth functions under a strict complementary condition.Preliminary numerical results on a family of Ei-optimization problems are reported and demonstrate the eficiency of our approach.
文摘In the past several centuries,there have been two major different paradigms for doing scientific research:the Keplerian paradigm and the Newtonian paradigm.In the Keplerian paradigm,natural laws are discovered through the analysis of data while in the Newtonian paradigm,one focuses on pursuing fundamental principles that govern Nature.
文摘This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where non- negativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on tile classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspeetral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.
基金supported by the Fundamental Research Fund—Shenzhen Research Institute for Big Data Startup Fund(Grant No.JCYJ-AM20190601)the Shenzhen Institute of Artificial Intelligence and Robotics for Society+2 种基金National Natural Science Foundation of China(Grant Nos.11831002 and 11871135)the Key-Area Research and Development Program of Guangdong Province(Grant No.2019B121204008)Beijing Academy of Artificial Intelligence。
文摘In this work,we present probabilistic local convergence results for a stochastic semismooth Newton method for a class of stochastic composite optimization problems involving the sum of smooth nonconvex and nonsmooth convex terms in the objective function.We assume that the gradient and Hessian information of the smooth part of the objective function can only be approximated and accessed via calling stochastic firstand second-order oracles.The approach combines stochastic semismooth Newton steps,stochastic proximal gradient steps and a globalization strategy based on growth conditions.We present tail bounds and matrix concentration inequalities for the stochastic oracles that can be utilized to control the approximation errors via appropriately adjusting or increasing the sampling rates.Under standard local assumptions,we prove that the proposed algorithm locally turns into a pure stochastic semismooth Newton method and converges r-linearly or r-superlinearly with high probability.
基金The computational results were obtained at GPUs supported by the National Engineering Laboratory for Big Data Analysis and Applications and the High-performance Computing Platform of Peking University.
文摘In this paper,we study a few challenging theoretical and numerical issues on the well known trust region policy optimization for deep reinforcement learning.The goal is to find a policy that maximizes the total expected reward when the agent acts according to the policy.The trust region subproblem is constructed with a surrogate function coherent to the total expected reward and a general distance constraint around the latest policy.We solve the subproblem using a preconditioned stochastic gradient method with a line search scheme to ensure that each step promotes the model function and stays in the trust region.To overcome the bias caused by sampling to the function estimations under the random settings,we add the empirical standard deviation of the total expected reward to the predicted increase in a ratio in order to update the trust region radius and decide whether the trial point is accepted.Moreover,for a Gaussian policy which is commonly used for continuous action space,the maximization with respect to the mean and covariance is performed separately to control the entropy loss.Our theoretical analysis shows that the deterministic version of the proposed algorithm tends to generate a monotonic improvement of the total expected reward and the global convergence is guaranteed under moderate assumptions.Comparisons with the state-of-the–art methods demonstrate the effectiveness and robustness of our method over robotic controls and game playings from OpenAI Gym.
文摘Most iterative algorithms for eigenpair computation consist of two main steps:a subspace update(SU)step that generates bases for approximate eigenspaces,followed by a Rayleigh-Ritz(RR)projection step that extracts approximate eigenpairs.So far the predominant methodology for the SU step is based on Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner.In this work,we investigate block methods in the SU step that allow a higher level of concurrency than what is reachable by Krylov subspace methods.To achieve a competitive speed,we propose an augmented Rayleigh-Ritz(ARR)procedure.Combining this ARR procedure with a set of polynomial accelerators,as well as utilizing a few other techniques such as continuation and deflation,we construet a block algorithm designed to reduce the number of RR steps and elevate concurrency in the SU steps.Extensive computational experiments are conducted in C on a representative set of test problems to evaluate the performance of two variants of our algorithm.Numerical results,obtained on a many-core computer without explicit code parallelization,show that when computing a relatively large number of eigenpairs,the performance of our algorithms is competitive with that of several state-of-the-art eigensolvers.
文摘A new two-level subspace method is proposed for solving the general unconstrained minimization formulations discretized from infinite-dimensional optimization problems. At each iteration, the algorithm executes either a direct step on the current level or a coarse subspace correction step. In the coarse subspace correction step, we augment the traditional coarse grid space by a two-dimensional subspace spanned by the coordinate direction and the gradient direction at the current point. Global convergence is proved and convergence rate is studied under some mild conditions on the discretized functions. Preliminary numerical experiments on a few variational problems show that our two-level subspace method is promising.
文摘In this paper, we consider two different formulations (one is smooth and the other one is nonsmooth) for solving linear matrix inequalities (LMIs), an important class of semidefinite programming (SDP), under a certain Slater constraint qualification assumption. We then propose two first-order methods, one based on subgradient method and the other based on Nesterov's optimal method, and show that they converge linearly for solving these formulations. Moreover, we introduce an accelerated prox-level method which converges linearly uniformly for both smooth and non-smooth problems without requiring the input of any problem parameters. Finally, we consider a special case of LMIs, i.e., linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a much weaker assumption.
文摘In this paper, we propose an extended Levenberg-Marquardt (ELM) framework that generalizes the classic Levenberg-Marquardt (LM) method to solve the unconstrained minimization problem min ρ(r(x)), where r : Rn→ Rm and ρ : Rm → R. We also develop a few inexact variants which generalize ELM to the cases where the inner subproblem is not solved exactly and the Jaeobian is simplified, or perturbed. Global convergence and local superlinear convergence are established under certain suitable conditions. Numerical results show that our methods are promising.
基金supported by the National Natural Science Foundation of China under Grant 11831002。
文摘In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem under path cardinality constraints.Specifically,such a problem formulation captures various types of objectives including proportional fairness,average delay,as well as load balancing.In addition,in order to handle the"unsplittable flows",path cardinality constraints are added,making the resulting optimization problem quite challenging to solve due to intrinsic nonsmoothness and nonconvexity.Almost all existing works deal with such a problem using relaxation techniques to transform it into a convex optimization problem.However,we provide a novel solution framework based on the linearized alternating direction method of multipliers(LADMM)to split the original problem with coupling terms into several subproblems.We then derive that these subproblems,albeit nonconvex nonsmooth,are actually simple to solve and easy to implement,which can be of independent interest.Under some mild assumptions,we prove that any limiting point of the generated sequence of the proposed algorithm is a stationary point.Numerical simulations are performed to demonstrate the advantages of our proposed algorithm compared with various baselines.