This paper is devoted to the introduction and analysis of a penalty-type method for the numerical treatment of a class of bilevel optimization problems arising from inverse optimal control. The algorithm is designed to compute stationary points of the associated relaxed value function reformulation. This is achieved by determining a sequence of stationary points associated with a sequence of surrogate problems where the relaxed value function constraint is penalized, where the updates of upper- and lower-level decision variables are decoupled, and where the penalty parameter is enlarged only in those iterations which do not come along with a sufficient improvement of some feasibility measure. The resulting method does not comprise any linesearch, the lower-level problem has to be evaluated just once per iteration, and the penalty parameter does not need to be driven to infinity. Nevertheless, subsequential convergence results are obtained under reasonable assumptions. Numerical experiments, where the relaxation parameter is also driven to zero, visualize effectiveness of the approach.
Penalty function methods are fundamental for solving constrained optimization problems, yet the widely used l1 exact penalty function is non-differentiable and therefore incompatible with gradient-based algorithms. This paper proposes a continuously differentiable smoothing approximation that preserves the exactness of the original penalty while enabling efficient numerical solution. The proposed smoothing function is shown to be C1 on R, with explicit error bounds and a computable lower bound for the penalty parameter that guarantees exactness under standard constraint qualifications. An iterative algorithm is developed and its convergence is proved. Numerical experiments on benchmark problems validate the effectiveness of the approach. The method is then applied to a policy-driven university financial risk management model with twelve decision variables, three conflicting objectives, and multiple regulatory constraints. Results demonstrate faster convergence and improved objective values compared with the traditional non-smooth penalty method, confirming the practical utility of the proposed smoothing technique.
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
Theoretically, this work belongs to a fairly broad class of articles and books devoted to solving control problems for dynamic objects with constraints on control actions and the Bolza functional. The necessary conditions for the existence of optimal controls for a terminal differential game are described by a two-point boundary value problem and the condition for choosing the control itself as a function dependent on the behavior of the Hamiltonian along the optimal trajectory. The main problem of finding optimal control is associated with finding a solution to the two-point boundary value problem. It should be noted that the existence of an optimal control is not necessary: the set of admissible controls may not even contain controls that transform the object from the initial state to a given set of goals. Typically, numerical methods are used to solve such problems. In this paper, an alternative to numerical methods for solving two-point boundary value problems, applied to the problem of synthesizing controls for nonlinear objects, is proposed. This approach is based on the assumption of the validity of R. Bellman’s inverse optimality principle, which maintains the functional relationship between the components of a two-point boundary value problem not only at the end of the transient process but throughout the entire control interval. Based on this, a new analytical method for constructing control for nonlinear objects, called the pseudo-optimal control synthesis method, is proposed. A condition is formulated for determining the set of initial conditions of the original nonlinear system that ensure the execution of the formulated control problem. Mathematical modeling of a quadcopter control system with synthesized control confirmed the theoretical results of the proposed method for synthesizing pseudo-optimal control for nonlinear dynamic objects.
V. Afanas'ev, K. Khalifekh· Mekhatronika Avtomatizatsiya...· 0 citations
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 discusses some aspects related to gradient-based optimization algorithms with special focus on the requirements associated to their use in the implementation of Nonlinear Model Predictive Control. Based on a dedicated discussion, a new algorithm, termed Search and Accelerate (SaA) is proposed that mixes together a novel line search, a trust region mechanism together with an adaptation of the gradient acceleration scheme. A dedicated benchmark involving a set of 600 instances of box constrained optimization problems is designed and used in order to show the algorithm performances which make it a highly competitive general purpose gradient-based alternative for box-constrained optimization problems. An appealing feature of the algorithm is its robustness to the choice of the few parameters involved in its definition making the default values a valid option for any problem without a priori knowledge of the related Lipchitz constant. Moreover, an example of use of the proposed algorithm in NMPC implementation is proposed showing the possibility to reduce the control updating period which might be mandatory in some circumstances.
Path Integral (PI) control is a powerful sampling-based method for stochastic optimal control, but it requires a restrictive coupling between the noise covariance and the control cost matrix that is rarely satisfied in practice, particularly in aerospace and cyber-physical systems. We propose Bound-Optimized Task Choice (BOTC), a framework that optimizes over the entire space of valid approximations, termed tasks, satisfying the PI coupling constraint. We prove that every task provides an upper bound on the true cost-to-go and that BOTC minimizes this bound. We derive a change-of-measure formulation that enables evaluation of all candidate tasks from a single set of Monte Carlo samples, eliminating the need to resample for each candidate task. The resulting optimization is parameterized by a positive semi-definite matrix. Furthermore, we propose a novel Normal-Inverse-Wishart distribution-based importance sampling scheme to improve global optimization. We validate BOTC on a finite-horizon stochastic linear-quadratic regulator problem, demonstrating that it tracks the constrained optimum.
R. Anderson, Goutam Das, Takashi Tanaka· 0 citations