## Lipschitz properties of minima/minimizers of convex functions of two variables

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Suppose I have a function $f(x,y)$ from $\mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ that is convex in both $x$ and $y$. Set

$g(y) = \min_{x} f(x,y)$

What I would like is for $g(y)$ to be Lipschitz:

$|g(y) - g(y')| \le c \cdot \| y - y' \|$

Unfortunately, $f(x,y)$ may have a very poor Lipschitz constant for general $x$. Are there general conditions on $f$ for which the minima are Lipschitz?

Alternatively, when can we say the minimizer $x^{\ast}(y) = \arg \min_x f(x,y)$ is Lipschitz in $y$?

I've tried looking in a few convex optimization books for answers, but no luck.

-

At least for "the" minimizer $x^*(y)$ the situation can be complicated: Consider something like $f(x,y) = \max(|x|-y,0)$. Here $x^*(0)=0$ but for $y<0$, the set of minimizers is an interval. – Dirk Nov 5 2010 at 4:45
I'm perfectly willing to assume strict convexity (or even strong convexity).  In the end I'm interested in "for what kinds of functions can we expect the minimizer (or minimum value) to have small Lipschitz constant."  I have a particular function in mind for an application, but this problem seemed more general so I thought I would ask it here. – Anand Sarwate Nov 5 2010 at 5:16

## 1 Answer

I encountered the same problem three years ago and found some relevant literature. Here are a few. See also the refs therein.

Lipschitz Behavior of Solutions to Convex Minimization Problems. Jean-Pierre Aubin, Mathematics of Operations Research, Vol. 9, No. 1. (Feb., 1984), pp. 87-111.

Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. O. L. MANGASARIAN and T.-H. SHIAU. SIAM J. CONTROL AND OPTIMIZATION, 25(3), 1987.

Lipschitz Continuity of Solutions of Variational Inequalities with a Parametric Polyhedral Constraint. N. D. Yen, Mathematics of Operations Research, Vol. 20, No. 3. (Aug., 1995), pp. 695-708.

On Lipschitzian Stability of Optimal Solutions of Parametrized Semi-Infinite Programs. Alexander Shapiro, Mathematics of Operations Research, Vol. 19, No. 3. (Aug., 1994), pp. 743-752.

SHARP LIPSCHITZ CONSTANTS FOR BASIC OPTIMAL SOLUTIONS AND BASIC FEASIBLE SOLUTIONS OF LINEAR PROGRAMS. Wu Li, SIAM J. CONTROL AND OPTIMIZATION Vol. 32, No. I, pp. 140-153, January 1994

-

Thanks a bunch!  This is the direction I was missing before.  I don't know why "Lipschitz convex minimization" failed to find these references earlier.  Google has failed me. – Anand Sarwate Nov 6 2010 at 15:56
it is also related to those sensitivity analysis in convex optimization. see for example chap. 5 of luenberger's red book. – mr.gondolier Nov 6 2010 at 20:19
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8922713398933411, "perplexity_flag": "middle"}