Comparison of two algorithms for solving a two‐stage bilinear stochastic programming problem with quantile criterion

The paper is devoted to solving the two‐stage problem of stochastic programming with quantile criterion. It is assumed that the loss function is bilinear in random parameters and strategies, and the random vector has a normal distribution. Two algorithms are suggested to solve the problem, and they are compared. The first algorithm is based on the reduction of the original stochastic problem to a mixed integer linear programming problem. The second algorithm is based on the reduction of the problem to a sequence of convex programming problems. Performance characteristics of both the algorithms are illustrated by an example. A modification of both the algorithms is suggested to reduce the computing time. The new algorithm uses the solution obtained by the second algorithm as a starting point for the first algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

线性半向量二层规划问题的全局优化方法

研究了线性半向量二层规划问题的全局优化方法. 利用下层问题的对偶间隙构造了线性半向量二层规划问题的罚问题, 通过分析原问题的最优解与罚问题可行域顶点之间的关系, 将线性半向量二层规划问题转化为有限个线性规划问题, 从而得到线性半向量二层规划问题的全局最优解. 数值结果表明所设计的全局优化方法对线性半向量二层规划问题是可行的.     

A multidimensional tropical optimization problem with a non-linear objective function and linear constraints

We examine a multidimensional optimization problem in the tropical mathematics setting. The problem involves the minimization of a non-linear function defined on a finite-dimensional semimodule over an idempotent semifield subject to linear inequality constraints. We start with an overview of known tropical optimization problems with linear and non-linear objective functions. A short introduction to tropical algebra is provided to offer a formal framework for solving the problem under study. As a preliminary result, a solution to a linear inequality with an arbitrary matrix is presented. We describe an example optimization problem drawn from project scheduling and then offer a general representation of the problem. To solve the problem, we introduce an additional variable and reduce the problem to the solving of a linear inequality, in which the variable plays the role of a parameter. A necessary and sufficient condition for the inequality to hold is used to evaluate the parameter, whereas the solution to the inequality is considered a solution to the problem. Based on this approach, a complete direct solution in a compact vector form is derived for the optimization problem under fairly general conditions. Numerical and graphical examples for two-dimensional problems are given to illustrate the obtained results.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

An algorithm to solve a quantile optimization problem with loss function having a separable structure,and its application to an aerospace problem

A quantile minimization problem with loss function having separable structure is considered. The distribution of the random parameters is assumed to be normal. To solve the problem, the confidence method and the sample average approximation method are used. Thus, the problem is reduced to a combinatorial one, which is solved by using the variable neighborhood search. The suggested algorithm is applied to optimization of runway area. Parameters of the runway are selected to minimize the area taking into account random wind speed.     

Production planning problem with sequence dependent setups as a bilevel programming problem

Each of n products is to be processed on two machines in order to satisfy known demands in each of T periods. Only one product can be processed on each machine at any given time. Each switch from one item to another requires sequence dependent setup time. The objective is to minimize the total setup time and the sum of the costs of production, storage and setup. We consider the problem as a bilevel mixed 0–1 integer programming problem. The objective of the leader is to assign the products to the machines in order to minimize the total sequence dependent setup time, while the objective of the follower is to minimize the production, storage and setup cost of the machine. We develop a heuristics based on tabu search for solving the problem. At the end, some computational results are presented.     

A robust optimization approach to diet problem with overall glycemic load as objective function

The main purpose of the paper is to introduce a mixed-integer programming model for the diet problem with glycemic load (GL) values of foods as objective function parameters. It is assumed that the glycemic load values are subject to uncertainty. The diet problem with minimum cost function is well-known in the literature. However, the diet problem with minimum total daily GL values of foods that satisfies the daily nutritional and serving size requirements has not been proposed. Robust optimization approach is used to account for uncertainty in the GL values of foods. The decision maker is flexible to tune the degree of uncertainty rather than assuming a worst-case scenario. An experimental analysis with a total of 177 foods is performed based on the nutritional and serving size requirements and the basic food groups recommended by the U.S. Department of Health and Human Services & U.S. Department of Agriculture (USDA). The results of the experimental analysis with different scenarios give different solutions for different degrees of uncertainty. However, some foods are frequently found to be in the optimum solutions. These foods are in good agreement with the literature advising them as a part of a daily diet for attaining low level of blood glucose levels. Although we believe that the proposed diet problem with minimum total GL has contributions for satisfying the daily nutritional and serving size requirements with a minimum level of effect on blood glucose levels, it has several limitations. It is a basic diet problem, and assumes that the overall GL is a linear combination of number of serving sizes with the GL values of foods. It also does not consider any other factors such as several combinations of foods and their varying effects on blood glucose levels. These factors should be considered for the next research.     

