On optimality conditions in nondifferentiable programming

This paper is devoted to necessary optimality conditions in a mathematical programming problem without differentiability or convexity assumptions on the data. The main tool of this study is the concept of generalized gradient of a locally Lipschitz function (and more generally of a lower semi-continuous function). In the first part, we consider local extremization problems in the unconstrained case for objective functions taking values in (–, +]. In the second part, the constrained case is considered by the way of the cone of adherent displacements. In the presence of inequality constraints, we derive in the third part optimality conditions in the Kuhn—Tucker form under a constraint qualification.     

Constraint qualification in a general class of Lipschitzian mathematical programming problems

The Kuhn–Tucker type necessary optimality conditions are given for the problem of minimizing the sum of a differentiable function and a locally Lipschitzian function subject to a set of differentiable nonlinear inequalities on a convex subset C of , under the condition of a generalized Kuhn–Tucker constraint qualification or a generalized Arrow–Hurwicz–Uzawa constraint qualification. The case when the set C is open is shown to be a special one of our results, which helps us to improve some of the existing results in the literature. To finish we consider several test problems.     

Geometry of optimality conditions and constraint qualifications: The convex case

The cones of directions of constancy are used to derive: new as well as known optimality conditions; weakest constraint qualifications; and regularization techniques, for the convex programming problem. In addition, the badly behaved set of constraints, i.e. the set of constraints which causes problems in the Kuhn—Tucker theory, is isolated and a computational procedure for checking whether a feasible point is regular or not is presented.This research was supported by the National Research Council of Canada and le Gouvernement du Quebec and is part of the author's Ph.D. Dissertation done at McGill University, Montreal, Que., under the guidance of Professor S. Zlobec.     

On the complexity of approximating a KKT point of quadratic programming

We present a potential reduction algorithm to approximate a Karush—Kuhn—Tucker (KKT) point of general quadratic programming (QP). We show that the algorithm is a fully polynomial-time approximation scheme, and its running-time dependency on accuracy (0, 1) is O((l/) log(l/) log(log(l/))), compared to the previously best-known result O((l/)²). Furthermore, the limit of the KKT point satisfies the second-order necessary optimality condition of being a local minimizer. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research support in part by NSF grants DDM-9207347 and DMI-9522507, and the Iowa Business School Summer Grant.     

A priori estimates on the semiaxis t≥0 for the solutions of the equations of motion of linear viscoelastic fluids with an infinite Dirichlet integral,and their applications

The solvability on the semiaxis t0 of initial-boundary value problems are investigated for the equations of the motion of linear viscoelastic fluids — Oldroyd fluids and Kelvin—Voight fluids—for which the right-hand sides satisfy the conditions f, f_t L(R⁺; L₂()). The existence of small stable solutions, periodic with respect to t, is proved for the equations of the motion of Oldroyd fluids and Kelvin—Voight fluids, with a small right-hand side f, periodic with respect to t.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 182, pp. 86–101, 1990.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

A characterization of Gaussian measures on locally compact Abelian groups

Let and be independent random variables having equal variance. In order that + and – be independent, it is necessary and sufficient that and have normal distributions. This result of Bernshtein [1] is carried over in [7] to the case when and take values in a locally compact Abelian group. In the present note, a characterization of Gaussian measures on locally compact Abelian groups is given in which in place of + and –, functions of and are considered which satisfy the associativity equation.Translated from Matematicheskie Zametki, Vol. 22, No. 5, pp. 759–762, November, 1977.     

Constraint qualifications in quasidifferentiable optimization

The classical linearization procedure for differentiable nonlinear programming problems can be naturally generalized to the quasidifferentiable case. As in the classical case one has to impose so-called constraint qualifications on the constraint functions in order to ensure that optimality of a feasible point implies optimality of the nullvector for the corresponding quasilinearized problem. We present various constraint qualifications in a unified setting, propose a new one, and investigate the relations between these conditions.Supported by DFG Grant Pa 219/5-1.     

A Hubert space characterization among function spaces

— [0,1] ,E — - e=1 [0,1]. I — _E =1, E=L ₂ x _e =xL ₂ x E.

---

---

This work was prepared when the second author was a visiting professor of the CNR at the University of Firenze. He was supported by the Soros International Fund.     

A relation between spline approximation and the problem of the approximation of one class by another

An investigation of the approximation in L_q(–, ) of differentiable functions whose k-th derivatives belong to L_p(–, ), by splines S_m (x) with nonfixed nodes, under the extra assumption that the norms in L_s(–, ) of theirl-th derivatives have a common bound. A relation is established with the problem of approximating functions of one class by functions of another class.Translated from Matematicheskie Zametki, Vol. 9, No. 5, pp. 501–510, May, 1971.     

Indépendance conditionnelle et uniformité pour les lois fortes des grands nombres dans les espaces de Banach

