Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    A globally and quadratically convergent affine scaling method for linearℓ 1 problems (1992)
    Springer
    Mathematical programming 56 (1992), S. 189-222 
    Details
    ISSN: 1436-4646
    Keywords: 65H10 ; 65K05 ; 65K10 ; Linearℓ 1 estimation ; linear programming ; interior-point algorithm ; simplex method ; least absolute value regression ; affine scaling method ; Karmarkar
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this “interior point” philosophy can be adapted to the linear ℓ1 problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide aglobally and ultimatelyquadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580899
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds (1994)
    Springer
    Mathematical programming 67 (1994), S. 189-224 
    Details
    ISSN: 1436-4646
    Keywords: Box constraints ; Interior-point method ; Nonlinear minimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an “activity set”. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582221
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints (2000)
    Springer
    Mathematical programming 88 (2000), S. 1-31 
    Details
    ISSN: 1436-4646
    Keywords: Key words: trust region – interior point method – Dikin-affine scaling – Newton step
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased. Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.¶The objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity, dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve quadratic convergence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00011369
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances (1998)
    Springer
    Computational optimization and applications 10 (1998), S. 219-242 
    Details
    ISSN: 1573-2894
    Keywords: location problems ; the Weiszfeld algorithm ; Newton methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018333422414
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...