An Efficient Global Optimization Algorithm
for Nonlinear Sum-of-Ratios Problem
∗†
Yun-Chol Jong
a
a
Center of Natural Sciences, University of Science, Pyongyang, DPR Korea
May 3, 2012
Abstract
This paper presents a practical method for finding the globally optimal solution
to nonlinear sum-of-ratios problem arising in image processing, engineering and man-
agement. Unlike traditional methods which may get trapped in local minima due
to the non-convex nature of this problem, our approach provides a theoretical guar-
antee of global optimality. Our algorithm is based on solving a sequence of convex
programming problems and has global linear and local superlinear/quadratic rate of
convergence. The practical efficiency of the algorithm is demonstrated by numerical
experiments for synthetic data.
2010 Mathematics subject Classification: 90C26, 90C32, 65K05
Keywords: Fractional programming, non-convex optimization, global optimization algo-
rithm, sum-of ratios problem, guaranteed global optimality.
1 Introduction
The sum-of-ratios problem, which is to minimize (maximize) a sum of several fractional func-
tions subject to convex constraints, is a non-convex optimization problem that is difficult to
solve by traditional optimization methods. The problem arises in many applications such as
optimization of the average element shape quality in the finite element method, computer
∗
E-mail: yuncholjong@yahoo.com
†
Address: Gwahak-1 dong, Unjong distrct, Pyongyang, DPR Korea
1
剩余20页未读，继续阅读
资源评论
