## Files in this item

FilesDescriptionFormat

application/pdf

9305491.pdf (4MB)
(no description provided)PDF

## Description

 Title: Theory and Algorithms for Nonlinear Optimization and Variational Inequalities Author(s): Chu, Liang-Ju Doctoral Committee Chair(s): McLinden, L., Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics Abstract: We consider three separate topics in nonlinear optimization, one theoretical topic and two algorithmic topics. Each of these topics deals with a broad class of nonlinear optimization problems. We first introduce and analyze a generalized parametric variational inequality problem $PVI(E, T, C, \psi$, Z) in locally convex Hausdorff topological vector spaces. Based on Nikaido's coincidence theorem, we establish several general existence theorems, even without requiring convexity nor contractibility on T and C, but merely a certain acyclic property. The case where C is not compact is considered. We also analyze asymptotic convergence of the partial proximal point algorithm for solving the generalized nonlinear equation $0\in T(x),$ where $T : H\to H$ is a maximal monotone multifunction, and $H := H\sb1 \times H\sb2$ is a product of two real Hilbert spaces. Under the mild feasibility assumption $O\in int(coR(T)),$ we show that the partial proximal point algorithm has the same convergence properties as does Rockafellar's proximal point algorithm. Moreover, the partial convergence rates are shown to depend upon how rapidly $T\sp{-1}$ grows away from the solution set $T\sb{-1}(0).$ The partial rate of convergence is linear, superlinear, or quadratic, depending upon certain parameters. Finally, we describe a primal-dual path-following interior point algorithm for solving the pair of primal-dual problems (P) and (D):(P) sk20inf$\sb{x}\{f(x); Ax=b, x\ge 0\}$(D) sk20sup$\sb{x,s}\{g(x,s); Ax=b, x\ge 0$ and $s=\nabla f(x) - A\sp{T}y\ge 0$ for some $y\in R\sp{m}\}.$Here, f is a continuously differentiable convex function in $R\sp{n},$ and g is defined by $g(x, s) := f(x) - x\sp{T}s.$ Under a kind of strict feasibility assumption, we show that the algorithm under modification requires a total of $O(\sqrt{n\ell})$ number of iterations, with total arithmetic operations of order $O(n\sp3\ell),$ where $\ell$ is the initial input size. As an application to usual linear or convex quadratic programming, this algorithm solves the pair (P) and (D) in at most $O(\sqrt{nL})$ iterations, with total arithmetic operations of order $O(n\sp3 L),$ where L is the input size. Moreover, we show the duality gap sequence goes to zero linearly, superlinearly, or quadratically, depending upon a certain parameter $\theta.$ Also, we show that any limit point of the induced sequence ($x\sp{k},s\sp{k})$ is a maximal complementary solution of a certain monotone multifunction. Issue Date: 1992 Type: Text Description: 169 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992. URI: http://hdl.handle.net/2142/72533 Other Identifier(s): (UMI)AAI9305491 Date Available in IDEALS: 2014-12-17 Date Deposited: 1992
﻿