Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

Smooth solutions of an initial-value problem for some differential difference equations

The subject matter of this paper is an initial-value problem with an initial function for a linear differential difference equation of neutral type. The problem is to find an initial function such that the solution generated by this function has some given smoothness at the points multiple of the delay. The problem is solved using a method of polynomial quasisolutions, which is based on a representation of the unknown function in the form of a polynomial of some degree. Substituting this into the initial problem yields some incorrectness in the sense of degree of polynomials, which is compensated for by introducing some residual into the equation. For this residual, an exact analytical formula as a measure of disturbance of the initial-value problem is obtained. It is shown that if a polynomial quasisolution of degree N is chosen as an initial function for the initial-value problem in question, the solution generated will have smoothness not lower than N at the abutment points.     

Integer programming formulation of combinatorial optimization problems

This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2ⁿ - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists.     

The dynamic programming equation for stochastic optical control in hilbert spaces: a variational approach

The global existence of a point wise solution to the Hamilton-Jacobi equation for totally observed controlled diffusions in Hilbert spaces is proved by studying the corresponding control problem. The optimality principle for the control problem leads to local results, whilst an a priori bound is achieved by introducing a secondary minimization problem.     

Saddle-Point Criteria in an η-Approximation Method for Nonlinear Mathematical Programming Problems Involving Invex Functions

In this paper, the η-approximation method introduced by Antczak (Ref. 1) for solving a nonlinear constrained mathematical programming problem involving invex functions with respect to the same function η is extended. In this method, a so-called η-approximated optimization problem associated with the original mathematical programming problems is constructed; moreover, an η-saddle point and an η-Lagrange function are defined. By the help of the constructed η-approximated optimization problem, saddle-point criteria are obtained for the original mathematical programming problem. The equivalence between an η-saddle point of the η-Lagrangian of the associated η-approximated optimization problem and an optimal solution in the original mathematical programming problem is established.     

A finite element method for approximating electromagnetic scattering from a conducting object

We provide an error analysis of a fully discrete finite element – Fourier series method for approximating Maxwell's equations. The problem is to approximate the electromagnetic field scattered by a bounded, inhomogeneous and anisotropic body. The method is to truncate the domain of the calculation using a series solution of the field away from this domain. We first prove a decomposition for the Poincaré-Steklov operator on this boundary into an isomorphism and a compact perturbation. This is proved using a novel argument in which the scattering problem is viewed as a perturbation of the free space problem. Using this decomposition, and edge elements to discretize the interior problem, we prove an optimal error estimate for the overall problem.     

Buckling of a von Kármán Plate Adhesively Connected to a Rigid Support Allowing for Delamination: Existence and Multiplicity Results

The present paper deals with an eigenvalue problem for a hemivariational inequality, arising in the study of a mechanical problem: the buckling of a von Kármán plate adhesively connected to a rigid support with delamination effects. For this eigenvalue problem an existence result is obtained by applying a critical point method suitable for nonconvex nonsmooth functions. Further, a result concerning the multiplicity of solutions is proved. The mechanical interpretation of these results is briefly discussed.     

On noninferior performance index vectors

The noninferior vector index problem of optimal control theory is investigated in an effort to establish some basic properties of the noninferior index surface in the generalN-dimensional index problem. The vector performance index problem is first converted to a family of scalar index problems by forming an auxiliary scalar index as a function of the vector index and a vector of weighting parameters. The functional relationship between noninferior vectors and the weighting vectors of the auxiliary index problem is investigated for the particular case in which the auxiliary index is a weighted sum of the vector index elements. Special attention is devoted to the noninferior index problem for whichN = 2.     

Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract)

Motivated by a food promotion problem, we introduce the Knapsack Problem for Perishable Items (KPPI) to address a dynamic problem of optimally filling a knapsack with items that disappear randomly. The KPPI naturally bridges the gap and elucidates the relation between the PSPACE-hard restless bandit problem and the NP-hard knapsack problem. Our main result is a problem decomposition method resulting in an approximate transformation of the KPPI into an associated 0-1 knapsack problem. The approach is based on calculating explicitly the marginal productivity indices in a generic finite-horizon restless bandit subproblem.     

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.     

Sensitivity optimization problem for uncertain discrete SISO system

We consider an optimal stabilization problem for an uncertain system described as a linear time-invariant plant closed by an uncertain feedback which is a conic nonlinearity. We apply the so-called S-procedure losslessness theorem by Yakubovich to reduce the original problem to a parametrized H-infinity optimization problem. We prove that the minimal cost in this parameterized optimization is a concave function of the parameter. This fact makes applicable the standard methods of the H-infinity control theory and the convex analysis in developing optimal linear feedback design algorithms for the original problem.This work was supported by the Swedish Academy of Science and by the Göran Gustafsson Foundation. The author is grateful to the anonymous referees for many useful remarks.     

Solution procedures for three-dimensional eddy current problems

