- 성과
-
연구보고서
비볼록최적화문제에 대한 고정밀 원추계획법 연구
(Exact and highly accurate conic relaxations for nonconvex optimization problems)
| 등록번호 | TRKO202200019402 | 발행년월 | 2022-03 |
|---|---|---|---|
| 발행기관명 | 이화여자대학교 | 발행국가/사용언어 | 대한민국 /국문 |
| 발주기관 | 한국연구재단 | 과제관리(전문)기관 | 한국연구재단 |
| 키워드 |
비볼록최적화문제;고정밀의 해;고효율성수치해법;정확도 증대;
Nonconvex optimization problems;Exactness;Efficient solution methods;Improved accuracy; |
||
- 초록
-
□ 연구개요
본 연구의 대상은 비볼록최적화문제 (nonconvex optimization problems)에 관한 고정밀해법(exact, highly accurate methods)에 관한 연구이다. 비볼록최적화문제는 2차 다항식최적화문제, 고차다항식최적화문제까지 광범위한 응용문제를 포함하고 있다. 하지만, 비볼록최적화문제는 NP-hard의 문제로 알려져 있어 polynomial-time 알고리즘으로 해를 구할 수 없다고 알려져 있다. 이러한 연유로, 일반적 비볼록최적화문제는 근사해법의 적용이 불가피하며, 근사해법 중 원추완화방법( convex relaxation methods)의 연구를 통해 보다 효율적이고 정확한 해를 찾는 해법연구를 이론적, 수치적으로 진행한다.
□ 연구 목표대비 연구결과
1. 고차다항식해법과 알고리즘개발연구
- 고차다항식최적화문제의 해법에 대한 새로운 framework을 제시하였으며, 이를 바탕으로 이론적 수렴성을 증명하였음. 또한, 수치방법을 first-order method에 근거하여 개발하였다. 기존의 결과보다 우수한 결과를 도출하였다. 논문으로 Lagrangian-Conic Relaxations, Part I, Part II의 논문을 발표하였다.
- 수치해법관한 연구로는 BBCPOP라는 소프트웨어를 개발 논문으로 출간하였다.
2. 응용문제에 관한 정확한 해법과 수치알고리즘 제시
- 현재연구되고 있는 응용문제 중 가장 난해하다고 알려진 2차할당문제(Quadratic Assignment Problems)에 관한 이론적, 수치적연구를 진행하였다. 논문으로 본 문제 여러 형태구성의 동치성 및 차이점을 연구하여 발표하고, 대용량문제를 수치적으로 해결하여 기존에 해결하지 못한 크기의 문제를 해결하였다.
- Pooling 문제를 연구하여 효율적인 해법을제시하고 논문으로 발표하였다.
3. 원추완화방법에 관한 이론적, 알고리즘개발연구
- 이중양의 정부호완화방법, Completely positive cone programming에 관한 연구진행하고 이론적 논문을 발표하고 수치방법에 대한 결과를 출간하였다.
□ 연구개발성과의 활용 계획 및 기대효과(연구개발결과의 중요성)
비볼록최적화문제는 여러 다양한 응용문제를 표현할 수 있다. 네트워크가 스케쥴링에 관한 Maxcut problem, Equicut problem, Stable set problem, Qudratic Assignment Problem 문제, 근래에는 센서네트워크문제 등이 각종 응용에서 무선통신이 사용됨에 따라 더욱 주목을 받게 되었다. 중요한 문제였던 단백질의 구조를 결정하는 문제, 무선센서네트워크, 인공위성 범위문제(satellite ranging), 환경변화를 추적하는 센서, 기밀을 전달하는 센서 등의 문제에 적용되어 보다 적은 비용으로 정확한 위치를 제공하는 솔루션의 역할을 할 것으로 예상된다. 지금까지 SDP완화법보다 정확한 해를 효율적으로 제공하는 해법을 제시할 수 있을 것이다. 또한, 근래관심대상인 Big data의 관련 문제도 본 연구에서 개발하는 유클리디언행렬문제의 기법으로 접근할 수 있다.
(출처 : 연구결과 요약문 2p)
- 목차
-
※ 연구개발성과 비공개원문 및 활용 문의는 과제관리(전문)기관을 통해 문의하시기 바랍니다.
※ 연구보고서 원문 열람 문의는 ScienceON 고객센터로 문의하시기 바랍니다.
[문의] ScienceON 고객센터 Tel : 080-969-4114, E-mail : helpdesk@kisti.re.kr
※ NTIS 관련 이용문의는 NTIS 콜센터(042-869-1115)로 문의하시기 바랍니다.
