ɛ-Subdifferentials of Set-valued Maps and ɛ-Weak Pareto Optimality for Multiobjective Optimization

In this paper we consider vector optimization problems where objective and constraints are set-valued maps. Optimality conditions in terms of Lagrange-multipliers for an ɛ-weak Pareto minimal point are established in the general case and in the case with nearly subconvexlike data. A comparison with existing results is also given. Our method used a special scalarization function, introduced in optimization by Hiriart-Urruty. Necessary and sufficient conditions for the existence of an ɛ-weak Pareto minimal point are obtained. The relation between the set of all ɛ-weak Pareto minimal points and the set of all weak Pareto minimal points is established. The ɛ-subdifferential formula of the sum of two convex functions is also extended to set-valued maps via well known results of scalar optimization. This result is applied to obtain the Karush–Kuhn–Tucker necessary conditions, for ɛ-weak Pareto minimal points     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique. Received: April 2002 / Accepted: December 2002 Published online: March 21, 2003 RID="⋆" ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587. Key Words. global optimization – multiextremal constraints – local tuning – index approach     

A note on global optimization via the heat diffusion equation

We consider the interesting smoothing method of global optimization recently proposed in Lau and Kwong (J Glob Optim 34:369–398, 2006) . In this method smoothed functions are solutions of an initial-value problem for a heat diffusion equation with external heat source. As shown in Lau and Kwong (J Glob Optim 34:369–398, 2006), the source helps to control global minima of the smoothed functions—they are not shifted during the smoothing. In this note we point out that for certain (families of) objective functions the proposed method unfortunately does not affect the functions, in the sense, that the smoothed functions coincide with the respective objective function. The key point here is that the Laplacian might be too weak in order to smooth out critical points.     

Strong Kuhn–Tucker conditions and constraint qualifications in locally Lipschitz multiobjective optimization problems

We consider a Pareto multiobjective optimization problem with a feasible set defined by inequality and equality constraints and a set constraint, where the objective and inequality constraints are locally Lipschitz, and the equality constraints are Fréchet differentiable. We study several constraint qualifications in the line of Maeda (J. Optim. Theory Appl. 80: 483–500, 1994) and, under the weakest ones, we establish strong Kuhn–Tucker necessary optimality conditions in terms of Clarke subdifferentials so that the multipliers of the objective functions are all positive.     

Globally Convergent Cutting Plane Method for Nonconvex Nonsmooth Minimization

Nowadays, solving nonsmooth (not necessarily differentiable) optimization problems plays a very important role in many areas of industrial applications. Most of the algorithms developed so far deal only with nonsmooth convex functions. In this paper, we propose a new algorithm for solving nonsmooth optimization problems that are not assumed to be convex. The algorithm combines the traditional cutting plane method with some features of bundle methods, and the search direction calculation of feasible direction interior point algorithm (Herskovits, J. Optim. Theory Appl. 99(1):121–146, 1998). The algorithm to be presented generates a sequence of interior points to the epigraph of the objective function. The accumulation points of this sequence are solutions to the original problem. We prove the global convergence of the method for locally Lipschitz continuous functions and give some preliminary results from numerical experiments.     

A combined DCA: GA for constructing highly nonlinear balanced boolean functions in cryptography

Substitution boxes, aka S-boxes, are a key component of modern crypto-systems. Several studies and developments were carried out on the problem of building high-quality S-boxes in the last few years. Qualities of such boxes, such as nonlinearity and balance, steer the robustness of modern block ciphers. This work is concerned with the construction of highly nonlinear balanced Boolean functions. A deterministic optimization model which is the minimization of a polyhedral convex function on a convex polytope with 0–1 variables is introduced. A local deterministic optimization approach called DCA (Difference of Convex functions Algorithm) is investigated. For finding a good starting point of DCA we propose two versions of a combined DCA–GA (Genetic Algorithm) method. Numerical simulations prove that DCA is a promising approach for this problem. Moreover the combination of DCA–GA improves the efficiency of DCA and outperforms other standard approaches.     

Nonsmooth ρ ? (η, θ)-invexity in multiobjective programming problems

In this paper we extend Reiland’s results for a nonlinear (single objective) optimization problem involving nonsmooth Lipschitz functions to a nonlinear multiobjective optimization problem (MP) for ρ − (η, θ)-invex functions. The generalized form of the Kuhn–Tucker optimality theorem and the duality results are established for (MP).     

