On Minimizing Some Merit Functions for Nonlinear Complementarity Problems under <Emphasis Type="Italic">H</Emphasis>-Differentiability

In this paper, we describe the H-differentials of some well known NCP functions and their merit functions. We show how, under appropriate conditions on an H-differential of f, minimizing a merit function corresponding to f leads to a solution of the nonlinear complementarity problem. Our results give a unified treatment of such results for C ¹-functions, semismooth-functions, and locally Lipschitzian functions. Illustrations are given to show the usefulness of our results. We present also a result on the global convergence of a derivative-free descent algorithm for solving the nonlinear complementarity problem. The first author is deeply indebted to Professor M. Seetharama Gowda for his numerous helpful suggestions and encouragement. Special thanks to Professor J.-P. Crouzeix and an anonymous referees for their constructive suggestions which led to numerous improvements in the paper. The research of the first author was supported in part by the Natural Sciences and Engineering Research Council of Canada and Scholar Activity Grant of Thompson Rivers University. The research of the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

On Two Applications of H-Differentiability to Optimization and Complementarity Problems

In a recent paper, Gowda and Ravindran (Algebraic univalence theorems for nonsmooth functions, Research Report, Department of Mathematics and Statistics, University of Maryland, Baltimore, MD 21250, March 15, 1998) introduced the concepts of H-differentiability and H-differential for a function f : R ⁿ R ⁿ and showed that the Fréchet derivative of a Fréchet differentiable function, the Clarke generalized Jacobian of a locally Lipschitzian function, the Bouligand subdifferential of a semismooth function, and the C-differential of a C-differentiable function are particular instances of H-differentials.In this paper, we consider two applications of H-differentiability. In the first application, we derive a necessary optimality condition for a local minimum of an H-differentiable function. In the second application, we consider a nonlinear complementarity problem corresponding to an H-differentiable function f and show how, under appropriate conditions on an H-differential of f, minimizing a merit function corresponding to f leads to a solution of the nonlinear complementarity problem. These two applications were motivated by numerous studies carried out for C ¹, convex, locally Lipschitzian, and semismooth function by various researchers.     

Equivalence of the generalized complementarity problem to differentiable unconstrained minimization

We consider an unconstrained minimization reformulation of the generalized complementarity problem (GCP). The merit function introduced here is differentiable and has the property that its global minimizers coincide with the solutions of GCP. Conditions for its stationary points to be global minimizers are given. Moreover, it is shown that the level sets of the merit function are bounded under suitable assumptions. We also show that the merit function provides global error bounds for GCP. These results are based on a condition which reduces to the condition of the uniform P-function when GCP is specialized to the nonlinear complementarity problem. This condition also turns out to be useful in proving the existence and uniqueness of a solution for GCP itself. Finally, we obtain as a byproduct an error bound result with the natural residual for GCP.We thank Jong-Shi Pang for his valuable comments on error bound results with the natural residual for the nonlinear complementarity problem. We are also grateful to the anonymous referees for some helpful comments. The research of the second author was supported in part by the Science Research Grant-in-Aid from the Ministry of Education, Science, and Culture, Japan.     

Computation of generalized differentials in nonlinear complementarity problems

Let f and g be continuously differentiable functions on R ⁿ . The nonlinear complementarity problem NCP(f,g), 0≤f(x)⊥g(x)≥0, arises in many applications including discrete Hamilton-Jacobi-Bellman equations and nonsmooth Dirichlet problems. A popular method to find a solution of the NCP(f,g) is the generalized Newton method which solves an equivalent system of nonsmooth equations F(x)=0 derived by an NCP function. In this paper, we present a sufficient and necessary condition for F to be Fréchet differentiable, when F is defined by the “min” NCP function, the Fischer-Burmeister NCP function or the penalized Fischer-Burmeister NCP function. Moreover, we give an explicit formula of an element in the Clarke generalized Jacobian of F defined by the “min” NCP function, and the B-differential of F defined by other two NCP functions. The explicit formulas for generalized differentials of F lead to sharper global error bounds for the NCP(f,g).     

Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥ ₂ ² , we extend results which hold for sufficiently smooth functionsF to the nonsmooth case. In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1+p.     

