New algorithm for the conical combination representation problem of a vector

An important problem in constrained optimization is to determine whether or not a vector can be represented as the conical combination (i.e., linear n onnegative combination) of some given vectors. This problem can be transfor med into a special linear programming problem (SLP). A new approach, the va riable-dimension boundary-point algorithm (VDBPA), based on the projection of a vector into a variable-dimension subspace, is proposed to solve this p roblem. When a conical combination representation (CCR) of a vector exists, the VDBPA can compute its CCR coefficients; otherwise, the algorithm certi ficates the nonexistence of such representation. In order to assure converg ence, the VDBPA may call the lexicographically ordered method (LOM) for lin ear programming at the final stage. In fact, the VDBPA terminates often by solving SLP for most instances before calling the LOM. Numerical results in dicate that the VDBPA works more efficiently than the LOM for problems that have more variables or inequality constraints. Also, we have found instanc es 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 ins tances. In addition, the convergence of the VDBPA without calling the LOM i s established under certain conditions.