The problem under consideration is that of the scattering of time periodic electromagnetic fields by metallic obstacles. A common approximation here is that in which the metal is assumed to have infinite conductivity. The resulting problem, called the perfect conductor problem, involves solving Maxwell's equations in the region exterior to the obstacle with the tangential component of the electric field zero on the obstacle surface. In the interface problem different sets of Maxwell equations must be solved in the obstacle and outside while the tangential components of both electric and magnetic fields are continuous across the obstacle surface. Solution procedures for this problem are given. There is an exact integral equation procedure for the interface problem and an asymptotic procedure for large conductivity. Both are based on a new integral equation procedure for the perfect conductor problem. The asymptotic procedure gives an approximate solution by solving a sequence of problems analogous to the one for perfect conductors.     

An optimal control problem with a random stopping time

This paper deals with a stochastic optimal control problem where the randomness is essentially concentrated in the stopping time terminating the process. If the stopping time is characterized by an intensity depending on the state and control variables, one can reformulate the problem equivalently as an infinite-horizon optimal control problem. Applying dynamic programming and minimum principle techniques to this associated deterministic control problem yields specific optimality conditions for the original stochastic control problem. It is also possible to characterize extremal steady states. The model is illustrated by an example related to the economics of technological innovation.This research has been supported by NSERC-Canada, Grants 36444 and A4952; by FCAR-Québec, Grant 88EQ3528, Actions Structurantes; and by MESS-Québec, Grant 6.1/7.4(28).     

The solvability of a coupled thermoviscoelastic contact problem with small Coulomb friction and linearized growth of frictional heat

A coupled thermoviscoelastic frictional contact problem is investigated. The contact is modelled by the Signorini condition for the displacement velocities and the friction by the Coulomb law. The heat generated by friction is described by a non‐linear boundary condition with at most linear growth. The weak formulation of the problem consists of a variational inequality for the elasticity part and a variational equation for the heat conduction part. In order to prove the existence of a solution to this problem we first use an approximation of the Signorini condition by the penalty method. The existence of a solution for the approximate problem is shown using the fixed‐point theorem of Schauder. This theorem is applied to the composition of the solution operator for the contact problem with given temperature field and the solution operator for the heat equation problem with known displacement field. To obtain this proof, the unique solvability of both problems is necessary. Due to this reason it is necessary to introduce the penalty method. While the penalized contact problem has a unique solution, this is not clear for the original contact problem. The solvability of the original frictional contact problem is verified by an investigation of the limit for vanishing penalty parameter. Copyright © 1999 John Wiley & Sons, Ltd.     

On an Area Problem in Conformal Mapping

We consider an area problem for quadrilaterals Q. The geometry of Q is partly prescribed and partly free; the module is to be fixed, and its area is to be minimized. If Q is sufficiently simple, we can solve the problem explicitly by using a modified Schwarz-Christoffel integral. The free boundary arc is represented by an integral. The corresponding area problem for doubly connected domains can be reduced to the area problem for quadrilaterals, if the given boundary component is a regular polygon. We give results of numerical experiments.     

A primal–dual algorithm for the economic lot-sizing problem with multi-mode replenishment

The classical economic lot-sizing problem assumes that a single supplier and a single transportation mode are used to replenish the inventory. This paper studies an extension of this problem where several suppliers and transportation modes are available. The decision-making process in this case involves identifying (i) the timing for an order; (ii) the choice of shipment modes; and (iii) the order size for each mode. The problem is defined as a network flow problem with multiple setups cost function and additional side constraints. This study provides an MIP formulation for the problem. We also provide an additional formulation of the problem by redefining its decision variables and show that the dual of the corresponding LP-relaxation has a special structure. We take advantage of the structure of the dual problem to develop a primal–dual algorithm that generates tight lower and upper bounds. Computational results demonstrate the effectiveness of the algorithm.     

An Iterative Method for Finding the Least Solution to the Tensor Complementarity Problem

In this paper, we are concerned with finding the least solution to the tensor complementarity problem. When the involved tensor is strongly monotone, we present a way to estimate the nonzero elements of the solution in a successive manner. The procedure for identifying the nonzero elements of the solution gives rise to an iterative method of solving the tensor complementarity problem. In each iteration, we obtain an iterate by solving a lower-dimensional tensor equation. After finitely many iterations, the method terminates with a solution to the problem. Moreover, the sequence generated by the method is monotonically convergent to the least solution to the problem. We then extend this idea for general case and propose a sequential mathematical programming method for finding the least solution to the problem. Since the least solution to the tensor complementarity problem is the sparsest solution to the problem, the method can be regarded as an extension of a recent result by Luo et al. (Optim Lett 11:471–482, 2017). Our limited numerical results show that the method can be used to solve the tensor complementarity problem efficiently.     

A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ?) for any ? > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.     

Decomposition through formalization in a product space

When an optimization problem is posed in a product space it is classical to decompose this problem. The goal of this paper is to show how such an approach can be used when the problem to be solved is not naturally posed in a product space. By associating systematically to this problem an equivalent one posed in ann-fold cartesian product space, we obtain by decomposition of the latter both a splitting of operators and a desintegration of constraints for the former. Applications to three rather classical mathematical programming problems are given.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation