-

 

 

 




Optimization Online





 

A NEW SELF-CONCORDANT BARRIER FOR THE HYPERCUBE

Erik Alex Quiroz (erik***at***cos.ufrj.br)
Paulo Roberto Oliveira (poliveir***at***cos.ufrj.br)

Abstract: In this paper we introduce a new barrier function $\sum\limits_{i=1}^n(2x_i-1)[\ln{x_i}-\ln(1-x_i)]$ to solve the following optimization problem: $\min\,\, f(x)$ subject to: $Ax=b;\;\;0\leq x\leq e$. We show that this function is a $(3/2)n$-self-concordant barrier on the hypercube $[0,1]^n$. We prove that the central path is well defined and that under an additional assumption on the objective function, which includes linear and convex quadratic problems, the primal central path converges to the analytic center of the optimal set (with respect to the given barrier). Finally, we present a new polynomial long step path following algorithm to solve the problem when the objective function is linear. For that algorithm we give an upper bound for the total number of Newton iterations to obtain an $\epsilon$-optimal solution, with similar complexity to the classic logarithmic barrier, that is $O(n\ln(n\mu_0/\epsilon))$.

Keywords: Interior point methods, self-concordant function,

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Citation: J Optim Theory Appl (2007) 135:475-490

Download:

Entry Submitted: 08/10/2004
Entry Accepted: 08/10/2004
Entry Last Modified: 05/15/2008

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society