1,109
Views
0
CrossRef citations to date
0
Altmetric
Research Article

Space splitting convexification: a local solution method for nonconvex optimal control problems

ORCID Icon, ORCID Icon & ORCID Icon
Pages 517-540 | Received 09 May 2021, Accepted 05 Nov 2021, Published online: 25 Nov 2021

Abstract

Many optimal control tasks for engineering problems require the solution of nonconvex optimisation problems, which are rather hard to solve. This article presents a novel iterative optimisation procedure for the fast solution of such problems using successive convexification. The approach considers two types of nonconvexities. Firstly, equality constraints with possibly multiple univariate nonlinearities, which can arise for nonlinear system dynamics. Secondly, nonconvex sets comprised of convex subsets, which may occur for semi-active actuators. By introducing additional decision variables and constraints, the decision variable space is decomposed into affine segments yielding a convex subproblem which is solved efficiently in an iterative manner. Under certain conditions, the algorithm converges to a local optimum of a scalable, piecewise linear approximation of the original problem. Furthermore, the algorithm tolerates infeasible initial guesses. Using a single-mass oscillator application, the procedure is compared with a nonlinear programming algorithm, and the sensitivity regarding initial guesses is analysed.

1. Introduction

Many optimal control tasks for engineering problems require the solution of nonconvex optimisation problems (OPs), which are harder to solve than convex ones. The nonconvexity can have various causes. Restrictions in the operating range of actuators can result in nonconvex sets. Nonconvexity can also be caused by nonlinear system dynamics resulting in nonlinear and thus nonconvex equality constraints. Since a fast and robust computation of the optimum is always desirable and even essential for real-time control applications, convexification represents a fundamental field in optimal control. Convex OPs can be solved efficiently and robustly with elaborate solvers capable of computing the global optimum with high accuracy and generally short computation times. Various convexification methods have been proposed, which generally solve nonconvex problems by iteratively solving convex substitute problems.

1.1. Literature survey on convexification techniques

Lossless convexification (LC) transforms a special class of nonconvex sets into convex ones by lifting the optimisation space into a higher dimension using additional decision variables (Acikmese & Blackmore, Citation2011; Acikmese & Ploen, Citation2007). The approach is applicable to a special class of nonconvex sets: sets generated by removing a convex subset from a convex set. This has been used in aeronautic optimal control applications to successfully convexify annulus-shaped sets. An overview regarding the individual findings on LC is given in Raković and Levine (Citation2018, p.338).

Another often employed technique for convex approximation is linearisation since linear objectives and constraints are convex (Boyd & Vandenberghe, Citation2004). However, linearisation can introduce conservativeness and infeasibility since the resulting accuracy strongly depends on the nonlinearity as well as the linearisation point. Various linearisation techniques have been used to approximate nonlinear systems when applying optimal control methods. In the simplest case, the system is linearised at each time instant around the current operating point, exemplarily implemented in Falcone et al. (Citation2007). However, the model approximation is only sufficiently valid in a close neighbourhood around the linearisation point. With increasing distance to this point, the linearised OP can strongly differ from the original one. Thus, this approach can result in poor controller performance or even lead to infeasibility or instability.

In order to mitigate linearisation errors, the system can be linearised around predicted trajectories resulting in efficiently solvable quadratic programming (QP) problems (Diehl et al., Citation2005; Seki et al., Citation2004). One method using iterative linearisation around trajectories in a model predictive control (MPC) setup is the so-called real-time iteration approach (Diehl et al., Citation2005). The procedure assumes that at every time instant, the shifted solution from the preceding time instant represents a good initial guess close to the actual solution. Thus, a full Newton-step is taken, omitting underlying line-search routines to reduce computation time.

Another iterative scheme linearising around changing trajectories has been presented in Mao et al. (Citation2016). Starting from an initial trajectory, the nonlinear system equations are successively linearised around the solution computed in the preceding iteration. Adding virtual control inputs eliminates the artificial infeasibility introduced by the linearisation. Furthermore, including trust regions ensures that the solution does not deviate too much from the preceding succession and thus the linearisation represents a valid approximation. This avoids unboundedness of the linearised OP. Based on the ratio between actual objective change and linearised objective change, the algorithm adjusts the trust regions and terminates if the objectives coincide.

A linearise-and-project (LnP) approach has been used in Mao et al. (Citation2017) to resolve the nonconvexity due to nonlinear system equations and nonconvex constraints. The approach presumes convex functions for the right-hand side of the system differential equations. The satisfaction of the system dynamics is ensured by relaxing the corresponding equality constraints into inequality constraints and using exact penalty functions. In an iterative optimisation routine, the computed solution is projected onto the constraints in each iteration to gain adequate linearisation points.

Instead of linearising the system equations around trajectories, a linear input-to-state behaviour can be enforced via feedback-linearisation (Khalil, Citation2002, p. 505). An optimal control method can then be used to optimally control the linearised system in an outer control loop (Del Re et al., Citation1993). However, it is possible that the nonlinear mapping of the feedback linearisation transforms originally convex objective and constraint functions into nonconvex ones (Simon et al., Citation2013). Then, the exact satisfaction of these constraints requires a nonlinear programming (NLP) strategy or an iterative scheme which both eliminate the computational benefits of the feedback-linearisation (Kurtz & Henson, Citation1997). One possible solution to this problem is approximating these constraints by estimating future inputs based on the preceding time instant within an MPC scheme (Kurtz & Henson, Citation1997; Schnelle & Eberhard, Citation2015). The authors in Simon et al. (Citation2013) have proposed an alternative MPC approach that replaces such nonlinear constraints via dynamically generated local inner polytopic approximations rendering the OP convex.

Fuzzy MPC with models of Takagi-Sugeno (TS) type has been successfully used for nonlinear MPC. The TS modelling procedure enables an accurate approximation of nonlinear systems by using data combined with model knowledge (Tanaka & Wang, Citation2004). The modelling approach decomposes nonlinear models into several local approximations which are blended together via fuzzy rules. However, this requires the system matrices to be stored, thus occupying more memory. Although TS fuzzy models have been successfully used in nonlinear MPC, computation time can be strongly reduced by linearising the TS models around predicted trajectories (Mollov et al., Citation2004Citation1998). The resulting convex QP problem can be solved efficiently while guaranteeing convergence via a line search mechanism.

Differential dynamic programming initially linearises the system equations around a nominal trajectory. Starting from the terminal state, a backward pass identifies the optimal controller gains of a linear quadratic regulator at each time step using the linearised system. Subsequently, a forward pass computes new nominal trajectories via numerical integration using the controller gains previously computed in the backward pass. This procedure is repeated until convergence. Iterative linear quadratic regulators are a variant of differential dynamic programming (Mayne, Citation1973). The main difference is that only first-order derivatives are used for the approximation of the system dynamics via Taylor expansion instead of second-order ones which decreases computation time (Tassa et al., Citation2012). Constrained versions of this optimisation technique have been presented in Tassa et al. (Citation2014), Xie et al. (Citation2017) and Chen et al. (Citation2017).

Lifting-based MPC methods represent another class of linearisation approaches used for solving optimal control problems (OCPs) with nonlinear systems. By lifting the nonlinear dynamics to a space of higher dimension, the evolution of the system can be represented in a bilinear or linear fashion via Carleman linearisation or the Koopman operator framework, respectively. Representing the nonlinear system equations via bilinear terms enables the analytical computation of sensitivity functions (Armaou & Ataei, Citation2014) and of solutions (Fang & Armaou, Citation2015) which speeds up computation time. The Koopman MPC approach employs a linear predictor of higher order, which is identified via data sets, to approximate the nonlinear system (Korda & Mezić, Citation2018). The resulting larger OCP is condensed by eliminating the state decision variables and then solved for the input decision variables using linear MPC. Hence, this method enables a fast solution of nonlinear OCPs. However, identifying the linear Koopman system involves some effort requiring an adequate selection of basis functions, non-recurrent data sets and the solution of convex OPs (Cibulka et al., Citation2019). Furthermore, the Koopman MPC approach does not always outperform the standard MPC method using local linearisations (Cibulka et al., Citation2020). Depending on the dimension of the lifted states, both approaches can require the storage of a great number of offline computed matrices.

Various local methods for solving nonconvex quadratically constrained quadratic programming (QCQP) problems have been summarised in d'Aspremont and Boyd (Citation2003) and Park and Boyd (Citation2017). A two-phase coordinate descent method first reduces the maximum constraint violation trying to find a feasible point. The second phase is restricted to feasible points only and searches in each iteration for a feasible point with a better objective function value. The convex-concave procedure (CCP) is a method for finding a local optimum for difference-of-convex programming problems, thus suitable for QCQP. The nonconvex part of the constraints is linearised rendering the constraints convex. In order to deal with infeasible initial guesses, penalty CCP relaxes the linearised constraints via slack variables and introduces a gradually increasing penalty objective for constraint violations. The alternating directions method of multipliers (ADMM) is a variant of the augmented Lagrangian method. It forms an equivalent OP by using auxiliary decision variables which must satisfy a consensus constraint. The objective function is augmented using switching indicator functions which penalise individual constraint violations. The augmented objective function terms are separated into two groups of decision variables. Instead of solving the proximal augmented Lagrangian function for both groups of decision variables simultaneously, the solution is computed using an alternating approach. First, the first group of decision variables is fixed and the problem is solved for the second group. Then, the solution of the second group is fixed and the problem is solved for the first one. The results are used for the dual variable update and the procedure is repeated. This alternating approach requires the solution of simplified QCQP problems enhancing computation time compared to simultaneously solving for both groups of decision variables.

Convexification measures for sequential quadratic programming (SQP) approaches on a more algorithmic level have been presented in Verschueren (Citation2018). Many QP solvers do not support an indefinite Hessian of the Lagrangian since then a descent direction is not guaranteed. The author has presented a structure-preserving convexification procedure for indefinite Hessians. The convexified Hessian can be fed to any structure-exploiting QP solver (Verschueren, Citation2018, p. 39). Furthermore, sequential convex quadratic programming is proposed which uses second-order derivatives of convex objective functions and convex constraint functions to construct positive definite Hessians enabling the sequential solution of convex QP problems (Verschueren, Citation2018, p. 70).

Using the notion of space decomposition for convexification, global optimisation (GO) techniques have similarities with the convexification approach presented in this article. In order to compute the global optimum of continuous, nonconvex OPs, spatial branch-and-bound (BnB) techniques iteratively divide the search space into increasingly smaller subdomains (Liberti, Citation2008; Liberti & Maculan, Citation2006; Ryoo & Sahinidis, Citation1995; Tawarmalani & Sahinidis, Citation2002). A convex relaxation of nonconvex functions is applied on each subdomain. The efficiently solvable relaxed problem provides a lower bound of the objective function for the corresponding subdomain. The comparison with an upper bound, which can be computed using local optimisation techniques, determines if a further space subdivision is necessary. Thus, this technique searches over a tree whose nodes correspond to individual relaxed problems which consider different subdomains. Comparing the solutions on the individual subdomains provides the global solution. Tree nodes are excluded on the fly based on the evaluation of the lower and upper bounds of the individual nodes eliminating the need to explore the entire domain.

1.2. Contribution

In this article, a novel successive convexification method called space splitting convexification (SSC) is proposed aiming at reducing the computation time required to solve nonconvex OPs. The key contribution of the approach is the space decomposition procedure which provides a piecewise linear approximation of the original, nonconvex problem by introducing auxiliary decision variables and absolute value constraints (AVCs). These AVCs possess a beneficial structure for linearisation and point projection onto constraints. The AVCs are transferred to the objective function using the concept of exact penalty functions and then iteratively linearised around changing points. The linearisation of the AVCs results in a binary decision: wrong or right sign of the AVC-linearisation. In each iteration, the computed solution is projected onto the AVCs and the sign is corrected if necessary enabling the linearisation errors to vanish in subsequent iterations. This concludes the iterative solution of a convex QP problem or even linear programming (LP) problem if the original objective is linear. The violation of the linearised AVCs serves as feedback if the correct sign was chosen which is used as an indicator for convergence. The approach is capable of considering two types of nonconvexities. Firstly, a class of nonconvex sets that can be split into convex subsets which are called zonally convex sets (ZCSs) in this article. Such sets arise for instance when semi-active actuators are used. Secondly, equality constraints with possibly multiple but univariate nonlinearities. As already mentioned, a common source for these nonlinear equality constraints are nonlinear system equations when applying optimal control methods. Requiring only simple mathematical operations, the AVC-projection is of linear computational complexity. Furthermore, the binary nature of the AVC-linearisation generally results in few superordinate iterations. Thus, the SSC algorithm greatly reduces computation time enabling an efficient solution in polynomial-time. Furthermore, robust initialisation properties are given since the initial guess is not required to be feasible. The algorithm converges under certain conditions to local optima of the piecewise linear substitute problem, which represents a scalable approximation of the original problem. However, being a local solution method, the computed local solution generally depends on the provided initial guess. For good initialisations, the algorithm computes solutions which are close to the global optimum.

1.3. Article structure

