Optimization of non-smooth convex function in a polytope

Question

We know that accelerated proximal gradient descent method can be applied to solve the following convex programming problem: $$\min{f(x)+g(x)}$$ where $f$ is smooth and convex, and $g$ is a non-smooth convex function such as $|x|$, whose proximal operator is easy to calculate.

However, is there an algorithm that can solve $$\min f(x)+g(x)$$ $$\text{s.t. } Ax \leq b? $$

I have tried to formulate this problem as $$\min f(x) + g(x) + h(x)$$ with $h(x) = \chi_{\{Ax\leq b\}}$, the proximal operator is hard to be represented;

I also tried to use inner point method to solve this problem, but because the value of the penalized objective go to infinity when $x$ is close to the boundary of the feasible region, the function is no longer has Lipschitz derivative, and it looks like that there is no step size that can guarantee the convergence.

Answer 1

You could dualize the $h$ to get a saddle point problem. To be specific: Write $h(x) = H(Ax)$ with $H(y) = I_{\cdot\leq b}(y)$ and write $H(Ax) = \sup_y (Ax)^Ty - H^*(y)$. The resulting saddle point problem (min over $x$ max over $y$) could be solved by several primal-dual methods, e.g. the one by Condat (similar to the one by Pock and myself) which uses a primal proximal-gradiet step and a dual prox step).

Answer 2

A good survey may be found here: www.mat.univie.ac.at/~herman/skripten/NCO_OSGA.pdf (M Ahookosh, 2017)