WEKO3
AND
Item
{"_buckets": {"deposit": "d29422aaa4794e1abfbae869997de303"}, "_deposit": {"id": "31440", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "31440"}, "status": "published"}, "_oai": {"id": "oai:tsukuba.repo.nii.ac.jp:00031440"}, "item_10_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "201405", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}]}]}, "item_10_description_33": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"subitem_description": "text", "subitem_description_type": "Other"}]}, "item_10_description_4": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "A symmetric matrix is called copositive if it generates a quadratic form taking no negative values over the nonnegative orthant, and the linear optimization problem over the set of copositive matrices is called the copositive programming problem. Recently, many studies have been done on the copositive programming problem (see, for example, [13, 5]). Among others, several branch and bound type algorithms have been provided to test copositivity in the context of the fact that deciding whether a given matrix is copositive is coNPcomplete [21, 12]. In this paper, we propose a new branch and bound type algorithm for this testing problem based on Sponsel, Bundfuss and D\u00a8ur\u2019s algorithm[25]. Two features of our algorithm are: (1) we introduce new classes of matrices Gsn and !Gsn which are relatively large subsets of the set of copositive matrices and work well to check copositivity of a given n \u00d7 n symmetric matrix, and (2) for incorporating the sets Gsnor !Gsn in checking copositivity, we only have to solve a linear optimization problem with n + 1 variables and O(n2) constraints after computing a singular value matrix decomposition, which implies that our algorithm is not so timeconsuming. Our preliminary numerical experiments suggest that our\nalgorithm is promising for determining upper bounds of the maximum clique problem.", "subitem_description_type": "Abstract"}]}, "item_10_publisher_27": {"attribute_name": "\u51fa\u7248\u8005", "attribute_value_mlt": [{"subitem_publisher": "University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems \u0026 Management "}]}, "item_10_relation_36": {"attribute_name": "\u30b7\u30ea\u30fc\u30ba", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_text": "Department of Social Systems and Management Discussion Paper Series;no.1320"}]}]}, "item_10_select_15": {"attribute_name": "\u8457\u8005\u7248\u30d5\u30e9\u30b0", "attribute_value_mlt": [{"subitem_select_item": "author"}]}, "item_10_subject_20": {"attribute_name": "NII\u30b5\u30d6\u30b8\u30a7\u30af\u30c8", "attribute_value_mlt": [{"subitem_subject": "\u30d3\u30b8\u30cd\u30b9\u30fb\u7d4c\u55b6\u30fb\u7523\u696d", "subitem_subject_scheme": "Other"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "TANAKA, Akihiro"}], "nameIdentifiers": [{"nameIdentifier": "108191", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "YOSHISE, Akiko"}], "nameIdentifiers": [{"nameIdentifier": "108192", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "20141106"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "1320.pdf", "filesize": [{"value": "325.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 325600.0, "url": {"label": "1320", "url": "https://tsukuba.repo.nii.ac.jp/record/31440/files/1320.pdf"}, "version_id": "fd87d44b53064ca3bd1d15ca7ee6e97a"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "research report", "resourceuri": "http://purl.org/coar/resource_type/c_18ws"}]}, "item_title": "An LPbased Algorithm to Test Copositivity", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "An LPbased Algorithm to Test Copositivity"}]}, "item_type_id": "10", "owner": "1", "path": ["3/2658/2662"], "permalink_uri": "http://hdl.handle.net/2241/00122201", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_name_i18n": "\u516c\u958b\u65e5", "attribute_value": "20141007"}, "publish_date": "20141007", "publish_status": "0", "recid": "31440", "relation": {}, "relation_version_is_last": true, "title": ["An LPbased Algorithm to Test Copositivity"], "weko_shared_id": 5}
An LPbased Algorithm to Test Copositivity
http://hdl.handle.net/2241/00122201
e1b0c34debab438cb71e775a9be76f8f
Name / File  License  Actions  

1320 (325.6 kB)


item type  Research Paper(1)  

公開日  20141007  
タイトル  
タイトル  An LPbased Algorithm to Test Copositivity  
言語  
言語  eng  
資源タイプ  
タイプ  research report  
著者 
TANAKA, Akihiro
× TANAKA, Akihiro× YOSHISE, Akiko 

抄録  
内容記述  A symmetric matrix is called copositive if it generates a quadratic form taking no negative values over the nonnegative orthant, and the linear optimization problem over the set of copositive matrices is called the copositive programming problem. Recently, many studies have been done on the copositive programming problem (see, for example, [13, 5]). Among others, several branch and bound type algorithms have been provided to test copositivity in the context of the fact that deciding whether a given matrix is copositive is coNPcomplete [21, 12]. In this paper, we propose a new branch and bound type algorithm for this testing problem based on Sponsel, Bundfuss and D¨ur’s algorithm[25]. Two features of our algorithm are: (1) we introduce new classes of matrices Gsn and !Gsn which are relatively large subsets of the set of copositive matrices and work well to check copositivity of a given n × n symmetric matrix, and (2) for incorporating the sets Gsnor !Gsn in checking copositivity, we only have to solve a linear optimization problem with n + 1 variables and O(n2) constraints after computing a singular value matrix decomposition, which implies that our algorithm is not so timeconsuming. Our preliminary numerical experiments suggest that our algorithm is promising for determining upper bounds of the maximum clique problem. 

書誌情報  発行日 201405  
著者版フラグ  
値  author  
出版者  
出版者  University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems & Management  
シリーズ  
関連名称  
関連名称  Department of Social Systems and Management Discussion Paper Series;no.1320 