The article is organised as follows. The novel successive convexification method is presented in Section 2. Starting with the general formulation of optimal control problems, the original static OP for the numerical solution of the optimal control task is presented in Section 2.1. Afterwards, Section 2.2 derives the successive convexification algorithm and provides a proof of convergence. The specific application of the SSC algorithm to two-dimensional ZCSs and nonlinear equality constraints is illustrated in Section 2.3. Remarks on the computation time of the algorithm are given in Section 2.4. The comparison of the SSC approach with existing methods in Section 2.5 concludes the theoretical part of the article. Using a single mass oscillator (SMO) application as an example, the SSC algorithm is compared with the NLP solver IPOPT (Wächter & Biegler, Citation2006) in Section 3. The required NLP problem and QP problem are defined in Section 3.1 and the corresponding results are discussed in Section 3.2. Furthermore, the sensitivity regarding initial guesses is analysed in Section 3.3 and rotated space splitting is briefly addressed in Section 3.4. The article closes with concluding remarks in Section 4. In order to promote swift comprehension, a table of notation is included at the end of the article.

2. Space splitting convexification

Optimal control deals with computing the optimal input and state trajectories for a given system model. The motion of a nonlinear, continuous, time-invariant system is given by the differential equation system (1) x˙(t)=fx(t),u(t)(1) with states xXRnx and inputs uURnu. An optimal control trajectory u(t) for a system described by (Equation1) and time interval t[t0,tf] can be computed by solving a dynamic OP of following form: (2a) minu(t)J~=ϑx(tf),tf+t0tfϕx(t),u(t),tdt(2a) (2b) s.t.x˙(t)f(x(t),u(t))=0 tt0,tf,(2b) (2c) c~x(t),u(t),t=0 tt0,tf,(2c) (2d) h~x(t),u(t),t0 tt0,tf.(2d) The performance index J~ in (Equation2a) to be minimised is comprised of the terminal cost function ϑ and the intermediate cost term ϕ. Equality constraint (Equation2b) ensures that the system equations (Equation1) are satisfied. General equality constraints c~Rnc and inequality constraints h~Rnh are included via (Equation2c) and (Equation2d), respectively. Solving the dynamic OP (2) analytically is generally only possible for simple problems. Thus, dynamic OPs are mostly solved numerically via direct or indirect methods (Sedlacek et al., Citation2020c). While direct methods solve the original OP, indirect methods deduce a boundary-value problem which is analytically derived from the optimality conditions. A discretisation of trajectories via collocation or shooting can be used to obtain a static OP. Collocation methods employ decision variables for the inputs and states at discrete time points and deduce the trajectory via polynomial interpolation between these points. Single shooting methods only employ decision variables for the inputs and compute the corresponding state trajectories via numerical integration. Multiple shooting methods divide the time interval into subintervals on which the numerical integration is performed. The states at the interval margins represent additional decision variables and continuity constraints are introduced to ensure that the boundary points of the individual integration segments coincide. A direct collocation method is employed in this article due to the simpler initialisation of direct methods and the increased sparsity of collocation methods.

2.1. Problem formulation

Using separated Hermite-Simpson collocation with a discretisation into nseg segments yields npts=2nseg+1 collocation points and thus the vector of decision variables (3) w=w0Tw12TwnsegTTRnw, wkxkuk.(3) The SSC procedure is applicable to NLP problems of the form (4a) minwJ(w)=12wTP0w+q0Tw+r0(4a) (4b) s.t.ccoll,i(wi,wi+12,wi+1)=0 iI,(4b) (4c) ck=Acwk+kc=0 kK,(4c) (4d) hk(wk)0 kK,(4d) (4e) hzcs,k(wk)0 kK(4e) with indices iI{i=0,1,2,,nseg1} and kK{0,12,1,,nseg} representing the corresponding collocation segment and collocation point, respectively. Objective (Equation4a) is assumed to be quadratic and convex in the decision variables with r0R, q0Rnw and 0P0Rnw×nw. The positive semi-definiteness of P0 concludes the convexity of the objective. Collocation constraints (Equation4b) ensure that the system equations (Equation1) are satisfied. For Hermite-Simpson collocation, these equality constraints are given by (5) ccoll,ixi+1xi16Δi(fi+4fi+12+fi+1)xi+1212(xi+xi+1)18Δi(fifi+1)=0(5) with fjf(xj,uj) and segment width Δiti+1ti(Betts, Citation2010; Kelly, Citation2017). The SSC approach considers nonlinear right-hand sides of the form (6) f(x,u)=Ax+Bu+k+fpwl(x,u)(6) with ARnx×nx, BRnx×nu and k,fpwlRnx. Therein fpwl represents a composition of univariate nonlinearities that can be depicted or approximated by piecewise linear curves. For simplicity, it is assumed that the remaining equality constraints (Equation4c) are affine in the decision variables. The inequality constraints (Equation4d) are required to be convex in the decision variables. However, aiming at constructing a QP problem, it is assumed below that the inequality constraints are even affine. This stricter assumption can be posed without loss of generality, since convex inequality constraints can be approximated via a polyhedron using multiple affine functions (Boyd & Vandenberghe, Citation2004, p. 32). The inequalities (Equation4e) depict ZCSs, which are nonconvex sets that can be split into convex subsets.

2.2. Successive convexification procedure

Considering the standard form of convex OPs (Boyd & Vandenberghe, Citation2004, p. 136), all equality constraints must be affine in the decision variables to enable the convexity of the problem. Hence, a nonlinear right-hand side of the system equations (Equation1) results in nonlinear equality constraints (Equation5), yielding a nonconvex OP. Furthermore, the nonconvex inequality constraints (Equation4e) also prohibit a convex problem. The SSC algorithm iteratively solves a convex substitute problem which is derived from the original problem (4) as schematically illustrated in Figure . The core idea of this concept is considering the transformed problem (15) which represents a piecewise linear approximation of the original problem (4). This transformation is achieved by introducing space splitting constraints. These constraints are nonconvex but render the original constraints convex. Furthermore, they possess an advantageous structure which is exploited by the algorithm. In order to deal with the remaining nonconvexity, the nonconvex space splitting constraints are transferred to the objective following the theory of exact penalty functions. The resulting problem (19) possesses a convex feasible set but a nonconvex objective. Thus, the nonconvex part of the objective is iteratively linearised around points that are adjusted based on the previous iterate using an intermediate projection routine. This yields the convex problem (22), which is sequentially solved within the SSC algorithm. A smoothable absolute value function is introduced (7) absϵ(x)x2+ϵs|x|=abs(x)with 0ϵs1(7) which recovers the true absolute value for ϵs=0. The intermediate OPs (15)ϵ and (19)ϵ depicted in Figure  apply ϵs>0 to provide continuous differentiability for the validity of the optimality conditions legitimising the application of exact penalty functions. Afterwards, this smoothing is removed since it represents an approximation which is not required in problem (22) for continuous differentiability. The subsequent sections describe the problem transformation process in more detail.

2.2.1. Space splitting constraints

Before presenting the individual OPs, the basic principle for the space splitting of a decision variable is illustrated in this section providing graphical support. If collocation is used, the inputs as well as states represent decision variables. Thus, the input space and the state space can be split. The splitting procedure is presented using wW[w_,w¯] as a representative decision variable which is split at the transition point w=wtr. As illustrated in Figure (a), the auxiliary decision variables wlowWlow[w_,wtr] and wupWup[wtr,w¯] are introduced aiming at satisfying the following relations: (8) wlow=w wwtr,wtrelse,wup=w wwtr,wtrelse.(8)

Figure 1. Transformation of OP; Dotted and solid arrows represent approximated and exact transformations, respectively.

Figure 1. Transformation of OP; Dotted and solid arrows represent approximated and exact transformations, respectively.

Figure 2. Space splitting. (a) Splitting of decision variable w into wlow and wup. (b) Absolute value constraint (Equation9b) and its relaxed linearisation according to (Equation13a). (c) Projection after optimisation with initially wrong sign; I: initial guess; O: optimum; P: projection of optimum.

Figure 2. Space splitting. (a) Splitting of decision variable w into wlow and wup. (b) Absolute value constraint (Equation9b(9b) gabs=wup−wlow⏟wΔ−|w−wtr⏟w~|=0.(9b) ) and its relaxed linearisation according to (Equation13a(13a) w−2$Δ$−σww~=sw(13a) ). (c) Projection after optimisation with initially wrong sign; I: initial guess; O: optimum; P: projection of optimum.

Lemma 2.1

The splitting relations (Equation8) can be implemented via the splitting constraints (9a) gaff=wup+wlow(w+wtr)=0(9a) (9b) gabs=wupwlowwΔ|wwtrw~|=0.(9b)

Proof.

Solving (Equation9a) for one of the auxiliary decision variables yields (10a) wlow=w+wtrwup.(10a) Inserting (Equation10a) into (Equation9b) results in (10b) wup=12|wwtr|+w+wtrwup=w(10a)wlow=wtr wwtrwup=wtr(10a)wlow=w wwtr.(10b) Thus, constraints (9) ensure the desired splitting according to (Equation8).

The AVC (Equation9b) is relaxed into a convex inequality constraint which can be depicted using two linear inequality constraints (11a) gabs=w2$Δ$|w~|0habs=w2$Δ$w~w2$Δ$+w~0.(11a) Furthermore, the linearisation of the AVC based on the result of the preceding iteration wprev is added as an additional objective term in form of an exact penalty function (11b) labs=w2$Δ$σww~=0, σwsign(w~)=sign(wprevwtr)(11b) (11c) Jgτlabs(11c)

with penalty parameter τ. Considering (Equation11b), the linearisation breaks down to choosing the sign σw of the absolute value based on the previous solution wprev.Furthermore, the projection of the previous solution onto the constraints in (9) follows from (Equation8) and provides the initial solution, marked as ()˘, for the subsequent iteration: (12) w˘=wprev,w˘low=min(wprev,wtr),w˘up=max(wprev,wtr).(12) The projection step is depicted in Figure (c) for an initial guess with a different sign than the computed solution: sign(w˘prev)sign(wprev). For a graphical interpretation, the additional cost term (Equation11c) can be replaced by an additional relaxed equality constraint with the slack variable sw0 being minimised via a penalty objective: (13a) w2$Δ$σww~=sw(13a) (13b) Jsτsw.(13b) Since adding slack variables increases the number of decision variables, this is not desirable from an implementation standpoint; however, it fosters comprehension. The relaxation of constraint (Equation13a) via the slack variable sw is necessary to avoid infeasibility, which is illustrated in Figure (b): Since gabs=wΔ|w~|0 holds, an unrelaxed constraint (Equation13a) with sw0 would only allow values satisfying w~0 for σw=1 and only values w~0 for σw=1. However, the sign is based on the previous iteration and can thus be wrong. Then, a relaxation represented by the slack variable is necessary to allow values w~ of the opposite region and avoid infeasibility. The sign is corrected for the subsequent iteration step to enable eradicating the additional objective (Equation13b) and thus the slack variable. This concludes that the initial solution does not have to represent a feasible solution, which results in robust initialisation behaviour. The relaxation via the slack variable sw in (Equation13a) corresponds to the violation of constraint labs via (Equation11c). The fact that the constraint violation will be large in case of a wrong sign is used as feedback for the algorithm. The algorithm will iterate until a feasible point satisfying labs0sw is reached. Then, the additional objective (Equation11c) vanishes.

2.2.2. Piecewise linear approximation of optimisation problem

The first step towards a convex OP is the derivation of a piecewise linear approximation of the original problem (4). This is achieved by using the concept of space splitting presented in the previous section. Since multiple decision variables can be split, the formulation of the OP is posed using the augmented vector of decision variables (14) z=z0Tz12TznsegTT, zkxkukwaux,kRnz(14) with the auxiliary decision variables waux,kRns. Therein some of the original states and inputs are excluded when they are depicted using affine transformations as illustrated in Section 2.3.1. The corresponding substitute problem is given for all iI and kK by (15a) minzJ(w)(15a) (15b) s.t.cˆcoll,i(z)=ccoll,i(w=Φ(z),fpwl=Φpwl)=0,(15b) (15c) cˆk(z)=ck(w=Φ(z))=0,(15c) (15d) hˆk(z)=hk(w=Φ(z))0,(15d) (15e) hˆzcs,k(z)0,(15e) (15f) gaff,k(z)E2$Σ$,kwaux,k(Ez,kzk+wtr)=0,(15f) (15g) gabs,k(z)E2$Δ$,kwaux,kα(Ez,kzkwtrz~k)=0.(15g) Therein α():RnsRns represents a function which applies the smoothable absolute value function (Equation7) to each vector component individually: No smoothing occurs for ϵs=0. Furthermore, the right-hand side of the system equations (Equation6) is depicted or approximated by the affine expression (16) fΦ(x,u,waux)=AΦx(x,u,waux)+BΦu(x,u,waux)+k++Φpwl(x,u,waux)(16) with Φu:RnzRnu and Φx,Φpwl:RnzRnx representing functions which are affine in the decision variables. Thus, (Equation16) enables affine collocation constraints (Equation15b). The transformation function Φ(z) in problem (15) represents the accumulation of the affine transformations Φx and Φu with nΦ=(nx+nu)npts yielding (17) w=Φ(z)=Φ0ΦnsegAˆz+bˆ, ΦkΦxkΦuk(17) with AˆRnΦ×nΦ and bˆRnΦ inserting the affine mapping (Equation17) into the affine constraints (Equation4c) and (Equation4d) results in the affine constraints (Equation15c) and (Equation15d), respectively (Boyd & Vandenberghe, Citation2004, p. 79). Furthermore, the auxiliary variables are used to represent the ZCSs (Equation4e) using convex functions hˆzcs in (Equation15e). In order to get a QP problem, these constraints are assumed to be affine or approximated by affine inequality constraints. The application of space splitting for the convexification of the original constraints will be shown in more detail in Section 2.3. The splitting constraints (Equation15f) and (Equation15g) represent the constraints (Equation9a) and (Equation9b), respectively. These constraints are necessary to ensure that problem (15) correctly represents the original problem (4). They implement a bisection of selected decision variables at predefined transition values which are stored in the vector wtr. The matrices EΣ,k, EΔ,k and Ez,k are selection matrices extracting the desired decision variables. It is assumed that ns2 decision variables are split at each collocation point.

