<p>We study a class of nonconvex optimization problems in which the feasible set is defined by the nonconvex <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\ell _{p}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation> ball, and the objective function is continuously differentiable. To tackle such structured problems, we propose a novel hybrid algorithm that combines the Frank-Wolfe method with the gradient projection method. The Frank-Wolfe step is amenable to a closed-form solution, while the gradient projection step can be efficiently performed in a reduced subspace. We prove the global convergence of the proposed algorithm and establish a worst-case convergence rate of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(O(1/\sqrt{k})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msqrt> <mi>k</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in terms of the optimality error under reasonable assumptions. Numerical experiments demonstrate the practicality and efficiency of our proposed algorithm compared with existing cutting-edge methods.</p>

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

Minimization Over the \(\ell _{p}\) Ball Using A Hybrid First-Order Method

  • Xiangyu Yang,
  • Hao Wang,
  • Yichen Zhu,
  • Xiao Wang

摘要

We study a class of nonconvex optimization problems in which the feasible set is defined by the nonconvex \(\ell _{p}\) p ball, and the objective function is continuously differentiable. To tackle such structured problems, we propose a novel hybrid algorithm that combines the Frank-Wolfe method with the gradient projection method. The Frank-Wolfe step is amenable to a closed-form solution, while the gradient projection step can be efficiently performed in a reduced subspace. We prove the global convergence of the proposed algorithm and establish a worst-case convergence rate of \(O(1/\sqrt{k})\) O ( 1 / k ) in terms of the optimality error under reasonable assumptions. Numerical experiments demonstrate the practicality and efficiency of our proposed algorithm compared with existing cutting-edge methods.