首页 | 本学科首页   官方微博 | 高级检索  
     


New Algorithm for the Conical Combination Representation Problem of a Vector
Authors:H. X. Huang  P. M. Pardalos
Affiliation:(1) Department of Mathematical Sciences, Tsinghua University, Beijing, China;(2) Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Abstract:An important problem in constrained optimization is to determine whether or not a vector can be represented as the conical combination (i.e., linear nonnegative combination) of some given vectors. This problem can be transformed into a special linear programming problem (SLP). A new approach, the variable-dimension boundary-point algorithm (VDBPA), based on the projection of a vector into a variable-dimension subspace, is proposed to solve this problem. When a conical combination representation (CCR) of a vector exists, the VDBPA can compute its CCR coefficients; otherwise, the algorithm certificates the nonexistence of such representation. In order to assure convergence, the VDBPA may call the lexicographically ordered method (LOM) for linear programming at the final stage. In fact, the VDBPA terminates often by solving SLP for most instances before calling the LOM. Numerical results indicate that the VDBPA works more efficiently than the LOM for problems that have more variables or inequality constraints. Also, we have found instances of the SLP, when the number of inequality constraints is about twice the number of variables, which are much more difficult to solve than other instances. In addition, the convergence of the VDBPA without calling the LOM is established under certain conditions.
Keywords:conical combination representation  special linear programming problem  lexicographically ordered method  variable-dimension boundary-point algorithm  essential constraints  orthogonal projections  projective coordinates
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号