A problem on convex functions

A conjecture is made on convex functions. It leads to the problem of characterizing a class of convex functions, which is of interest both from the theoretical point of view and in the field of minimization methods.     

Numerical decomposition of a convex function

Given then×p orthogonal matrixA and the convex functionf:R ⁿR, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).     

On convex decompositions of a planar point set

Let P be a planar point set in general position. Neumann-Lara et al. showed that there is a convex decomposition of P with at most elements. In this paper, we improve this upper bound to .     

On a special class of convex functions

We answer in the affirmative to a conjecture concerning convex functions.     

Some results on the convex hull of finitely many convex sets

A better than quadratic estimate is given for the volume of the convex hull of points on Hadamard manifolds with pinched curvature. It was known previously that the volume is bounded by some polynomial in . The estimate comes from the study of the convex hull of finitely many convex sets on Hadamard manifolds.

     

Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces

We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a half-space or onto the intersection of two half-spaces. Convergence of the algorithm is established and special choices of the half-spaces are proposed.The option to project onto half-spaces instead of general convex sets makes the algorithm more practical. The fact that the half-spaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms.The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super half-spaces, i.e., half-spaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super half-space from a family of such half-spaces. Since projecting a point onto a half-space is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super half-spaces themselves is not too difficult.     

On the structure of convex piecewise quadratic functions

Convex piecewise quadratic functions (CPQF) play an important role in mathematical programming, and yet their structure has not been fully studied. In this paper, these functions are categorized into difference-definite and difference-indefinite types. We show that, for either type, the expressions of a CPQF on neighboring polyhedra in its domain can differ only by a quadratic function related to the common boundary of the polyhedra. Specifically, we prove that the monitoring function in extended linear-quadratic programming is difference-definite. We then study the case where the domain of the difference-definite CPQF is a union of boxes, which arises in many applications. We prove that any such function must be a sum of a convex quadratic function and a separable CPQF. Hence, their minimization problems can be reformulated as monotropic piecewise quadratic programs.This research was supported by Grant DDM-87-21709 of the National Science Foundation.     

The conjugate of the difference of convex functions

Given an arbitrary functiong and a convex functionh, we derive the expression of the conjugate ofg —h via a simple proof.     

On the number of disjoint convex quadrilaterals for a planar point set

For a given planar point set P, consider a partition of P into disjoint convex polygons. In this paper, we estimate the maximum number of convex quadrilaterals in all partitions.     

Dini derivative and a characterization for Lipschitz and convex functions on Riemannian manifolds

Dini derivatives in Riemannian manifold settings are studied in this paper. In addition, a characterization for Lipschitz and convex functions defined on Riemannian manifolds and sufficient optimality conditions for constraint optimization problems in terms of the Dini derivative are given.     

Some exact iterative procedures for finding the puncture point of a convex set

LetK be a convex set in the Hilbert spaceH, and let the ray {c: R} punctureK at *c. Some algorithms are given for finding *. Each algorithm results in a nonincreasing sequence { _i } which converges to *. The points _j c lie in successive supporting hyperplanes toK. The normal to thenth hyperplane is obtained by a minimization over a set no larger than the unitn cube. It is assumed that the subset ofK which maximizes (,x) forx inK is found relatively easily.This research was sponsored by NSF Grant No. MCS-76-11040.     

A general theory of almost convex functions

Let be the standard -dimensional simplex and let . Then a function with domain a convex set in a real vector space is -almost convex iff for all and the inequality

holds. A detailed study of the properties of -almost convex functions is made. If contains at least one point that is not a vertex, then an extremal -almost convex function is constructed with the properties that it vanishes on the vertices of and if is any bounded -almost convex function with on the vertices of , then for all . In the special case , the barycenter of , very explicit formulas are given for and . These are of interest, as and are extremal in various geometric and analytic inequalities and theorems.

     

Three-term conjugate gradient method for the convex optimization problem over the fixed point set of a nonexpansive mapping

Many constrained sets in problems such as signal processing and optimal control can be represented as a fixed point set of a certain nonexpansive mapping, and a number of iterative algorithms have been presented for solving a convex optimization problem over a fixed point set. This paper presents a novel gradient method with a three-term conjugate gradient direction that is used to accelerate conjugate gradient methods for solving unconstrained optimization problems. It is guaranteed that the algorithm strongly converges to the solution to the problem under the standard assumptions. Numerical comparisons with the existing gradient methods demonstrate the effectiveness and fast convergence of this algorithm.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].     

On the convolution and subordination of convex functions

In this work we present some new results on convolution and subordination in geometric function theory. We prove that the class of convex functions of order α is closed under convolution with a prestarlike function of the same order. Using this, we prove that subordination under the convex function order α is preserved under convolution with a prestarlike function of the same order. Moreover, we find a subordinating factor sequence for the class of convex functions. The work deals with several ideas and techniques used in geometric function theory, contained in the book Convolutions in Geometric Function Theory by Ruscheweyh (1982).     

Asymptotics of the convex hull of spherically symmetric samples

In this paper we consider the convex hull of a spherically symmetric sample in R^d. Our main contributions are some new asymptotic results for the expectation of the number of vertices, number of facets, area and the volume of the convex hull assuming that the marginal distributions are in the Gumbel max-domain of attraction. Further, we briefly discuss two other models assuming that the marginal distributions are regularly varying or O-regularly varying.     

Smooth approximation of convex functions in Banach spaces

This paper shows that every extended-real-valued lower semi-continuous proper (respectively Lipschitzian) convex function defined on an Asplund space can be represented as the point-wise limit (respectively uniform limit on every bounded set) of a sequence of Lipschitzian convex functions which are locally affine (hence, C^∞) at all points of a dense open subset; and shows an analogous for w^∗-lower semi-continuous proper (respectively Lipschitzian) convex functions defined on dual spaces whose pre-duals have the Radon-Nikodym property.     

Coefficient bounds for some families of starlike and convex functions of complex order

In the present work, the authors determine coefficient bounds for functions in certain subclasses of starlike and convex functions of complex order, which are introduced here by means of a family of nonhomogeneous Cauchy–Euler differential equations. Several corollaries and consequences of the main results are also considered.