Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

Robust optimal strategies in Markov decision problems

An optimal strategy in a Markov decision problem is robust if it is optimal in every decision problem (not necessarily stationary) that is close to the original problem. We prove that when the state and action spaces are finite, an optimal strategy is robust if and only if it is the unique optimal strategy.     

Optimal Quarantine Programmes for Controlling an Epidemic Spread

An optimal control problem is formulated with a simple epidemic model in which the control of the epidemic is effected by varying the scale of the quarantine program in a way which minimizes a discounted linear cost over an infinite horizon. An important function of the problem parameters is identified. It is shown that if this function has a value of less than or equal to one, then the optimal policy is not to quarantine at all. While if this functions assume a value in excess of one, then the optimal policy is not to quarantine at all if the initial fraction of infectives is sufficiently high; otherwise, it is optimal to have a full scale quarantine program. Slight modification in these policies are required for the finite horizon version of the problem.     

Solutions to Constrained Optimal Control Problems with Linear Systems

This paper is devoted to present solutions to constrained finite-horizon optimal control problems with linear systems, and the cost functional of the problem is in a general form. According to the Pontryagin’s maximum principle, the extremal control of such problem is a function of the costate trajectory, but an implicit function. We here develop the canonical backward differential flows method and then give the extremal control explicitly with the costate trajectory by canonical backward differential flows. Moreover, there exists an optimal control if and only if there exists a unique extremal control. We give the proof of the existence of the optimal solution for this optimal control problem with Green functions.     

Preemptive and nonpreemptive multi-objective programming: Relationship and counterexamples

In this paper, we formally establish connections between two standard approaches proposed for resolving multi-objective programs, namely, the nonpreemptive and the preemptive methods. We demonstrate in the linear case that, if the preemptive problem has an optimal solution, then there exists a set of weights for the nonpreemptive problem, such that any optimal solution to the nonpreemptive problem is optimal to the preemptive problem. Conversely, and more importantly, any optimal solution to the preemptive problem is optimal to the nonpreemptive problem. A similar result is established for arbitrary multi-objective functions being optimized over a finite discrete set. Thus, the preemptive problem is subsumed within the nonpreemptive problem in these cases. Although we actually construct a set of equivalent weights, we do not advocate our technique as a computational device for solving the preemptive problem. However, a previous attempt (Ref. 1), which does prescribe a set of equivalent weights to solve a preemptive problem as a linear program, is shown to be erroneous. Moreover, our constructive proof exhibits the features of the problem which govern the determination of such equivalent weights.     

Abort landing in the presence of windshear as a minimax optimal control problem,part 1: Necessary conditions

The landing of a passenger aircraft in the presence of windshear is a threat to aviation safety. The present paper is concerned with the abort landing of an aircraft in such a serious situation. Mathematically, the flight maneuver can be described by a minimax optimal control problem. By transforming this minimax problem into an optimal control problem of standard form, a state constraint has to be taken into account which is of order three. Moreover, two additional constraints, a first-order state constraint and a control variable constraint, are imposed upon the model. Since the only control variable appears linearly, the Hamiltonian is not regular. Thus, well-known existence theorems about the occurrence of boundary arcs and boundary points cannot be applied. Numerically, this optimal control problem is solved by means of the multiple shooting method in connection with an appropriate homotopy strategy. The solution obtained here satisfies all the sharp necessary conditions including those depending on the sign of certain multipliers. The trajectory consists of bang-bang and singular subarcs, as well as boundary subarcs induced by the two state constraints. The occurrence of boundary arcs is known to be impossible for regular Hamiltonians and odd-ordered state constraints if the order exceeds two. Additionally, a boundary point also occurs where the third-order state constraint is active. Such a situation is known to be the only possibility for odd-ordered state constraints to be active if the order exceeds two and if the Hamiltonian is regular. Because of the complexity of the optimal control, this single problem combines many of the features that make this kind of optimal control problems extremely hard to solve. Moreover, the problem contains nonsmooth data arising from the approximations of the aerodynamic forces and the distribution of the wind velocity components. Therefore, the paper can serve as some sort of user's guide to solve inequality constrained real-life optimal control problems by multiple shooting.An extended abstract of this paper was presented at the 8th IFAC Workshop on Control Applications of Nonlinear Programming and Optimization, Paris, France, 1989 (see Ref. 1).This paper is dedicated to Professor Hans J. Stetter on the occasion of his 60th birthday.     

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.     

On the terminal control problem

A minimum-time problem is considered, where the final point is locally controllable. It is shown that it is possible to construct a suboptimal control with a transfer time close to the optimal transfer time of the relaxed system. The resulting trajectory will satisfy initial and final conditions. Furthermore, it is shown that, if an optimal solution exists for the problem, then this optimal solution is also an optimal solution of the relaxed problem. In this case, the relaxed problem need not be solved.The authors wish to thank Dr. D. Hazan, Scientific Department, Ministry of Defense, Israel, for a fruitful discussion of this problem.     

Bilevel problems over polyhedra with extreme point optimal solutions

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem, we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of an extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem. An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique. On the other hand, if the lower level objective function is not quasiconcave but convex quadratic, assuming the optimistic approach we prove that the optimal solution is attained at an extreme point of an ??enlarged?? polyhedron.     

