Study On Circular Cone Complementarity Functions And Interior-point Algorithms For Circular Cone Programming

Not only has cone programming abundant expression ability and good structure characteristics, but also it has powerful duality theory and effective algorithm. It is one of the hot topics in recent years, on which is focused by international researchers. Up until 2000, cone programming likely means optimization over symmetric cones, which contain linear programming(LP), second order cone programming(SOCP) and semidefinite programming(SDP). Because many data mining and image processing problems can be described as a nonsymmetric cone programming, nonsymmetric cone programming have been one of leading issues of the international optimization. As nonsymmetric cone programming, circular cone programming is a cone optimization model that minimize a linear objective function over the intersection of an affine linear space and the Cartesian product of a finite number of circular cones. Circular cone programming can describe engineering problems, such as optimal design problems of grasping manipulation for multi-fingered robots.The dissertation mainly contains the study of circular cone complementary functions and interior-point algorithms for solving circular cone programming.Specific work can be divided into three parts:Firstly, we study complementary functions over circular cones. On the one hand, we present a class of complementary functions regarding nonlinear programming. These complementary functions are extension of Fischer-Burmeister function and possess continuous differentiability. On the other hand, we show that the new functions can be extended to the circular cone complementary problems as complementarity functions via Jordan algebra. The optimality condition of circular cone programming is a special circular cone complementarity problem.If circular cone complementarity problems can be effectively solved, we can effectively solve circular cone programming. Therefore, our research provides a new path for solving circular cone programming.Secondly, we present an interior-point algorithm for circular cone programming based on kernel functions. We establish an invertible linear mapping based on algebraic relationship between a circular cone and its corresponding second order cone. The linear mapping can project the elements of the circular cone and its dual cone to second order cones. Based on the linear mapping, we convert circular cone programming into SOCP. We develop a kernel function based interior-point algorithm to solve circular cone optimization in terms of the corresponding SOCP. We derive the complexity bound of the interior-point algorithm and conclude that circular cone optimization is polynomial-time solvable. At last, we illustrate the performance of interior-point algorithm by a real-world quadruped robot example of optimal contact forces.Finally, we propose a self-concordant interior-point algorithm for circular cone programming. We first introduce a pair of logarithmically homogeneous self-concordant barrier function for circular cone and its dual cone. Then, based on these two logarithmically homogeneous self-concordant barrier functions and their related properties, we present an interior-point algorithm for circular cone programming. We derive the complexity bound for this interior-point algorithm.Furthermore, we show some numerical tests to demonstrate the performance of the proposed algorithm.