Strong Geodesic Convex Functions of Order m

Abstract

Strong geodesic convex function and strong monotone vector field of order m on Riemannian manifolds are established. A characterization of strong geodesic convex function of order m for the continuously differentiable functions is discussed. The relation between the solution of a new variational inequality problem and the strict minimizers of order m for a multiobjective programing problem is also established.     

Canonical dual least square method for solving general nonlinear systems of quadratic equations

This paper presents a canonical dual approach for solving general nonlinear algebraic systems. By using least square method, the nonlinear system of m-quadratic equations in n-dimensional space is first formulated as a nonconvex optimization problem. We then proved that, by the canonical duality theory developed by the second author, this nonconvex problem is equivalent to a concave maximization problem in ℝ ^m , which can be solved easily by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.     

Infinitesimal Rigidity of Convex Polytopes

Aleksandrov [1] proved that a simple convex d -dimensional polytope, d ≥ 3 , is infinitesimally rigid if the volumes of its facets satisfy a certain assumption of stationarity. We extend this result by proving that this assumption can be replaced by a stationarity assumption on the k -dimensional volumes of the polytope's k -dimensional faces, where k ∈{1,. . .,d-1} . Received November 20, 1997.     

Set Containment Characterization

Characterization of the containment of a polyhedral set in a closed halfspace, a key factor in generating knowledge-based support vector machine classifiers [7], is extended to the following: (i) containment of one polyhedral set in another; (ii) containment of a polyhedral set in a reverse-convex set defined by convex quadratic constraints; (iii) Containment of a general closed convex set, defined by convex constraints, in a reverse-convex set defined by convex nonlinear constraints. The first two characterizations can be determined in polynomial time by solving m linear programs for (i) and m convex quadratic programs for (ii), where m is the number of constraints defining the containing set. In (iii), m convex programs need to be solved in order to verify the characterization, where again m is the number of constraints defining the containing set. All polyhedral sets, like the knowledge sets of support vector machine classifiers, are characterized by the intersection of a finite number of closed halfspaces.     

Ensembles maximaux accrétifs etm-Accrétifs

It is proved that ifX is a uniformly convex Banach space such thatX ^* is also uniformly convex andX is not a Hilbert space then there always exists a subsetA ofX×X which is maximal accretive but notm-accretive.      

A characterization ofC 1-convex sets in Sobolev spaces

In this paper we prove that, ifK is a closed subset ofW ₀ ^1,p (Ω,R ^m ) with 1<p<+∞ andm≥1, thenK is stable under convex combinations withC ¹ coefficients if and only if there exists a closed and convex valued multifunction from Ω toR ^m such that The casem=1 has already been studied by using truncation arguments which rely on the order structure ofR (see [2]). In the casem>1 a different approach is needed, and new techniques involving suitable Lipschitz projections onto convex sets are developed. Our results are used to prove the stability, with respect to the convergence in the sense of Mosco, of the class of convex sets of the form (*); this property may be useful in the study of the limit behaviour of a sequence of variational problems of obstacle type. This article was processed by the author using the Springer-Verlag TEX mamath macro package 1990     

Construction of a linear Pfaff system with <Emphasis Type="Italic">m</Emphasis>-dimensional time and with given characteristic set and lower characteristic set

For any positive integers n ≥ 1 and m ≥ 2, we give a constructive proof of the existence of linear n-dimensional Pfaff systems with m-dimensional time and with infinitely differentiable coefficient matrices such that the characteristic and lower characteristic sets of these systems are given sets that are the graphs of a concave continuous function and a convex continuous function, respectively, defined and monotone decreasing on simply connected closed bounded convex domains of the space ?^m?1.     

Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m ? 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m ? 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.     

The Dirichlet problem for the minimal surface system in arbitrary dimensions and codimensions

Let Ω be a bounded C² domain in ?ⁿ and ? ?Ω → ?^m be a continuous map. The Dirichlet problem for the minimal surface system asks whether there exists a Lipschitz map f : Ω → ?^m with f|_?Ω = ? and with the graph of f a minimal submanifold in ?^n+m. For m = 1, the Dirichlet problem was solved more than 30 years ago by Jenkins and Serrin [12] for any mean convex domains and the solutions are all smooth. This paper considers the Dirichlet problem for convex domains in arbitrary codimension m. We prove that if ψ : ¯Ω → ?^m satisfies 8nδ sup_Ω |D²ψ| + √2 sup_?Ω |Dψ| < 1, then the Dirichlet problem for ψ|_?Ω is solvable in smooth maps. Here δ is the diameter of Ω. Such a condition is necessary in view of an example of Lawson and Osserman [13]. In order to prove this result, we study the associated parabolic system and solve the Cauchy‐Dirichlet problem with ψ as initial data. © 2003 Wiley Periodicals, Inc.     

Block-Coordinate Gradient Descent Method for?Linearly Constrained Nonsmooth Separable Optimization

We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O(n ²/ε) iterations with an ε-optimal solution. If P is separable, then the Gauss-Southwell-q rule is implementable in O(n) operations when m=1 and in O(n ²) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m=1, this complexity bound is comparable to the best known bound for decomposition methods. If f is convex, then, by gradually reducing the weight on P to zero, the method can be adapted to solve the bilevel problem of minimizing P over the set of minima of f+δ _X , where X denotes the closure of the feasible set. This has application in the least 1-norm solution of maximum-likelihood estimation. This research was supported by the National Science Foundation, Grant No. DMS-0511283.     

