Journal Search Engine

ISSN : 1229-3431(Print)
ISSN : 2287-3341(Online)

Journal of the Korean Society of Marine Environment and Safety Vol.24 No.3 pp.295-301
DOI : https://doi.org/10.7837/kosomes.2018.24.3.295

A Comparison of Optimization Algorithms: An Assessment of Hydrodynamic Coefficients

Daewon Kim^*†

^*Graduate School, Faculty of Mechanical Engineering and Marine Technology, University of Rostock, Albert-Einstein-Strasse 2, 18059 Rostock, Germany

Corresponding Author : daewon.kim@uni-rostock.de

Received 20180115 Review 20180212 Accepted 20180529

Abstract

This study compares optimization algorithms for efficient estimations of ship’s hydrodynamic coefficients. Two constrained algorithms, the interior point and the sequential quadratic programming, are compared for the estimation. Mathematical optimization is designed to get optimal hydrodynamic coefficients for modelling a ship, and benchmark data are collected from sea trials of a training ship. A calibration for environmental influence and a sensitivity analysis for efficiency are carried out prior to implementing the optimization. The optimization is composed of three steps considering correlation between coefficients and manoeuvre characteristics. Manoeuvre characteristics of simulation results for both sets of optimized coefficients are close to each other, and they are also fit to the benchmark data. However, this similarity interferes with the comparison, and it is supposed that optimization conditions, such as designed variables and constraints, are not sufficient to compare them strictly. An enhanced optimization with additional sea trial measurement data should be carried out in future studies.

Key Words : Hydrodynamic coefficients , Optimization algorithms , Interior point , Sequential quadratic programming , Sensitivity analysis

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1 Introduction

Increasing the size and speed of a vessel gives economic benefits, but at the same time the risk of accidents increases. Thus, understanding a ship's manoeuvrability is important to reduce risk and simulation technology is a representative measure to estimate manoeuvrability. Estimation of the hydrodynamic coefficients for the forces and moments acting on the hull is important in a ship modelling process for the simulation. The International Towing Tank Conference (ITTC) presents a classification for estimation methods and their accuracy in effort/cost characteristics, as shown in Figure 1 and Figure 2 (ITTC, 2008).

Unlike a captive model test and computational fluid dynamics (CFD), which are widely used for ships under construction (Lee, 2015), a system identification using sea trials is an efficient method for existing ships (Kim et al., 2017). This system identification estimates the hydrodynamic coefficients using a mathematical optimization algorithm. The algorithm conducts manoeuvre simulation and compares its result with benchmark data, such as sea trial data, at every iteration and it provides updated target variables to be optimized.

The Extended Kalman Filter (EKF) was used at the beginning of this method (Abkowitz, 1980; Hwang, 1980), and System Based (SB) free running tests were included in the EKF algorithm (Rhee and Kim, 1999; Zahng and Zou, 2011). Other mathematical algorithms were also introduced with the development of computer technology, such as the sequential quadratic programming (SQP) and the Broyden-Fletcher-Goldfarb-Shanno method (BFGS) and an interior point (Saha and Sarker, 2010; Tran et al., 2014).

This study compares the optimization algorithms with the same benchmark from the sea trial and optimization conditions. The interior point and the SQP were selected for comparison and three manoeuvres were used to conduct the optimization.

2 Optimization algorithms

2.1 Interior point

An interior point algorithm finds a solution for linear and nonlinear convex optimization problems by searching the interior of the feasible region. Since von Neumann suggested the concept of the algorithm as the classical simplex method, there has been great progress with the interior point algorithm (Dantzig and Thapa, 2003). Khachiyan provided an ellipsoid method, which is slower than the simplex method for the worst case (Khachiyan, 1980). Karmarkar discovered a faster one than Khachiyan’s and it could apply to convex problems (Karmarkar, 1984). Beyond Karmarkar, the interior point algorithm has several varied subclasses, and it is accepted that a primal-dual method is the most efficient (Gondzio, 2012).

An idea of the primal-dual method starts from that a linear program can be solved by using another linear program, which is the opposite of the original one. The primal problem is the following:(1)

minimize \sum_{x} c^{T} x

(1)

subject to A_x = b, x ≥ 0

where $c, x \in R^{n}, b \in R^{m}$ and A is an m × n matrix. The dual problem can be formulated as follows.(2)

maximize \sum_{y} b^{T} y

(2)

subject to $A^{T} y + s = c, s \geq 0$