The Dissipation Inequality for Differential-Algebraic Systems

We discuss the infinite time-horizon linear-quadratic optimal control problem for differential-algebraic equations. In contrast to previous approaches we do not impose any assumptions on the system except for impulse controllability. In particular, we show that the optimal control problem is feasible if and only if a dissipation inequality has a solution. Moreover, we discuss conditions under which the problem has a minimizing (instead of only an infimizing) solution and furthermore, when this minimizing solution is unique. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the uniqueness of solutions to linear programs

We provide a constructive method of checking whether a linear programming problem (LPP) has a unique feasible or a unique optimal solution. Our method requires the solution of only one extra LPP such that the original problem has alternative solutions if and only if the optimal value of the new LPP is positive. If the original solution is not unique, an alternative solution is displayed. Possible applications are discussed.     

First-order strong variation algorithm for optimal control problems involving hyperbolic systems

This paper considers an optimal control problem involving linear, hyperbolic partial differential equations. A first-order strong variational technique is used to obtain an algorithm for solving the optimal control problem iteratively. It is shown that the accumulation points of the sequence of controls generated by the algorithm (if they exist) satisfy a necessary condition for optimality.     

A synthesis problem for the optimal control of epidemics *

The present paper deals with the problem of preventing an epidemic by vaccination. Existence and uniqueness results for the optimal solutions are obtained. Moreover it is shown that if the treatment interval is suitably small then the problem has a unique optimal synthesis.     

A conditional gradient method for an optimal control problem involving a class of nonlinear second-order hyperbolic partial differential equations

The aim of this paper is to consider an optimal control problem involving a class of nonlinear hyperbolic partial differential equations. A conditional gradient method is used to obtain an algorithm for solving the optimal control problem iteratively. It is then shown that any accumulation point of the sequence of controls generated by the algorithm (if it exists) satisfies a necessary condition for optimality.     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

An easy way to teach interior-point methods

In this paper the duality theory of Linear Optimization (LO) is built up based on ideas emerged from interior-point methods (IPMs). All we need is elementary calculus. We will embed the LO problem and its dual in a self-dual skew-symmetric problem. Most duality results, except the existence of a strictly complementary solution, are trivial for this embedding problem. The existence of the central path and its convergence to the analytic center of the optimal face will be proved. The proof is based on an elementary, careful analysis of a Newton step.We show also that if an almost optimal solution on the central path is known, then a simple strongly polynomial rounding procedure provides an exact strictly complementary optimal solution.The all-one vector is feasible for the embedding problem and it is an interior-point on the central path. This way an elegant solution to the initialization of IPMs is obtained as well. This approach allows to apply any IPM to the embedding problem while complexity results obtained for feasible IPMs are preserved.     

Bounds for the position of the smallest job in completion time variance minimization

The problem of scheduling jobs on a single machine so as to minimize the variance of job completion times is considered. We develop bounds on the position of the smallest job in an optimal sequence, which is vital due to the fact that an optimal sequence is necessarily a V-shaped sequence. Results of numerical experimentation indicate that the bounds are very effective if the job processing times are homogeneous. Using these bounds, we develop a new heuristic method to solve the problem. Based on numerical investigation, it is shown that performance of this heuristic compares favorably with existing but older heuristics.     

Equivalent time-dependent scheduling problems

We introduce a general transformation of parallel-machine time-dependent scheduling problems with critical lines. Using the transformation we define the class of equivalent time-dependent scheduling problems. We show that given an initial parallel-machine time-dependent scheduling problem with linear job processing times and the total weighted starting time criterion, the problem can be transformed in a unique way into another problem of this type in such a way that both these problems are mutually dual. We prove that a schedule is optimal for the initial problem if and only if the schedule constructed by this transformation is optimal for the transformed problem. The presented results explain remarkable similarities between different time-dependent scheduling problems and simplify the proofs of properties of such problems.     

Saturation in Linear Optimization

In a solvable linear optimization problem, a constraint is saturated if it is binding at a certain optimal solution and it is weakly saturated if it is binding at a proper subset of the optimal set. Nonsaturation and weak saturation can be seen as redundancy phenomena in the sense that the elimination of a finite number of these constraints preserves the value of the given problem. We consider also the effect of sufficiently small perturbations of the cost coefficients in the classification of a given constraint as either saturated or nonsaturated.     

Convex Semi-Infinite Programming: Implicit Optimality Criterion Based on the Concept of Immobile Indices

We state a new implicit optimality criterion for convex semi-infinite programming (SIP) problems. This criterion does not require any constraint qualification and is based on concepts of immobile index and immobility order. Given a convex SIP problem with a continuum of constraints, we use an information about its immobile indices to construct a nonlinear programming (NLP) problem of a special form. We prove that a feasible point of the original infinite SIP problem is optimal if and only if it is optimal in the corresponding finite NLP problem. This fact allows us to obtain new efficient optimality conditions for convex SIP problems using known results of the optimality theory of NLP. To construct the NLP problem, we use the DIO algorithm. A comparison of the optimality conditions obtained in the paper with known results is provided.