tailieunhanh - Interior-point algorithms for a class of convex optimization problems

In this paper we consider interior-point methods (IPM) for the nonlinear, convex optimization problem where the objective function is a weighted sum of reciprocals of variables subject to linear constraints (SOR). This problem appears often in various applications such as statistical stratified sampling and entropy problems, to mention just few examples. | Yugoslav Journal of Operations Research Volume 19 (2009) Number 2, 239-248 DOI: INTERIOR-POINT ALGORITHMS FOR A CLASS OF CONVEX OPTIMIZATION PROBLEMS Goran LEŠAJA goran@. Verlynda N. SLAUGHTER Department of Mathematical Sciences Georgia Southern University Statesboro, Georgia, USA Received: March 2009 / Accepted: November 2009 Abstract: In this paper we consider interior-point methods (IPM) for the nonlinear, convex optimization problem where the objective function is a weighted sum of reciprocals of variables subject to linear constraints (SOR). This problem appears often in various applications such as statistical stratified sampling and entropy problems, to mention just few examples. The SOR is solved using two IPMs. First, a homogeneous IPM is used to solve the Karush-Kuhn-Tucker conditions of the problem which is a standard approach. Second, a homogeneous conic quadratic IPM is used to solve the SOR as a reformulated conic quadratic problem. As far as we are aware of it, this is a novel approach not yet considered in the literature. The two approaches are then numerically tested on a set of randomly generated problems using optimization software MOSEK. They are compared by CPU time and the number of iterations, showing that the second approach works better for problems with higher dimensions. The main reason is that although the first approach increases the number of variables, the IPM exploits the structure of the conic quadratic reformulation much better than the structure of the original problem. Keywords: SOR problem, convex optimization problems, conic quadratic optimization problem, interior-point methods. G., Lešaja, V., N., Slaughter / Interior-Point Algorithms 240 1. INTRODUCTION In this paper we consider the problem n ci ( SOR ) Minimize ∑ i =1 xi n subject to ∑a x ≤ b i =1 () i i li ≤ xi ≤ ui , i = 1,., n where ci , li , and ui ∈ R+ . The above problem is a nonlinear, optimization problem .