Files in this item



application/pdf9305491.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Theory and Algorithms for Nonlinear Optimization and Variational Inequalities
Author(s):Chu, Liang-Ju
Doctoral Committee Chair(s):McLinden, L.,
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
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
Description:169 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.
Other Identifier(s):(UMI)AAI9305491
Date Available in IDEALS:2014-12-17
Date Deposited:1992

This item appears in the following Collection(s)

Item Statistics