Change search
ReferencesLink to record
Permanent link

Direct link
On Some Properties of Interior Methods for Optimization
KTH, Superseded Departments, Mathematics.
2003 (English)Doctoral thesis, comprehensive summary (Other scientific)
Abstract [en]

This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments.

The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct.

In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints.

The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case.

The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming.

Keywords:Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path.

Mathematics Subject Classification (2000):Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.

Place, publisher, year, edition, pages
Stockholm: Matematik , 2003. , xi, 28 p.
Trita-MAT. OS, ISSN 1401-2294 ; 03:02
Keyword [en]
Interior method, primal-dual interior method, linear programming, quadratic programming, nonlinear programming, semidefinite programming, weighted least-squares problems, central path
URN: urn:nbn:se:kth:diva-3472ISBN: 91-7283-438-2OAI: diva2:9275
Public defence
NR 20140805Available from: 2003-02-11 Created: 2003-02-11Bibliographically approved

Open Access in DiVA

fulltext(293 kB)670 downloads
File information
File name FULLTEXT01.pdfFile size 293 kBChecksum SHA-1
Type fulltextMimetype application/pdf

By organisation

Search outside of DiVA

GoogleGoogle Scholar
Total: 670 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 188 hits
ReferencesLink to record
Permanent link

Direct link