Unique solvability of a non‐local problem for mixed‐type equation with fractional derivative

In this work, we investigate a boundary problem with non‐local conditions for mixed parabolic–hyperbolic‐type equation with three lines of type changing with Caputo fractional derivative in the parabolic part. We equivalently reduce considered problem to the system of second kind Volterra integral equations. In the parabolic part, we use solution of the first boundary problem with appropriate Green's function, and in hyperbolic parts, we use corresponding solutions of the Cauchy problem. Copyright © 2016 John Wiley & Sons, Ltd.     

Two‐level additive Schwarz algorithms for nonlinear complementarity problem with an M‐function

Nonlinear complementarity problem (NCP) is a wide class of problems. In this paper, some two‐level additive Schwarz algorithms for NCPs with an M‐function are developed and analyzed. The algorithms are proved to be convergent monotonically and can reach the solution of the problem within finite steps. They may also offer a possibility of making use of fast nonlinear solvers for solving the subproblems involved in the algorithms. Some preliminary numerical results are reported. Copyright © 2009 John Wiley & Sons, Ltd.     

Using integer programming techniques for the solution of an experimental design problem

Latin hypercube sampling is often used to estimate the distribution function of a complicated function of many random variables. In so doing, it is typically necessary to choose a permutation matrix which minimizes the correlation among the cells in the hypercube layout. This problem can be formulated as a generalized, multi-dimensional assignment problem. For the two-dimensional case, we provide a polynomial algorithm. For higher dimensions, we offer effective heuristic and bounding procedures.Supported in part by a grant from the National Institute of Standards and Technology (60NANB9D-0974).Supported in part by grants from the Office of Naval Research (N00014-90-J-1324) and the Air Force Office of Scientific Research (F49 620-90-C-0022).Research partially performed while visiting the Department of Mathematics, Brunel University, Uxbridge, England.     

Solution of and bounding in a linearly constrained optimization problem with convex,polyhedral objective function

A dual method is presented to solve a linearly constrained optimization problem with convex, polyhedral objective function, along with a fast bounding technique, for the optimum value. The method can be used to solve problems, obtained from LPs, where some of the constraints are not required to be exactly satisfied but are penalized by piecewise linear functions, which are added to the objective function of the original problem. The method generalizes an earlier solution technique developed by Prékopa (1990). Applications to stochastic programming are also presented.This research was supported by the National Science Foundation, Grant No. DMS-9005159.Corresponding author.     

Analysis of an augmented mixed‐primal formulation for the stationary Boussinesq problem

In this article, we propose and analyze a new mixed variational formulation for the stationary Boussinesq problem. Our method, which uses a technique previously applied to the Navier–Stokes equations, is based first on the introduction of a modified pseudostress tensor depending nonlinearly on the velocity through the respective convective term. Next, the pressure is eliminated, and an augmented approach for the fluid flow, which incorporates Galerkin‐type terms arising from the constitutive and equilibrium equations, and from the Dirichlet boundary condition, is coupled with a primal‐mixed scheme for the main equation modeling the temperature. In this way, the only unknowns of the resulting formulation are given by the aforementioned nonlinear pseudostress, the velocity, the temperature, and the normal derivative of the latter on the boundary. An equivalent fixed‐point setting is then introduced and the corresponding classical Banach Theorem, combined with the Lax–Milgram Theorem and the Babu?ka–Brezzi theory, are applied to prove the unique solvability of the continuous problem. In turn, the Brouwer and the Banach fixed‐point theorems are used to establish existence and uniqueness of solution, respectively, of the associated Galerkin scheme. In particular, Raviart–Thomas spaces of order k for the pseudostress, continuous piecewise polynomials of degree ≤ k+1 for the velocity and the temperature, and piecewise polynomials of degree ≤ k for the boundary unknown become feasible choices. Finally, we derive optimal a priori error estimates, and provide several numerical results illustrating the good performance of the augmented mixed‐primal finite element method and confirming the theoretical rates of convergence. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 445–478, 2016     

On a discrimination problem for a class of stochastic processes with ordered first‐passage times

