Doctoral Thesis Defense, Optimization and Systems Theory
Monday, February 17, 2003, 10.00, Kollegiesalen, Administration building, Valhallavägen 79, KTH

Göran Sporre

On some properties of interior methods for optimization

Akademisk avhandling som med tillstånd av Kungliga Tekniska Högskolan framlägges till offentlig granskning för avläggande av teknologie doktorsexamen måndagen den 17:e februari 2003 kl 10.00 i Kollegiesalen, Administrationsbyggnaden, Kungliga Tekniska Högskolan, Valhallavägen 79.

This thesis consists of four independent papers concerning different aspects of interior methods for optimization. Three of the papers focus on theoretical aspects while the fourth one concerns some computational experiments.

The systems of equations solved within an interior method applied to a convex quadratic program can be viewed as weighted linear least-squares problems. In the first paper, it is shown that the sequence of solutions to such problems is uniformly bounded. Further, boundedness of the solution to weighted linear least-squares problems for more general classes of weight matrices than the one in the convex quadratic programming application are obtained as a byproduct.

In many linesearch interior methods for nonconvex nonlinear programming, the iterates can ``falsely'' converge to the boundary of the region defined by the inequality constraints in such a way that the search directions do not converge to zero, but the step lengths do. In the second paper, it is shown that the multiplier search directions then diverge. Furthermore, the direction of divergence is characterized in terms of the gradients of the equality constraints along with the asymptotically active inequality constraints.

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

The final paper describes of some computational experiments concerning possibilities of reusing previous information when solving system of equations arising in interior methods for linear programming.

Calendar of seminars
Last update: January 10, 2003 by Anders Forsgren,