On the Local Uniqueness of Solutions of Variational Inequalities Under H-Differentiability

In this paper, we give some sufficient conditions for the local uniqueness of solutions to nonsmooth variational inequalities where the underlying functions are H-differentiable and the underlying set is a closed convex set/polyhedral set/box/polyhedral cone. We show how the solution of a linearized variational inequality is related to the solution of the variational inequality. These results extend/unify various similar results proved for C ¹ and locally Lipschitzian variational inequality problems. When specialized to the nonlinear complementarity problem, our results extend/unify those of C ² and C ¹ nonlinear complementarity problems.     

The (<Emphasis Type="Italic">S</Emphasis>)<Subscript>+</Subscript> condition on generalized variational inequalities

In this paper, we derive some existence results for generalized variational inequalities associated with mappings satisfying the (S)₊ condition. The relation between the (S)₊ and (S)₊¹ conditions is discussed. As an application, we also consider multivalued complementarity problems associated with mappings satisfying the (S)₊ condition, and prove a theorem to characterize the solvability of such problems in terms of exceptional families of elements.     

Implicit function theorems for generalized equations

We show that Lipschitz and differentiability properties of a solution to a parameterized generalized equation 0 f(x, y) + F(x), wheref is a function andF is a set-valued map acting in Banach spaces, are determined by the corresponding Lipschitz and differentiability properties of a solution toz g(x) + F(x), whereg strongly approximatesf in the sense of Robinson. In particular, the inverse map (f + F)^–1 has a local selection which is Lipschitz continuous nearx ₀ and Fréchet (Gateaux, Bouligand, directionally) differentiable atx ₀ if and only if the linearization inverse (f (x ₀) + f (x₀) (× – x₀) + F(×))^–1 has the same properties. As an application, we study directional differentiability of a solution to a variational inequality.This work was supported by National Science Foundation Grant Number DMS 9404431.     

Remarks on g-functions on H^n

In this paper, the authors study some properties of Littlewood-Paley g-functions gψ（f）,Lusin area functions Sψ,α（f） and Littlewood-Paley gψ^＊,λ（f） functions defined on H^n, where α,λ 〉 0 and ψ, f are suitable functions. They are the generalization of the corresponding operators on R^n.     

On convex optimization without convex representation

We consider the convex optimization problem P:min_x {f(x) : x ? K}{{\rm {\bf P}}:{\rm min}_{\rm {\bf x}} \{f({\rm {\bf x}})\,:\,{\rm {\bf x}}\in{\rm {\bf K}}\}} where f is convex continuously differentiable, and K ì \mathbb Rⁿ{{\rm {\bf K}}\subset{\mathbb R}^n} is a compact convex set with representation {x ? \mathbb Rⁿ : g_j(x) 3 0, j = 1,?,m}{\{{\rm {\bf x}}\in{\mathbb R}^n\,:\,g_j({\rm {\bf x}})\geq0, j = 1,\ldots,m\}} for some continuously differentiable functions (g _j ). We discuss the case where the g _j ’s are not all concave (in contrast with convex programming where they all are). In particular, even if the g _j are not concave, we consider the log-barrier function f_m{\phi_\mu} with parameter μ, associated with P, usually defined for concave functions (g _j ). We then show that any limit point of any sequence (x_m) ì K{({\rm {\bf x}}_\mu)\subset{\rm {\bf K}}} of stationary points of f_m, m? 0{\phi_\mu, \mu \to 0} , is a Karush–Kuhn–Tucker point of problem P and a global minimizer of f on K.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Generalized -complementarity problems in Banach spaces

