Theory and Algorithms for Nonlinear Optimization and Variational Inequalities

Chu, Liang-Ju

Permalink

https://hdl.handle.net/2142/72533 Copy

Description

Title

Theory and Algorithms for Nonlinear Optimization and Variational Inequalities

Author(s)

Chu, Liang-Ju

Issue Date

1992

Doctoral Committee Chair(s)

McLinden, L.,

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

1992

Type of Resource

text

Permalink

http://hdl.handle.net/2142/72533

Owning Collections