New Algorithm for the Conical Combination Representation Problem of a Vector

H. X. Huang and P. M. Pardalos
Additional contact information
H. X. Huang: Tsinghua University
P. M. Pardalos: University of Florida

Journal of Optimization Theory and Applications, 2001, vol. 109, issue 3, No 2, 495-519

Abstract: 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 (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1017507519943 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:109:y:2001:i:3:d:10.1023_a:1017507519943

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1017507519943

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().