Depending on the individual approximations of the nonlinear constraints, the piecewise linear representation is subject to some error. The approximation error of this substitute problem is defined beforehand by the implemented number of space subdivisions. If the original problem is piecewise linear, this substitute problem can be an exact representation.

Remark 2.1

Let fnl(w) represent a nonlinearity within a constraint depending on the decision variable representative w, as depicted in Figure . Then, the total absolute error of the piecewise linear approximation ppwl(w) is given by the sum of absolute errors at each collocation point of the decision variable: (18) epwl=kK|fnl(wk)ppwl(wk)|.(18) An adequate number and position of knot points for the segmentation into piecewise linear parts achieve sufficiently small approximation errors. However, a higher number of splitting segments increases the size of the OP influencing the computation time.

Figure 3. Approximation of nonlinearity fnl with three-/five-segmented piecewise linear polynom ppwl,3/ppwl,5; Approximation error can be reduced with an increasing number of splitting segments.

Figure 3. Approximation of nonlinearity fnl with three-/five-segmented piecewise linear polynom ppwl,3/ppwl,5; Approximation error can be reduced with an increasing number of splitting segments.

2.2.3. Nonconvex optimisation problem with convex feasible set

The absolute values in equality constraint (Equation15g) still prohibit convexity. Deploying the theory of exact penalty functions (Di Pillo & Grippo, Citation1989; Han & Mangasarian, Citation1979), the absolute value equality constraints are moved to the objective without compromising optimality:

Theorem 2.1

Let z¯ be a stationary point of the OP (19a) minzJ(w)+τkKj=1nsgabs,k,j=gabs,k1(19a) (19b) s.t.cˆcoll,iTcˆkTgaff,kT=0T iI,kK(19b) (19c) hˆkThˆzcs,kT0T kK(19c) (19d) gabs,k0 kK(19d) with λ representing the Lagrangian multipliers of the corresponding equality constraints. Since a L1norm is an exact penalty function, z¯ is a critical point of problem (15) for ϵs>0 and sufficiently large but finite penalty weights τλ.

Proof.

The prerequisite for the optima recovery is that the optimality conditions are admissible for problem (15) (Nocedal & Wright, Citation2006, p. 507). For this purpose, the linear independence constraint qualification (LICQ) (Nocedal & Wright, Citation2006, p. 320) is analysed subsequently. Since the transformation Φ(z) in (Equation17) is affine, the gradients of the transformed basic constraints (Equation15c) and (Equation15d) remain linearly independent if the original constraints c(w):RnwRnc and h(w):RnwRnh are linearly independent. This can be verified for i{1,,nc} and j{1,,nh} via (20a) zcˆi(z)=ci(Φ(z))ΦΦzT=AˆTwci(w=Φ(z))(20a) (20b) zhjˆ(z)=hj(Φ(z))ΦΦzT=AˆTwhj(w=Φ(z)).(20b) The gradients of the splitting constraints (Equation15f) and (Equation15g) are by definition linearly independent from each other and from the remaining constraints. Furthermore, it can be assumed without loss of generality that the gradients of the collocation constraints (Equation15b), of the basic constraints (Equation15c)–(Equation15d) and of the ZCS-constraints (Equation15e) are linearly independent. Thus, if the LICQ holds for the original problem (4), then it is also satisfied by the problem (15). By choosing a sufficiently small but positive smoothing parameter 0<ϵs1, the prerequisite of continuous differentiable objective and constraint functions is given while approximation errors are kept small. Thus, the optimal solution will satisfy the Karush–Kuhn–Tucker conditions (Nocedal & Wright, Citation2006, p. 321).

Constraints (Equation19d) are added to enable omitting the norm in the objective as illustrated in (Equation19a). Since gabs,k is a vector of concave functions, the AVCs (Equation19d) represent a convex set. Thus, the feasible set of OP (19) is convex.

2.2.4. Convex optimisation problem for iterative solution

From Theorem 2.1 follows that solving (19) provides the solution for problem (15) assuming ϵs>0. Unfortunately, the augmented objective (Equation19a) is nonconvex, which will be addressed via linearisation. Subsequently, the smoothing is removed by setting ϵs=0 since it will not be required for continuous differentiability. Omitting the smoothing represents an approximation to the smoothed version of (19); however, it is beneficial from a practical standpoint since the splitting constraints are exact for ϵs=0. Furthermore, it enables representing the AVCs (Equation19d) by two affine inequalities which yields exclusively affine constraints required for an LP and QP problem. For a convex OP, the absolute value of the AVCs in the augmented objective is linearised around the points z~kRns yielding the linearised constraints (21a) labs,k(z,z~k)E2$Δ$,kwaux,kΣkz~k=0 kK,(21a) which represent (Equation11b), with the linearisation points being stored in matrix (21b) ΣΣ0Σ12ΣnsegwithΣkdiagsign(z~k,1),,sign(z~k,ns).(21b) Comparing (Equation15g) and (Equation21a) shows that the linearisation breaks down to a binary decision: choosing the correct sign of the absolute value term z~k. The linearisation (Equation21a) is affine in the decision variables. Since the sum of convex functions preserves convexity (Boyd & Vandenberghe, Citation2004, p. 79), the composite objective function is then convex in the decision variables. With all constraints being affine, using linearisation (Equation21a) results in the convex QP problem (22a) minzJtot(z,z)J(w)+τkKj=1nslabs,k,j(22a) (22b) s.t.cˆcoll,i=0iI,(22b) (22c) ctot,kT(z)cˆkTgaff,kT=0T kK,(22c) (22d) htot,kT(z)hˆkThˆzcs,kT0T kK,(22d) (22e) habs,k(z)E2$Δ$,kwaux,kz~kE2$Δ$,kwaux,k+z~k0 kK.(22e) For linear objectives J(w), the SSC approach results in a LP problem. The convex problem (22) is iteratively solved, whereas the linearisation points in Σ are updated based on the solution zT=z0TznsegT of the preceding iteration yielding (23) z~k=Ez,kzkwtr kK.(23) However, the question arises if replacing the constraint gabs in the objective with its linearisation labs falsifies the solution. This motivates the following lemma:

Lemma 2.2

The satisfaction of habs,k(z)0 and labs,k(z,z~k)=0 concludes gabs,k(z)=0, independently of the linearisation point z~k.

Proof.

This can be verified using Figure (b) as graphical support. For this purpose, the following equations are given in general notation and are compared with the equations from the illustrative example in Section 2.2.1 using the vector of decision variables zex=wwupwlowT. The nonsmoothed absolute value constraint gabs,k,j spans the following set of points: (24a) Gk,j(z){z|e2$Δ$,kTwaux,k|z~k,j|=0}=ˆ{zex|w2$Δ$|w~|=0}(24a) with eΔ,kT representing the jth row of matrix EΔ,k. The admissible points for the AVC-linearisation labs,k,j are given by (24b) Lk,j(z,z~k,j){z|e2$Δ$,kTwaux,ksign(z~k,j)z~k,j=0}=ˆ{zex|w2$Δ$σww~=0}(24b) representing the infinite extension of the positive and negative branch of the AVC for z~k,j,σw0 and z~k,j,σw0, respectively. Then, the intersection with the admissible points of the inequality constraint habs,k,j (24c) Hk,j(z)z|e2$Δ$,kTwaux,kz~k,je2$Δ$,kTwaux,k+z~k,j0=ˆzex|w2$Δ$w~w2$Δ$+w~0(24c) provides the sets (24d) Nk,j(z){z|zHk,j,zLk,j(z,z~k,j)|z~k,j0}(24d) (24e) Pk,j(z){z|zHk,j,zLk,j(z,z~k,j)|z~k,j0},(24e) which represent the negative and positive branch of the AVC and are thus a subset: Nk,j, Pk,j Gk,j.

This important lemma ensures that convergence of problem (22) to a solution which satisfies the linearised constraints labs,k(z,z~k)=0 also fulfils the original nonlinear constraints gabs,k(z)=0 in (Equation15g).

2.2.5. Space splitting convexification algorithm

Subsequently, the SSC algorithm 1 is presented in detail and the proof of its convergence is provided. The algorithm inputs are described in line 1. An initial solution for the inputs U0Rnu×npts and states X0Rnx×npts must be provided. The algorithm iteratively solves the convex problem (22) using the solution of the previous iterate to correct the signs of the linearisation if necessary. The algorithm terminates when all signs are chosen correctly or the maximum number of iterations qmax is reached. Thus, if the algorithm converges before reaching the maximum number of iterations q<qmax, the largest constraint violation is smaller than a small value l¯absϵg with 0ϵg1. As already mentioned, the violation of the linearised AVCs indicates that a wrong sign was chosen. The reason why the constraint violations are a suitable feedback for correct sign selection can be visualised using Figure (b). The signs and thus the linearised constraints labs,k,j in the objective (Equation22a) are fixed before optimisation. Then, running into the region of w~=ˆz~k,j with the opposite sign requires increasing wΔ=ˆeΔ,kTwaux,k due to the constraints habs=ˆhabs,k0, which in turn increases the linearised constraints in the objective. Based on the solution of the preceding iteration, the updating routine in line 7 adjusts the convex QP problem (22) to satisfy (Equation15f)–(Equation15g) using the projection procedure (Equation12): The update routine computes the projected initial solution Z˘ and the correct signs Σ for the linearisation of the AVCs. Afterwards, the optimiser is invoked in line 8 to solve the convex QP problem or LP problem if the main objective is linear. The theory of exact penalty functions states that the penalty parameter τ must be larger than the largest optimal dual variable of the corresponding constraints. Since estimating the limit value for the penalty parameter is a rather complicated task, Algorithm 1 pursues the straightforward approach in line 6 of gradually increasing the penalty parameter up to a high value. A reasonably high but finite upper bound on the penalty parameter τ¯ avoids numerical problems. Although this is not the best updating approach, it can work well in practice (Nocedal & Wright, Citation2006, p. 511) as it is the case for the examples considered in this article.

Finally, the following theorem verifies that the algorithm produces a sequence of solutions which eventually converges to a local solution satisfying the AVCs:

Theorem 2.2

Let the feasible set of problem (Equation22) be denoted with (25) Ωfz|cˆcoll,i=0, ctot,k(z)=0,htot,k(z)0, habs,k(z)0, iI, kK,(25) which is a convex set. Starting from a point z(0), Algorithm 1 generates a sequence {z(q)} according to (26) z(q+1)=minzJtotz,z(q)|zΩfq=0,1,(26) with Jtot being a convex function. This sequence eventually converges to a limit point z which satisfies gabs,k=0  kK.

Proof.

Algorithm 1 iteratively solves problem (22) and gradually increases the penalty parameter up to a finite value ττ¯. Let the condition τλ mentioned in Theorem 2.1 hold for qQλN. Then, the theory of exact penalty functions states that labs,k=0  kK is satisfied for all qQλ. As described in Lemma 2.2, this concludes that only solutions on one branch of the AVCs are admissible. Thus, no sign changes of z~k,j=ˆw~ are possible for qQλ. This concludes that the linearisation points of labs,k  kK and thus OP (22) remain unchanged for qQλ. The convexity of the problem entails that only one optimum exists yielding (27) z(q+1)z(q)=0  z(q+1)z(q)=0   qQλ.(27) This concludes that for every ϵτ>0, there is a QN such that (28) Δzz(n)z(m)<ϵτfor every n,mQ(28) since (Equation28) holds at the latest from the value Q=Qλ with Δz=0<ϵτ. This proves that (Equation26) is a Cauchy sequence and thus converges (Zorich, Citation2016, p. 85). Hence, the solutions of the individual iterations can oscillate; however, this oscillation vanishes with an increasing number of iterations finally converging to a single point z. Due to Lemma 2.2, labs,k=0  kK concludes that this point satisfies gabs,k=0  kK.

Theorem 2.2 concludes that the iterative solution of OP (Equation22) within the SSC algorithm basically solves the OP (Equation15) with ϵs=0: From convergence to labs,k=0  kK follows that the computed solution satisfies gabs,k=0=habs,k  kK and the augmented objective term vanishes. The remaining constraints of problems (Equation15) and (Equation22) are identical. Thus, the SSC algorithm computes a solution that is arbitrarily close, but not necessarily identical, to the solution of the piecewise linearly approximated problem (Equation15). The potential discrepancy in solutions is rooted in the necessity to smoothen the problem (Equation15) with ϵs>0 for the admissibility of the optimality conditions in Theorem 2.1. Since the linearisation removes the discontinuity, the smoothing is disregarded within the SSC algorithm. From a practical standpoint, the discrepancy is negligible since the smoothing parameter can be assumed arbitrarily small ϵs0 making the impact of the smoothing numerically irrelevant. This procedure for the approximation of discontinuities in optimal control problems is common practice, see e.g. (Perantoni & Limebeer, Citation2014). In summary, the SSC approach chooses one branch of the discontinuity, resulting in the continuously differentiable problem (Equation22) with ϵs=0, and switches in the following iterations to the other branch if the wrong side of the discontinuity was selected.

2.3. Constraint convexification via space splitting

The previous sections derived the basic structure of the convex OP (Equation22a), which is solved in an iterative manner. However, the question of how the original constraints can be convexified via space splitting to gain the convex constraints (Equation15b)–(Equation15e) is still open. The basic procedure of bisecting the space of a variable into two subdomains has been illustrated in Section 2.2.1. This can be employed to consider ZCSs and equality constraints with univariate nonlinearities in a convex manner, which is demonstrated in Sections 2.3.1 and 2.3.2, respectively. Subsequently, the index for the collocation discretisation kK is omitted for readability.

2.3.1. Convexification of zonally convex sets

One prominent physical example of ZCSs are constraints ensuring semi-activity. Semi-active actuators like limited slip differentials and semi-active dampers are used in many engineering applications due to their good compromise between low energy consumption and high performance (Savaresi et al., Citation2010; Sedlacek et al., Citation2020aCitation2020c). A typical ZCS for a semi-active damper is depicted in Figure (a) with damper force Fd=u and damper velocity v. The nonconvexity of the set is apparent considering that it is easy to draw a line that contains non-admissible points and connects an admissible point in the first quadrant with an admissible point in the third quadrant. Note that simply linearising the inequality constraints depicting this nonconvex set results in a half-plane, which represents a poor approximation of the set. The main idea for the novel convexification approach is appropriately decomposing nonconvex sets, described in the original decision variables, into convex subsets using auxiliary decision variables. The applicability of the SSC method to the ZCS types depicted in Figure  is proven in the subsequent paragraphs.

Figure 4. Space splitting convexification of zonally convex sets. (a) ZCS with a single transition point. (b) Shifted, rotated ZCS with a single transition point. (c) ZCS with shared line at transition.

Figure 4. Space splitting convexification of zonally convex sets. (a) ZCS with a single transition point. (b) Shifted, rotated ZCS with a single transition point. (c) ZCS with shared line at transition.

The approach is initially illustrated using the ZCS depicted in Figure (a). Let the convex subset in the first and third quadrant be given by (29a) Spu,v|uU, vV, hˆzcs,p(u,v)0and(29a) (29b) Snu,v|uU, vV, hˆzcs,n(u,v)0,(29b) respectively. Therein v and u are original decision variables. Moreover, hˆzcs,p0 and hˆzcs,n0 are convex sets. The union of convex sets does not necessarily result in a convex set. As illustrated in Figure (a), the union S=SpSn is assumed to be nonconvex in this article. Thus, S is a nonconvex set comprised of convex subsets: a ZCS. The velocity v is split at v=vtr=0 by a vertical line following Lemma 2.1. The two auxiliary variables vnVn[v_,vtr]=[v_,0] and vpVp[vtr,v¯]=[0,v¯] are introduced aiming at implementing (30) vn=v v0,0elseandvp=vv0,0else.(30)

Introducing analogous constraints to (Equation9a) and (Equation11a) as well as additional objective terms in form of (Equation11c) ensures the relations in (Equation30). Furthermore, the auxiliary variables unUn[u_,utr] and upUp[utr,u¯] are introduced for the individual subsets. Therein utr represents the ordinate value of the common point, which lies on the origin in the current example depicted in Figure (a) resulting in utr=0. However, the common point of the subsets is not required to lie on the abscissa or ordinate. The vector of auxiliary decision variables is given by waux=vpvnupun. While the original state variable v remains a decision variable in the problem, the input variable is replaced according to the transformation (31) Φuun+uputr=11upunutr,(31) which is affine in the decision variables. The convex subsets in terms of the auxiliary decision variables are given by (32a) Sˆpup,vp | upUp,vpVp,hˆzcs,p(up,vp)0(32a) (32b) Sˆnun,vn | unUn,vnVn,hˆzcs,n(un,vn)0.(32b) Hence, the convex subsets Sˆp and Sˆn are now defined for separate decision variables and will be linked via the affine mapping (Equation31). This enables the formulation of convex constraints as depicted in problem (Equation15). The proof that this procedure produces the same set as S will be given in Theorem 2.3.

For convexity, hˆzcs,p and hˆzcs,n in (Equation32a) and (Equation32b) must be convex functions. As exemplarily illustrated in Figure (a), the convex subsets are assumed in this article to be representable by nzcs=nzcs,n+nzcs,p affine inequality constraints (33a) hˆzcs,p(u,v)Azcs,puv+bzcs,p0(33a) (33b) hˆzcs,n(u,v)Azcs,nuv+bzcs,n0(33b) with Azcs,pRnzcs,p×2, bzcs,pRnzcs,p, Azcs,nRnzcs,n×2 and bzcs,nRnzcs,n. These constraints represent (Equation15e) in the convex OP. Although nonlinear, convex functions for hˆzcs,p and hˆzcs,n would not prevent convexity, introducing such constraints would prohibit an LP or QP problem, which can be solved especially efficiently. Asymmetric subsets like the one illustrated in Figure (a) can be easily implemented by using varying coefficients in (Equation33a) and (Equation33b) or by using different domains for Un and Up.

Theorem 2.3

The subsets (Equation32a) and (Equation32b) in combination with the affine mapping (Equation31) depict the set S which is given by the union of the convex subsets (Equation29a) and (Equation29b).

Proof.

For proving that the splitting approach provides sets that depict the original one, the individual cases for the bisected variable space are considered subsequently.

Case 1: vtr<v

The decision variable v is split at v=vtr. Thus, vn=vtr holds according to Lemma 2.1. This concludes un=utr since the subsets converge to the common point (utr,vtr) when leaving the subset towards the other subset. Lemma 2.1 also concludes vp=v. Then, the affine mapping (Equation31) is given by Φu=upSˆp. For v>vtr, S=Sp holds. Since vp=v, uSp and ΦuSˆp provide the same feasible set. The chain of conclusions for the remaining cases follows the same reasoning but is given below in equations for conciseness.

Case 2: v<vtr (34a) vp=vtrup=utrvn=vΦu=unSˆn=ˆuS=Sn.(34a) Case 3: v=vtr (34b) vp=vtrup=utrvn=vtrun=utrΦu=utr=ˆu=utr.(34b)

Thus, inserting the affine mapping (Equation31) into the constraints while replacing the original set S with the sets (Equation32a) and (Equation32b) yields the same feasible set.

The presented proof requires a space splitting of the variable v which is represented by splitting the convex subsets via a vertical line. Thus, the SSC approach is capable of convexifying two-dimensional ZCSs, which can be divided into two convex subsets connected in a single point using any vertical line. Following theorem is added to show that this also holds for any splitting line which is straight but possibly rotated:

Theorem 2.4

Space splitting applied to a rotated, two-dimensional ZCS also results in convex constraints.

Proof.

This can be verified by applying the previously described procedure to a rotated coordinate frame, exemplarily depicted in Figure (b). The auxiliary decision variables need to split the rotated two-dimensional space spanned by the variables v and u. Assuming the coordinate system is rotated by the angle φ with counter-clockwise rotations depicting positive rotations, following relations hold between the original coordinates vu and the rotated coordinates vu: (35) vu=cos(φ)sin(φ)sin(φ)cos(φ)R(φ)vvtruutrandvu=cos(φ)sin(φ)sin(φ)cos(φ)R(φ)vu+vtrutr.(35) The vector of auxiliary decision variables is chosen as waux=vpvnupun. For a concise notation, the equations below use the abbreviations cφcos(φ) and sφsin(φ). Constraints (Equation33) are analogously formulated on the rotated, auxiliary decision variables: hˆzcs,p(up,vp) and hˆzcs,n(un,vn). However, an adjustment using (Equation35) is necessary for the constraints (Equation9a), (Equation11a) and (Equation11b) as well as the input mapping (Equation31): (36a) gaff=(vp+vn)v~=0 withv~=cφ(vvtr)+sφ(sφ(vp+vn)+cφ(up+un))(36a) (36b) gabs=(vpvn)|v~|0(36b) (36c) labs=(vpvn)sign(v~)v~0(36c) (36d) Φu=u=sφsφvpvn+cφcφupun+utr.(36d) Since the angle φ is constant, the trigonometric functions represent constant values. Thus, a rotated space splitting procedure also yields affine constraints and mappings enabling the formulation of a convex OP.

The previous theorems required the subsets to be connected in a single point. Following theorem states that the SSC approach can be used to approximate ZCSs which share a line of points:

Theorem 2.5

When a two-dimensional ZCSs is comprised of two convex subsets sharing a line of points, the SSC approach can only approximate the original set however with sufficiently small approximation error.

Proof.

Without loss of generality, this can be analysed considering Figure (c) as example. For the depicted case, the transition line lies on the ordinate vtr=0. Analysing the individual cases shows that using the original subsets within the SSC approach would yield a larger set than the original set:

Case 1: vtr<v (37a) vp=vupSˆpvn=vtrun[0,u¯0]Φu=(un+up)SˆΦ,pSˆp=ˆ  uS=Sp.(37a)

Case 2: v<vtr (37b) vp=vtrup[0,u¯0]vn=vunSˆnΦu=(un+up)SˆΦ,nSˆn=ˆ  uS=Sn.(37b)

Case 3: v=vtr (37c) vp=vtrup[0,u¯0]vn=vtrun[0,u¯0]Φu=un+up[0,2u¯0]=ˆ  u[0,u¯0].(37c)

Thus, using the original subsets can render non-admissible points of the original problem admissible. When the input variable is replaced by the auxiliary inputs according to (Equation31), both sets must be adjusted at the transition line v=vtr. The simplest set adjustment is enforcing un=0=up at the transition axis, as illustrated in Figure  by the dotted lines. Then, the subsets are connected in a single point enabling the application of Theorem 2.4. However, other set manipulations are possible and can be numerically better. Generally, such set approximations introduce conservativeness for the sake of feasible trajectories. However, the introduced error is negligible when the removed area is sufficiently small which can be implemented by choosing steep linear constraints at the transition between the subsets.

Remark 2.2

In this article, only two-dimensional ZCSs which can be split into two convex subsets have been considered. However, the SSC approach can be applied to certain two-dimensional ZCSs with more than two subsets. For instance, consider three convex subsets positioned horizontally to each other, whereas each subset is connected to the next subset in a single point on the abscissa. This can be verified using the procedures described previously in this section.

This section illustrated the convexification procedure for ZCSs in regards to inputs. This results in the depicted affine input transformation Φu. Implementing the approach for a ZCS with state decision variables yields an affine transformation Φx. This procedure can be applied to multiple inputs and states. The corresponding vector functions for the affine transformations are given by (38) Φu=Φu,1Φu,nuandΦx=Φx,1Φx,nx(38) with Φu,i and Φx,j representing the transformation for the individual input and state, respectively. If no transformation is necessary, a direct mapping is implemented according to Φu,i=ui and Φx,i=xi. The vectors of transformations (Equation38) are used to generate Φ in (Equation17) which is used for the convex depiction of the original constraints in (Equation15b)–(Equation15d).

2.3.2. Convexification of nonlinear equality constraints

Some nonlinearities in physical systems are characterised by a univariate function. Examples are nonlinear springs, saturation, dead-zones or the tire force shape curve of vehicles. Since nonlinear system equations yield nonlinear thus nonconvex equality constraints, this section presents how such nonlinear univariate terms can be convexified. The nonlinear univariate curve is depicted using piecewise affine parts. Hence, if the nonlinearity is not a piecewise linear function, SSC introduces approximation errors. The subsequent paragraphs illustrate the application of the SSC algorithm for convexifying piecewise linear nonlinearities.

Theorem 2.6

The splitting constraints in (Equation9) can be used to convexify equality constraints by transforming a univariate nonlinearity with two piecewise linear segments into an expression which is affine in multiple decision variables.

Proof.

Proof is provided using the piecewise linear curve depicted in Figure (a) as example, which represents a typical function for piecewise linear springs. Assuming the position x is a state of the system, it represents a decision variable which will be split at the transition point x=xtr<0. Thus, the auxiliary position variables xlowXlow[x_,xtr] and xupXup[xtr,x¯] are introduced. By including analogous constraints to (Equation9a) and (Equation11a) as well as additional objective terms in form of (Equation11c), following relations are ensured using Lemma 2.1: (39) xlow=x xxtr,xtrelse,xup=x xxtr,xtrelse.(39) Hence, the piecewise linear function can be represented by the expression (40) Φpwl,2=cupxup+clow(xlowxtr)=cupclowxupxlowwaux+clowxtr(40) which is affine in the decision variables waux. The relations in (Equation39) yield following two segments for the piecewise linear function (Equation40): (41a) I: xtrxxup=xxlow=xtrΦpwl,2=cupx.(41a) (41b) II: x<xtrxup=xtrxlow=xΦpwl,2=cupxtr+clow(xxtr).(41b) Thus, (Equation41a) and (Equation41b) depict the upper and lower segment of the nonlinearity, respectively.

