2
$\begingroup$

Consider the following optimization problem \begin{align} \min_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad&h_i(x) = 0,\,i=1,\ldots,m\\ \nonumber \quad&x\in X\subseteq\mathbb{R}^n \end{align}

Also define the Lagrangian as $$\mathcal{L}(x,\lambda) = f(x) + \lambda^\top h(x)$$ where $h(x) = (h_1(x),\ldots,h_m(x))$ and $\lambda$ are (unconstrained) dual variables. Let us construct the dual function as \begin{align} \phi(\lambda) = \min_{x\in X}\mathcal{L}(x,\lambda) \end{align}

It is known (see Thm 6.3.3 in Bazaraa, Sherali, Shetty - Nonlinear programming: theory and algorithms) that if $X$ is nonempty and compact, $f,h$ are continuous, and, given $\bar\lambda\in\mathbb{R}^m$, the set $X(\bar\lambda) = \{y:y\text{ minimizes } f(x) + \bar\lambda^\top h(x)\text{ over }x\in X \}=\{\bar x\}$ (is a singleton) then the dual function is differentiable at $\bar\lambda$ with gradient (denoting $\bar x$ by $x(\bar\lambda)$) \begin{align} \nabla \phi(\bar\lambda)=h(x(\bar\lambda)) \end{align} Furthermore, the Hessian of the dual function is (not necessarily true, see the edit at the bottom of this post) \begin{align} \nabla^2\phi(\bar\lambda) = -\nabla h(x(\bar\lambda))\left(\nabla^2 \mathcal{L}(x(\bar\lambda),\bar\lambda)\right)^{-1}\nabla h(x(\bar\lambda))^\top \end{align}

Question: I am wondering under what conditions is the dual function self-concordant? The definition of self-concordance is as follows,

Def'n (Self-concordance): Let $\Omega\subseteq\mathbb{R}^n$ be a convex open set. Then a three-times continuously differentiable function $f:\Omega\to\mathbb{R}$ is said to be $\kappa$-self-concordant if \begin{align} [\nabla^3f(x)(h,h,h)] \le 2\kappa(\nabla^2f(x)(h,h))^{3/2} \end{align} for all $h\in\mathbb{R}^n$, $x\in\Omega$.

Determining if the dual function is self-concordant would first involve finding the tensor $\nabla^3\phi(\lambda)$ -- something that I am not sure how to do.

Would it be possible to show self-concordance of the dual function under some smoothness and convexity conditions of the functions in the original problem?


EDIT: I have come to discover that the expression $\nabla^2\phi(\bar\lambda) = -\nabla h(x(\bar\lambda))\left(\nabla^2 \mathcal{L}(x(\bar\lambda),\bar\lambda)\right)^{-1}\nabla h(x(\bar\lambda))^\top$ is not necessarily true due to the existence of the constraint set $x\in X$. This set causes the dual Hessian to exhibit discontinuities along manifolds in the dual space. I suppose this answers my question: with existence of constraints of the form $x\in X$ (where $X$ is compact) the dual function is not twice-continuously differentiable (and therefore not three-times continuously differentiable) and it cannot be self-concordant.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .