Scholarlink

<p>We optimize the running time of the primal-dual algorithms by optimizing their stopping criteria for solving convex optimization problems under affine equality constraints, which means terminating the algorithm earlier with fewer iterations. We study the relations between four stopping criteria and show under which conditions they are accurate to detect optimal solutions. The uncomputable one: <i>"Optimality gap and Feasibility error"</i>, and the computable ones: the <i>"Karush–Kuhn–Tucker error"</i>, the <i>"Projected Duality Gap"</i>, and the <i>"Smoothed Duality Gap"</i>. Assuming metric sub-regularity or quadratic error bound, we establish that all of the computable criteria provide practical upper bounds for the optimality gap, and approximate it effectively. Furthermore, we establish comparability between some of the computable criteria under certain conditions. Numerical experiments on basis pursuit, and quadratic programs with(out) non-negative weights corroborate these findings and show that the smoothed duality gap is more widely applicable than the rest.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The smoothed duality gap as a stopping criterion

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年5月24日

查看全文
  • Iyad Walwil,
  • Olivier Fercoq

摘要

We optimize the running time of the primal-dual algorithms by optimizing their stopping criteria for solving convex optimization problems under affine equality constraints, which means terminating the algorithm earlier with fewer iterations. We study the relations between four stopping criteria and show under which conditions they are accurate to detect optimal solutions. The uncomputable one: "Optimality gap and Feasibility error", and the computable ones: the "Karush–Kuhn–Tucker error", the "Projected Duality Gap", and the "Smoothed Duality Gap". Assuming metric sub-regularity or quadratic error bound, we establish that all of the computable criteria provide practical upper bounds for the optimality gap, and approximate it effectively. Furthermore, we establish comparability between some of the computable criteria under certain conditions. Numerical experiments on basis pursuit, and quadratic programs with(out) non-negative weights corroborate these findings and show that the smoothed duality gap is more widely applicable than the rest.