Summary A. Beck has given an uniform strong law of large numbers for families of mutually symmetric and uniformly essentially bounded sequences of centered random variables, with values in (k, )—B-convex spaces. We show that, without any limitation on the Banach spaces, the technique used by A. Beck allows to replace, in strong law of large numbers making use of conditions bearing on essential bounds, the hypothesis of independence by an hypothesis called conditional-independence-and-centering, which is weaker than both hypothesis of independence and of mutual symmetry; moreover, in several cases, one gets uniform strong laws of large numbers (for families of conditionally-independent-and-centered sequences). The results we get are compared with recent results of G. Pisier, obtained with type p spaces techniques.     

Characterizing the Single-Valuedness of Multifunctions

We characterize the local single-valuedness and continuity of multifunctions (set-valued mappings) in terms of their premonotonicity and lower semicontinuity. This result completes the well-known fact that lower semicontinuous, monotone multifunctions are single-valued and continuous. We also show that a multifunction is actually a Lipschitz single-valued mapping if and only if it is premonotone and has a generalized Lipschitz property called Aubin continuity. The possible single-valuedness and continuity of multifunctions is at the heart of some of the most fundamental issues in variational analysis and its application to optimization. We investigate the impact of our characterizations on several of these issues; discovering exactly when certain generalized subderivatives can be identified with classical derivatives, and determining precisely when solutions to generalized variational inequalities are locally unique and Lipschitz continuous. As an application of our results involving generalized variational inequalities, we characterize when the Karush–Kuhn–Tucker pairs associated with a parameterized optimization problem are locally unique and Lipschitz continuous.     

Upper Subderivatives and Generalized Gradients of the Marginal Function of a Non-Lipschitzian Program

We obtain an upper bound for the upper subderivative of the marginal function of an abstract parametric optimization problem when the objective function is lower semicontinuous. Moreover, we apply the result to a nonlinear program with right-hand side perturbations. As a result, we obtain an upper bound for the upper subderivative of the marginal function of a nonlinear program with right-hand side perturbations, which is expressed in dual form in terms of appropriate Lagrange multipliers. Finally, we present conditions which imply that the marginal function is locally Lipschitzian.     

A new class of cutting planes for the symmetric travelling salesman problem

A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known comb inequalities, the path inequalities and the 3-star constraints as special cases. Its relation to the clique tree inequalities is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and—under certain conditions—to define facets of the polyhedron associated with this problem.     

Contingent Derivatives of Implicit (Multi-) Functions and Stationary Points

For an implicit multifunction (p) defined by the generally nonsmooth equation F(x,p)=0, contingent derivative formulas are derived, being similar to the formula =–F _x ^–1 F _p in the standard implicit function theorem for smooth F and . This will be applied to the projection X(p)={xy: (x,y)(p)} of the solution set (p) of the system F(x,y,p)=0 onto the x-space. In particular settings, X(p) may be interpreted as stationary solution sets. We discuss in detail the situation in which X(p) arises from the Karush–Kuhn–Tucker system of a nonlinear program.     

Semimodular lattices with isomorphic graphs

Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik.     

A Uniqueness Result for an Overdetermined Problem in Non-Linear Parabolic Potential Theory

In this paper we study the question of uniqueness for an inverse problem, arising in the (thermal) linear and/or non-linear potential theory. The overdetermined problem we shall study is represented by(div(|u| ^p–2u)–D _t u–+)u=0where supp()R ⁿ ×(0,), 1<p<, L and {t=} is bounded for >0.The problem has applications in shape-recognition in underground water/oil recovery, subject to shape-change during time intervals. The particular case u0, D _t u0, and p=2, is an example of the well-known Stefan.     

Admissibility of linear estimators of regression coefficients under quadratic loss

For the general fixed effects linear model:Y=X+, N(0,V),V0, we obtain the necessary and sufficient conditions forLY+a to be admissible for a linear estimable functionS in the class of all estimators under the loss function (d -S)D(d -S), whereD0 is known. For the general random effects linear model: =XV ₁₁ X+XV ₁₂+V ₂₁ X+V ₂₂0, we also get the necessary and sufficient conditions forLY+a to be admissible for a linear estimable functionS+Q in the class of all estimators under the loss function (d -S -Q)D(d -S -Q), whereD0 is known.     

Some best possible bounds concerning the traces of finite sets II

LetX be ann-element set and be a family of its subsets. Consider the family _x = {F – {x} : F } for a givenx X. We write(m, n) (m – k, n – 1), when for all with || m, there exists an elementx ofX such that| _x| m – k. We show that (m, n) (m – 10,n – 1) for allm 5n and (m, n) (m – 13,n – 1) for allm 29n/5.     

An explicit solution of the linear filtering problem for certain classes of nonrational spectral densities

We present an explicit solution of the problem of optimal linear filtering: the recovery of the useful signal(s) at the instantt+, (>0,<0, or=0) from known values of the received signal(s)=(s)+(s) in the past, i.e., at the instantt–s, s0. In doing so we assume the random processes(s) and /gr(s) are stationary and jointly stationary, while the stationary process of noise (s) with zero mean is assumed to be mutually correlated and jointly stationary with the process(s) under the assumption that there exists a common spectral densityf() for these processes.Translated fromTeoriya Sluchaínykh Protsessov, Vol. 14, pp. 83–91, 1986.