Variational conditions with smooth constraints: structure and analysis

 This is an expository paper about the analysis of variational conditions over sets defined in finite-dimensional spaces by fairly smooth functions satisfying a constraint qualification. The primary focus is on results that can provide quantitative and computable sensitivity information for particular instances of the problems under study, and our objective is to give a personal view of the state of current knowledge in this area and of gaps in that knowledge that require future work. The writing style is informal, in keeping with the objective of focusing the reader's attention on the basic concepts and the relationships between them, rather than on details of the particular results themselves. Received: December 1, 2002 / Accepted: April 25, 2003 Published online: May 28, 2003 Key words. variational condition – variational inequality – complementarity – sensitivity – stability – nondegeneracy Mathematics Subject Classification (2000): Primary: 90C31. Secondary: 47J20, 49J40, 49J53, 90C33     

System of Generalized Vector Quasi-Equilibrium Problems in Locally FC-Spaces

A new class of locally finite continuous topological spaces （for short, locally FC-spaces） and a class of system of generalized vector quasi-equilibrium problems are introduced. By applying a generalized Himmelberg type fixed point theorem for a set-valued mapping with KKM-property due to the author, a collectively fixed point and an equilibrium existence theorem of generalized game are first proved in locally FC-spaces. By applying our equilibrium existence theorem of generalized game, some new existence theorems of equilibrium points for the system of generalized vector quasi-equilibrium problems are proved in locally FC-spaces. These theorems improve, unify and generalize many known results in the literatures.     

Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation,convergence and numerical results

An Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by Weiser et al. (Optim Methods Softw 22(3):413–431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective function is determined, and this ensures a significant improvement in the objective so long as the Hessian of the objective is locally Lipschitz continuous. The new method uses an adaptive estimation of the local Lipschitz constant and approximations to the global model-minimizer which remain computationally-viable even for large-scale problems. We show that the excellent global and local convergence properties obtained by Nesterov and Polyak are retained, and sometimes extended to a wider class of problems, by our ARC approach. Preliminary numerical experiments with small-scale test problems from the CUTEr set show encouraging performance of the ARC algorithm when compared to a basic trust-region implementation.     

Necessary Optimality Conditions and a New Approach to Multiobjective Bilevel Optimization Problems

Multiobjective optimization problems typically have conflicting objectives, and a gain in one objective very often is an expense in another. Using the concept of Pareto optimality, we investigate a multiobjective bilevel optimization problem (say, P). Our approach consists of proving that P is locally equivalent to a single level optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification may hold at any feasible solution. With the help of a special scalarization function introduced in optimization by Hiriart–Urruty, we convert our single level optimization problem into another problem and give necessary optimality conditions for the initial multiobjective bilevel optimization problem P.     

On non-smooth α-invex functions and vector variational-like inequality

In this paper, we establish some relationships between vector variational-like inequality and non-smooth vector optimization problems under the assumptions of α-invex non-smooth functions. We identify the vector critical points, the weakly efficient points and the solutions of the weak vector variational-like inequality, under non-smooth pseudo-α-invexity assumptions. These conditions are more general than those of existing ones in the literature. In particular, this work extends an earlier work of Ruiz-Garzon et al. (J Oper Res 157:113–119, 2004) to a wider class of functions, namely the non-smooth pseudo-α-invex functions. Moreover, this work extends an earlier work of Mishra and Noor (J Math Anal Appl 311:78–84, 2005) to non-differentiable case.     

Nilpotent groups admitting an almost regular automorphism of order four

We consider locally nilpotent periodic groups admitting an almost regular automorphism of order 4. The following are results are proved: (1) If a locally nilpotent periodic group G admits an automorphism ϕ of order 4 having exactly m<∞ fixed points, then (a) the subgroup {ie176-1} contains a subgroup of m-bounded index in {ie176-2} which is nilpotent of m-bounded class, and (b) the group G contains a subgroup V of m-bounded index such that the subgroup {ie176-3} is nilpotent of m-bounded class (Theorem 1); (2) If a locally nilpotent periodic group G admits an automorphism ϕ of order 4 having exactly m<∞ fixed points, then it contains a subgroup V of m-bounded index such that, for some m-bounded number f(m), the subgroup {ie176-4}, generated by all f(m) th powers of elements in {ie176-5} is nilpotent of class ≤3 (Theorem 2). Supported by RFFR grant No. 94-01-00048 and by ISF grant NQ7000. Translated fromAlgebra i Logika, Vol. 35, No. 3, pp. 314–333, May–June, 1996.     

From Scalar to Vector Optimization

Initially, second-order necessary optimality conditions and sufficient optimality conditions in terms of Hadamard type derivatives for the unconstrained scalar optimization problem ϕ(x) → min, x ∈ ℝ ^m , are given. These conditions work with arbitrary functions ϕ: ℝ ^m → ℝ, but they show inconsistency with the classical derivatives. This is a base to pose the question whether the formulated optimality conditions remain true when the “inconsistent” Hadamard derivatives are replaced with the “consistent” Dini derivatives. It is shown that the answer is affirmative if ϕ is of class (i.e., differentiable with locally Lipschitz derivative). Further, considering functions, the discussion is raised to unconstrained vector optimization problems. Using the so called “oriented distance” from a point to a set, we generalize to an arbitrary ordering cone some second-order necessary conditions and sufficient conditions given by Liu, Neittaanmaki, Krizek for a polyhedral cone. Furthermore, we show that the conditions obtained are sufficient not only for efficiency but also for strict efficiency.     

Solving monotone inclusions with linear multi-step methods

 In this paper a new class of proximal-like algorithms for solving monotone inclusions of the form T(x)∋0 is derived. It is obtained by applying linear multi-step methods (LMM) of numerical integration in order to solve the differential inclusion , which can be viewed as a generalization of the steepest decent method for a convex function. It is proved that under suitable conditions on the parameters of the LMM, the generated sequence converges weakly to a point in the solution set T ⁻¹ (0). The LMM is very similar to the classical proximal point algorithm in that both are based on approximately evaluating the resolvants of T. Consequently, LMM can be used to derive multi-step versions of many of the optimization methods based on the classical proximal point algorithm. The convergence analysis allows errors in the computation of the iterates, and two different error criteria are analyzed, namely, the classical scheme with summable errors, and a recently proposed more constructive criterion. Received: April 2001 / Accepted: November 2002 Published online: February 14, 2003 Key Words. proximal point algorithm – monotone operator – numerical integration – strong stability – relative error criterion Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

A numerical verification method of bifurcating solutions for 3-dimensional Rayleigh–Bénard problems

This paper is the three dimensional extension of the two dimensional work in Nakao et al. (Reliable Comput 9(5):359–372, 2003) and Watanabe et al. (J Math Fluid Mech 6:1–20, 2004) on a computer assisted proof of the existence of nontrivial steady state solutions for Rayleigh–Bénard convection based on the fixed point theorem using a Newton like operator. The differences are emerging of complicated types of bifurcation, direct attack on the problem without stream functions, and increased complexity of numerical computation. The last one makes it hard to proceed the verification of solutions corresponding to the points on bifurcation diagram for three dimensional case. Actually, this work should be the first result for the three dimensional Navier–Stokes problems which seems to be very difficult to solve by theoretical approaches.     

A characterization of quadrics by intersection numbers

This work is inspired by a paper of Hertel and Pott on maximum non-linear functions (Hertel and Pott, A characterization of a class of maximum non-linear functions. Preprint, 2006). Geometrically, these functions correspond with quasi-quadrics; objects introduced in De Clerck et al. (Australas J Combin 22:151–166, 2000). Hertel and Pott obtain a characterization of some binary quasi-quadrics in affine spaces by their intersection numbers with hyperplanes and spaces of codimension 2. We obtain a similar characterization for quadrics in projective spaces by intersection numbers with low-dimensional spaces. Ferri and Tallini (Rend Mat Appl 11(1): 15–21, 1991) characterized the non-singular quadric Q(4,q) by its intersection numbers with planes and solids. We prove a corollary of this theorem for Q(4,q) and then extend this corollary to all quadrics in PG(n,q),n ≥ 4. The only exceptions occur for q even, where we can have an oval or an ovoid as intersection with our point set in the non-singular part.      

A Modified Quasi-Newton Method for Structured Optimization with Partial Information on the Hessian

This paper develops a modified quasi-Newton method for structured unconstrained optimization with partial information on the Hessian, based on a better approximation to the Hessian in current search direction. The new approximation is decided by both function values and gradients at the last two iterations unlike the original one which only uses the gradients at the last two iterations. The modified method owns local and superlinear convergence. Numerical experiments show that the proposed method is encouraging comparing with the methods proposed in [4] for structured unconstrained optimization Presented at the 6th International Conference on Optimization: Techniques and Applications, Ballarat, Australia, December 9–11, 2004     

Generalized Benders’ Decomposition for topology optimization problems

This article considers the non-linear mixed 0–1 optimization problems that appear in topology optimization of load carrying structures. The main objective is to present a Generalized Benders’ Decomposition (GBD) method for solving single and multiple load minimum compliance (maximum stiffness) problems with discrete design variables to global optimality. We present the theoretical aspects of the method, including a proof of finite convergence and conditions for obtaining global optimal solutions. The method is also linked to, and compared with, an Outer-Approximation approach and a mixed 0–1 semi definite programming formulation of the considered problem. Several ways to accelerate the method are suggested and an implementation is described. Finally, a set of truss topology optimization problems are numerically solved to global optimality.