An ε-subgradient projection algorithm for solving a convex feasibility problem is presented.Based on the iterative projection methods and the notion of ε-subgradient,a series of special projection hyperplanes is est...An ε-subgradient projection algorithm for solving a convex feasibility problem is presented.Based on the iterative projection methods and the notion of ε-subgradient,a series of special projection hyperplanes is established.Moreover,compared with the existing projection hyperplanes methods with subgradient,the proposed hyperplanes are interactive with ε,and their ranges are more larger.The convergence of the proposed algorithm is given under some mild conditions,and the validity of the algorithm is proved by the numerical test.展开更多
This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one c...This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.展开更多
A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints.At each step of the algorithm,a system of linear equations is solved to get a search direction and the Ar...A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints.At each step of the algorithm,a system of linear equations is solved to get a search direction and the Armijo's rule is used to determine a stepsize.It is proved that the algorithm is globally convergent.Computational results are reported.展开更多
Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In ...Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.展开更多
The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off betwee...The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interiorpoint method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.展开更多
A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. I...A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.展开更多
Nowadays, distributed optimization algorithms are widely used in various complex networks. In order to expand the theory of distributed optimization algorithms in the direction of directed graph, the distributed conve...Nowadays, distributed optimization algorithms are widely used in various complex networks. In order to expand the theory of distributed optimization algorithms in the direction of directed graph, the distributed convex optimization problem with time-varying delays and switching topologies in the case of directed graph topology is studied. The event-triggered communication mechanism is adopted, that is, the communication between agents is determined by the trigger conditions, and the information exchange is carried out only when the conditions are met. Compared with continuous communication, this greatly saves network resources and reduces communication cost. Using Lyapunov-Krasovskii function method and inequality analysis, a new sufficient condition is proposed to ensure that the agent state finally reaches the optimal state. The upper bound of the maximum allowable delay is given. In addition, Zeno behavior will be proved not to exist during the operation of the algorithm. Finally, a simulation example is given to illustrate the correctness of the results in this paper.展开更多
Given two disjoint 3-dimensional convex polytopes P and Q and a straight direction along Which P moves in translation, this paper presents a linear algorithm for determining Whether P collides with Q, and the possible...Given two disjoint 3-dimensional convex polytopes P and Q and a straight direction along Which P moves in translation, this paper presents a linear algorithm for determining Whether P collides with Q, and the possible collision positions on P and Q. This result is achieved by using the hierarchicat representation of polytopes, of which the preprocessing time is linear with space.展开更多
Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax ...Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax rule. Theorem of the convergence for the algorithm is proved. Finally, a numerical example about two-stage convex recourse problem shows the essential character and the efficiency.展开更多
With the development of the compressive sensing theory, the image reconstruction from the projections viewed in limited angles is one of the hot problems in the research of computed tomography technology. This paper d...With the development of the compressive sensing theory, the image reconstruction from the projections viewed in limited angles is one of the hot problems in the research of computed tomography technology. This paper develops an iterative algorithm for image reconstruction, which can fit the most cases. This method gives an image reconstruction flow with the difference image vector, which is based on the concept that the difference image vector between the reconstructed and the reference image is sparse enough. Then the l1-norm minimization method is used to reconstruct the difference vector to recover the image for flat subjects in limited angles. The algorithm has been tested with a thin planar phantom and a real object in limited-view projection data. Moreover, all the studies showed the satisfactory results in accuracy at a rather high reconstruction speed.展开更多
The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approxim...The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approximate convex hull from a set of n points in the plane in O(n+k) time, where k is the approximation error control parameter. The proposed algorithm is suitable for applications preferred to reduce the computation time in exchange of accuracy level such as animation and interaction in computer graphics where rapid and real-time graphics rendering is indispensable.展开更多
In this paper, we present two parallel multiplicative algorithms for convex programming. If the objective function has compact level sets and has a locally Lipschitz continuous gradient, we discuss convergence of the ...In this paper, we present two parallel multiplicative algorithms for convex programming. If the objective function has compact level sets and has a locally Lipschitz continuous gradient, we discuss convergence of the algorithms. The proofs are essentially based on the results of sequential methods shown by Eggermontt[1].展开更多
The box-constrained weighted maximin dispersion problem is to find a point in an n-dimensional box such that the minimum of the weighted Euclidean distance from given m points is maximized. In this paper, we first ref...The box-constrained weighted maximin dispersion problem is to find a point in an n-dimensional box such that the minimum of the weighted Euclidean distance from given m points is maximized. In this paper, we first reformulate the maximin dispersion problem as a non-convex quadratically constrained quadratic programming (QCQP) problem. We adopt the successive convex approximation (SCA) algorithm to solve the problem. Numerical results show that the proposed algorithm is efficient.展开更多
We consider the problem of guillotine cutting a rectangular sheet into rectangular pieces with two heights. A polynomial time algorithm for this problem is constructed.
基金supported by the National Natural Science Foundation of China (10671126)Shanghai Leading Academic Discipline Project(S30501)
文摘An ε-subgradient projection algorithm for solving a convex feasibility problem is presented.Based on the iterative projection methods and the notion of ε-subgradient,a series of special projection hyperplanes is established.Moreover,compared with the existing projection hyperplanes methods with subgradient,the proposed hyperplanes are interactive with ε,and their ranges are more larger.The convergence of the proposed algorithm is given under some mild conditions,and the validity of the algorithm is proved by the numerical test.
基金Project supported by the National Science Foundation of China (60574071) the Foundation for University Key Teacher by the Ministry of Education.
文摘This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.
基金Supported by National High Technology Research and Development Program of China （863 Program） （2007AA809502C） National Natural Science Foundation of China （50979093） Program for New Century Excellent Talents in University （NCET-06-0877）
文摘A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints.At each step of the algorithm,a system of linear equations is solved to get a search direction and the Armijo's rule is used to determine a stepsize.It is proved that the algorithm is globally convergent.Computational results are reported.
文摘Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.
文摘The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interiorpoint method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.
文摘A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.
文摘Nowadays, distributed optimization algorithms are widely used in various complex networks. In order to expand the theory of distributed optimization algorithms in the direction of directed graph, the distributed convex optimization problem with time-varying delays and switching topologies in the case of directed graph topology is studied. The event-triggered communication mechanism is adopted, that is, the communication between agents is determined by the trigger conditions, and the information exchange is carried out only when the conditions are met. Compared with continuous communication, this greatly saves network resources and reduces communication cost. Using Lyapunov-Krasovskii function method and inequality analysis, a new sufficient condition is proposed to ensure that the agent state finally reaches the optimal state. The upper bound of the maximum allowable delay is given. In addition, Zeno behavior will be proved not to exist during the operation of the algorithm. Finally, a simulation example is given to illustrate the correctness of the results in this paper.
文摘Given two disjoint 3-dimensional convex polytopes P and Q and a straight direction along Which P moves in translation, this paper presents a linear algorithm for determining Whether P collides with Q, and the possible collision positions on P and Q. This result is achieved by using the hierarchicat representation of polytopes, of which the preprocessing time is linear with space.
文摘Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax rule. Theorem of the convergence for the algorithm is proved. Finally, a numerical example about two-stage convex recourse problem shows the essential character and the efficiency.
基金Project supported by the National Basic Research Program of China(Grant No.2006CB7057005)the National High Technology Research and Development Program of China(Grant No.2009AA012200)the National Natural Science Foundation of China (Grant No.60672104)
文摘With the development of the compressive sensing theory, the image reconstruction from the projections viewed in limited angles is one of the hot problems in the research of computed tomography technology. This paper develops an iterative algorithm for image reconstruction, which can fit the most cases. This method gives an image reconstruction flow with the difference image vector, which is based on the concept that the difference image vector between the reconstructed and the reference image is sparse enough. Then the l1-norm minimization method is used to reconstruct the difference vector to recover the image for flat subjects in limited angles. The algorithm has been tested with a thin planar phantom and a real object in limited-view projection data. Moreover, all the studies showed the satisfactory results in accuracy at a rather high reconstruction speed.
文摘The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approximate convex hull from a set of n points in the plane in O(n+k) time, where k is the approximation error control parameter. The proposed algorithm is suitable for applications preferred to reduce the computation time in exchange of accuracy level such as animation and interaction in computer graphics where rapid and real-time graphics rendering is indispensable.
文摘In this paper, we present two parallel multiplicative algorithms for convex programming. If the objective function has compact level sets and has a locally Lipschitz continuous gradient, we discuss convergence of the algorithms. The proofs are essentially based on the results of sequential methods shown by Eggermontt[1].
文摘The box-constrained weighted maximin dispersion problem is to find a point in an n-dimensional box such that the minimum of the weighted Euclidean distance from given m points is maximized. In this paper, we first reformulate the maximin dispersion problem as a non-convex quadratically constrained quadratic programming (QCQP) problem. We adopt the successive convex approximation (SCA) algorithm to solve the problem. Numerical results show that the proposed algorithm is efficient.
文摘We consider the problem of guillotine cutting a rectangular sheet into rectangular pieces with two heights. A polynomial time algorithm for this problem is constructed.
