5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Dirk
    Nov 5, 2010 at 4:45
  • $\begingroup$ 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. $\endgroup$ Nov 5, 2010 at 5:16

1 Answer 1

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 6, 2010 at 15:56
  • $\begingroup$ it is also related to those sensitivity analysis in convex optimization. see for example chap. 5 of luenberger's red book. $\endgroup$
    – gondolier
    Nov 6, 2010 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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