English, Article edition: A HYBRID ADAPTIVE ALGORITHM FOR LINEAR OPTIMIZATION MAZIAR SALAHI; TAMÃS TERLAKY

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/40226
Physical Description
  • article
Language
  • English

Edition details

Title
  • A HYBRID ADAPTIVE ALGORITHM FOR LINEAR OPTIMIZATION
Author
  • MAZIAR SALAHI
  • TAMÃS TERLAKY
Physical Description
  • article
Notes
  • Recently, using the framework of self-regularity, Salahi in his Ph.D. thesis proposed an adaptive single step algorithm which takes advantage of the current iterate information to find an appropriate barrier parameter rather than using a fixed fraction of the current duality gap. However, his algorithm might do at most one bad step after each good step in order to keep the iterate in a certain neighborhood of the central path. In this paper, using the same framework, we propose a hybrid adaptive algorithm. Depending on the position of the current iterate, our new algorithm uses either the classical Newton search direction or a self-regular search direction. The larger the distance from the central path, the larger the barrier degree of the self-regular search direction is. Unlike the classical approach, here we control the iterates by guaranteeing certain reduction of the proximity measure. This itself leads to a one dimensional equation which determines the target barrier parameter at each iteration. This allows us to have a large update algorithm without any need for safeguard or special steps. Finally, we prove that our hybrid adaptive algorithm has an $\mathcal{O}\Big(n^\frac{71}{100}\, {\rm log}\, n\, {\rm log}\, \frac{(x^0)^Ts^0}{\epsilon}\Big)$ worst case iteration complexity.
  • Linear optimization, interior point methods, self-regular functions, polynomial complexity
  • RePEc:wsi:apjorx:v:26:y:2009:i:02:p:235-256
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment