Characterizations of strict local minima and necessary conditions for weak sharp minima

In nonlinear programming, sufficient conditions of orderm usually identify a special type of local minimizer, here termed a strict local minimizer of orderm. In this paper, it is demonstrated that, if a constraint qualification is satisfied, standard sufficient conditions often characterize this special sort of minimizer. The first- and second-order cases are treated in detail. Necessary conditions for weak sharp local minima of orderm, a larger class of local minima, are also presented.This paper was completed during a sabbatical leave at the University of Waterloo. The author is grateful for the help and support of the Department of Combinatorics and Optimization. The helpful comments of the referees are also appreciated.     

The struction of a graph: Application toCN-free graphs

We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction. This work was completed while this author was visiting the Dept. of Combinatories and Optimization at the University of Waterloo, Ontario.     

Properties of Distortion Risk Measures

The current literature does not reach a consensus on which risk measures should be used in practice. Our objective is to give at least a partial solution to this problem. We study properties that a risk measure must satisfy to avoid inadequate portfolio selections. The properties that we propose for risk measures can help avoid the problems observed with popular measures, like Value at Risk (VaR _α ) or Conditional VaR _α (CVaR _α ). This leads to the definition of two new families: complete and adapted risk measures. Our focus is on risk measures generated by distortion functions. Two new properties are put forward for these: completeness, ensuring that the distortion risk measure uses all the information of the loss distribution, and adaptability, forcing the measure to use this information adequately. This research was partially funded by ^1,3 Welzia Management, SGIIC SA, RD Sistemas SA, Comunidad Autónoma de Madrid Grant s-0505/tic/000230, and MEyC Grant BEC2000-1388-C04-03 and by ² the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 36860-06.     

The complexity of anl p method for discrete Tchebycheff approximation in exact arithmetic

A discrete Tchebycheff problem is approximated by a sequence ofl _p norm problems. This is an algorithm to be used if a large number of variables is involved as is the case in the approximation of a function of several variables by a polynomial. The complexity of this procedure is investigated and a lower bound for the number of steps to reach ε-optimality is established. Supported by NIH Grant RR01243 at the University of Washington     

Acceleration of the leastpth algorithm for minimax optimization with engineering applications

Over the past few years a number of researchers in mathematical programming and engineering became very interested in both the theoretical and practical applications of minimax optimization. The purpose of the present paper is to present a new method of solving the minimax optimization problem and at the same time to apply it to nonlinear programming and to three practical engineering problems. The original problem is defined as a modified leastpth objective function which under certain conditions has the same optimum as the original problem. The advantages of the present approach over the Bandler-Charalambous leastpth approach are similar to the advantages of the augmented Lagrangians approach for nonlinear programming over the standard penalty methods.This work was supported by the National Research Council of Canada under Grant A4414, and from the University of Waterloo.     

Some complete metrics on spaces of fuzzy subsets

The classes of the L_p,∞- and L_p-metrics play an important role to develop a probability theory in fuzzy sample spaces. All of these metrics are known to be separable, but not complete. The classes are closely related as for each L_p,∞-metric there exists some L_p-metric which induces the same topology. This paper deals with the completion of the L_p,∞- and L_p-metrics. We can also show that the relationship between the classes of L_p,∞- and L_p-metrics still holds for the obtained respective classes of their completions.     

A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints

