Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Constraint-Reduced MPC Algorithm for Convex Quadratic Programming, with a Modified Active Set Identification Scheme
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A constraint-reduced Mehrotra-Predictor-Corrector algorithm for convex quadratic programming is proposed. (At each iteration, such algorithms use only a subset of the inequality constraints in constructing the search direction, resulting in CPU savings.) The proposed algorithm makes use of a regularization scheme to cater to cases where the reduced constraint matrix is rank deficient. Global and local convergence properties are established under arbitrary working-set selection rules subject to satisfaction of a general condition. A modified active-set identification scheme that fulfills this condition is introduced. Numerical tests show great promise for the proposed algorithm, in particular for its active-set identification scheme. While the focus of the present paper is on dense systems, application of the main ideas to large sparse systems is briefly discussed.
rate research
Read More
A framework is proposed for solving general convex quadratic programs (CQPs) from an infeasible starting point by invoking an existing feasible-start algorithm tailored for inequality-constrained CQPs. The central tool is an exact penalty function scheme equipped with a penalty-parameter updating rule. The feasible-start algorithm merely has to satisfy certain general requirements, and so is the updating rule. Under mild assumptions, the framework is proved to converge on CQPs with both inequality and equality constraints and, at a negligible additional cost per iteration, produces an infeasibility certificate, together with a feasible point for an (approximately) $ell_1$-least relaxed feasible problem when the given problem does not have a feasible solution. The framework is applied to a feasible-start constraint-reduced interior-point algorithm previously proved to be highly performant on problems with many more constraints than variables (imbalanced). Numerical comparison with popular codes (SDPT3, SeDuMi, MOSEK) is reported on both randomly generated problems and support-vector machine classifier training problems. The results show that the former typically outperforms the latter on imbalanced problems.
This paper presents a sparse solver based on the alternating direction method of multipliers algorithm for a linear model predictive control (MPC) formulation in which the terminal state is constrained to a given ellipsoid. The motivation behind this solver is to substitute the typical polyhedral invariant set used as a terminal constraint in many nominal and robust linear MPC formulations with an invariant set in the form of an ellipsoid, which is (typically) much easier to compute and results in an optimization problem with significantly fewer constraints, even for average-sized systems. However, this optimization problem is no longer the quadratic programming problem found in most linear MPC approaches, thus meriting the development of a tailored solver. The proposed solver is suitable for its use in embedded systems, since it is sparse, has a small memory footprint and requires no external libraries. We show the results of its implementation in an embedded system to control a simulated multivariable plant, comparing it against other alternatives.
We describe an active-set method for the minimization of an objective function $phi$ that is the sum of a smooth convex function and an $ell_1$-regularization term. A distinctive feature of the method is the way in which active-set identification and {second-order} subspace minimization steps are integrated to combine the predictive power of the two approaches. At every iteration, the algorithm selects a candidate set of free and fixed variables, performs an (inexact) subspace phase, and then assesses the quality of the new active set. If it is not judged to be acceptable, then the set of free variables is restricted and a new active-set prediction is made. We establish global convergence for our approach, and compare the new method against the state-of-the-art code LIBLINEAR.
We consider the minimization problem with the truncated quadratic regularization with gradient operator, which is a nonsmooth and nonconvex problem. We cooperated the classical preconditioned iterations for linear equations into the nonlinear difference of convex functions algorithms with extrapolation. Especially, our preconditioned framework can deal with the large linear system efficiently which is usually expensive for computations. Global convergence is guaranteed and local linear convergence rate is given based on the analysis of the Kurdyka-L ojasiewicz exponent of the minimization functional. The proposed algorithm with preconditioners turns out to be very efficient for image restoration and is also appealing for image segmentation.
In this paper, we consider the problem of recovering a sparse signal based on penalized least squares formulations. We develop a novel algorithm of primal-dual active set type for a class of nonconvex sparsity-promoting penalties, including $ell^0$, bridge, smoothly clipped absolute deviation, capped $ell^1$ and minimax concavity penalty. First we establish the existence of a global minimizer for the related optimization problems. Then we derive a novel necessary optimality condition for the global minimizer using the associated thresholding operator. The solutions to the optimality system are coordinate-wise minimizers, and under minor conditions, they are also local minimizers. Upon introducing the dual variable, the active set can be determined using the primal and dual variables together. Further, this relation lends itself to an iterative algorithm of active set type which at each step involves first updating the primal variable only on the active set and then updating the dual variable explicitly. When combined with a continuation strategy on the regularization parameter, the primal dual active set method is shown to converge globally to the underlying regression target under certain regularity conditions. Extensive numerical experiments with both simulated and real data demonstrate its superior performance in efficiency and accuracy compared with the existing sparse recovery methods.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
