國立東華大學應用數學系

專    題    演    講

主講人：許瑞麟

        國立成功大學數學系

講  題： Maximizing the sum of quadratic ratios on the unit sphere via semidefinite programming approach

時  間：104 年 04月 15 日 (星期三)  10:00-12:00

地  點：理工一館 A324會議室

摘   要

The talk is about solving a type of "sum-of-ratios'' fractional programming which is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter $\mu$ and generate a family of quadratic subproblems $({\rm P}_{\mu})'s$ subject to two quadratic constraints. Each $({\rm P}_{\mu})$, if the problem dimension $n\ge3$, can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become an one-dimensional maximization problem over an interval of parameters $[\underline{\mu},\bar{\mu}]$. We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find $\mu^*$ numerically. Computational experiments show that our method solve the problem correctly and efficiently. Finally, we show that this approach can be further extended to solve the sum of three quadratic ratios.

※※※   歡      迎      參      加   ※※※se1040415 附檔：