The algorithm's objective is to efficiently solve Dynamic Linear Programs by taking advantage of their special staircase structure, which constitutes a stepping stone to an improved algorithm for solving Dynamic Quadratic Programs, which would make the nonlinear programming method of Successive Quadratic Programs more practical for solving trajectory optimization problems.
For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.
Frank E. Curtis, Ling-Jun Guo, Daniel P. Robinson· 0 citations
This paper solves the targeting problem focusing on accuracy, computational efficiency, and reliability. The trajectory optimization problem is first recast as a polynomial optimization problem (POP) by leveraging differential algebra to compute high-order Taylor expansions of the nonlinear dynamics and constraints. Moment-sum-of-squares (SOS) optimization is then utilized to solve this POP. A convex formulation based on a second-order expansion of the dynamics is also proposed. For impulsive targeting, the moment-SOS and convex approaches are compared against traditional nonlinear programming (NLP) solvers and map inversion techniques. Results indicate that the moment-SOS approach provides solutions as accurate as traditional NLP, but with the critical advantage of guaranteeing convergence to the global optimum under mild assumptions. Furthermore, the method excels at handling large maneuvers and long propagation times, conditions in which standard linear approximations rapidly degrade. To demonstrate its versatility, the methodology is extended to a continuous low-thrust station keeping (SK) scenario in the Earth-Moon Circular Restricted Three-Body Problem. The algorithm's performance is then evaluated in the presence of significant state errors. The ability to directly handle non-convex constraints and recast complex, nonlinear dynamics into formulations with reliable convergence properties makes the moment-SOS approach suitable for autonomous onboard applications.
Adam Evans, Alberto Fossà, Roberto Armellin et al.· 0 citations
Abstract Refinery network optimization is a challenging Mixed-Integer Nonlinear Programming (MINLP) problem due to complex process interactions and non-linearities. This paper proposes a multi-period solution strategy that decomposes the original MINLP into a sequence of tractable sub-problems. First, all non-linear terms are linearized, and the resulting linear program is solved to obtain an initial feasible solution. Then, each non-linear term is restored iteratively, using the solution of the previous step as a starting point. After all non-linearities are reintroduced, the full MINLP is solved with the refined initial conditions. The approach is demonstrated on a real-world refinery case study. Compared to the benchmark of Seinfeld and McBride (1970), the proposed strategy achieves a 2.7 % increase in profit while maintaining computational feasibility. The step-by-step evolution of the solution, intermediate results, and computational performance (CPU time: 0.45 s, optimality gap: 0.0 %) are discussed in detail.
M. Khalilipour, Mohammad Reza Sardashti Birjandi, F. Shahraki· Chemical product and process...· 0 citations
One of the peculiar features of multi-parametric approach for bilevel programs is that most methods using this approach can be extended to tri-level (and generally to $k$-level) programs, which is not always the case with other non-heuristic solution methods. However, most of existing multi-parametric methods work well when the constraint of the lower-level problem is polyhedral. In this article we propose a multi-parametric programming based solution algorithm for bilevel optimization problems whose lower-level problem involves convex smooth nonlinear constraints. The method is also extended to solve some classes of $k$-level convex optimization problems with nonlinear constraints. The algorithm recasts the lower-level problem as a multi-parametric problem and employs an equivalent barrier problem reformulation. The solution obtained through multi-parametric programming is incorporated in the upper-level problem to create a set of single-level optimization problems which are solved using standard global optimization techniques. The proposed algorithm can give an exact global solution to some class of nonlinear Multi-level problems with convex nonlinear constraints.
The method introduces a structured loop-enumeration strategy within the transportation simplex framework that yields optimal solutions identical to classical methods and achieves comparable or improved performance on average runtime, with clearer benefits on medium-to-large instances where loop redundancy is more pronounced.
D. K. Boah, Suleman Abudu Fiele, C. J. Etwire· Discover Analytics· 0 citations
We consider a quadratic minmax problem with coupled inner constraints and propose a method to compute a class of stationary points. To motivate the need to compute such stationary points, we first show that they are meaningful, in the sense that they can be locally optimal for our problem under suitable{non-degeneracy} conditions. Then based on a suitable log barrier function, we build an infeasible interior point-type {single loop method} (which does not explicitly distinguish between the outer and inner problem) and prove that a non-degenerate stationary point is an attraction point as the algorithm moves along the designed central path. We show in particular that our method is polynomial in the special case where the inner feasible set of our constrained minmax problem is independent from outer variables. Our numerical experiments, on both synthetic data and a class of min-cost flow problems, showcase the behavior of our method and how it outperforms existing algorithms from the literature in terms of the quality of the computed stationary points.
S. Cipolla, O. Stein, Alain B. Zemkoho· 0 citations