In this article we consider a variant of the classical asymmetric traveling salesman problem (ATSP), namely the ATSP in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed tour. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin, Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989), sequencing in flexible manufacturing (Ascheuer et al., Integer Programming and Combinatorial Optimization, University of Waterloo, Waterloo, 1990, pp. 19–28; Idem., SIAM Journal on Optimization, vol. 3, pp. 25–42, 1993), to stacker crane routing in an automatic storage system (Ascheuer, Ph.D. Thesis, Tech. Univ. Berlin, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&cut-algorithm and give computational results on real-world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances with more than 200 nodes can be solved to optimality within a few minutes of CPU-time. As a side product we obtain a branch&cut-algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time.     

A New Inequality for Weakly （K1, K2）-Quasiregular Mappings

We obtain a new inequality for weakly （K1,K2）-quasiregular mappings by using the McShane extension method. This inequality can be used to derive the self-improving regularity of （K1, K2）-Quasiregular Mappings.     

Nonlinear leastpth optimization and nonlinear programming

Over the past few years a number of researchers in mathematical programming became very interested in the method of the Augmented Lagrangian to solve the nonlinear programming problem. The main reason being that the Augmented Lagrangian approach overcomes the ill-conditioning problem and the slow convergence of the penalty methods. The purpose of this paper is to present a new method of solving the nonlinear programming problem, which has similar characteristics to the Augmented Lagrangian method. The original nonlinear programming problem is transformed into the minimization of a leastpth objective function which under certain conditions has the same optimum as the original problem. Convergence and rate of convergence of the new method is also proved. Furthermore numerical results are presented which illustrate the usefulness of the new approach to nonlinear programming.This work was supported by the National Research Council of Canada and by the Department of Combinatorics and Optimization of the University of Waterloo.     

Higher order Lipschitz classes of functions and absolutely convergent Fourier series

We introduce the higher order Lipschitz classes Λ _r (α) and λ _r (α) of periodic functions by means of the rth order difference operator, where r = 1, 2, ..., and 0 < α ≦ r. We study the smoothness property of a function f with absolutely convergent Fourier series and give best possible sufficient conditions in terms of its Fourier coefficients in order that f belongs to one of the above classes. This research was supported by the Hungarian National Foundation for Scientific Research under Grant T 046 192.     

An application of coding theory to a problem in graphical enumeration

This note was written while the first author was visiting the Department of Combinatorics and Optimization of the University of Waterloo as an Adjunct Professor. He would like to thank his colleagues there for their hospitality. The second author acknowledges the support of the National Science and Engineering Research Council of Canada given under grant #0GP0009258.     

<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-mixed intersection bodies

In this paper the author first introduce a new concept of L _p -dual mixed volumes of star bodies which extends the classical dual mixed volumes. Moreover, we extend the notions of L _p intersection body to L _p -mixed intersection body. Inequalities for L _p -dual mixed volumes of L _p -mixed intersection bodies are established and the results established here provide new estimates for these type of inequalities. This work was supported by the Natural Science Foundation of Zhejiang Province of China (Grant No. Y605065) and the Foundation of the Education Department of Zhejiang Province of China (Grant No. 20050392)     

Uniform Group Divisible Designs with Block Sizes Three and <Emphasis Type="Italic">n</Emphasis>

 The existence of group divisible designs of type g ^t with block sizes three and n, 4≤ n≤10, is completely settled for all values of g and t. Received: July 21, 1999 Final version received: September 10, 2001 RID="*" ID="*" This work was done in 1995 while the authors were graduate students at the University of Waterloo, Waterloo, Ontario N2L 3G1, Canada Acknowledgments. The authors would like to thank the referee for his careful reading and for pointing out some errors in an earlier draft of the paper.     

Zero duality gaps in infinite-dimensional programming

In this paper we study the following infinite-dimensional programming problem: (P) inff ₀(x), subject toxC,f _i(x)0,iI, whereI is an index set with possibly infinite cardinality andC is an infinite-dimensional set. Zero duality gap results are presented under suitable regularity hypotheses for convex-like (nonconvex) and convex infinitely constrained program (P). Various properties of the value function of the convex-like program and its connections to the regularity hypotheses are studied. Relationships between the zero duality gap property, semicontinuity, and -subdifferentiability of the value function are examined. In particular, a characterization for a zero duality gap is given, using the -subdifferential of the value function without convexity.The authors are extremely grateful to the referees for their constructive criticisms and helpful suggestions which have contributed to the final preparation of this paper. This research was partially completed while the first author was a visitor of the Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada.This work was partially supported by NSERC Grant No. A9161.     

Solving ℓ1 Regularization Problems With Piecewise Linear Losses

This article is concerned with the computational aspect of ?₁ regularization problems with a certain class of piecewise linear loss functions. The problem of computing the ?₁ regularization path for a piecewise linear loss can be formalized as a parametric linear programming problem. We propose an efficient implementation method of the parametric simplex algorithm for such a problem. We also conduct a simulation study to investigate the behavior of the number of “breakpoints” of the regularization path when both the number of observations and the number of explanatory variables vary. Our method is also applicable to the computation of the regularization path for a piecewise linear loss and the blockwise ?_∞ penalty. This article has supplementary material online.     

Flatness properties of diagonal acts over monoids

If S is a monoid, the right S-act S×S, equipped with componentwise S-action, is called the diagonal act of S. The question of when this act is cyclic or finitely generated has been a subject of interest for many years, but so far there has been no explicit work devoted to flatness properties of diagonal acts. Considered as a right S-act, the monoid S is free, and thus is also projective, flat, weakly flat, and so on. In 1991, Bulman-Fleming gave conditions on S under which all right acts S ^I (for I a non-empty set) are projective (or, equivalently, when all products of projective right S-acts are projective). At approximately the same time, Victoria Gould solved the corresponding problem for strong flatness. Implicitly, Gould’s result also answers the question for condition (P) and condition (E). For products of flats, weakly flats, etc. to again have the same property, there are some published results as well. The specific questions of when S×S has certain flatness properties have so far not been considered. In this paper, we will address these problems. S. Bulman-Fleming research supported by Natural Sciences and Engineering Research Council of Canada Research Grant A4494. Some of the results in this article are contained in the M.Math. thesis of A. Gilmour, University of Waterloo (2007).     

An Efficient Algorithm for Generating Univariate Cubic L 1 Splines

An active set based algorithm for calculating the coefficients of univariate cubic L ₁ splines is developed. It decomposes the original problem in a geometric-programming setting into independent optimization problems of smaller sizes. This algorithm requires only simple algebraic operations to obtain an exact optimal solution in a finite number of iterations. In stability and computational efficiency, the algorithm outperforms a currently widely used discretization-based primal affine algorithm.     

Differential-geometric Newton method for the best rank-(R1, R2, R3) approximation of tensors

An increasing number of applications are based on the manipulation of higher-order tensors. In this paper, we derive a differential-geometric Newton method for computing the best rank-(R ₁, R ₂, R ₃) approximation of a third-order tensor. The generalization to tensors of order higher than three is straightforward. We illustrate the fast quadratic convergence of the algorithm in a neighborhood of the solution and compare it with the known higher-order orthogonal iteration (De Lathauwer et al., SIAM J Matrix Anal Appl 21(4):1324–1342, 2000). This kind of algorithms are useful for many problems. This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The scientific responsibility rests with its authors. Research supported by: (1) Research Council K.U.Leuven: GOA-Ambiorics, CoE EF/05/006 Optimization in Engineering (OPTEC), (2) F.W.O.: (a) project G.0321.06, (b) Research Communities ICCoS, ANMMM and MLDM, (3) the Belgian Federal Science Policy Office: IUAP P6/04 (DYSCO, “Dynamical systems, control and optimization”, 2007–2011), (4) EU: ERNSI. M. Ishteva is supported by a K.U.Leuven doctoral scholarship (OE/06/25, OE/07/17, OE/08/007), L. De Lathauwer is supported by “Impulsfinanciering Campus Kortrijk (2007–2012)(CIF1)” and STRT1/08/023.     

<Emphasis Type="Italic">∂</Emphasis>-operations and <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">V</Emphasis></Subscript>-fields

The hyperoperations, called theta-operations （δ）, are motivated from the usual property, which the derivative has on the derivation of a product of functions. Using any map on a set, one can define δ-operations. In this paper, we continue our study on the δ-operations on groupoids, rings, fields and vector spaces or on the corresponding hyperstructures. Using δ-operations one obtains, mainly, Hwstructures, which form the largest class of the hyperstructures. For representation theory of hyperstructures, by hypermatrices, one needs special Hv-rings or Hy-fields, so these hyperstructures can be used. Moreover, we study the relation of these δ-structures with other classes of hyperstructures, especially with the Hv-structures.     

Constructions for Octonion and Exceptional Jordan Algebras

In this note we reverse theusual process of constructing the Lie algebras of types G ₂and F ₄ as algebras of derivations of the splitoctonions or the exceptional Jordan algebra and instead beginwith their Dynkin diagrams and then construct the algebras togetherwith an action of the Lie algebras and associated Chevalley groups.This is shown to be a variation on a general construction ofall standard modules for simple Lie algebras and it is well suitedfor use in computational algebra systems. All the structure constantswhich occur are integral and hence the construction specialisesto all fields, without restriction on the characteristic, avoidingthe usual problems with characteristics 2 and 3.