{"id":2663,"date":"2024-05-29T02:10:27","date_gmt":"2024-05-29T02:10:27","guid":{"rendered":"https:\/\/elo-x.eu\/?p=2663"},"modified":"2024-05-29T02:11:36","modified_gmt":"2024-05-29T02:11:36","slug":"algorithms-for-solving-hard-optimization-problems-2","status":"publish","type":"post","link":"https:\/\/elo-x.eu\/?p=2663","title":{"rendered":"Algorithms for solving hard optimization problems"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Algorithms for solving nonlinear programs<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Lahcen El Bourkhissi,\u00a0<\/span><\/span>Polytechnic University of Bucharest<\/span><\/span>
<\/span><\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In my research, I focus on addressing nonlinear programs, which commonly arise in Nonlinear Model Predictive Control and other areas like machine learning. Solving these problems is challenging due to their nonconvex and sometimes nonsmooth nature. My primary goal is to develop efficient methods based on penalty and augmented Lagrangian approaches capable of effectively handling such challenges. Specifically, I aim to devise methods that involve solving only simple subproblems, such as convex subproblems.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Penalty-based method for solving nonlinear programs<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

[1] El Bourkhissi, Necoara “Complexity of linearized quadratic penalty for optimization with nonlinear equality constraints” – submitted, 2023<\/em><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

\u00a0<\/p>

IN [1], we considered a nonconvex optimization problem with nonlinear equality constraints. We assumed that both the objective function and the functional constraints were locally smooth. To solve this problem, we applied a linearized quadratic penalty method. That is, we linearized the objective function and the functional constraints in the penalty formulation at the current iterate and added a quadratic regularization, thus yielding a subproblem that is easy to solve (in fact, the solution of our subproblem is equiavlent to the solving a linear system), and whose solution was the next iterate. Under a dynamic regularization parameter choice, we derived convergence guarantees for the iterates of our method to an \u03b5 first-order optimal solution in O(1\/\u03b5^3) evaluations of the first order information of the objective function and functional constraints. Finally, we showed that when the problem data satisfied the Kurdyka-Lojasiewicz property, e.g., were semialgebraic, the whole sequence generated by our algorithm converged and we derived convergence rates. We validated the theory and the performance of the proposed algorithm by numerically comparing it with some existing methods from the literature.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t

\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t
Performance profiles for the computation time (left) and the number of iterations (right).<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

ADMM scheme for nonsmooth nonlinear programs<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

[2] El Bourkhissi, Necoara, Patrinos, “Linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints”, CDC 2023<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In [2], we proposed a new approach for solving a structured nonsmooth nonconvex optimization problem with nonlinear equality constraints, where both the objective function and constraints were 2-block separable. Our method was based on a 2-block linearized ADMM, where we linearized the smooth part of the cost function and the nonlinear term of the functional constraints in the augmented Lagrangian at each outer iteration. This resulted in simple subproblems, whose solutions were used to update the iterates of the 2 blocks variables. We proved global convergence for the sequence generated by our method to a stationary point of the original problem. We applied our proposed algorithm as a solver for the nonlinear model predictive control problem of an inverted pendulum on a cart.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t

\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t
Nonlinear MPC inputs $u$ (top), cart lateral position $z_1$ (middle) and pendulum angular position $z_3$ (bottom) computed using Linearized ADMM<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Algorithms for solving nonlinear programs Lahcen El Bourkhissi,\u00a0Polytechnic University of Bucharest In my research, I focus on addressing nonlinear programs, which commonly arise in Nonlinear Model Predictive Control and other areas like machine learning. Solving these problems is challenging due to their nonconvex and sometimes nonsmooth nature. My primary goal is to develop efficient methods … <\/p>\n

Continue reading “Algorithms for solving hard optimization problems”<\/span><\/a><\/p>\n","protected":false},"author":19,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"elementor_header_footer","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[],"class_list":["post-2663","post","type-post","status-publish","format-standard","hentry","category-projects"],"_links":{"self":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts\/2663","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/users\/19"}],"replies":[{"embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2663"}],"version-history":[{"count":3,"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts\/2663\/revisions"}],"predecessor-version":[{"id":2668,"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts\/2663\/revisions\/2668"}],"wp:attachment":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}