Maximizing set function formulation of two scheduling problems

In this note we consider two problems: (1) Schedulingn jobs non-preemptively on a single machine to minimize total weighted earliness and tardiness (WET). (2) Schedulingn jobs nonpreemptively on two parallel identical processors to minimize weighted mean flow time (WMFT). A new approach for these problems is presented. The approach is based on a problem of maximizing a submodular set function. Heuristic algorithm for the problems also is presented.     

一个新的填充函数

填充函数法是一种解无约束全局极小化问题的方法.这种方法的关键是构造填充函数,在已发表的文献中已经介绍了几种填充函数.在此介绍只含一个参数的填充函数,并且根据此填充函数提出了一种填充函数算法.给出了用这种填充函数法解几个测试问题的计算结果.     

Finding discrete global minima with a filled function for integer programming

The filled function method is an approach to find the global minimum of multidimensional functions. This paper proposes a new definition of the filled function for integer programming problem. A filled function which satisfies this definition is presented. Furthermore, we discuss the properties of the filled function and design a new filled function algorithm. Numerical experiments on several test problems with up to 50 integer variables have demonstrated the applicability and efficiency of the proposed method.     

Methods for Estimating the Global Maximum Point and the Integral of a Continuous Function on a Compact Set

Doklady Mathematics - A new approach to the problems of estimating the global maximum point and the integral of a continuous function on a compact set is proposed. The approach combines a simple...     

A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic

In this article, a new memetic algorithm has been proposed to solve job shop scheduling problems (JSSPs). The proposed method is a genetic-algorithm-based approach combined with a local search heuristic. The proposed local search heuristic is based on critical operations. It removes the critical operations and reassigns them to a new position to improve the fitness value of the schedule. Moreover, in this article, a new fitness function is introduced for JSSPs. The new fitness function called priority-based fitness function is defined in three priority levels to improve the selection procedure. To show the generality of our proposed method, we apply it to three different types of job scheduling problems including classical, flexible and multi-objective flexible JSSPs. The experiment results show the efficiency of the proposed fitness function. In addition, the results show that incorporating local search not only offers better solutions but also improves the convergence rate. Compared to the state-of-the-art algorithms, the proposed method outperforms the existing methods in classical JSSPs and offers competitive solutions in other types of scheduling problems.     

A penalty function approach for solving bi-level linear programs

The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.     

Computable bounds on parametric solutions of convex problems

We present a new method for computing bounds on parametric solutions of convex problems. The approach is based on a uniform quadratic underestimation of the objective function and a simple technique for the calculation of bounds on the optimal value function.Research supported by Grant ECS-8619859, National Science Foundation and Contract N00017-86-K-0052, Office of Naval Research.     

Adaptive reliability analysis based on a support vector machine and its application to rock engineering

The response surface method (RSM), a simple and effective approximation technique, is widely used for reliability analysis in civil engineering. However, the traditional RSM needs a considerable number of samples and is computationally intensive and time-consuming for practical engineering problems with many variables. To overcome these problems, this study proposes a new approach that samples experimental points based on the difference between the last two trial design points. This new method constructs the response surface using a support vector machine (SVM); the SVM can build complex, nonlinear relations between random variables and approximate the performance function using fewer experimental points. This approach can reduce the number of experimental points and improve the efficiency and accuracy of reliability analysis. The advantages of the proposed method were verified using four examples involving random variables with different distributions and correlation structures. The results show that this approach can obtain the design point and reliability index with fewer experimental points and better accuracy. The proposed method was also employed to assess the reliability of a numerically modeled tunnel. The results indicate that this new method is applicable to practical, complex engineering problems such as rock engineering problems.     

A new approach to filtering and adaptive control: stability results

A new approach to adaptive control is proposed. The principal distinguishing feature is the direct estimation and updating of the criterion function by means of a filtering operation on a vector of transitional pseudo-return functions. The data storage and computational problems often associated with explicit probability distribution updating via Bayes' rule are thus avoided. Convergence properties are established for a simple linear criterion function filter designed for a class of adaptive control problems typified by a well-known two-armed bandit problem. Optimality properties are established for the filter in a companion paper.     

An efficient nonmonotone trust-region method for unconstrained optimization

The monotone trust-region methods are well-known techniques for solving unconstrained optimization problems. While it is known that the nonmonotone strategies not only can improve the likelihood of finding the global optimum but also can improve the numerical performance of approaches, the traditional nonmonotone strategy contains some disadvantages. In order to overcome to these drawbacks, we introduce a variant nonmonotone strategy and incorporate it into trust-region framework to construct more reliable approach. The new nonmonotone strategy is a convex combination of the maximum of function value of some prior successful iterates and the current function value. It is proved that the proposed algorithm possesses global convergence to first-order and second-order stationary points under some classical assumptions. Preliminary numerical experiments indicate that the new approach is considerably promising for solving unconstrained optimization problems.     

