A new algorithm for computing the convex hull of a planar point set

When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster.

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.

Almost Fixed Points and Fixed Points of Upper [Lower] Semicontinuous Multimap on Locally G-convex Spaces

In this paper, we use the well known KKM type theorem for generalized convex spaces due to Park （Elements of the KKM theory for generalized convex spaces, Korean J. Comp. Appl. Math., 7（2000）, 1-28） to obtain an almost fixed point theorem for upper [resp., lower] semicontinuous multimaps in locally G-convex spaces, and then give a fixed point theorem for upper semicontinuous multimap with closed Γ-convex values.

FIXED POINT THEOREMS AND BEST APPROXIMATION IN CONVEX METRIC SPACES

Results regarding best approximation and best Simultaneous approximation on convex metric spaces are Obtained.Existence of fixed points for an ultimately nonexpansive semigroup of mappings is also shown.

A new primal-dual interior-point algorithm for convex quadratic optimization

In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization （CQO） based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method （IPM） to O（√n log nlog n/e）, which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.

Fixed-Point Iteration Method for Solving the Convex Quadratic Programming with Mixed Constraints

The present paper is devoted to a novel smoothing function method for convex quadratic programming problem with mixed constrains, which has important application in mechanics and engineering science. The problem is reformulated as a system of non-smooth equations, and then a smoothing function for the system of non-smooth equations is proposed. The condition of convergences of this iteration algorithm is given. Theory analysis and primary numerical results illustrate that this method is feasible and effective.

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions, we propose a combined homotopy infeasible interior-point method （CHIIP） for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.

Fixed point theorems for better admissible multimaps on Abstract convex spaces

In this paper, a better admissible class B＋ is introduced and a new fixed point theorem for better admissible multimap is proved on abstract convex spaces. As a consequence, we deduce a new fixed point theorem on abstract convex Ф-spaces. Our main results generalize some recent work due to Lassonde, Kakutani, Browder, and Park

A RANDOM FIXED POINT ITERATION FOR THREE RANDOM OPERATORS ON UNIFORMLY CONVEX BANACH SPACES

In the present paper we introduce a random iteration scheme for three random operators defined on a closed and convex subset of a uniformly convex Banach space and prove its convergence to a common fixed point of three random operators. The result is also an extension of a known theorem in the corresponding non-random case.

Common Fixed Points for a Countable Family of Quasi-Contractive Mappings on a Cone Metric Space with the Convex Structure

In this paper, we consider a countable family of surjective mappings {Tn}n∈N satisfying certain quasi-contractive conditions. We also construct a convergent sequence { Xn } n c∈Nby the quasi-contractive conditions of { Tn } n ∈N and the boundary condition of a given complete and closed subset of a cone metric space X with convex structure, and then prove that the unique limit x＂ of {xn}n∈N is the unique common fixed point of {Tn}n∈N. Finally, we will give more generalized common fixed point theorem for mappings {Ti,j}i,j∈N. The main theorems in this paper generalize and improve many known common fixed point theorems for a finite or countable family of mappings with quasi-contractive conditions.

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interiorpoint method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.

Common Fixed Points for a Countable Family of Non-self Mappings in Cone Metric Spaces with the Convex Prop erty

A new common fixed point result for a countable family of non-self mappings defined on a closed subset of a cone metric space with the convex property is obtained, and from which, a more general result is given. Our main results improve and generalize many known common fixed point theorems.

On Properties of p-critical Points of Convex Bodies

Properties of the p-measures of asymmetry and the corresponding affine equivariant p-critical points, defined recently by the second author, for convex bodies are discussed in this article. In particular, the continuity of p-critical points with respect to p on （1, ＋∞） is confirmed, and the connections between general p-critical points and the Minkowski-critical points （∞-critical points） are investigated. The behavior of p-critical points of convex bodies approximating a convex bodies is studied as well.

FIXED POINT THEOREM OF NONEXPANSIVE MAPPINGS IN CONVEX METRIC SPACES

Let X be a convex metric space with the property that every decreasing sequence of nonenply dosed subsets of X with diameters tending to has menemptyintersection. This paper proved that if T is a mapping of a elosed conver nonempty subset K of X into itself satisfying the inequality:for all x,y in K,where then T has a unique fixed point in K.

Common Fixed Points for a Countable Family of Set-Valued Mappings with Quasi-Contractive Conditions on Metrically Convex Spaces

In this paper, we consider a countable family of set-valued mappings satisfying some quasi-contractive conditions. We also construct a sequence by the quasi-contractive conditions of mappings and the boundary condition of a closed subset of a metrically convex space, and then prove that the unique limit of the sequence is the unique common fixed point of the mappings. Finally, we give more generalized common fixed point theorems for a countable family of single-valued mappings. The main results generalize and improve many common fixed point theorems for a finite or countable family of single valued or set-valued mappings with quasi-contractive conditions.

Predictor-corrector interior-point algorithm for linearly constrained convex programming

Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.

Coincidence Points and Almost-like Coincidence Points on Generalized ConvexSpaces with Applications

We introduce the concept of a weakly G-quasiconvex map with respect to a map on generalized convex spaces and use the concept to prove coincidence point theorems and almost-like coincidence point theorems. As applications of the above results, we derive almost fixed point theorems and fixed point theorem. These main results generalize and improve some known results in the literature.

A Fixed Point Method for Convex Systems

We present a new fixed point technique to solve a system of convex equations in several variables. Our approach is based on two powerful algorithmic ideas: operator-splitting and steepest descent direction. The quadratic convergence of the proposed approach is established under some reasonable conditions. Preliminary numerical results are also reported.

COINCIDENCE POINT THEOREMS iN PROBABILISTIC METRIC SPACES WITH A CONVEX STRUCTURES

In lhis paper we draw some coincidence and common fixed point theorems fornonlinear hybrid contraction mappings on probabilistic metric spaces with a convexstructure.

A Family of Non-Self Maps Satisfying <i>Φ</i>_i-Contractive Condition and Having Unique Common Fixed Point in Metrically Convex Spaces

Class of 5-dimensional functions Φ was introduced and a convergent sequence determined by non-self mappings satisfying certain Φi-contractive condition was constructed, and then that the limit of the sequence is the unique com-mon fixed point of the mappings was proved. Finally, several more general forms were given. Our main results gener-alize and unify many same type fixed point theorems in references.