where $s \in R^{n}, y \in R^{m}$ . The optimality conditions are the following:(3)

\begin{array}{l} A^{T} y + s = c \\ A x = b \\ X S e = 0 \\ (x, s) \geq 0 \end{array}

(3)

where X is a form of diagonal matrix.
Benefits and disadvantages of the interior point algorithm are as follows (Bertsimas and Tsitsiklis, 1997):
Benefits
- Good for large, sparse problems
- Have polynomial time asymptotic complexity Disadvantages
- Slower calculation for small problems than the simplex method
- Easily stuck at a local minimum due to the great influence of the starting points

2.2 Sequential quadratic programming

Sequential quadratic programming (SQP) is a reliable method of solving optimization problems that have nonlinear constraints. Like most optimization algorithms, SQP is not a single algorithm, but a concept with which various sub-algorithms are associated (Boggs et al., 1995). The idea of SQP is to solve a nonlinear problem by quadratic programming subproblems to get a better optimization result. A standard problem with nonlinear constraints can be written as follows:(4)

\begin{array}{l} minimize f (x), subject to \\ c_{E} (x) = 0 \\ c_{I} (x) ≺ 0 \end{array}

(4)

where f is an objective function $(f : R^{n} \to R)$ is an equality constraint $(c_{E} : R^{n} \to R_{m})$ and c_I is an inequality constraint $(c_{I} : R^{n} \to R^{p})$ .

The SQP algorithm solves a problem locally (Gilbert, 2017). At each iteration k, the algorithm calculates a solution to the quadratic programming subproblem with its Lagrangian:(5)

\begin{array}{l} min_{d \in R^{n}} \nabla f {(x_{k})}^{T} d + \frac{1}{2} d^{T} M_{k} d \\ c_{E} (x_{k}) + c_{E}^{T} (x_{d}) d = 0 \\ c_{I} (x_{k}) + c_{I}^{T} (x_{k}) d ≺ 0 \end{array}

(5)

where M_k is the Hessian of the Lagrangian ℒ or an approximation.(6)(7)

L (x, y, z) = f (x) + y^{T} c_{E} (x) + z^{T} c_{I} (x)

(6)

M_{k} = H L (x^{k}, y^{k}, z^{k}) = \frac{\partial^{2} L (x^{k}, y^{k}, z^{k})}{\partial x^{k} \partial y^{k} \partial z^{k}}

(7)

The benefit of the SQP algorithm is that each iteration does not have to be a feasible point. It is advantageous when a critical constraint is near the feasible points. However, this also means that an iteration that is not the final minimum is not guaranteed regardless of whether it is in the feasible area.

3 Estimation of hydrodynamic coefficients

3.1 Mathematical model

All simulations are carried out under the three degrees of freedom ship- and earth-fixed coordinate systems. As shown in Fig. 3, the Earth-fixed-coordinate $O_{0} - x_{0} y_{0}$ plane and the Ship-fixed-coordinate O-xy place on the undisturbed free surface. The x₀ axis points in the direction of a ship's heading, and the z₀ and z axis point downward.

where,

G : Center of gravity
Ψ : Heading
β : Drift angle
: Rudder angle
$\vec{V}$ : Ship’s speed
r : yaw rate

In the mathematical model, a ship is considered as a massive and rigid body. Equation (8) presents the forces and moment acting on a vessel according to the Newtonian law of motion (Rheinmetall Defense, 2008).

\begin{array}{l} X = m (\dot{u} - υ r - x_{g} r^{2}) \\ Y = m (\dot{υ} - u r + x_{g} \dot{r}) \\ N = I_{z} \dot{r} + m x_{g} (\dot{υ} + u r) \end{array}

(8)

All forces and moment in the mathematical model are composed of several modules: hull, propeller, rudder and external forces and moments, if necessary. Equation (9) shows the detailed composition of the hydrodynamic forces and moment, especially acting on the hull. This study applied the empirical estimation formulas of Norrbin and Clarke to calculate initial values for the optimization (Norrbin, 1971; Clarke et al., 1983). As shown in Equation (10), every coefficient can be formalized by the function of the ship's main dimensions: length, beam, draught, displacement and trim. Ynon and Nnon are non-linear components for sway force and yaw moment.

