ISSN:
1547-5816
eISSN:
1553-166X
All Issues
Journal of Industrial & Management Optimization
April 2014 , Volume 10 , Issue 2
Select all articles
Export/Reference:
2014, 10(2): 363-381
doi: 10.3934/jimo.2014.10.363
+[Abstract](2337)
+[PDF](255.3KB)
Abstract:
We consider fractional order optimal control problems in which the dynamic control system involves integer and fractional order derivatives and the terminal time is free. Necessary conditions for a state/control/terminal-time triplet to be optimal are obtained. Situations with constraints present at the end time are also considered. Under appropriate assumptions, it is shown that the obtained necessary optimality conditions become sufficient. Numerical methods to solve the problems are presented, and some computational simulations are discussed in detail.
We consider fractional order optimal control problems in which the dynamic control system involves integer and fractional order derivatives and the terminal time is free. Necessary conditions for a state/control/terminal-time triplet to be optimal are obtained. Situations with constraints present at the end time are also considered. Under appropriate assumptions, it is shown that the obtained necessary optimality conditions become sufficient. Numerical methods to solve the problems are presented, and some computational simulations are discussed in detail.
2014, 10(2): 383-396
doi: 10.3934/jimo.2014.10.383
+[Abstract](1545)
+[PDF](571.4KB)
Abstract:
Verification of semiconductor chip designs is commonly driven by single goal orientated measures. With increasing design complexities, this approach is no longer effective. We enhance the effectiveness of coverage driven design verifications by applying multi-objective optimization techniques. The technique is based on genetic evolutionary algorithms. Difficulties with conflicting test objectives and selection of tests to achieve multiple verification goals in the genetic evolutionary framework are also addressed.
Verification of semiconductor chip designs is commonly driven by single goal orientated measures. With increasing design complexities, this approach is no longer effective. We enhance the effectiveness of coverage driven design verifications by applying multi-objective optimization techniques. The technique is based on genetic evolutionary algorithms. Difficulties with conflicting test objectives and selection of tests to achieve multiple verification goals in the genetic evolutionary framework are also addressed.
2014, 10(2): 397-412
doi: 10.3934/jimo.2014.10.397
+[Abstract](1791)
+[PDF](550.9KB)
Abstract:
This paper presents a new method for linear semi-infinite programming. With the introduction of the so-called generalized ladder point, a ladder method for linear semi-infinite programming is developed. This work includes the generalization of the inclusive cone version of the fundamental theorem of linear programming and the extension of a linear programming ladder algorithm. The extended ladder algorithm finds a generalized ladder point optimal solution of the linear semi-infinite programming problem, which is approximated by a sequence of ladder points. Simple convergence properties are provided. The algorithm is tested by solving a number of linear semi-infinite programming examples. These numerical results indicate that the algorithm is very efficient when compared with other methods.
This paper presents a new method for linear semi-infinite programming. With the introduction of the so-called generalized ladder point, a ladder method for linear semi-infinite programming is developed. This work includes the generalization of the inclusive cone version of the fundamental theorem of linear programming and the extension of a linear programming ladder algorithm. The extended ladder algorithm finds a generalized ladder point optimal solution of the linear semi-infinite programming problem, which is approximated by a sequence of ladder points. Simple convergence properties are provided. The algorithm is tested by solving a number of linear semi-infinite programming examples. These numerical results indicate that the algorithm is very efficient when compared with other methods.
2014, 10(2): 413-441
doi: 10.3934/jimo.2014.10.413
+[Abstract](2509)
+[PDF](730.5KB)
Abstract:
In this paper we study optimal control problems with multiple time delays in control and state and mixed type control-state constraints. We derive necessary optimality conditions in the form of a Pontryagin type Minimum Principle. A discretization method is presented by which the delayed control problem is transformed into a nonlinear programming problem. It is shown that the associated Lagrange multipliers provide a consistent numerical approximation for the adjoint variables of the delayed optimal control problem. We illustrate the theory and numerical approach on an analytical example and an optimal control model from immunology.
In this paper we study optimal control problems with multiple time delays in control and state and mixed type control-state constraints. We derive necessary optimality conditions in the form of a Pontryagin type Minimum Principle. A discretization method is presented by which the delayed control problem is transformed into a nonlinear programming problem. It is shown that the associated Lagrange multipliers provide a consistent numerical approximation for the adjoint variables of the delayed optimal control problem. We illustrate the theory and numerical approach on an analytical example and an optimal control model from immunology.
2014, 10(2): 443-460
doi: 10.3934/jimo.2014.10.443
+[Abstract](1462)
+[PDF](598.3KB)
Abstract:
We study optimal cooperative collision avoidance strategies for two participants in a planar close proximity encounter. Previous research focused on special cases of this problem and showed that bang-bang strategies without switching are optimal in most situations, while singular controls only appear for the case of participants with unequal linear speeds under certain conditions. This paper extends the earlier analyses to a general case of a coplanar close proximity encounter, for which both parameters of the problem may take arbitrary admissible values. For such a case, we present a theoretical and numerical study of the structure of optimal controls. We prove that both controls can not be singular simultaneously and that the only possible singular control is a zero control. We derive formulas for the singular surfaces and verify that sufficient conditions hold for the computed extremal solutions. We identify different types of structural changes of the control strategies and show how the control structure changes with the change in the model parameters and initial conditions.
We study optimal cooperative collision avoidance strategies for two participants in a planar close proximity encounter. Previous research focused on special cases of this problem and showed that bang-bang strategies without switching are optimal in most situations, while singular controls only appear for the case of participants with unequal linear speeds under certain conditions. This paper extends the earlier analyses to a general case of a coplanar close proximity encounter, for which both parameters of the problem may take arbitrary admissible values. For such a case, we present a theoretical and numerical study of the structure of optimal controls. We prove that both controls can not be singular simultaneously and that the only possible singular control is a zero control. We derive formulas for the singular surfaces and verify that sufficient conditions hold for the computed extremal solutions. We identify different types of structural changes of the control strategies and show how the control structure changes with the change in the model parameters and initial conditions.
2014, 10(2): 461-476
doi: 10.3934/jimo.2014.10.461
+[Abstract](1760)
+[PDF](253.0KB)
Abstract:
In this paper, we propose a new parallel splitting descent method for solving a class of variational inequalities with separable structure. The new method can be applied to solve convex optimization problems in which the objective function is separable with three operators and the constraint is linear. In the framework of the new algorithm, we adopt a new descent strategy by combining two descent directions and resolve the descent direction which is different from the methods in He (Comput. Optim. Appl., 2009, 42: 195-212.) and Wang et al. (submitted to J. Optimiz. Theory App.). Theoretically, we establish the global convergence of the new method under mild assumptions. In addition, we apply the new method to solve problems in management science and traffic equilibrium problem. Numerical results indicate that the new method is efficient and reliable.
In this paper, we propose a new parallel splitting descent method for solving a class of variational inequalities with separable structure. The new method can be applied to solve convex optimization problems in which the objective function is separable with three operators and the constraint is linear. In the framework of the new algorithm, we adopt a new descent strategy by combining two descent directions and resolve the descent direction which is different from the methods in He (Comput. Optim. Appl., 2009, 42: 195-212.) and Wang et al. (submitted to J. Optimiz. Theory App.). Theoretically, we establish the global convergence of the new method under mild assumptions. In addition, we apply the new method to solve problems in management science and traffic equilibrium problem. Numerical results indicate that the new method is efficient and reliable.
2014, 10(2): 477-501
doi: 10.3934/jimo.2014.10.477
+[Abstract](1633)
+[PDF](4452.7KB)
Abstract:
Temporarily-captured Natural Earth Satellites (NES) are very appealing targets for space missions for many reasons. Indeed, NES get captured by the Earth's gravity for some period of time, making for a more cost-effective and time-effective mission compared to a deep-space mission, such as the 7-year Hayabusa mission. Moreover, their small size introduces the possibility of returning with the entire temporarily-captured orbiter (TCO) to Earth. Additionally, NES can be seen as interesting targets when examining figures of their orbits. It requires to expand the current state-of-art of the techniques in geometric optimal control applied to low-thrust orbital transfers. Based on a catalogue of over sixteen-thousand NES, and assuming ionic propulsion for the spacecraft, we compute time minimal rendezvous missions for more than $96%$ of the NES. The time optimal control transfers are calculated using classical indirect methods of optimal control based on the Pontryagin Maximum Principle. Additionally we verify the local optimality of the transfers using second order conditions.
Temporarily-captured Natural Earth Satellites (NES) are very appealing targets for space missions for many reasons. Indeed, NES get captured by the Earth's gravity for some period of time, making for a more cost-effective and time-effective mission compared to a deep-space mission, such as the 7-year Hayabusa mission. Moreover, their small size introduces the possibility of returning with the entire temporarily-captured orbiter (TCO) to Earth. Additionally, NES can be seen as interesting targets when examining figures of their orbits. It requires to expand the current state-of-art of the techniques in geometric optimal control applied to low-thrust orbital transfers. Based on a catalogue of over sixteen-thousand NES, and assuming ionic propulsion for the spacecraft, we compute time minimal rendezvous missions for more than $96%$ of the NES. The time optimal control transfers are calculated using classical indirect methods of optimal control based on the Pontryagin Maximum Principle. Additionally we verify the local optimality of the transfers using second order conditions.
2014, 10(2): 503-519
doi: 10.3934/jimo.2014.10.503
+[Abstract](2102)
+[PDF](1340.4KB)
Abstract:
A mathematical model for laser cutting with time-dependent cutting velocity is presented. The model involves two coupled nonlinear partial differential equations for the interacting dynamical behaviors of the free melt boundaries during the process. We define a measurement for the roughness of a cutting surface and introduce an optimal control problem for minimizing the roughness with respect to the cutting velocity and the laser beam intensity along the free melt surface. The optimal control problem involves an additional finite-dimensional averaging constraint. Necessary optimality conditions will be deduced and illustrated by means of numerical examples with data from industrial applications.
A mathematical model for laser cutting with time-dependent cutting velocity is presented. The model involves two coupled nonlinear partial differential equations for the interacting dynamical behaviors of the free melt boundaries during the process. We define a measurement for the roughness of a cutting surface and introduce an optimal control problem for minimizing the roughness with respect to the cutting velocity and the laser beam intensity along the free melt surface. The optimal control problem involves an additional finite-dimensional averaging constraint. Necessary optimality conditions will be deduced and illustrated by means of numerical examples with data from industrial applications.
2014, 10(2): 521-542
doi: 10.3934/jimo.2014.10.521
+[Abstract](1524)
+[PDF](511.7KB)
Abstract:
A new adaptive mesh refinement algorithm is proposed for solving Euler discretization of state- and control-constrained optimal control problems. Our approach is designed to reduce the computational effort by applying the inexact restoration (IR) method, a numerical method for nonlinear programming problems, in an innovative way. The initial iterations of our algorithm start with a coarse mesh, which typically involves far fewer discretization points than the fine mesh over which we aim to obtain a solution. The coarse mesh is then refined adaptively, by using the sufficient conditions of convergence of the IR method. The resulting adaptive mesh refinement algorithm is convergent to a fine mesh solution, by virtue of convergence of the IR method. We illustrate the algorithm on a computationally challenging constrained optimal control problem involving a container crane. Numerical experiments demonstrate that significant computational savings can be achieved by the new adaptive mesh refinement algorithm over the fixed-mesh algorithm. Conceivably owing to the small number of variables at start, the adaptive mesh refinement algorithm appears to be more robust as well, i.e., it can find solutions with a much wider range of initial guesses, compared to the fixed-mesh algorithm.
A new adaptive mesh refinement algorithm is proposed for solving Euler discretization of state- and control-constrained optimal control problems. Our approach is designed to reduce the computational effort by applying the inexact restoration (IR) method, a numerical method for nonlinear programming problems, in an innovative way. The initial iterations of our algorithm start with a coarse mesh, which typically involves far fewer discretization points than the fine mesh over which we aim to obtain a solution. The coarse mesh is then refined adaptively, by using the sufficient conditions of convergence of the IR method. The resulting adaptive mesh refinement algorithm is convergent to a fine mesh solution, by virtue of convergence of the IR method. We illustrate the algorithm on a computationally challenging constrained optimal control problem involving a container crane. Numerical experiments demonstrate that significant computational savings can be achieved by the new adaptive mesh refinement algorithm over the fixed-mesh algorithm. Conceivably owing to the small number of variables at start, the adaptive mesh refinement algorithm appears to be more robust as well, i.e., it can find solutions with a much wider range of initial guesses, compared to the fixed-mesh algorithm.
2014, 10(2): 543-556
doi: 10.3934/jimo.2014.10.543
+[Abstract](1602)
+[PDF](411.8KB)
Abstract:
Multicriterion optimization and Pareto optimality are fundamental tools in economics. In this paper we propose a new relaxation method for solving multiple objective quadratic programming problems. Exploiting the technique of the linear weighted sum method, we reformulate the original multiple objective quadratic programming problems into a single objective one. Since such single objective quadratic programming problem is still nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative relaxation, respectively, this single objective quadratic programming problem is transformed to a computable convex doubly nonnegative programming problem. The optimal solutions of this computable convex problem are (weakly) Pareto optimal solutions of the original problem under some mild conditions. Moreover, the proposed method is tested with two examples and a practical portfolio selection example. The test examples are solved by CVX package which is a solver for convex optimization. The numerical results show that the proposed method is effective and promising.
Multicriterion optimization and Pareto optimality are fundamental tools in economics. In this paper we propose a new relaxation method for solving multiple objective quadratic programming problems. Exploiting the technique of the linear weighted sum method, we reformulate the original multiple objective quadratic programming problems into a single objective one. Since such single objective quadratic programming problem is still nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative relaxation, respectively, this single objective quadratic programming problem is transformed to a computable convex doubly nonnegative programming problem. The optimal solutions of this computable convex problem are (weakly) Pareto optimal solutions of the original problem under some mild conditions. Moreover, the proposed method is tested with two examples and a practical portfolio selection example. The test examples are solved by CVX package which is a solver for convex optimization. The numerical results show that the proposed method is effective and promising.
2014, 10(2): 557-566
doi: 10.3934/jimo.2014.10.557
+[Abstract](1801)
+[PDF](345.4KB)
Abstract:
In this paper, the integer programming problem is studied. We introduce the notion of integer basis and show that a given integer set can be converted into a fixed number of linear combinations of the basis elements. By employing the Stiefel manifold and optimal control theory, the combinatorial optimization problem can be converted into a continuous optimization problem over the continuous Stiefel manifold. As a result, gradient descent methods can be applied to find the optimal integer solution. We demonstrate by numerical examples that this approach can obtain good solutions. Furthermore, this method gives new insights into continuous relaxation for solving integer programming problems.
In this paper, the integer programming problem is studied. We introduce the notion of integer basis and show that a given integer set can be converted into a fixed number of linear combinations of the basis elements. By employing the Stiefel manifold and optimal control theory, the combinatorial optimization problem can be converted into a continuous optimization problem over the continuous Stiefel manifold. As a result, gradient descent methods can be applied to find the optimal integer solution. We demonstrate by numerical examples that this approach can obtain good solutions. Furthermore, this method gives new insights into continuous relaxation for solving integer programming problems.
2014, 10(2): 567-590
doi: 10.3934/jimo.2014.10.567
+[Abstract](1915)
+[PDF](3758.3KB)
Abstract:
For the problem of multimodal image registration, an optimal control approach is presented. The geometrical information of the images will be transformed into weighted edge sketches, for which a linear-elastic or hyperelastic registration will be performed. For the numerical solution of this problem, we provide a direct method based on discretization methods and large-scale optimization techniques. A comparison of a separated and a joint access for the generation of the edge sketches and the determination of the matching deformation is made. The quality of the results obtained with the optimal control method competes well with those generated by a standard variational method.
For the problem of multimodal image registration, an optimal control approach is presented. The geometrical information of the images will be transformed into weighted edge sketches, for which a linear-elastic or hyperelastic registration will be performed. For the numerical solution of this problem, we provide a direct method based on discretization methods and large-scale optimization techniques. A comparison of a separated and a joint access for the generation of the edge sketches and the determination of the matching deformation is made. The quality of the results obtained with the optimal control method competes well with those generated by a standard variational method.
2014, 10(2): 591-611
doi: 10.3934/jimo.2014.10.591
+[Abstract](1650)
+[PDF](640.6KB)
Abstract:
The problem of scheduling with time-dependent processing times has been studied for more than two decades and significant advances have been made over the years. However, most work has paid more attention to the single-criterion models. Furthermore, most heuristics are constructed for the time-dependent scheduling problems in a step-by-step way. Motivated by the observations, this paper studies a two-agent scheduling model with increasing linear deterioration jobs in which the processing time of a job is modeled as an increasing linear function of its starting time. The objective function is to minimize the sum of the maximum weighted tardiness of the jobs of the first agent and the total weighted tardiness of the jobs of the second agent. This problem is known to be strongly NP-hard. Thus, as an alternative, the branch-and-bound, ant colony algorithm and simulated annealing algorithms are developed for the problem. Computational results are also presented to determine the performance of the proposed algorithms.
The problem of scheduling with time-dependent processing times has been studied for more than two decades and significant advances have been made over the years. However, most work has paid more attention to the single-criterion models. Furthermore, most heuristics are constructed for the time-dependent scheduling problems in a step-by-step way. Motivated by the observations, this paper studies a two-agent scheduling model with increasing linear deterioration jobs in which the processing time of a job is modeled as an increasing linear function of its starting time. The objective function is to minimize the sum of the maximum weighted tardiness of the jobs of the first agent and the total weighted tardiness of the jobs of the second agent. This problem is known to be strongly NP-hard. Thus, as an alternative, the branch-and-bound, ant colony algorithm and simulated annealing algorithms are developed for the problem. Computational results are also presented to determine the performance of the proposed algorithms.
2014, 10(2): 613-620
doi: 10.3934/jimo.2014.10.613
+[Abstract](1738)
+[PDF](353.5KB)
Abstract:
In inverse scheduling problems, a job sequence is given and the objective is to determine the minimal perturbation to parameters, such as processing times or weights of jobs so that the given schedule becomes optimal with respect to a pre-selected objective function. In this paper we study the necessary and sufficient conditions for optimality of the total completion time problem on parallel machines and inverse scheduling problem of the total completion time objective on parallel machines in which the processing times are minimally adjusted, so that a given target job sequence becomes an optimal schedule.
In inverse scheduling problems, a job sequence is given and the objective is to determine the minimal perturbation to parameters, such as processing times or weights of jobs so that the given schedule becomes optimal with respect to a pre-selected objective function. In this paper we study the necessary and sufficient conditions for optimality of the total completion time problem on parallel machines and inverse scheduling problem of the total completion time objective on parallel machines in which the processing times are minimally adjusted, so that a given target job sequence becomes an optimal schedule.
2014, 10(2): 621-636
doi: 10.3934/jimo.2014.10.621
+[Abstract](1305)
+[PDF](395.0KB)
Abstract:
By using the Least Squares Support Vector Machines (LS-SVMs), we develop a numerical approach to find an approximate solution for affine nonlinear systems with partially unknown functions. This approach can obtain continuous and differential approximate solutions of the nonlinear differential equations, and can also identify the unknown nonlinear part through a set of measured data points. Technically, we first map the known part of the affine nonlinear systems into high dimensional feature spaces and derive the form of approximate solution. Then the original problem is formulated as an approximation problem via kernel trick with LS-SVMs. Furthermore, the approximation of the known part can be expressed via some linear equations with coefficient matrices as coupling square matrices, and the unknown part can be identified by its relationship to the known part and the approximate solution of affine nonlinear systems. Finally, several examples for different systems are presented to illustrate the validity of the proposed approach.
By using the Least Squares Support Vector Machines (LS-SVMs), we develop a numerical approach to find an approximate solution for affine nonlinear systems with partially unknown functions. This approach can obtain continuous and differential approximate solutions of the nonlinear differential equations, and can also identify the unknown nonlinear part through a set of measured data points. Technically, we first map the known part of the affine nonlinear systems into high dimensional feature spaces and derive the form of approximate solution. Then the original problem is formulated as an approximation problem via kernel trick with LS-SVMs. Furthermore, the approximation of the known part can be expressed via some linear equations with coefficient matrices as coupling square matrices, and the unknown part can be identified by its relationship to the known part and the approximate solution of affine nonlinear systems. Finally, several examples for different systems are presented to illustrate the validity of the proposed approach.
2014, 10(2): 637-663
doi: 10.3934/jimo.2014.10.637
+[Abstract](1899)
+[PDF](536.0KB)
Abstract:
We present a substitution secant/finite difference (SSFD) method to solve the finite minimax optimization problems with a number of functions whose Hessians are often sparse, i.e., these matrices are populated primarily with zeros. By combining of a substitution method, a secant method and a finite difference method, the gradient evaluations can be employed as efficiently as possible in forming quadratic approximations to the functions, which is more effective than that for large sparse unconstrained differentiable optimization. Without strict complementarity and linear independence, local and global convergence is proven and $q$-superlinear convergence result and $r$-convergence rate estimate show that the method has a good convergence property. A handling method of a nonpositive definitive Hessian is given to solve nonconvex problems. Our numerical tests show that the algorithm is robust and quite effective, and that its performance is comparable to or better than that of other algorithms available.
We present a substitution secant/finite difference (SSFD) method to solve the finite minimax optimization problems with a number of functions whose Hessians are often sparse, i.e., these matrices are populated primarily with zeros. By combining of a substitution method, a secant method and a finite difference method, the gradient evaluations can be employed as efficiently as possible in forming quadratic approximations to the functions, which is more effective than that for large sparse unconstrained differentiable optimization. Without strict complementarity and linear independence, local and global convergence is proven and $q$-superlinear convergence result and $r$-convergence rate estimate show that the method has a good convergence property. A handling method of a nonpositive definitive Hessian is given to solve nonconvex problems. Our numerical tests show that the algorithm is robust and quite effective, and that its performance is comparable to or better than that of other algorithms available.
2018 Impact Factor: 1.025
Authors
Editors
Referees
Librarians
Email Alert
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]