Consider the Bayes problem in which one has to discriminate if the random unknown initial state of a stochastic process is distributed according to either of two preassigned distributions, on the base of the observation of the first‐passage time of the process through 0. For processes whose first‐passage times to state 0 are increasing in the initial state according to the likelihood ratio order, such problem is solved by determining the Bayes decision function and the corresponding Bayes error. The special case of fixed initial values including a family of first‐passage times with proportional reversed hazard functions is then studied. Finally, various applications to birth‐and‐death and to diffusion processes are discussed. Copyright © 2001 John Wiley & Sons, Ltd.     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

Determination of an unknown function in a parabolic inverse problem by Sinc‐collocation method

In this article, an inverse problem of determining an unknown time‐dependent source term of a parabolic equation is considered. We change the inverse problem to a Volterra integral equation of convolution‐type. By using Sinc‐collocation method, the resulting integral equation is replaced by a system of linear algebraic equations. The convergence analysis is included, and it is shown that the error in the approximate solution is bounded in the infinity norm by the condition number and the norm of the inverse of the coefficient matrix multiplied by a factor that decays exponentially with the size of the system. Some examples are given to demonstrate the computational efficiency of the method. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1584–1598, 2010     

On the calculation of a membership function for the solution of a fuzzy linear optimization problem

In the present paper the fuzzy linear optimization problem (with fuzzy coefficients in the objective function) is considered. Recent concepts of fuzzy solution to the fuzzy optimization problem based on the level-cut and the set of Pareto optimal solutions of a multiobjective optimization problem are applied. Chanas and Kuchta suggested one approach to determine the membership function values of fuzzy optimal solutions of the fuzzy optimization problem, which is based on calculating the sum of lengths of certain intervals. The purpose of this paper is to determine a method for realizing this idea. We derive explicit formulas for the bounds of these intervals in the case of triangular fuzzy numbers and show that only one interval needs to be considered.     

A remark on the Riemann‐Hilbert problem with a vanishing coefficient

This paper concerns the existence of nontrivial solutions of the Riemann‐Hilbert problem with a continuous coefficient whose values belong to two rays in the complex plane. Our results extend those recently obtained by E. Shargorodsky and J. F. Toland [6]. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The quasi‐reversibility method for a final value problem of the time‐fractional diffusion equation with inhomogeneous source

This paper is devoted to discuss a multidimensional backward heat conduction problem for time‐fractional diffusion equation with inhomogeneous source. This problem is ill‐posed. We use quasi‐reversibility regularization method to solve this inverse problem. Moreover, the convergence estimates between regularization solution and the exact solution are obtained under the a priori and the a posteriori choice rules. Finally, the numerical examples for one‐dimensional and two‐dimensional cases are presented to show that our method is feasible and effective.     

Some investigations in a new algorithm for nonlinear optimization based on conic models of the objective function

An appealing approach to the solution of nonlinear optimization problems based on conic models of the objective function has been recently introduced by Davidon. It leads to a broad class of algorithms which, in some sense, can be considered to generalize the existing quasi-Newton algorithms. One particular member of this class has been deeply examined by Sorensen, who has proved some interesting theoretical properties. A new interpretation of this algorithm is suggested in this paper from a more straightforward and somewhat familiar point of view. In addition, numerical experiments have been carried out to compare the Sorensen algorithm with a straightforward BFGS implementation of the classical quasi-Newton method with the final aim to assess the real merits and benefits of the new algorithm. Although some challenging test functions are used in computational experiments, the results are not particularly favorable to the new algorithm. As a matter of fact they do not exhibit any jump of quality, as it might be expected. Lastly, it is pointed out that a difficulty may affect the new method in situations in which it is necessary to exploit the special structure of large-scale problems.This work was supported by the National Research Council of Italy under Grant No. 80-01144.     

The max‐length‐vector line of best fit to a set of vector subspaces and an optimization problem over a set of hyperellipsoids

Let be a collection of subspaces of a finite‐dimensional real vector space V. Let L denote a one‐dimensional subspace of V, and let θ(L,V_i) denote the principal angle between L and V_i. Motivated by a problem in data analysis, we seek an L that maximizes the function . Conceptually, this is the line through the origin that best represents with respect to the criterion F(L). A reformulation shows that L is spanned by a vector , which maximizes the function subject to the constraints v_i∈V_i and ||v_i||=1. In this setting, v is seen to be the longest vector that can be decomposed into unit vectors lying on prescribed hyperspheres. A closely related problem is to find the longest vector that can be decomposed into vectors lying on prescribed hyperellipsoids. Using Lagrange multipliers, the critical points of either problem can be cast as solutions of a multivariate eigenvalue problem. We employ homotopy continuation and numerical algebraic geometry to solve this problem and obtain the extremal decompositions. Copyright © 2015 John Wiley & Sons, Ltd.