No description available.

No description available.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1980. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 101-106).

In this thesis, we study several interior point continuous trajectories for linearly constrained convex programming (CP) and convex semidefinite programming (SDP). The continuous trajectories are characterized as the solution trajectories of corresponding ordinary differential equation (ODE) systems. All our ODE systems are closely related to interior point methods.. First, we propose and analyze three continuous trajectories, which are the solutions of three ODE systems for linearly constrained convex programming. The three ODE systems are formulated based on an variant of the affine scaling direction, the central path, and the affine scaling direction in interior point methods. The resulting solutions of the first two ODE systems are called generalized affine scaling trajectory and generalized central path, respectively. Under some mild conditions, the properties of the continuous trajectories, the optimality and convergence of the continuous trajectories are all obtained. Furthermore, we show that for the example of Gilbert et al. [Math. Program., { 103}, 63-94 (2005)], where the central path does not converge, our generalized central path converges to an optimal solution of the same example in the limit.. Then we analyze two primal dual continuous trajectories for convex programming. The two continuous trajectories are derived from the primal-dual path-following method and the primal-dual affine scaling method, respectively. Theoretical properties of the two interior point continuous trajectories are fully studied. The optimality and convergence of both interior point continuous trajectories are obtained for any interior feasible point under some mild conditions. In particular, with proper choice of some parameters, the convergence for both continuous trajectories does not require the strict complementarity or the analyticity of the objective function.. For convex semidefinite programming, four interior continuous trajectories defined by matrix differential equations are proposed and analyzed. Optimality and convergence of the continuous trajectories are also obtained under some mild conditions. We also propose a strategy to guarantee the optimality of the affine scaling algorithm for convex SDP.

Finding the convex hull of a finite set of points is important not only for practical applications but also for theoretical reasons: a number of geometrical problems, such as constructing Voronoi diagrams or intersecting hyperspheres, can be reduced to the convex hull problem, and a fast convex hull algorithm yields fast algorithms for these other problems. This thesis deals with the problem of constructing the convex hull of a finite point set in R . Mathematical properties of convex hulls are developed, in particular, their facial structure, their representation, bounds on the number of faces, and the concept of duality. The main result of this thesis is an O(nlogn + n[(d+1)/2]) algorithm for the construction of the convex hull of n points in Rd. It is shown that this algorithm is worst case optimal for even d≥2. / Science, Faculty of / Computer Science, Department of / Graduate

No description available.

No description available.

by Cheng Tak Wai, Johnny. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 59-62). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Self-dual embedding --- p.7 / Chapter 2.2 --- Conic optimization --- p.8 / Chapter 2.3 --- Self-dual embedded conic optimization --- p.9 / Chapter 2.4 --- Connection with convex programming --- p.11 / Chapter 2.5 --- Chapter summary --- p.15 / Chapter 3 --- Implementation of the algorithm --- p.17 / Chapter 3.1 --- The new search direction --- p.17 / Chapter 3.2 --- Select the step-length --- p.23 / Chapter 3.3 --- The multi-constraint case --- p.25 / Chapter 3.4 --- Chapter summary --- p.32 / Chapter 4 --- Numerical results on randomly generated problem --- p.34 / Chapter 4.1 --- Single-constraint problems --- p.35 / Chapter 4.2 --- Multi-constraint problems --- p.36 / Chapter 4.3 --- Running time and the size of the problem --- p.39 / Chapter 4.4 --- Chapter summary --- p.42 / Chapter 5 --- Geometric optimization --- p.45 / Chapter 5.1 --- Geometric programming --- p.45 / Chapter 5.1.1 --- Monomials and posynomials --- p.45 / Chapter 5.1.2 --- Geometric programming --- p.46 / Chapter 5.1.3 --- Geometric program in convex form --- p.47 / Chapter 5.2 --- Conic transformation --- p.48 / Chapter 5.3 --- Computational results of geometric optimization problem --- p.50 / Chapter 5.4 --- Chapter summary --- p.55 / Chapter 6 --- Conclusion --- p.57

No description available.

Thesis (Ph. D.)--University of Washington, 1990. / Vita. Includes bibliographical references (leaves [97]-100).