In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization(LCCO) is presented.The algorithm is based on a new technique for finding a class of search directions a...In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization(LCCO) is presented.The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path.At each iteration, only full-Newton steps are used.Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O(√n log n /ε).展开更多
Linearly constrained convex optimization has many applications.The first-order optimal condition of the linearly constrained convex optimization is a monotone variational inequality(VI).For solving VI,the proximal poi...Linearly constrained convex optimization has many applications.The first-order optimal condition of the linearly constrained convex optimization is a monotone variational inequality(VI).For solving VI,the proximal point algorithm(PPA)in Euclideannorm is classical but abstract.Hence,the classical PPA only plays an important theoretical role and it is rarely used in the practical scientific computation.In this paper,we give a review on the recently developed customized PPA in Hnorm(H is a positive definite matrix).In the frame of customized PPA,it is easy to construct the contraction-type methods for convex optimization with different linear constraints.In each iteration of the proposed methods,we need only to solve the proximal subproblems which have the closed form solutions or can be efficiently solved up to a high precision.Some novel applications and numerical experiments are reported.Additionally,the original primaldual hybrid gradient method is modified to a convergent algorithm by using a prediction-correction uniform framework.Using the variational inequality approach,the contractive convergence and convergence rate proofs of the framework are more general and quite simple.展开更多
The cubic regularization(CR)algorithm has attracted a lot of attentions in the literature in recent years.We propose a new reformulation of the cubic regularization subproblem.The reformulation is an unconstrained con...The cubic regularization(CR)algorithm has attracted a lot of attentions in the literature in recent years.We propose a new reformulation of the cubic regularization subproblem.The reformulation is an unconstrained convex problem that requires computing the minimum eigenvalue of the Hessian.Then,based on this reformulation,we derive a variant of the(non-adaptive)CR provided a known Lipschitz constant for the Hessian and a variant of adaptive regularization with cubics(ARC).We show that the iteration complexity of our variants matches the best-known bounds for unconstrained minimization algorithms using first-and second-order information.Moreover,we show that the operation complexity of both of our variants also matches the state-of-the-art bounds in the literature.Numerical experiments on test problems from CUTEst collection show that the ARC based on our new subproblem reformulation is comparable to the existing algorithms.展开更多
In this paper, we investigate heterogeneous multiscale method （HMM） for the optimal control problem with distributed control constraints governed by elliptic equations with highly oscillatory coefficients. The state...In this paper, we investigate heterogeneous multiscale method （HMM） for the optimal control problem with distributed control constraints governed by elliptic equations with highly oscillatory coefficients. The state variable and co-state variable are approximated by the multiscale discretization scheme that relies on coupled macro and micro finite elements, whereas the control variable is discretized by the piecewise constant. By applying the well- known Lions＇ Lemma to the discretized optimal control problem, we obtain the necessary and sufficient optimality conditions. A priori error estimates in both L^2 and H^1 norms are derived for the state, co-state and the control variable with uniform bound constants. Finally, numerical examples are presented to illustrate our theoretical results.展开更多
基金supported by the Shanghai Pujiang Program (Grant No.06PJ14039)the Science Foundation of Shanghai Municipal Commission of Education (Grant No.06NS031)
文摘In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization(LCCO) is presented.The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path.At each iteration, only full-Newton steps are used.Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O(√n log n /ε).
文摘Linearly constrained convex optimization has many applications.The first-order optimal condition of the linearly constrained convex optimization is a monotone variational inequality(VI).For solving VI,the proximal point algorithm(PPA)in Euclideannorm is classical but abstract.Hence,the classical PPA only plays an important theoretical role and it is rarely used in the practical scientific computation.In this paper,we give a review on the recently developed customized PPA in Hnorm(H is a positive definite matrix).In the frame of customized PPA,it is easy to construct the contraction-type methods for convex optimization with different linear constraints.In each iteration of the proposed methods,we need only to solve the proximal subproblems which have the closed form solutions or can be efficiently solved up to a high precision.Some novel applications and numerical experiments are reported.Additionally,the original primaldual hybrid gradient method is modified to a convergent algorithm by using a prediction-correction uniform framework.Using the variational inequality approach,the contractive convergence and convergence rate proofs of the framework are more general and quite simple.
基金supported in part by the National Natural Foundation of China(Nos.11801087 and 12171100).
文摘The cubic regularization(CR)algorithm has attracted a lot of attentions in the literature in recent years.We propose a new reformulation of the cubic regularization subproblem.The reformulation is an unconstrained convex problem that requires computing the minimum eigenvalue of the Hessian.Then,based on this reformulation,we derive a variant of the(non-adaptive)CR provided a known Lipschitz constant for the Hessian and a variant of adaptive regularization with cubics(ARC).We show that the iteration complexity of our variants matches the best-known bounds for unconstrained minimization algorithms using first-and second-order information.Moreover,we show that the operation complexity of both of our variants also matches the state-of-the-art bounds in the literature.Numerical experiments on test problems from CUTEst collection show that the ARC based on our new subproblem reformulation is comparable to the existing algorithms.
基金The work was supported by the Shandong Province Outstanding Y- oung Scientists Research Award Fund Project （Grant No. BS2013DX010）, by the Natural Science Foundation of Shandong Province, China （Grant No. ZR2011FQ030, ZR2013FQ001, ZR2013FM025）, by Natural Science Foundation of China （Grant No. 11501326 and 11571356）, and by the Shandong Academy of Sciences Youth Fund Project （Grant No. 2013QN007）.
文摘In this paper, we investigate heterogeneous multiscale method （HMM） for the optimal control problem with distributed control constraints governed by elliptic equations with highly oscillatory coefficients. The state variable and co-state variable are approximated by the multiscale discretization scheme that relies on coupled macro and micro finite elements, whereas the control variable is discretized by the piecewise constant. By applying the well- known Lions＇ Lemma to the discretized optimal control problem, we obtain the necessary and sufficient optimality conditions. A priori error estimates in both L^2 and H^1 norms are derived for the state, co-state and the control variable with uniform bound constants. Finally, numerical examples are presented to illustrate our theoretical results.