In this paper, a class of generalized f-complementarity problems and three classes of variational inequalities are introduced in real Banach spaces, and the equivalences among them are established under certain conditions. Several coercivity conditions are introduced for the existence of solutions of the generalized f-complementarity problem. Under some suitable assumptions, it is shown that each of these coercivity conditions is equivalent to the nonemptyness and boundedness of the solution set for the generalized f-complementarity problem in infinite-dimensional Banach spaces, and even the nonemptyness and compactness of the solution set for the generalized f-complementarity problem in finite-dimensional spaces. The existence of least elements for the feasible set of the generalized f-complementarity problem is also presented under suitable conditions.     

Tail estimates for positive solutions of stochastic heat equation

In this paper, we study the solution of a class of stochastic heat equations of convolution type. We give an explicit solution X _t using two basic tools: the characterization theorem for generalized functions and the convolution calculus. For positive initial condition f and coefficients processes Vt, Mt, we prove that the corresponding solution X _t admits an integral representation by a certain measure. Finally, we compute the tail estimate for the obtained solution and its expectation.     

Generalized Derivations with Invertible or Nilpotent Values on Multilinear Polynomials

Let R be a ring with unity, g a generalized derivation on R and f(X ₁,…,X _k ) a multilinear polynomial. In this article we describe the structure of R provided that g(f(x ₁,…,x _k )) is either invertible or nilpotent for every x ₁,…,x _k in some nonzero ideal of R.     

Estimates in the corona theorem and ideals ofH ∞ : A problem of T. Wolff

The main result of the paper is that there exist functionsf ₁,f ₂,f inH ^∞ satisfying the “corona condition”

On the Hartley – Fourier sine generalized convolution

In this paper, we construct and study a new generalized convolution (f * g)(x) of functions f,g for the Hartley (H₁,H₂) and the Fourier sine (F_s) integral transforms. We will show that these generalized convolutions satisfy the following factorization equalities: We prove the existence of this generalized convolution on different function spaces, such as . As examples, applications to solve a type of integral equations and a type of systems of integral equations are presented. Copyright © 2013 John Wiley & Sons, Ltd.     

On double sine and cosine transforms,Lipschitz and Zygmund classes

We consider complex-valued functions f ∈ L 1 (R+2),where R +:= [0,∞),and prove sufficient conditions under which the double sine Fourier transform f ss and the double cosine Fourier transform f cc belong to one of the two-dimensional Lipschitz classes Lip(α,β) for some 0 α,β≤ 1;or to one of the Zygmund classes Zyg(α,β) for some 0 α,β≤ 2.These sufficient conditions are best possible in the sense that they are also necessary for nonnegative-valued functions f ∈ L 1 (R+2).     

A Principle for Critical Point Under Generalized Regular Constraint and Ill-Posed Lagrange Multipliers Under Nonregular Constraints

In this article, a kind of nonregular constraint and a principle for seeking critical point under the constraint are presented, where no Lagrange multiplier is involved. Let E, F be two Banach spaces, g: E → F a c ¹ map defined on an open set U in E, and the constraint S = the preimage g ^?1(y ₀), y ₀ ∈ F. A main deference between the nonregular constraint and regular constraint is that g′(x) at any x ∈ S is not surjective. Recently, the critical point theory under the nonregular constraint is a concerned focus in optimization theory. The principle also suits the case of regular constraint. Coordinately, the generalized regular constraint is introduced and the critical point principle on generalized regular constraint is established. Let f: U → ? be a nonlinear functional. While the Lagrange multiplier L in classical critical point principle is considered, its expression is given by using generalized inverse g′⁺(x) of g′(x) as follows: if x ∈ S is a critical point of f| _S , then L = f′(x) ○ g′⁺(x) ∈ F*. Moreover, it is proved that if S is a regular constraint, then the Lagrange multiplier L is unique; otherwise, L is ill-posed. Hence, in case of the nonregular constraint, it is very difficult to solve Euler equations; however, it is often the case in optimization theory. So the principle here seems to be new and applicable. By the way, the following theorem is proved: if A ∈ B(E, F) is double split, then the set of all generalized inverses of A, GI(A) is smooth diffeomorphic to certain Banach space. This is a new and interesting result in generalized inverse analysis.