AnEfficientGlobalOptimizationAlgorithm.pdf资源-CSDN文库

需积分: 9 115 浏览量 2020-02-14 15:52:56 上传评论收藏 291KB PDF 举报

资源推荐

资源详情

资源评论

An Eﬃcient Global Optimization Algorithm

for Nonlinear Sum-of-Ratios Problem

∗†

Yun-Chol Jong

Center of Natural Sciences, University of Science, Pyongyang, DPR Korea

May 3, 2012

Abstract

This paper presents a practical method for ﬁnding 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 eﬃciency of the algorithm is demonstrated by numerical

experiments for synthetic data.

2010 Mathematics subject Classiﬁcation: 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 diﬃcult to

solve by traditional optimization methods. The problem arises in many applications such as

optimization of the average element shape quality in the ﬁnite element method, computer

∗

E-mail: yuncholjong@yahoo.com

†

Address: Gwahak-1 dong, Unjong distrct, Pyongyang, DPR Korea

graphics and management ([2],[3],[4]). In [4], many problems of projective geometry in-

cluding multiview triangulation, camera resectioning and homography estimation have been

formulated as the sum-of-ratios problem and a branch-and-bound method has been proposed

to ﬁnd its global solution which relies on recent developments in fractional programming and

the theory of convex underestimators ([6],[7],[8],[9],[14],[15]). In the method of [4], number

of variables increases as twice as the number of fractional functions involving in the sum and

a second-order cone programming problem is needed to solve for obtaining a lower bound of

the optimal value in each iteration. Their algorithm is provably optimal, that is, given any

tolerance , if the optimization problem is feasible, the algorithm returns a solution which

is at most  far from the global optimum. The branch-and-bound method requires a lot of

computations, has low convergence and it is not easy to ﬁnd a reasonable branching strategy.

Recently there has been some progress made towards ﬁnding the global solution to a few

of these optimization problems ([16],[17]). However, the resulting algorithm is numerically

unstable, computationally expensive and does not generalize for more views or harder prob-

lems like resectioning. In [18], linear matrix inequalities were used to approximate the global

optimum, but no guarantee of actually obtaining the global optimum is given. Also, there

are unsolved problems concerning numerical stability. Robustiﬁcation using L

-norm was

presented in [19], but the approach is restricted to the aﬃne camera model.

In this paper, an eﬃcient global optimization algorithm is presented which transforms

the sum-of-ratios problem into parametric convex programming problem and ﬁnds the global

solution successfully.

2 Equivalent parametric convex programming

The sum-of-ratios problem seeks to minimize the sum of fractional functions subject to

convex constraints, which is formulated as follows.

min F (x) =

i=1

(x),

subject to g

(x) ≤ 0, i = 1, ··· , m,

x ∈ R

(2.1)

where F

(x) =

(x)

, i = 1, ··· , N, and f

(x), g

(x) and −h

(x) are twice continuously diﬀer-

entiable convex functions.

Let X = {x ∈ R

(x) ≤ 0, i = 1, ··· , m}. It is assumed that f

(x) ≥ 0 and h

(x) > 0

for every x ∈ X, and that intX = {x ∈ R

(x) < 0, i = 1, ··· , m} 6= ∅. Even with these

restrictions the above problem is NP-complete [5].

剩余20页未读，继续阅读

评论收藏

内容反馈

我是YJJ啊

粉丝: 8
资源: 3

An Efficient Global Optimization Algorithm.pdf

最新资源

An Efficient Global Optimization Algorithm.pdf

An efficient algorithm for large scale global optimization of continuous functions

Global Optimization Algorithms – Theory and Application

A Binary Particle Swarm Optimization Algorithm For Uncapacitated.pdf

Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector.pdf

The Whale Optimization Algorithm.pdf

Introduction_to_Optimum_Design.pdf

启发式算法，代码和参考文献

IE598NH-lecture-23-Global Convergence of Policy Optimization.pdf

论文研究-An Efficient Trip Planning Algorithm Under Constraints.pdf

论文研究-An Efficient Algorithm of Convolutional Multicast Coding.pdf

论文研究-Imperialist Competitive Algorithm with Trading Mechanism for Optimization.pdf

蜂群算法代码

tabu search fundmentals and uses ---fred glover

matlab标准，并行，约束和多目标EGO算法.zip

LEACH-GA_Genetic_Algorithm-BasedEnergy-Efficient_A.pdf

A Hybrid Global Optimization Algorithm Based on Wind Driven Optimization and Differential Evolution

An Efficient Boosting Algorithm for Combining Preferences.pdf

An Enhanced Gravitational Search Algorithm for Global Optimization

Artech House - SMS and MMS Interworking in Mobile Networks

微软内部资料-SQL性能优化3

最新资源