Since (Equation40) is an affine function in the decision variables, it can be inserted into the differential equations without preventing convexity. The subsequent theorem proves that this approach can be extended to univariate nonlinearities with more than two piecewise linear segments:

Figure 5. Space splitting convexification of piecewise linear equalities. (a) Nonlinearity with two linear segments. (b) Nonlinearity with three linear segments. (c) Splitting of state variable x for three segments.

Figure 5. Space splitting convexification of piecewise linear equalities. (a) Nonlinearity with two linear segments. (b) Nonlinearity with three linear segments. (c) Splitting of state variable x for three segments.

Theorem 2.7

A repeated application of the space bisection approach using the splitting constraints in (Equation9) can be used to convexify equality constraints by transforming a univariate nonlinearity with more than two piecewise linear segments into an expression which is affine in multiple decision variables.

Proof.

The general procedure for this extension is illustrated using the piecewise linear curve depicted in Figure (b). The position x is split at the transition points x=x_tr<0 and x=x¯tr>0. Thus, the auxiliary position variables xlowXlow[x_,x_tr], xlow¯Xlow¯[x_tr,x¯], xmidXmid[x_tr,x¯tr] and xupXup[x¯tr,x¯] are employed. The space is repeatedly bisected following Lemma 2.1 to gain (42a) xlow=x xx_tr,x_trelse,xlow¯=x xx_tr,x_trelse(42a) (42b) xmid=xlow¯ xlow¯x¯tr,x¯trelse,xup=xlow¯ xlow¯x¯tr,x¯trelse(42b) which is depicted in Figure . Thus, the position space is bisected into a region below and a region above x=x_tr whereas the upper region is again bisected into a region below and above x=x¯tr. The piecewise linear function can then be represented by the expression (43) Φpwl,3=cupcmidclowxupxmidxlowwaux(cupx¯tr+clowx_tr)(43) which is affine in the decision variables waux. The relations in (Equation42) yield following three segments for the piecewise linear function (Equation43): (44a) I: x¯tr<xxup=xxmid=x¯trxlow=x_trΦpwl,3=cmidx¯tr+cup(xx¯tr).(44a) (44b) II: x_trxx¯trxup=x¯trxmid=xxlow=x_trΦpwl,3=cmidx.(44b) (44c) III: x<x_trxup=x¯trxmid=x_trxlow=xΦpwl,3=cmidx_tr+clow(xx_tr).(44c) Hence, (Equation44a), (Equation44b) and (Equation44c) depict the upper, mid and lower segment of the nonlinearity, respectively.

This repeated bisection procedure enables the generation of a characteristic curve with an arbitrary number of segments. However, an increasing number of segments also increases the number of auxiliary decision variables and additional constraints making the OP larger.

The approach presented in this section yields a scalar function Φpwl which is affine in the decision variables. The procedure can be applied to multiple univariate, nonlinear terms yielding further scalar mapping functions. The affine vector-valued function in (Equation16) is given by (45) Φpwl=Φpwl,1,1+Φpwl,1,2+Φpwl,nx,1+Φpwl,nx,2+(45) with Φpwl,i,j representing the individual affine mapping functions. For states that are not affected by the space splitting approach, Φpwl,i,j=0 holds. The transformation (Equation45) is used to generate the convex collocation constraints (Equation15b).

2.4. Remarks on runtime

The application of optimisation methods within a real-time capable controller generally requires upper bounds on the necessary computation time. The SSC approach runs through a loop which is comprised of a projection step and an optimisation step resulting in the following theorem regarding computational complexity:

Theorem 2.8

The computational complexity of the SSC algorithm is polynomial.

Proof.

SSC solves a sequence of LP problems or convex QP problems, which are known to be solvable in polynomial time (Karmarkar, Citation1984; Kozlov et al., Citation1980). The projection step (Equation12) of the SSC algorithm uses minimum and maximum functions which possess linear time complexity. This concludes a polynomial time complexity of the SSC algorithm: (46) TSSC(n,q)=qO(nα)+cO(n)with α>1.(46) Therein n can be interpreted as the number of operations required by the algorithm. The parameters in (Equation46) depend on the utilised solver as well as the number of decision variables which is problem specific. Limiting the maximum number of superordinate iterations to qqmax enables terminating the algorithm prematurely at suboptimal solutions, if necessary.

Theorem 2.8 provides valuable insight for the application in a real-time capable controller. Firstly, a worst-case bound on computation time can be experimentally identified for the specific OP and solver. Secondly, the computation time scales well with increasing problem size. Since the number of superordinate SSC iterations is rather low in practice, this results in a fast solution of optimal control problems. Finally, the influences on computation time are summarised below:

  1. System and discretisation. The number of decision variables increases with rising number of inputs, states and collocation segments for both the original and the convexified OP. This increases computation time for NLP methods and the SSC algorithm. Due to the polynomial complexity, this increase in time will be generally less for SSC than for NLP.

  2. Nonlinearity. The more complicated the nonlinearity, the more splitting segments are required to reduce approximation errors. However, the space splitting increases the problem size compared to the original problem, which influences the variable n in (Equation46). This can put a practical bound on the number of space divisions via the SSC approach. Nevertheless, many physically motivated nonlinearities can be approximated sufficiently well using a moderate number of affine segments.

  3. Initial guess. Being a local method, the solution computed by the SSC approach depends on the provided initial solution. Furthermore, this initial guess can influence the order of sign-corrections regarding the AVC-linearisations, which can impact the number of superordinate iterations and, therefore, the convergence rate. For MPC frameworks, the optimal solution of the preceding time step often represents a good initial guess (Gros et al., Citation2020) promising low computation times.

  4. Penalty parameter update. Too small or too large penalty parameters can slow down convergence (Nocedal & Wright, Citation2006, p. 511). The straightforward approach of gradually increasing the penalty parameter is used in this article. However, more sophisticated routines have been proposed in Mayne and Maratos (Citation1979) and Maratos (Citation1978).

2.5. Comparison with existing methods

In order to highlight the novelty of the proposed algorithm, this section compares the SSC approach with the most related existing methods.

From an algorithmic standpoint, linearising only the nonconvex part of constraints combined with a relaxation and an increasing objective term penalising constraint violations corresponds to penalty CCP (Lipp & Boyd, Citation2016). CCP has the advantage over SQP and other linearisation techniques that it retains more problem information in each iterate: The information of the convex parts is kept and only the concave portions are linearised. Furthermore, CCP does not require to use line-search procedures or limit the progress in each iteration via trust-region methods. Inspired by Mangasarian (Citation2015), the SSC approach avoids additional slack variables by considering the linearised constraints directly in the penalty objective. This avoids further increasing the size of the OP as in penalty CCP. Moreover, SSC employs an intermediate projection to enhance convergence. While CCP linearises the concave part of all nonconvexities, SSC transforms the problem beforehand requiring only the linearisation of AVCs. This enables providing a feedback about the correctness of the selected linearisation points, which are subsequently adjusted. Thus, the linearisation error can vanish completely after the correct signs have been chosen. The binary nature of the linearisation facilitates a rapid convergence in a small number of superordinate iterations. Although the SSC method only computes solutions to the piecewise linear approximation of the original problem, the approximation can be designed to sufficient accuracy enabling small and known approximation errors. Especially the straightforward linearisation of ZCS-constraints yields very poor approximations, which can contain a large set of infeasible points. Thus, the vanishing AVC-linearisation errors result in an advantage of SSC regarding accuracy, also over further linearisation techniques like the ones presented in Mao et al. ( Citation2016, Citation2017). Generally, a scalable trade-off between accuracy and size of the OP, thus computation time, can be chosen. Opposed to Lipp and Boyd (Citation2016), this article provides a convergence proof, even if only converging to the solution of the approximated problem.

While LC possesses the advantage of avoiding approximation errors, it is only applicable to OPs with annulus-like, nonconvex sets resulting from excluding a convex subset from a convex set (Raković & Levine, Citation2018, p. 340). Opposed to that, SSC provides a method for the convexification of ZCS which cannot be considered via LC.

Similar to the LnP approach presented in Mao et al. (Citation2017), the SSC method is an iterative linearisation algorithm using intermediate projection steps. The updating routine for SSC is of linear computational complexity with few and simple mathematical operations. The projection step of the LnP approach generally requires the solution of a convex programming problem, which is of polynomial complexity at best. Thus, the projection step used by the SSC approach is computationally less costly, which is beneficial for splitting methods (Ferreau et al., Citation2017). Additionally, the binary nature of the AVC-linearisation provides the advantage that generally only few superordinate iterations are required, resulting in short computation times. Moreover, SSC is more robust regarding the initialisation since the LnP approach requires an additional lifting procedure to cope with arbitrary initialisations, which costs computation time (Mao et al., Citation2017). Furthermore, the LnP method requires the right-hand side of the system equations to be convex and the inequality constraints to be concave. However, nonconvex collision avoidance constraints can be easily considered via the LnP approach, whereas the SSC procedure requires further measures.

The ADMM is a splitting procedure utilising the augmented Lagrangian method instead of the exact penalty function method, which is employed by the SSC algorithm. Due to the alternating approach, the ADMM requires the solution of two QCQP problems in each iteration. The SSC approach only requires the solution of a single convex QP problem in each iteration, which is beneficial for computation time.

The spatial BnB method also uses space decomposition for the convexification of the optimisation problem. However, the SSC approach solves a piecewise linear approximation of the original problem, which is iteratively adjusted, on the full space domain of the decision variables. Opposed to that, the BnB method solves multiple OPs which represent convexly relaxed versions of the original problem on separate subdomains of the decision variables. BnB techniques determine upper bounds by evaluating the objective function at a feasible point. Since the problem is generally nonconvex, finding a feasible point can be difficult. This is often tackled by solving the nonconvex subproblem locally, which is computationally expensive (Liberti & Maculan, Citation2006, p. 253). Thus, the convergence rate of the SSC approach is most likely to be superior if sufficiently good initial guesses are provided. However, this depends on the nonlinearities of the OP, which influence the number of decision variables for SSC but also for BnB approaches which decompose factorable functions (Tawarmalani & Sahinidis, Citation2002, p. 125). Moreover, SSC only guarantees to find local optima of an approximation of the OP and is only applicable to certain classes of OPs. GO techniques cover a wide range of applicability and provide the global optimum.

3. Applications

In this section, the proposed SSC algorithm is evaluated using a hanging SMO example with piecewise linear spring and semi-active damping as illustrated in Figure . Semi-active dampers can only generate a force in the opposite moving direction and cannot impose a force at steady-state complying with the passivity constraint (Savaresi et al., Citation2010, p. 16). Hence, the admissible set for semi-active dampers always contains a subset in the first quadrant and a subset in the third quadrant which are connected in a single point, namely, the origin. A performance-oriented OP is formulated and solved using NLP and SSC, respectively. The results of both algorithms are compared regarding accuracy and computation time. Both problems are posed using the modelling language JuMP (Dunning et al., Citation2017) for mathematical OPs. For a fair comparison, the necessary derivatives are computed beforehand via automatic differentiation. Furthermore, the tolerances for constraint feasibility and objective improvement are set to 106 for both solvers. The utilised parameters are listed with description in Table .

Figure 6. Model characteristics for hanging SMO with semi-active damper and nonlinear spring. (a) Hanging SMO model. (b) ZCS for semi-active damper force. (c) Piecewise linear spring force characteristic.

Figure 6. Model characteristics for hanging SMO with semi-active damper and nonlinear spring. (a) Hanging SMO model. (b) ZCS for semi-active damper force. (c) Piecewise linear spring force characteristic.

Table 1. Parameters for SMO application.

The NLP problem is solved using the optimiser IPOPT(Wächter & Biegler, Citation2006), which employs an interior-point method: Using the concept of barrier functions, a sequence of relaxed problems is solved for decreasing values of barrier parameters. The barrier parameter relaxes the inequality constraints and hence represents the distance from the current iterate to the border of the admissible set. Thus, interior-point methods use a central path within the admissible set as opposed to SQP-methods which wander along the border. The resulting nonlinear equation system is solved via a damped Newton method. Furthermore, a filter line-search method, heuristics and further correction measures are employed to enhance convergence and robustness.

The novel SSC method transforms the OP into convex QP subproblems which are solved iteratively. In order to capitalise on this problem structure, the elaborate optimiser Gurobi (Gurobi Optimization, Citation2020) is selected.

3.1. Optimisation problems

The equations of motion for the state vector x=[xv]T result in (47) x˙=f=v1mmgFdFc(47) with x, v, Fd and Fc denoting the deflection position, deflection speed, damper force and spring force, respectively. The expression of these forces differs for the NLP method and the SSC approach. Starting from a specified initial state xiv=[xivviv]T with damper force Fd,iv=d_viv, the goal is to minimise the deviation from the steady-state position xss while considering the limitations of the system. Applying Simpson quadrature (Betts, Citation2010; Kelly, Citation2017), the main objective penalises the steady-state position deviation ess,jxjxss according to (48) Jssi=0nseg1Δi6ess,i2+4ess,i+122+ess,i+12.(48) Considering the values listed in Table , the steady-state position can be computed using a root-finding approach like Newton's method: At steady-state position, the gravitational force must equal the spring force. For the considered nonlinear springs with two piecewise linear segments the value xss=xss,2 is chosen and xss=xss,3 if the spring with three segments is used. An uniform discretisation of the time grid t[t0,tf]=[0,10] is employed yielding a constant segment width Δi=Δ=tft0nseg. Both, the NLP approach and the SSC method, are initialised with zero vectors U0=0 and X0=0. From (49) fss,i(x)Δi6(xixss)2fss,i(x)=2Δi6(xixss)fss,i(x)=2Δi6>0(49) follows that the Hessian of (Equation48) is a diagonal matrix with only positive and zero diagonal entries and therefore positive semi-definite. Hence, the main objective (Equation48) is a convex function.

3.1.1. Nonlinear nonconvex optimisation problem

For the solution of the OP via NLP, the decision variables are chosen as (50a) u=u0u0.5unsegR1×npts with uk=dk(50a) (50b) X=x0x0.5xnsegR2×npts with xkxkvk(50b) whereas the input represents the variable damping coefficient dk of the semi-active actuator. With iI and kK, the original OP is given by (51a) minu,XJss(51a) (51b) s.t.ccoll,i=(5)0 with fk=vk1mmgFd,kNLPFc,2,kNLP,Fd,kNLP=ukvk  andFc,2,kNLP=minϵcmidxk,clowxkx_tr(clowcmid),(51b) (51c) ukDd_,d¯, xkXx_,x¯ andvkVv_,v¯,(51c) (51d) F_dukvkF¯d,(51d) (51e) u0=d_,x0=xiv.(51e) The nonconvex NLP problem (51) is comprised of following parts: objective function (Equation51a), collocation constraints (51b), bounds for the decision variables (Equation51c), damper force bounds (Equation51d) and initial value condition (Equation51e). The piecewise linear spring force is approximated in (51b) via the smoothed minimum-function (52) minϵ(x,y)12(x+y)(xy)2+ϵ(52) using ϵ=1016 to guarantee that the problem is twice continuously differentiable (Sedlacek et al., Citation2020b). Problem (51) is nonconvex due to the right-hand side of the differential equation system in the collocation constraints (51b) and due to the damper force bounds (Equation51d).

3.1.2. Convex QP-problem for iterative solution

Following the SSC approach, auxiliary optimisation variables are introduced, which results in the subsequent decision variables: (53a) U=u0u0.5unsegR2×npts with ukupos,kuneg,k=Fd,pos,kFd,neg,k(53a)

(53b) X=x0x0.5xnsegR2×npts with xkxkvk(53b)

(53c) Xaux=xaux,0xaux,0.5xaux,nsegR2×npts with xaux,kxmid,kxlow,k(53c)

(53d) Vaux=vaux,0vaux,0.5vaux,nsegR2×npts with vaux,kvpos,kvneg,k.(53d) Opposed to the inputs (Equation50a) of the NLP problem (Equation51a), the inputs in (Equation53a) represent the positive and negative part of the damper force.

As illustrated in Algorithm 1, a projection routine is executed in each iteration. Based on the preceding solution marked by values (), this routine computes the projected initial solution ()˘ for kK via (54a) u˘k=u˘pos,ku˘neg,k=max(uneg,k+upos,k,0)min(uneg,k+upos,k,0),x˘k=xk(54a) (54b) x˘mid,kx˘low,k=x˘aux,k=max(xk,x_tr)min(xk,x_tr),v˘pos,kv˘neg,k=v˘aux,k=max(vk,0)min(vk,0)(54b) and the correct signs according to (54c) σx,k=sign(xkx_tr),σv,k=sign(vk).(54c) For a concise notation in the OP, the decision variables are lumped together in P{U,X,Xaux,Vaux}. With iI and kK, the convex QP problem, which is iteratively solved for updated values of τ, σx,k, σv,k and corresponding initial guesses, is given by (55a) minPJss+τkKlabs,x,k+labs,v,kwith(55a) (55b) s.t.labs,x,k(xmid,kxlow,k)σx,k(xkx_tr)labs,v,k(vpos,kvneg,k)σv,kvk,(55b) (55c) ccoll,i=(5)0 with fk=vk1mmgFd,kSSCFc,2,kSSC,Fd,kSSC=uneg,k+upos,k  andFc,2,kSSC=cmidxmid,k+clow(xlow,kx_tr),(55c) (55d) xkXx_,x¯,vkVv_,v¯,uneg,kUnegF_d,0,upos,kUpos0,F¯d,vneg,kVnegv_,0,vpos,kVpos0,v¯,xlow,kXlowx_,x_tr,xmid,kXmidx_tr,x¯,(55d) (55e) hˆzcs,p,k=d¯1d_1vpos,kupos,k0,hˆzcs,n,k=d_1d¯1vneg,kuneg,k0,(55e) (55f) gaff,x,k=xmid,k+xlow,k(xk+x_tr)=0,gaff,v,k=vpos,k+vneg,kvk=0,(55f) (55g) habs,x,k=labs,x,kσx,k=+1labs,x,kσx,k=10,habs,v,k=labs,v,kσv,k=+1labs,v,kσv,k=10,(55g) (55h) u0=max(d_viv,0)min(d_viv,0),x0=xiv.(55h) The QP problem (Equation55) is comprised of following parts: augmented objective function (Equation55a), collocation constraints (Equation55c), bounds for the decision variables (Equation55d), ZCS-constraints (Equation55e), the additional space splitting constraints (Equation55f)–(Equation55g) and initial value condition (Equation55h). Due to the splitting approach, the right-hand side of the differential equation system in (Equation55c) is an affine function in the decision variables. Thus, all constraints are affine in the decision variables and therefore convex. The additional objectives with (Equation55b) are affine in the decision variables representing convex functions. Hence, (Equation55) represents a convex QP problem. Using (Equation55b), the termination criterium in line 9 of Algorithm 1 is computed via (56) l¯abs=labs,x,0labs,v,0,,labs,x,nseglabs,v,nsegmax.(56) As illustrated in line 6 of Algorithm 1, the penalty weight τ is linearly increased with a maximum iteration number qmax=6 using the lower and upper bound τ_ and τ¯, respectively. Both OPs are now fully defined. The results generated by solving NLP problem (Equation51) and by applying the SSC algorithm with QP problem (Equation55) are compared in the following section.

3.2. Results

In order to inspect the performance of the proposed SSC algorithm, 100 OPs are analysed in this section using a desktop computer with Intel CoreTM i7-9850H CPU to determine the solutions. The OPs vary in size and the initial value condition. The number of collocation segments is gradually increased with nseg{10,50,100,250,500}. For each problem size, the OPs (Equation51) and (Equation55) are solved using the 10 random, admissible initial values xiv listed in Table . This procedure is also executed for a simplified QP problem (Equation55) with a fully linear spring of stiffness cmid. This simplifies the right-hand side of the differential equation system in (Equation55c) and eliminates the need for the auxiliary variables Xaux in (Equation53c), the corresponding additional objectives in (Equation55b) as well as the corresponding constraints in (Equation55f) and (Equation55g). The optimisation results are displayed in Table .

Table 2. Initial values of robustness analysis.

Table 3. Optimisation results of robustness analysis.

Firstly, the OPs with initial value xiv=xiv,1 and nseg=250 segments are studied in more detail. Figure (a) depicts the piecewise linear characteristic curve of the spring force and Figure (b) the admissible set for the damper force. The resulting trajectories of the states and damper force are illustrated in Figure (c). The mean absolute deviance between the damper force trajectory of the NLP solution and the SSC solution is defined as (57) e¯Fd1nptskKFd,kNLPFd,kSSC(57) for the npts collocation points. With e¯Fd=1.85N, the control trajectories differ only marginally considering the damper force domain Fd[400N,400N]. The mean absolute deviance between the position and the steady-state position (58) e¯ss1nptskK|xkxss,k|(58) is e¯ssSSC=7.12m and e¯ssNLP=7.18m for the SSC solution and NLP solution, respectively. However, the value for the main cost function (Equation48) is JssSSC=2550.73m2s and JssNLP=2549.86m2s for the SSC solution and NLP solution, respectively. Thus, the SSC objective value is higher but the mean deviance in the steady-state position error is lower. The reason for this is that the cost function is quadratic in the errors which penalises large errors unevenly more than small errors. As illustrated in the top subplot of Figure , the position of the NLP solution reaches the steady-state position faster however with an overshoot which slowly reduces. Thus, the larger errors at the beginning are reduced more quickly resulting in a lower cost function value. However, the mean position error, which is a better metric for the actual goal of minimising the deviance from the steady-state position, is worse than for the SSC solution. Although an objective penalising the absolute value of the errors would be more adequate, it is not used since it would prevent continuous differentiability of the objective function. Nevertheless, both algorithms reach the steady-state position xss in about 3 s resulting in similar state trajectories. The trajectories of the auxiliary variables verify correct switching at x=x_tr=5m and v=vtr=0ms for the position and velocity, respectively. Furthermore, Figure (a,b) shows that the spring forces lie on the characteristic line and the computed damper forces lie within the admissible set proving the compliance of the prescribed constraints. The bang-bang-like control strategy confirms correctness since it is expected due to the main objective (Equation48), which demands to reduce the errors as fast as possible. With q=4 superordinate iterations, the SSC method required a total optimisation time of tΣSSC=0.329s which is 47.71 % of the computation time of tΣNLP=0.690s required by the NLP solver. The cumulative optimisation time topt,Σ, which represents the time spent in the QP solver in line 8 of the SSC algorithm for all passed loops, is topt,ΣSSC=0.262s representing 37.97 % of the NLP time. Since the SSC algorithm converged in q<qmax=6 iterations, the largest relaxation value of the AVCs is smaller than ϵg ensuring conformity with the original problem.

Figure 7. Solution of OPs with initial value xiv,1 and nseg=250 collocation segments. (a) Piecewise linear spring force. (b) ZCS for damper force. (c) State and damper force trajectories.

Figure 7. Solution of OPs with initial value xiv,1 and nseg=250 collocation segments. (a) Piecewise linear spring force. (b) ZCS for damper force. (c) State and damper force trajectories.

Subsequently, the remaining results of Table  are analysed to identify tendencies. As stated in Section 2.2.1, the additional objective terms (55b) represent a relaxation of the constraints comparable with slack variables. Besides serving as feedback for determining convergence, this relaxation provides robustness regarding the initialisation. This is reflected in the results by a successful convergence of the SSC algorithm in 100% of the test cases, even though a rather poor initial guess was used. The accuracy of the computed solutions is evaluated using the mean values of the main cost function (Equation48) and of the averaged errors (Equation57) and (Equation58) defined as (59) J¯ssi=110Jss,i,e¯Fd¯i=110e¯Fd,iande¯ss¯i=110e¯ss,i.(59) These values represent the respective mean value over all 10 OPs, due to 10 different initial values, for one specified number of collocation segments nseg. With e¯Fd¯3.51N being small compared to the domain of Fd, the control trajectories of the SSC approach are close to the trajectories computed by the NLP solver. The small deviation of the mean values in (Equation59) between the SSC solution and the NLP solution indicates that both algorithms converged to a similar solution. Considering the mean value J¯ss of the main objective function, the NLP solver yields lower objective values than the SSC algorithm. As previously discussed, the mean deviance e¯ss¯ from the steady-state position is smaller when using the SSC algorithm.

The SSC approach greatly reduces the overall computation time tΣSSC and requires up to only 18.20% of the computation time needed by the NLP solver. The time advantage of the SSC algorithm over the NLP optimiser will be even bigger for asymmetric zonally convex damper sets. Such asymmetric sets require additional discontinuities in the NLP problem but can be easily implemented within the SSC procedure by using differing parameters for the individual convex subsets. As mentioned in Section 2.4, various aspects influence the runtime of the SSC algorithm which is reflected in the results: With rising number of collocation segments, the mean solution time increases and the computation time of SSC increases less than the NLP solution time. Another mentioned effect on runtime is the quality of the initial guess. The provided guess with zero vectors is of varying quality for the individual initial value conditions. A better initial guess in terms of the correct signs of the state trajectories reduces the number of superordinate iterations and thus the overall computation time. Hence, the sensitivity in regards to the initial guess is elaborated in the following section.

The pure optimisation time topt,ΣSSC reduces up to 6.45% of the corresponding NLP time and is generally significantly shorter than its overall computation time tΣSSC. Since the projection step of the SSC algorithm employs only simple computations using minimum and maximum functions with linear time complexity, the time spent outside of the QP solver, which solves convex QP-problems in polynomial time, seems quite long. Unfortunately, substantial time losses occur at building the updated optimisation model via JuMP and the Gurobi-wrapper. For future implementations, it is advisable to implement the SSC algorithm via C-code to circumvent this problem and minimise the overall computation time.

3.3. Influence of initial guess on results

In this section, the OPs (Equation51) and (Equation55) are modified to consider the nonlinear spring characteristic with three piecewise linear segments depicted in Figure . The NLP problem (Equation51) is adjusted by replacing the spring force Fc,2,kNLP in the differential equation system considered in constraint (51b) by (60) Fc,3,kNLP=maxϵminϵcmidxk,clowxkx_tr(clowcmid), cupxk+x¯tr(cmidcup)(60) using the smooth maximum function (61) maxϵ(x,y)12(x+y)+(xy)2+ϵ.(61) The adaptation of the QP problem (Equation55) requires slightly more changes. The auxiliary decision variables for the position (Equation53c) are augmented resulting in (62) xaux,kxlow¯,kxlow,kxup,kxmid,kT.(62) Thus, the position space is bisected into a region below and a region above x=x_tr, whereas the upper region is again bisected into a region below and above x=x¯tr. Compared to (Equation54), the update procedure remains unchanged for the decision variables of the inputs, states and auxiliary velocities: (63a) u˘pos,ku˘neg,k=max(uneg,k+upos,k,0)min(uneg,k+upos,k,0),xˆk=xk,v˘pos,kv˘neg,k=max(vk,0)min(vk,0).(63a) However, since the position space is partitioned into three segments, the updating routine changes for the auxiliary position states according to (63b) x˘low¯,kx˘low,k=max(xk,x_tr)min(xk,x_tr),x˘up,kx˘mid,k=max(x˘low¯,k,x¯tr)min(x˘low¯,k,x¯tr).(63b) Furthermore, the correct signs are now given by (63c) σxmu,k=sign(x˘low¯,kx¯tr),σxlm,k=sign(xkx_tr),σv,k=sign(vk).(63c) With iI and kK, the convex QP problem is formulated as (64a) minPJss+τkKlabs,xmu,k+labs,xlm,k+labs,v,kwith(64a) (64b) s.t.labs,xmu,k(xup,kxmid,k)σxmu,k(xlow¯,kx¯tr)labs,xlm,k(xlow¯,kxlow,k)σxlm,k(xkx_tr)labs,v,k(vpos,kvneg,k)σv,kvk,(64b) (64c) ccoll,i=(5)0 with fk=vk1mmgFd,kSSCFc,3,kSSC,Fd,kSSC=uneg,k+upos,k  andFc,3,kSSC=cup(xup,kx¯tr)+cmidxmid,k+clow(xlow,kx_tr),(64c) (64d) xkXx_,x¯,vkVv_,v¯,uneg,kUnegF_d,0,upos,kUpos0,F¯d,vneg,kVnegv_,0,vpos,kVpos0,v¯,xlow,kXlowx_,x_tr,xlow¯,kXlow¯x_tr,x¯,xmid,kXmidx_tr,x¯tr,xup,kXupx¯tr,x¯(64d) (64e) hˆzcs,p,k=d¯1d_1vpos,kupos,k0,hˆzcs,n,k=d_1d¯1vneg,kuneg,k0,(64e) (64f) gaff,xmu,k=xmid,k+xup,k(xlow¯,k+x¯tr)=0gaff,xlm,k=xlow,k+xlow¯,k(xk+x_tr)=0gaff,v,k=vpos,k+vneg,kvk=0,(64f) (64g) labs,xmu,kσxmu,k=+1labs,xmu,kσxmu,k=1=habs,xmu,k0,labs,xlm,kσxlm,k=+1labs,xlm,kσxlm,k=1=habs,xlm,k0,labs,v,kσv,k=+1labs,v,kσv,k=1=habs,v,k0,(64g) (64h) u0=max(d_viv,0)min(d_viv,0),x0=xiv.(64h) The termination criterium is computed via (65) l¯abs=labs,xmu,0labs,xlm,0labs,v,0,,labs,xmu,nseglabs,xlm,nseglabs,v,nsegmax.(65)

In order to analyse the effect of the initialisation on the computed solution, several initial guesses are fed to the SSC algorithm aiming at solving the OP with initial value xiv,1 considering nseg=250 collocation segments. The maximum number of iterations is increased to qmax=25 to check if poor approximations eventually converge. Using the solution of the NLP optimiser uoptNLP and XoptNLP as reference, the initial guesses are generated using (66) uneg,k=kinitminuopt,kNLP,0,upos,k=kinitmaxuopt,kNLP,0,xk=kinitxopt,kNLP(66) with kinit{0.0,0.5,0.75,0.95,1.0,1.05,10.0} which are fed to the SSC update routine. The computations are compared to the results of the NLP problem which is initialised with the same guesses. The results of the individual optimisations are listed in Table . As Figure (a,b) indicates for kinit=0, all solutions satisfy the prescribed constraints: The spring forces lie on the piecewise linear branches and the damper forces are within the admissible area. Considering the objective value Jss and mean error e¯ss in Table , the NLP solver converges to the same solution independently which initial guess is supplied. Thus, it is assumed that the computed NLP solution represents the global optimum or is at least very close to it. However, initialisation can have a massive impact on the computation time. Generally, the guesses close to the solution result in shorter computation times. It is striking that both algorithms have the most difficulty converging for kinit=0.5 which is not the guess with the biggest difference to the optimal solution. The SSC algorithm converges significantly faster than the NLP solver for all initial guesses. The number of superordinate iterations required by the SSC algorithm is small for good initial guesses. As for kinit=0.5, a high number of superordinate iterations can still yield a faster convergence compared to the NLP solver. As already mentioned, the SSC algorithm represents a local method and does not necessarily provide the global optimum, which is reflected in the results. Considering the objective value Jss and mean error e¯ss, only the SSC solutions for kinit0.5 are roughly in the vicinity of the global solution. The mean deviance between the input trajectories e¯Fd is then rather small. Even though the SSC solutions may not represent the global optimum, the solutions satisfy the prescribed constraints since q<qmax. Thus, they represent a local solution of the piecewise linear problem, which corresponds to the original problem for the example at hand. The results for kinit={0.95,1.0,1.05} confirm that the SSC algorithm converges to the global optimum if the initial guess is in a close vicinity of it.

Figure 8. Optimisation results for SMO application with three-segmented nonlinear spring for kinit=0. (a) Piecewise linear spring force with three segments. (b) ZCS for damper force.

Figure 8. Optimisation results for SMO application with three-segmented nonlinear spring for kinit=0. (a) Piecewise linear spring force with three segments. (b) ZCS for damper force.

Table 4. Analysis of sensitivity regarding initial guess.

As mentioned in Section 2.4, increasing the number of space divisions to depict the three-segmented spring raises computation time. This can be confirmed by comparing solution times of the SSC algorithm for kinit=0.0: For the two-segmented spring topt,ΣSSC=0.262s, tΣSSC=0.329s and q=4 holds whereas topt,ΣSSC=0.493s, tΣSSC=0.798s and q=7 holds for the spring with three segments. Thus, more iterations are required and the average computation time per iteration is increased by 7.52% and 38.6% for topt,ΣSSC and tΣSSC, respectively. This highlights the importance of an implementation in C-Code to reduce the time required for the updating routine and therefore the overall computation time.

3.4. Rotated space splitting

As elaborated in Section 2.3.1, some sets require to be split using a rotated straight line. Without going into detail, the approach is applied to the example of a hanging SMO with fully linear spring presented in Section 3.1. The OP is parametrised with initial value xiv,1 and nseg=250 collocation segments. The damper set is rotated by φ=7 resulting in the set depicted in Figure (a). This is implemented by applying the changes (Equation36) to the convex QP problem with fully linear spring. As depicted in Figure (a), the SSC algorithm computes damper forces which all lie within the admissible area. Although this example represents an artificial use-case, the corresponding position trajectories in Figure (b) prove that the rotated set yields a reduction of the objective. Starting with xiv,1<xss in a compression phase with viv,1<0, the mass is first decelerated and then accelerated using Fd<0 at v>0, hence active forces. These active forces enable a faster attainment of the steady-state position. Due to the similarity to the previous examples, no further discussion is given.

4. Conclusions

This article has presented a novel local solution method for efficiently solving nonconvex optimal control problems. Splitting the space of inputs and states enables the formulation of QP subproblems which are solved iteratively. The method is capable of considering two types of nonconvexities: ZCSs and equality constraints with possibly multiple univariate nonlinearities. The approach decomposes the nonconvexities into affine parts which are linked appropriately to approximate the original problem with scalable approximation error. It has been shown that the SSC algorithm converges to a local optimum of this approximated problem. The quality of the solution depends on the initial guess. For good initial guesses, the method converges to solutions close to the global one. A comparison of this successive convexification technique with other existing methods has been given, highlighting the advantages SSC provides.

Figure 9. SSC optimisation results for SMO application with fully linear spring and rotated damper set. (a) Rotated ZCS for damper force. (b) Position trajectory; xSSC: original damper force set; xSSC,φ: rotated damper force set.

Figure 9. SSC optimisation results for SMO application with fully linear spring and rotated damper set. (a) Rotated ZCS for damper force. (b) Position trajectory; xSSC: original damper force set; xSSC,φ: rotated damper force set.

Subsequently, possible directions for future research are disclosed. Even though it would not change the algorithm, using nondifferentiable constraint qualifications (Ye, Citation2004) could potentially avoid the AVC-smoothing required for continuous differentiability regarding the convergence proof. Due to the low computation time and robust convergence, the SSC method seems to be a promising approach for real-time optimal control applications. In this context, using MPC could provide sufficiently good initial guesses (Diehl et al., Citation2005; Gros et al., Citation2020) resulting in good SSC solutions. In order to enhance applicability, the SSC approach could be combined with other iterative linearisation schemes like (Carvalho et al., Citation2013; Liniger et al., Citation2015; Mao et al., Citation2017; Simon et al., Citation2013) which could enable considering collision avoidance constraints. Furthermore, extending the SSC approach to bivariate nonlinearities in equality constraints would enlarge the possible scope of applications. Moreover, applying a more sophisticated updating procedure for the penalty parameter would improve computation times (Maratos, Citation1978; Mayne & Maratos, Citation1979; Nocedal & Wright, Citation2006). For applications with real-time capability requirement, it is recommended to implement the algorithm via tailored C-code to avoid the overhead introduced by the high-level routines of JuMP and the Gurobi-wrapper. Then, the required time for the updating step can be greatly reduced to linear time complexity resulting in shorter overall computation times.

Notation

()ˆ=

Transformed constraints depending on z

()˘=

Projected initial solution of ()

()=

Previous optimal solution of ()

()tr=

Transition point for space bisection

()_,()¯=

Lower and upper bound of ()

()n/neg=

Negative region of bisected space

()p/pos=

Positive region of bisected space

α()=

Smoothable absolute value function

Aˆ,bˆ=

Matrix and vector of affine transformation function

A,B,k=

Matrices and vector for system behaviour description

Azcs,bzcs=

Matrix and vector describing affine ZCSs

c()=

Spring stiffness of corresponding segment () for SMO

c=

Left-hand sides of equality constraints

c~=

Left-hand sides of continuous-time equality constraints

ccoll=

Left-hand sides of collocation equality constraints

ctot=

Left-hand sides of aggregated equality constraints

d=

Damper coefficient for SMO

Δi=

Width of ith collocation segment

e¯Fd=

Mean absolute deviance in damper force trajectories between NLP and SSC solution

ess=

Steady-state position deviation of SMO

e¯ss=

Mean absolute deviance between position trajectory and steady-state position

ϵg=

Error tolerance for linearised AVCs

ϵs=

Smoothing parameter for absolute value function

EΣ/Δ/z=

Matrices for selecting specific decision variables

f=

Right-hand side of differential equation system of model

fΦ=

Affine approximation of right-hand side of model equations

fpwl=

Composition of univariate nonlinearities approximable by piecewise linear curves

Fc=

Spring force of SMO

Fd=

Damper force of SMO

ϕ=

Intermediate objective term

Φx/u/pwl=

Mapping functions affine in the decision variables

g=

Gravitational acceleration for SMO

gabs=

Left-hand sides of AVCs for space splitting

gaff=

Left-hand sides of affine constraints for space splitting

h=

Left-hand sides of inequality constraints

h~=

Left-hand sides of continuous-time inequality constraints

habs=

Left-hand sides of relaxed (inequality) AVCs for space splitting

htot=

Left-hand sides of aggregated inequality constraints

hzcs=

Left-hand sides of ZCS inequality constraints

I=

Set of collocation segment indices

J=

Objective function

J~=

Continuous-time objective functional

Jss=

Objective function for steady-state position deviation of SMO

kinit=

Perturbation parameter for initialisation error

K=

Set of collocation point indices

labs=

Left-hand sides of linearised AVCs for space splitting

m=

Mass of SMO

nc=

Number of equality constraints

nh=

Number of inequality constraints

npts=

Number of collocation points

ns=

Number of auxiliary decision variables

nseg=

Number of collocation segments

nu=

Number of input decision variables

nw=

Number of original decision variables

nx=

Number of state decision variables

O()=

Landau-notation for computational complexity

P0,q0,r0=

parameters of quadratic objective

q=

Number of superordinate iterations in SSC algorithm

qmax=

Maximum number of superordinate iterations

Rn=

Set of n-dimensional, real vectors

sw=

Slack variable for AVC

S()=

Set described by inequality constraints

σ()=

Sign of corresponding AVC

Σ=

Matrix containing all linearisation points of AVCs

t=

Time

topt,Σ=

Cumulative time spent in solver

tΣ=

Total computation time

τ=

Penalty parameter for additional objective terms

ϑ=

Terminal objective term

u=

Input vector of system

U=

Bounding-box set for system inputs

U0=

Initial solution for input decision variables

v=

Deflection velocity of SMO

w=

Vector of original decision variables

waux=