A new approach to the Pontryagin maximum principle for nonlinear fractional optimal control problems

In this paper, we discuss a new general formulation of fractional optimal control problems whose performance index is in the fractional integral form and the dynamics are given by a set of fractional differential equations in the Caputo sense. The approach we use to prove necessary conditions of optimality in the form of Pontryagin maximum principle for fractional nonlinear optimal control problems is new in this context. Moreover, a new method based on a generalization of the Mittag–Leffler function is used to solving this class of fractional optimal control problems. A simple example is provided to illustrate the effectiveness of our main result. Copyright © 2016 John Wiley & Sons, Ltd.     

A filled function method applied to nonsmooth constrained global optimization

The filled function method is an effective approach to find a global minimizer. In this paper, based on a new definition of the filled function for nonsmooth constrained programming problems, a one-parameter filled function is constructed to improve the efficiency of numerical computation. Then a corresponding algorithm is presented. It is a global optimization method which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Illustrative examples are provided to demonstrate the efficiency and reliability of the proposed filled function method.     

A deterministic approach to global box-constrained optimization

A deterministic global optimization algorithm for box-constrained problems is presented. The proposed approach is based on well-known non-uniform space covering technique. In the paper this approach is further elaborated. We propose a new techniques that enables a significant reduction of the search space by means of dropping parts of processed boxes. Also a new quadratic underestimation for the objective function based on hessian eigenvalues bounds is presented. It is shown how this underestimation can be improved by exploiting the first-order optimality conditions. In the experimental section we compare the proposed approach with existing methods and programming tools. Numerical tests indicate that the proposed algorithm is highly competitive with considered methods.     

Stability Analysis of Gradient-Based Neural Networks for Optimization Problems

The paper introduces a new approach to analyze the stability of neural network models without using any Lyapunov function. With the new approach, we investigate the stability properties of the general gradient-based neural network model for optimization problems. Our discussion includes both isolated equilibrium points and connected equilibrium sets which could be unbounded. For a general optimization problem, if the objective function is bounded below and its gradient is Lipschitz continuous, we prove that (a) any trajectory of the gradient-based neural network converges to an equilibrium point, and (b) the Lyapunov stability is equivalent to the asymptotical stability in the gradient-based neural networks. For a convex optimization problem, under the same assumptions, we show that any trajectory of gradient-based neural networks will converge to an asymptotically stable equilibrium point of the neural networks. For a general nonlinear objective function, we propose a refined gradient-based neural network, whose trajectory with any arbitrary initial point will converge to an equilibrium point, which satisfies the second order necessary optimality conditions for optimization problems. Promising simulation results of a refined gradient-based neural network on some problems are also reported.     

Modified Ratio Objective Approach in Mathematical Programming

A new approach to obtaining the optimality conditions for fractional mathematical programming problems involving one objective ratio in the objective function is considered. Using this approach, an equivalent optimization problem is constructed by a modification of the single-ratio objective function in the fractional programming problem. Furthermore, an η-Lagrange function is introduced for a constructed optimization problem and modified saddle-point results are presented.     

A new approach in studying one parameter nonlinear eigenvalue problems with constraints

The paper presents a new approach for obtaining existence and location of solutions to nonlinear eigenvalue problems depending on a parameter and subject to constraints. The location of eigensolutions and subsequent parameters is achieved by means of the graph of the derivative of a function used also to compensate the lack of coercivity. The applications concern one parameter families of semilinear elliptic eigenvalue problems with Dirichlet boundary conditions for which various qualitative properties of the solution sets are established.     

Nonsmooth nonconvex optimization approach to clusterwise linear regression problems

Clusterwise regression consists of finding a number of regression functions each approximating a subset of the data. In this paper, a new approach for solving the clusterwise linear regression problems is proposed based on a nonsmooth nonconvex formulation. We present an algorithm for minimizing this nonsmooth nonconvex function. This algorithm incrementally divides the whole data set into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate a good starting point for solving global optimization problems at each iteration of the incremental algorithm. Such an approach allows one to find global or near global solution to the problem when the data sets are sufficiently dense. The algorithm is compared with the multistart Späth algorithm on several publicly available data sets for regression analysis.     

Systems of nonlinear Volterra integro-differential equations

An efficient method based on operational Tau matrix is developed, to solve a type of system of nonlinear Volterra integro-differential equations (IDEs). The presented method is also modified for the problems with separable kernel. Error estimation of the new schemes are analyzed and discussed. The advantages of this approach and its modification is that, the solution can be expressed as a truncated Taylor series, and the error function at any stage can be estimated. Methods are applied on the four problems with separable kernel to show the applicability and efficiency of our schemes, specially for those problems at broad intervals.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.