\begin{array}{l} {X^{'}}_{H} = {X^{'}}_{u p} \dot{u} + {X^{'}}_{υ r} υ r + {X^{'}}_{u u} u | u | + {X^{'}}_{u 4} u^{3} | u | + {X^{'}}_{u υ υ υ} u υ^{2} | υ | \\ {Y^{'}}_{H} = {Y^{'}}_{υ p} \dot{υ} + {Y^{'}}_{r p} \dot{r} + {Y^{'}}_{u r} u r + {Y^{'}}_{u υ} | u | υ + {Y^{'}}_{n o n} \\ {N^{'}}_{H} = {N^{'}}_{r p} \dot{r} + {N^{'}}_{υ p} \dot{υ} + {N^{'}}_{u r} | u | r + {N^{'}}_{u υ} u υ + {N^{'}}_{n o n} \end{array}

(9)

{{Y^{'}}_{u υ}, {Y^{'}}_{u r}, {N^{'}}_{u υ}, {N^{'}}_{u r}, {Y^{'}}_{n o n}, {N^{'}}_{n o n}} = f (L, B, T, Δ)

(10)

3.2 Benchmark data

Sea trials are carried out with the training ship 'Hanbada' to collect the benchmark data. A preparation for the sea trials is borrowed from the trials of the training ship ‘Sae Yu Dal’ (Im et al., 2011). For the purpose of environment calibration, the International Maritime Organization’s (IMO) correction method is applied to raw measurement data (IMO, 2002). The correction requires a record of a turning manoeuvre, of at least a 720° change of heading. From the data, two half circles can be obtained after the ship’s heading change of 180° from the beginning of the test. The local current velocity V_i can be defined by the two corresponding positions $({x^{'}}_{1 i}, {y^{'}}_{1 i}, {t^{'}}_{1 i})$ and $({x^{'}}_{2 i}, {y^{'}}_{2 i}, {t^{'}}_{2 i})$ from the half circles as equation (11):

{\underline{V}}_{i} = \frac{(x_{2 i} - x_{1 i}, y_{2 i} - y_{1 i})}{(t_{2 i} - t_{1 i})}

(11)

From the set of local velocity, the estimated current velocity can be calculated by equation (12):

{\underline{V}}_{c} = \frac{1}{n} \sum_{i = 1}^{n} {\underline{V}}_{i} = \frac{1}{n} \sum_{i = 1}^{n} \frac{(x_{2 i} - x_{1 i}, y_{2 i} - y_{1 i})}{(t_{2 i} - t_{1 i})}

(12)

The magnitude of the current velocity can be calculated from the equation (13):

V_{c} = | {\underline{V}}_{c} |

(13)

The final corrected trajectories of the measurement data can be obtained from equation (14):

{\underline{X}}^{'} (t) = \underline{X} (t) - {\underline{V}}_{c} t

(14)

where X(t) is the measured position vector and $\underline{X^{'}} (t)$ is the corrected position vector of the ship and $\underline{X^{'}} (t) = \underline{X} (t)$ . Fig. 4 shows the result of the environmental calibration for the measurement data.

The number of target variables is an important factor to determine calculation time in an optimization. Unimportant target variables may cause confusion in the decision of the optimization algorithm. Thus, is it important to conduct a sensitivity analysis for all hydrodynamic coefficients prior to optimization. Table 1 presents the results of the sensitivity analysis, from a previous study (Kim et al., 2017).

3.3 Optimization conditions

Table 2 presents conditions for the whole optimization process which is composed of three steps. Different from steps 2 and e, step 1 does an optimization without constraints. A manoeuvre characteristic of straight motion, distance by LBP, is chosen for the objective function of step 1. For steps 2 and 3, an objective function is the trajectory difference between the benchmark and a simulation result. A nonlinear equality function is the difference in the first overshoot angle of the zigzag manoeuvre and the tactical diameter of the turning manoeuvre, respectively. The conditions are applied for both the Interior Point and SQP algorithms.

4 Comparison of algorithms

4.1 Optimization results

Table 3 presents the optimized hydrodynamic coefficients for all steps. The coefficients optimized by both algorithms differ from each other, but the difference is not very large. This is also shown in Table 4, which compares the manoeuvre characteristics and number of iterations for the benchmark, with simulation results using Clark estimation and simulation results optimizations. The number of iterations for both algorithms is the same, and derived manoeuvre characteristics are similar to each other.

Fig. 5 through Fig. 8 show the comparison of trajectories and heading changes for the straight motion, zigzag manoeuvre and turning manoeuvre, respectively. The results for both algorithms are close to the benchmark, compared to the result of the Clarke estimation. In the case of the turning manoeuvre, the advance and tactical diameter for the results of both algorithms are to with the benchmark, but the steady-state diameter is bigger than the benchmark. This can be solved by applying the constraints. Fig. 6, 7

4.2 Review of results

The comparison of simulations shows that there is only a minor difference between the results using the two algorithms. The results of the straight motion and the zigzag manoeuvre are almost the same. For the case of the turning manoeuvre, the advance and tactical diameter of the interior point method are fit to the benchmark more than the ones for the SQP. However, as shown in Fig. 8, the diameter of the steady-state circle for both methods is greater than that of the benchmark. It is supposed that this result is caused by the optimization settings: improper design variables, insufficient constraints and so on. An enhanced sensitivity analysis for design variables and strict constraints can be helpful for satisfactory and accurate optimization. This should be considered in future studies with additional sea trial measurement data.

5 Conclusion

This paper compared two algorithms for efficient optimization of the hydrodynamic coefficients for ship modelling. The mathematical optimization and its algorithm is the main idea of the system identification method and its result is dependent on choosing a proper algorithm. For this, an interior point and an SQP algorithm are chosen for comparison. The study can be summarized as follows:

1) The optimization is carried out under three steps, and each step has a different benchmark manoeuvre. Prior to the conduct of the optimization, an environmental correction for the measurements and a sensitivity analysis for the coefficients is carried out.
2) Simulation results using optimized coefficients for both algorithms are almost the same as each other, and they are close to the benchmark compared to the results of the Clarke estimation.