Vector of auxiliary decision variables

wlow/up=

Lower/upper region of bisected space of w

x=

Deflection position of SMO

xss=

Steady-state position of SMO

xlow/low¯=

Lower/upper region of position space bisection for SMO

xmid/up=

Lower/upper region of bisected position space xlow¯ for SMO

x=

State vector of system

X=

Bounding-box set for system states

X0=

Initial solution for state decision variables

xiv=

Initial value of system state for SMO

z=

Vector of accumulated decision variables

z~=

Argument vector for absolute value function

z~=

Linearisation point for AVCs

Disclosure statement

No potential conflict of interest was reported by the author(s).

References

  • Acikmese, B., & Blackmore, L. (2011). Lossless convexification of a class of optimal control problems with non-convex control constraints. Automatica, 47(2), 341–347. https://doi.org/10.1016/j.automatica.2010.10.037
  • Acikmese, B., & Ploen, S. R. (2007). Convex programming approach to powered descent guidance for Mars landing. Journal of Guidance, Control, and Dynamics, 30(5), 1353–1366. https://doi.org/10.2514/1.27553
  • Armaou, A., & Ataei, A. (2014). Piece-wise constant predictive feedback control of nonlinear systems. Journal of Process Control, 24(4), 326–335. https://doi.org/10.1016/j.jprocont.2014.02.002
  • Betts, J. T. (2010). Practical methods for optimal control and estimation using nonlinear programming (2nd ed.). Society for Industrial and Applied Mathematics.
  • Boyd, S., & Vandenberghe, L. (2004). Convex optimization (7th ed.). Cambridge University Press.
  • Carvalho, A., Gao, Y., Gray, A., Tseng, H. E., & Borrelli, F. (2013). Predictive control of an autonomous ground vehicle using an iterative linearization approach. 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013) (p. 2335–2340). doi:10.1109/ITSC.2013.6728576
  • Chen, J., Zhan, W., & Tomizuka, M. (2017). Constrained iterative LQR for on-road autonomous driving motion planning. 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC) (p. 1–7). doi:10.1109/ITSC.2017.8317745
  • Cibulka, V., Hanis, T., & Hromcik, M. (2019). Data-driven identification of vehicle dynamics using Koopman operator. https://arxiv.org/abs/1903.06103
  • Cibulka, V., Haniš, T., Korda, M., & Hromčík, M. (2020). Model predictive control of a vehicle using Koopman operator. IFAC-PapersOnLine, 53(2), 4228–4233. https://doi.org/10.1016/j.ifacol.2020.12.2469(21st IFAC World Congress)
  • d'Aspremont, A., & Boyd, S. (2003). Relaxations and randomized methods for nonconvex QCQPs. Retrieved November 24, Retrieved 2020, from https://web.stanford.edu/class/ee392o/relaxations.pdf.
  • Del Re, L., Chapuis, J., & Nevistic, V. (1993). Predictive control with embedded feedback linearization for bilinear plants with input constraints. Proceedings of 32nd IEEE Conference on Decision and Control (Vol. 4, p. 2984–2989). doi:10.1109/CDC.1993.325747
  • Diehl, M., Bock, H. G., & Schlöder, J. P. (2005). A real-time iteration scheme for nonlinear optimization in optimal feedback control. SIAM Journal on Control and Optimization, 43(5), 1714–1736. https://doi.org/10.1137/S0363012902400713
  • Di Pillo, G., & Grippo, L. (1989). Exact penalty functions in constrained optimization. SIAM Journal on Control and Optimization, 27(6), 1333–1360. https://doi.org/10.1137/0327068
  • Dunning, I., Huchette, J., & Lubin, M. (2017). JuMP: A modeling language for mathematical optimization. SIAM Review, 59(2), 295–320. https://doi.org/10.1137/15M1020575
  • Falcone, P., Borrelli, F., Asgari, J., Tseng, H. E., & Hrovat, D. (2007). Predictive active steering control for autonomous vehicle systems. IEEE Transactions on Control Systems Technology, 15(3), 566–580. https://doi.org/10.1109/TCST.2007.894653
  • Fang, Y., & Armaou, A. (2015). Nonlinear model predictive control using a bilinear Carleman linearization-based formulation for chemical processes. 2015 American Control Conference (ACC) (p. 5629–5634). doi:10.1109/ACC.2015.7172221
  • Ferreau, H., Almér, S., Verschueren, R., Diehl, M., Frick, D., Domahidi, A., Jerez, J.L., Stathopoulos, G., & Jones, C. (2017). Embedded optimization methods for industrial automatic control. IFAC-PapersOnLine, 50(1), 13194–13209. https://doi.org/10.1016/j.ifacol.2017.08.1946
  • Gros, S., Zanon, M., Quirynen, R., Bemporad, A., & Diehl, M. (2020). From linear to nonlinear MPC: Bridging the gap via the real-time iteration. International Journal of Control, 93(1), 62–80. https://doi.org/10.1080/00207179.2016.1222553
  • Gurobi Optimization (2020). Gurobi optimizer reference manual. Retrieved November 24, 2020, from https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/9.1/refman.pdf.
  • Han, S. P., & Mangasarian, O. L. (1979). Exact penalty functions in nonlinear programming. Mathematical programming, 17(1), 251–269. https://doi.org/10.1007/BF01588250
  • Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4, 373–395. https://doi.org/10.1007/BF02579150
  • Kelly, M. (2017). An introduction to trajectory optimization: How to do your own direct collocation. SIAM Review, 59(4), 849–904. https://doi.org/10.1137/16M1062569
  • Khalil, H. K. (2002). Nonlinear systems (3rd ed.). Prentice Hall.
  • Korda, M., & Mezić, I. (2018). Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control. Automatica, 93(1), 149–160. https://doi.org/10.1016/j.automatica.2018.03.046
  • Kozlov, M., Tarasov, S., & Khachiyan, L. (1980). The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics, 20(5), 223–228. https://doi.org/10.1016/0041-5553(80)90098-1
  • Kurtz, M. J., & Henson, M. A. (1997). Input-output linearizing control of constrained nonlinear processes. Journal of Process Control, 7(1), 3–17. https://doi.org/10.1016/S0959-1524(96)00006-6
  • Liberti, L. (2008). Introduction to global optimization. Retrieved January 23, 2021, from https://www.lix.polytechnique.fr/liberti/teaching/globalopt-lima.pdf.
  • Liberti, L., & Maculan, N. (2006). Global optimization – from theory to implementation. Springer Science and Business Media.
  • Liniger, A., Domahidi, A., & Morari, M. (2015). Optimization-based autonomous racing of 1:43 scale RC cars. Optimal Control Applications and Methods, 36, 628–647. https://doi.org/10.1002/oca.2123
  • Lipp, T., & Boyd, S. (2016). Variations and extension of the convex–concave procedure. Optimization and Engineering, 17, 263–287. https://doi.org/10.1007/s11081-015-9294-x
  • Mangasarian, O. L. (2015). A hybrid algorithm for solving the absolute value equation. Optimization Letters, 9, 1469–1474. https://doi.org/10.1007/s11590-015-0893-4
  • Mao, Y., Dueri, D., Szmuk, M., & Açíkmeşe, B. (2017). Successive Convexification of Non-Convex Optimal Control Problems with State Constraints. IFAC-PapersOnLine, 50(1), 4063–4069. https://doi.org/10.1016/j.ifacol.2017.08.789(20th IFAC World Congress)
  • Mao, Y., Szmuk, M., & Açíkmeşe, B. (2016). Successive convexification of non-convex optimal control problems and its convergence properties. 2016 IEEE 55th Conference on Decision and Control (CDC) (p. 3636–3641). https://doi.org/10.1109/CDC.2016.7798816
  • Maratos, N. (1978). Exact penalty function algorithms for finite dimensional and control optimization problems [Unpublished doctoral dissertation]. Imperial College London (University of London).
  • Mayne, D. Q. (1973). Differential dynamic programming – A unified approach to the optimization of dynamic systems. In C. Leondes (Ed.), Control and dynamic systems (Vol. 10, p. 179–254). Academic Press.
  • Mayne, D. Q., & Maratos, N. (1979). A first order, exact penalty function algorithm for equality constrained optimization problems. Mathematical Programming, 16(1), 303–324. https://doi.org/10.1007/BF01582118
  • Mollov, S., Babuska, R., Abonyi, J., & Verbruggen, H. B. (2004). Effective optimization for fuzzy model predictive control. IEEE Transactions on Fuzzy Systems, 12(5), 661–675. https://doi.org/10.1109/TFUZZ.2004.834812
  • Mollov, S., Babuška, R., Roubos, J., & Verbruggen, H. (1998). MIMO predictive control by multiple-step linearization of Takagi-Sugeno fuzzy models. IFAC Proceedings Volumes, 31(29), 197–202. https://doi.org/10.1016/S1474-6670(17)38944-9(7th IFAC Symposium on Artificial Intelligence in Real Time Control 1998., Grand Canyon National Park, USA, 5–8 October)
  • Nocedal, J., & Wright, S. (2006). Numerical optimization. Springer Science and Business Media.
  • Park, J., & Boyd, S. (2017). General heuristics for nonconvex quadratically constrained quadratic programming. https://arxiv.org/abs/1703.07870
  • Perantoni, G., & Limebeer, D. J. (2014). Optimal control for a Formula One car with variable parameters. Vehicle System Dynamics, 52(5), 653–678. https://doi.org/10.1080/00423114.2014.889315
  • Raković, S. V., & Levine, W. S. (2018). Handbook of model predictive control. Springer.
  • Ryoo, H., & Sahinidis, N. (1995). Global optimization of nonconvex NLPs and MINLPs with applications in process design. Computers and Chemical Engineering, 19(5), 551–566. https://doi.org/10.1016/0098-1354(94)00097-2
  • Savaresi, S. M., Poussot-Vassal, C., Spelta, C., Sename, O., & Dugard, L. (2010). Semi-active suspension control design for vehicles (1st ed.). Elsevier.
  • Schnelle, F., & Eberhard, P. (2015). Constraint mapping in a feedback linearization/MPC scheme for trajectory tracking of underactuated multibody systems. IFAC-PapersOnLine, 48(23), 446–451. https://doi.org/10.1016/j.ifacol.2015.11.319(5th IFAC Conference on Nonlinear Model Predictive Control NMPC 2015)
  • Sedlacek, T., Odenthal, D., & Wollherr, D. (2020a). Convexification of semi-activity constraints applied to minimum-time optimal control for vehicles with semi-active limited-slip differential. In 17th International Conference on Informatics in Control, Automation and Robotics – volume 1: Icinco (p. 15–25). SciTePress.
  • Sedlacek, T., Odenthal, D., & Wollherr, D. (2020b). Minimum-time optimal control for battery electric vehicles with four wheel-independent drives considering electrical overloading. Vehicle System Dynamics, 1–25. https://doi.org/10.1080/00423114.2020.1823004
  • Sedlacek, T., Odenthal, D., & Wollherr, D. (2020c). Minimum-time optimal control for vehicles with active rear-axle steering, transfer case and variable parameters. Vehicle System Dynamics, 59(8), 1227–1255. https://doi.org/10.1080/00423114.2020.1742925
  • Seki, H., Ooyama, S., & Ogawa, M. (2004). Nonlinear model predictive control using successive linearization. Transactions of the Society of Instrument and Control Engineers, E-3(1), 66–72. https://www.sice.jp/e-trans/papers/E3-9.pdf
  • Simon, D., Löfberg, J., & Glad, T. (2013). Nonlinear model predictive control using feedback linearization and local inner convex constraint approximations. 2013 European Control Conference (ECC) (p. 2056–2061). https://doi.org/10.23919/ECC.2013.6669575
  • Tanaka, K., & Wang, H. O. (2004). Fuzzy control systems design and analysis – a linear matrix inequality approach. John Wiley and Sons.
  • Tassa, Y., Erez, T., & Todorov, E. (2012). Synthesis and stabilization of complex behaviors through online trajectory optimization. 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (p. 4906–4913). https://doi.org/10.1109/IROS.2012.6386025
  • Tassa, Y., Mansard, N., & Todorov, E. (2014). Control-limited differential dynamic programming. 2014 IEEE International Conference on Robotics and Automation (ICRA) (p. 1168–1175). https://doi.org/10.1109/ICRA.2014.6907001
  • Tawarmalani, M., & Sahinidis, N. V. (2002). Convexification and global optimization in continuous and mixed-integer nonlinear programming - theory, algorithms, software, and applications. Springer Science and Business Media.
  • Verschueren, R. (2018). Convex approximation methods for nonlinear model predictive control [Unpublished doctoral dissertation]. University of Freiburg.
  • Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1), 25–57. https://doi.org/10.1007/s10107-004-0559-y
  • Xie, Z., Liu, C. K., & Hauser, K. (2017). Differential dynamic programming with nonlinear constraints. 2017 IEEE International Conference on Robotics and Automation (ICRA) (p. 695–702). https://doi.org/10.1109/ICRA.2017.7989086
  • Ye, J. J. (2004). Nondifferentiable multiplier rules for optimization and Bilevel optimization problems. SIAM Journal on Optimization, 15(1), 252–274. https://doi.org/10.1137/S1052623403424193
  • Zorich, V. A. (2016). Mathematical analysis I. Springer.