Second order necessary and sufficient conditions for convex composite NDO

In convex composite NDO one studies the problem of minimizing functions of the formF:=h ○f whereh:ℝ ^m → ℝ is a finite valued convex function andf:ℝ ⁿ → ℝ ^m is continuously differentiable. This problem model has a wide range of application in mathematical programming since many important problem classes can be cast within its framework, e.g. convex inclusions, minimax problems, and penalty methods for constrained optimization. In the present work we extend the second order theory developed by A.D. Ioffe in [11, 12, 13] for the case in whichh is sublinear, to arbitrary finite valued convex functionsh. Moreover, a discussion of the second order regularity conditions is given that illuminates their essentially geometric nature.     

The spectrum of the Leray transform for convex Reinhardt domains in

The Leray transform and related boundary operators are studied for a class of convex Reinhardt domains in . Our class is self-dual; it contains some domains with less than C²-smooth boundary and also some domains with smooth boundary and degenerate Levi form. L²-regularity is proved, and essential spectra are computed with respect to a family of boundary measures which includes surface measure. A duality principle is established providing explicit unitary equivalence between operators on domains in our class and operators on the corresponding polar domains. Many of these results are new even for the classical case of smoothly bounded strongly convex Reinhardt domains.     

Nodal lines of eigenfunctions of the fixed membrane problem in general convex domains

We describe the boundary behavior of the nodal lines of eigenfunctions of the fixed membrane problem in convex, possibly nonsmooth, domains. This result is applied to the proof of Payne’s conjecture on the nodal line of second eigenfunctions [P1], by removing theC ^∞ smoothness assumption which is present in the original proof of Melas [M].     

Convex integration with constraints and applications to phase transitions and partial differential equations

We study solutions of first order partial differential relations Du∈K, where u:Ω⊂ℝ ⁿ →ℝ ^m is a Lipschitz map and K is a bounded set in m×n matrices, and extend Gromov’s theory of convex integration in two ways. First, we allow for additional constraints on the minors of Du and second we replace Gromov’s P-convex hull by the (functional) rank-one convex hull. The latter can be much larger than the former and this has important consequences for the existence of ‘wild’ solutions to elliptic systems. Our work was originally motivated by questions in the analysis of crystal microstructure and we establish the existence of a wide class of solutions to the two-well problem in the theory of martensite. Received April 23, 1999 / final version received September 11, 1999     

Duality for optimization and best approximation over finite intersections

Recently Deutsch, Li and Swetits [2] have studied, in Hilbert space, a dual problem (Q_m ) to the primal problem (P) of minimization of a special class of convex functions f over the intersection of m closed convex sets, where m is finite. In the first part of this paper we obtain, in a locally convex space, some results on problem (Q_m ) and on its relations with the usual Lagrangian dual problem (Q) to (P) (studied in [9]), in the case when (P) has a solution. In the second part we give some applications to duality for the distance to the intersection of m closed convex sets in a normed linear space, in the case when a nearest point exists. Most of our results seem to be new even in the particular cases studied in [9] (the case m = 1), [l] (duality formulas for the distance to the intersection of m closed half-spaces in a normed linear space) and [2].     

The advantage of small machines in a stochastic fluid production process

We consider a stochastic fluid production model, where m machines which are subject to breakdown and repair, produce a fluid at ratep > 0 per machine if it is working. This fluid is fed into an infinite buffer with stochastic output rate. Under the assumption that the machine processes are independent and identically distributed, we prove that the buffer content at timet is less or equal in the increasing convex ordering to the buffer content at time t of a model withm m machines and production ratep =m/m p. This formulation includes a conjecture posed by Mitra [6]. More-over, it is shown how to extend this result to Brownian flow systems, systems obtained by diffusion approximation and simple stochastic flow networks like tandem buffer and assembly systems.     

Finite element methods for semilinear elliptic problems with smooth interfaces

The purpose of this paper is to study the finite element method for second order semilinear elliptic interface problems in two dimensional convex polygonal domains. Due to low global regularity of the solution, it seems difficult to achieve optimal order of convergence with straight interface triangles [Numer. Math., 79 (1998), pp. 175–202]. For a finite element discretization based on a mesh which involve the approximation of the interface, optimal order error estimates in L ² and H ¹-norms are proved for linear elliptic interface problem under practical regularity assumptions of the true solution. Then an extension to the semilinear problem is also considered and optimal error estimate in H ¹ norm is achieved.     

Approximation of the Jacobian matrix in (<Emphasis Type="Italic">m</Emphasis>, 2)-methods for solving stiff problems

An initial value problem for stiff systems of first-order ordinary differential equations is considered. In the class of (m, k)-methods, two integration algorithms with a variable step size based on second (m = k = 2) and third (k = 2, m = 3) order-accurate schemes are constructed in which both analytical and numerical Jacobian matrices can be frozen. A theorem on the maximum order of accuracy of (m, 2)-methods with a certain approximation of the Jacobian matrix is proved. Numerical results are presented.     

Minimization of convex functions on the convex hull of a point set

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in R ⁿ is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in R ^m , which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.