Based on the results of this study, it is shown that both algorithms are suitable to apply in the optimization. However, comparison is not satisfactory because their results are similar despite the difference in finding the optimal solution. A stricter sensitivity analysis for design variables and constraints should be considered in future studies for acceptable optimization results. Also, preparation of additional measurements with various type of ships is required for the reliability of the optimization.

Figure

Fig. 1..

Classification for estimation methods.

Fig. 2..

Accuracy to effort/cost characteristics.

Fig. 3..

Coordinate system of the vessel.

Fig. 4..

Result of environmental calibration.

Fig. 5..

Trajectory comparison for the straight motion.

Fig. 6..

Trajectory comparison for zigzag manoeuvre.

Fig. 7..

Heading change comparison for zigzag manoeuvre.

Fig. 8..

Trajectory comparison for turning manoeuvre.

Table

Table 1.

Design variables for each iteration

Optimization Step	Coefficients	Remarks
Step 1	Xuu Xu4	Straight motion
Step 2	Yuv Yur Nuv Nur	Small rudder angle
Step 3	Xvr Yvr Nrr Nvv	Large rudder angle

Table 2.

Detailed conditions in an optimization

	Step1	Step2	Step3
Algorithm	Interior-point /SQP
Initial values	Xuu	-0.0458	Yuv	-1.5336	Xvr	1.0225
Xu4	-0.3490	Yur	0.3245	Yvr	1.7265
	Nuv	-0.5796	Nrr	0.1079
Nur	-0.2429	Nvv	0.8633
Lower bounds	Xuu	-0.4000	Yuv	-15.336	Xvr	0.0001
Xu4	-3.0000	Yur	0.0001	Yvr	0.0001
	Nuv	-5.7960	Nrr	0.0001
Nur	-0.2429	Nvv	0.0001
Upper bounds	Xuu	-0.0001	Yuv	-0.0001	Xvr	10.000
Xu4	-0.0001	Yur	3.2450	Yvr	17.000
	Nuv	-0.0001	Nrr	1.0790
Nur	-0.0001	Nvv	8.6330
Objective function	Distance/LBP straight motion	Trajectory difference
zigzag 10 degrees	turning circle 35 degrees
Constraints	none	first over shoot	tactical diameter

Table 3.

Optimization results of hydrodynamic coefficients

Coeff.	Clarke	Interior point	SQP
Step1	Xuu	-0.0458	-0.0418	-0.0490
Xu4	-0.3490	-0.3148	-0.2214
Step2	Yuv	-1.5336	-1.0979	-1.2759
Yur	0.3245	0.4263	0.2700
Nuv	-0.5796	-1.9296	-1.4564
Nur	-0.2429	-0.5892	-0.5095
Step3	Xvr	1.0225	0.4556	0.4145
Yvr	1.7265	1.4809	1.8749
Nrr	0.1079	0.2082	0.0001
Nvv	0.8633	1.9587	2.2428

Table 4.

Optimization results of manoeuvre characteristics

	Clarke	Benchmark	Interior point	SQP
