A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

On the well-posedness of periodic problems for the system of hyperbolic equations with finite time delay

A periodic problem for the system of hyperbolic equations with finite time delay is investigated. The investigated problem is reduced to an equivalent problem, consisting the family of periodic problems for a system of ordinary differential equations with finite delay and integral equations using the method of a new functions introduction. Relationship of periodic problem for the system of hyperbolic equations with finite time delay and the family of periodic problems for the system of ordinary differential equations with finite delay is established. Algorithms for finding approximate solutions of the equivalent problem are constructed, and their convergence is proved. Criteria of well-posedness of periodic problem for the system of hyperbolic equations with finite time delay are obtained.     

A hybrid method for multidimensional scaling using city-block distances

The problem of multidimensional scaling with city-block distances in the embedding space is reduced to a two level optimization problem consisting of a combinatorial problem at the upper level and a quadratic programming problem at the lower level. A hybrid method is proposed combining randomized search for the upper level problem with a standard quadratic programming algorithm for the lower level problem. Several algorithms for the combinatorial problem have been tested and an evolutionary global search algorithm has been proved most suitable. An experimental code of the proposed hybrid multidimensional scaling algorithm is developed and tested using several test problems of two- and three-dimensional scaling.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

Error estimates for shooting methods in two-point boundary value problems for second-order equations

This paper is concerned with a procedure for estimating the global discretization error arising when a boundary value problem for a system of second order differential equations is solved by the simple shooting method, without transforming the original problem in an equivalent first order problem. Expressions of the global discretization error are derived for both linear and nonlinear boundary value problems, which reduce the error estimation for a boundary value problem to that for an initial value problem of same dimension. The procedure extends to second order equations a technique for global error estimation given elsewhere for first order equations. As a practical result the accuracy of the estimates for a second order problem is increased compared with the estimates for the equivalent first order problem.     

Reconstruction of boundary regimes in the inverse problem of thermal convection of a high-viscosity fluid

A problem of reconstruction of boundary regimes in a model for free convection of a high-viscosity fluid is considered. A variational method and a quasi-inversion method are suggested for solving the problem in question. The variational method is based on the reduction of the original inverse problem to some equivalent variational minimum problem for an appropriate objective functional and solving this problem by a gradient method. When realizing the gradient method for finding a minimizing element of the objective functional, an iterative process actually reducing the original problem to a series of direct well-posed problems is organized. For the quasi-inversion method, the original differential model is modified by means of introducing special additional differential terms of higher order with small parameters as coefficients. The new perturbed problem is well-posed; this allows one to solve this problem by standard methods. An appropriate choice of small parameters gives an opportunity to obtain acceptable qualitative and quantitative results in solving the inverse problem. A comparison of the methods suggested for solving the inverse problem is made with the use of model examples.     

Optimal design of an elastic beam with a unilateral elastic foundation: Semicoercive state problem

A design optimization problem for an elastic beam with a unilateral elastic foundation is analyzed. Euler-Bernoulli’s model for the beam and Winkler’s model for the foundation are considered. The state problem is represented by a nonlinear semicoercive problem of 4th order with mixed boundary conditions. The thickness of the beam and the stiffness of the foundation are optimized with respect to a cost functional. We establish solvability conditions for the state problem and study the existence of a solution to the optimization problem.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

An Algorithm for the 0-1 Equality Knapsack Problem

The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10,000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection.     

一类偏积分-微分方程中的反问题

对一类偏积分-微分方程中参数校准的反问题进行研究.在弱解的框架下,原问题可转化为含具体正则化项的最优化问题.文中证明了该最优化问题的解的存在性和稳定性,并考察了最优解存在的一阶必要条件.另外,证明了当正则化参数足够大时,该最优化问题关于参数a的凸性性质.基于偏积分-微分方程反问题的研究对于金融市场中的模型校准问题具有重要的意义.     

Coefficient identification in Euler-Bernoulli equation from over-posed data

A method for solving the inverse problem for coefficient identification in the Euler-Bernoulli equation from over-posed data is presented. The original inverse problem is replaced by a minimization problem. The method is applied to the problem for identifying the coefficient in the case when it is a piece-wise polynomial function. Several examples are elaborated and the numerical results confirm that the solution of the imbedding problem coincides with the direct simulation of the original problem within the second order of approximation.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Convergence of a continuous approach for zero-one programming problems

In this paper a new continuous formulation for the zero-one programming problem is presented, followed by an investigation of the algorithm for it. This paper first reformulates the zero-one programming problem as an equivalent mathematical programs with complementarity constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of approximate smooth variational principle, and with convergence properties established. To our benefit, the sequence of solutions generated converges to feasible solutions of the original problem, which provides a necessary basis for the convergence results.     

An approximation method for stochastic control problems with partial observation of the state — a method for constructing ∈-optimal controls

We consider a continuous-time stochastic control problem with partial observations. Given some assumptions, we reduce the problem in successive approximation steps to a discrete-time, complete-observation, stochastic control problem with a finite number of possible states and controls. For the latter problem an optimal control can always be explicitly computed. Convergence of the approximations is shown, which in turn implies that an optimal control for the last-stage approximating problem is ∈-optimal for the original problem.     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

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.