اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدReduction of the Number of Variables in Parametric Constrained Least-Squares Problems
51
0
0.0
(
0
)
نشر من قبل
Alberto Bemporad Prof.
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For linearly constrained least-squares problems that depend on a vector of parameters, this paper proposes techniques for reducing the number of involved optimization variables. After first eliminating equality constraints in a numerically robust way by QR factorization, we propose a technique based on singular value decomposition (SVD) and unsupervised learning, that we call $K$-SVD, and neural classifiers to automatically partition the set of parameter vectors in $K$ nonlinear regions in which the original problem is approximated by using a smaller set of variables. For the special case of parametric constrained least-squares problems that arise from model predictive control (MPC) formulations, we propose a novel and very efficient QR factorization method for equality constraint elimination. Together with SVD or $K$-SVD, the method provides a numerically robust alternative to standard condensing and move blocking, and to other complexity reduction methods for MPC based on basis functions. We show the good performance of the proposed techniques in numerical tests and in a linearized MPC problem of a nonlinear benchmark process.
قيم البحث
اقرأ أيضاً
We provide a full characterization of the oblique projector $U(VU)^+V$ in the general case where the range of $U$ and the null space of $V$ are not complementary subspaces. We discuss the new result in the context of constrained least squares minimization.
In this paper, the optimization problem of the supervised distance preserving projection (SDPP) for data dimension reduction (DR) is considered, which is equivalent to a rank constrained least squares semidefinite programming (RCLSSDP). In order to o
vercome the difficulties caused by rank constraint, the difference-of-convex (DC) regularization strategy was employed, then the RCLSSDP is transferred into a series of least squares semidefinite programming with DC regularization (DCLSSDP). An inexact proximal DC algorithm with sieving strategy (s-iPDCA) is proposed for solving the DCLSSDP, whose subproblems are solved by the accelerated block coordinate descent (ABCD) method. Convergence analysis shows that the generated sequence of s-iPDCA globally converges to stationary points of the corresponding DC problem. To show the efficiency of our proposed algorithm for solving the RCLSSDP, the s-iPDCA is compared with classical proximal DC algorithm (PDCA) and the PDCA with extrapolation (PDCAe) by performing DR experiment on the COIL-20 database, the results show that the s-iPDCA outperforms the PDCA and the PDCAe in solving efficiency. Moreover, DR experiments for face recognition on the ORL database and the YaleB database demonstrate that the rank constrained kernel SDPP (RCKSDPP) is effective and competitive by comparing the recognition accuracy with kernel semidefinite SDPP (KSSDPP) and kernal principal component analysis (KPCA).
The problem of fitting experimental data to a given model function $f(t; p_1,p_2,dots,p_N)$ is conventionally solved numerically by methods such as that of Levenberg-Marquardt, which are based on approximating the Chi-squared measure of discrepancy b
y a quadratic function. Such nonlinear iterative methods are usually necessary unless the function $f$ to be fitted is itself a linear function of the parameters $p_n$, in which case an elementary linear Least Squares regression is immediately available. When linearity is present in some, but not all, of the parameters, we show how to streamline the optimization method by reducing the nonlinear activity to the nonlinear parameters only. Numerical examples are given to demonstrate the effectiveness of this approach. The main idea is to replace entries corresponding to the linear terms in the numerical difference quotients with an optimal value easily obtained by linear regression. More generally, the idea applies to minimization problems which are quadratic in some of the parameters. We show that the covariance matrix of $chi^2$ remains the same even though the derivatives are calculated in a different way. For this reason, the standard non-linear optimization methods can be fully applied.
Stochastic gradient descent (SGD) exhibits strong algorithmic regularization effects in practice, which has been hypothesized to play an important role in the generalization of modern machine learning approaches. In this work, we seek to understand t
hese issues in the simpler setting of linear regression (including both underparameterized and overparameterized regimes), where our goal is to make sharp instance-based comparisons of the implicit regularization afforded by (unregularized) average SGD with the explicit regularization of ridge regression. For a broad class of least squares problem instances (that are natural in high-dimensional settings), we show: (1) for every problem instance and for every ridge parameter, (unregularized) SGD, when provided with logarithmically more samples than that provided to the ridge algorithm, generalizes no worse than the ridge solution (provided SGD uses a tuned constant stepsize); (2) conversely, there exist instances (in this wide problem class) where optimally-tuned ridge regression requires quadratically more samples than SGD in order to have the same generalization performance. Taken together, our results show that, up to the logarithmic factors, the generalization performance of SGD is always no worse than that of ridge regression in a wide range of overparameterized problems, and, in fact, could be much better for some problem instances. More generally, our results show how algorithmic regularization has important consequences even in simpler (overparameterized) convex settings.
We conduct a study and comparison of superiorization and optimization approaches for the reconstruction problem of superiorized/regularized least-squares solutions of underdetermined linear equations with nonnegativity variable bounds. Regarding supe
riorization, the state of the art is examined for this problem class, and a novel approach is proposed that employs proximal mappings and is structurally similar to the established forward-backward optimization approach. Regarding convex optimization, accelerated forward-backward splitting with inexact proximal maps is worked out and applied to both the natural splitting least-squares term/regularizer and to the reverse splitting regularizer/least-squares term. Our numerical findings suggest that superiorization can approach the solution of the optimization problem and leads to comparable results at significantly lower costs, after appropriate parameter tuning. On the other hand, applying accelerated forward-backward optimization to the reverse splitting slightly outperforms superiorization, which suggests that convex optimization can approach superiorization too, using a suitable problem splitting.
الأسئلة المقترحة
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