Iterations	-	-	14	14
Dist./LBP	23.01	23.40	23.4210	23.1490
1st overshoot [°]	3.10	7.20	6.70	6.50
2nd overshoot[°]	4.70	12.70	15.10	13.30
Advance [m]	298.16	298.00	292.17	288.72
Tactical diameter [m]	432.11	399.50	399.50	399.69

Reference

M.A. Abkowitz (1980) Measurement of Hydrodynamic Characteristics from Ship Maneuvering Trials by System Identification., SNAME Transactions, Vol.88 ; pp.283-318
D.J. Bertsimas , J.N. Tsitsiklis (1997) Introduction to Linear Optimization, Athena Scientific, Vol. 6, Belmont, pp. 438-439.,
P.T. Boggs , J.W. Tolle , A.J. Kearsley (1995) On the Convergence of a Trust Region SQP Algorithm for Nonlinearly Constrained Optimization Problems, Proceedings of the Seventeenth IFIP TC7 Conference on System Modelling and Optimization, pp. 3-12.,
D. Clarke , P. Gedling , G. Hine (1983) The Application of Manoeuvring Criteria in Hull Design Using Linear Theory, Transactions of the RINA, ; pp.45-68
G.B. Dantzig , M.N. Thapa (2003) Linear Programming 2 Theory and Extensions., Springer, ; pp.67-70
J.C. Gilbert (2017) An SQP Solver in Nonlinear Optimization Application to the Hanging Chain Problem Session 2 The Local SQP Algorithm, Project of the Course Advanced Continuous Optimization., University Paris-Saclay, ; pp.2
J. Gondzio (2012) Interior Point Methods 25 Years Later., Eur. J. Oper. Res., Vol.218 (3) ; pp.587-601
W.Y. Hwang (1980) Application of System Identification to Ship Maneuvering, PhD thesis, MIT, pp. 84-91.,
N.K. Im , S.H. Han , T.N.L. Nguyen (2011) A study on Ship’s Maneuverability Evaluation by Real Ship Test., Journal of the Korean Society of Marine Environment & Safety, Vol.17 (4) ; pp.383-389
IMO (2002) International Maritime Organization, Explanatory Notes to the Standards for Ship Manoeuvrability, MSC/Circ. 1053, pp. 14-16.,
ITTC (2008) The Manoeuvring Committee Final Report and Recommendations to the 25th ITTC, Proceedings of 25^th ITTC, Vol.Vol. 1 ; pp.145-152
N. Karmarkar (1984) A New Polynimial-Time Algorithm for Linear Programming., Combinatorica, Vol.4 (4) ; pp.373-395
L.G. Khachiyan (1980) Polynomial Algorithms in Linear Programming., USSR Comput. Math. Math. Phys., Vol.20 (1) ; pp.53-72
D.W. Kim , K. Benedict , M. Paschen (2017) Estimation of Hydrodynamic Coefficients from Sea Trials Using a System Identification Method., Journal of the Korean Society of Marine Environment & Safety, Vol.23 (3) ; pp.258-265
S. Lee (2015) Study on the Manoeuvrability as Function of Stern Hull Form in Shallow Water., Journal of the Korean Society of Marine Environment & Safety, Vol.21 (5) ; pp.558-570
N.H. Norrbin (1971) Theory and Observations on the Use of a Mathematical Model for Ship Manoeuvring in Deep and Confined Waters, SSPA Publication, No. 68, Gothenburg.,
K.P. Rhee , K. Kim (1999) A New Sea Trial Method for Estimating Hydrodynamic Derivatives., Journal of Ship and Ocean Technology, Vol.3 (3) ; pp.25-44
Rheinmetall Defence Electronic (2008) Advanced Nautical Simulator 5000 (ANS 5000) - Software Requirement Specification (SRS)., Company Publication, ; pp.3.58-3.67
G.K. Saha , A.K. Sarker (2010) Optimization of Ship Hull Parameter of Inland Vessel with Respect to Regression Based Resistance Analysis, Proceedings of The International Conference of Marine Technology 2010 (MARTEC), ; pp.471-476
K.T. Tran , A. Ouahsine , F. Hissel , P. Sergent (2014) Identification of Hydrodynamic Coefficients from Sea Trials for Ship Maneuvering Simulation, Transport Research Arena 2014, Paris.,
X. Zhang , Z. Zou (2011) Identification of Abkowitz Model for Ship Manoeuvring Motion using ε-support Vector Regression., J. Hydrodynam., Vol.23 (3) ; pp.353-360