Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '10 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 '10 at 5:16

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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 '10 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 '10 at 20:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.