0
$\begingroup$

Somewhat based on: Reformulation of optimization problem using kkt and lagrange conditions

Say I have the following optimization problem: $$ \begin{aligned} \min_{z}\min_{y} \, &\frac{1}{2} y^T \bar{H}y,\\ &\begin{aligned} \text{s.t. } &\bar{E}y = 0,\\ &\bar{A}y \leq \bar{b} + \bar{d}z, \end{aligned} \end{aligned} $$ (with $y \in \mathbb{R}^{n}, z\in \{0,1\}^{2r},\bar{H}\in \mathbb{R}^{n\times n},\bar{E} \in \mathbb{R}^{m_1\times n},\bar{A}\in \mathbb{R}^{m_2\times n},\bar{b} \in \mathbb{R}^{m_2},\bar{d} \in \mathbb{R}^{m_2\times 2r}).$

Also, importantly, $\bar{H}$ is indefinite.

My goal is to reformulate the inner minimization problem over $y$ using the KKT conditions.

I am wondering under which circumstances the KKT conditions are actually first order necessary conditions. From my understanding and from what I gathered from my previous question (see link above), the minimum has to exist in order for the KKT conditions to be necessary. Thus, I would say that in the following cases they are indeed necessary:

  • $\bar{H}$ is semidefinite on the feasible set $\mathcal{F} = \left\{y \, \middle| \, \bar{E}y = 0 \, \land \, \bar{A}y \leq \bar{b} + \bar{d}z\right\}$
  • the feasible set $\mathcal{F}$ is bounded

Are there any other situations which I did not mention (assuming my findings are correct) under which I can apply the KKT conditions to the optimization problem at hand?

$\endgroup$
11
  • $\begingroup$ You might want to research on constraint qualification. $\endgroup$
    – user251257
    Aug 17, 2018 at 8:10
  • $\begingroup$ Thanks for your comment. As can be seen, e.g. my inequalty and equalty constraints are affine and according to wikipedia (en.wikipedia.org/wiki/…, this would suffice. But if you check the answer to my previous question, this does not necessarily mean that the KKT conditions are necessary if the minimum does not exist. $\endgroup$
    – VGD
    Aug 17, 2018 at 8:13
  • $\begingroup$ KKT is always necessary for a minimizer (assuming CQ and sufficient smoothness). Do you want to know, when KKT is sufficient? $\endgroup$
    – user251257
    Aug 17, 2018 at 8:22
  • $\begingroup$ Have you checked the answer of the question to which I provided the link? There, the CQ conditions are met, but the KKT conditions are not necessary conditions in the sense that the optimal point is not part of the solution set of the KKT conditions (as the minimum does not exist/is $-\infty$) $\endgroup$
    – VGD
    Aug 17, 2018 at 8:32
  • $\begingroup$ i wrote "assuming sufficient smoothness". Usually minimizer is continuous at best, but not differentiable. You need a non-smooth version of KKT, usually involving subgradient. $\endgroup$
    – user251257
    Aug 17, 2018 at 8:36

1 Answer 1

1
$\begingroup$

The constraints in your problem are affine linear, hence KKT conditions are necessary for local optimality. That is, every local minimum also satisfies the KKT conditions (together with appropriate multipliers). The KKT conditions do not tell you anything about the existence of minimizers.

Assume the inner problem has feasible points. Then it is solvable if and only if there exists no vector $v$ such that $v^THv<0$, $Ev=0$, and $Av\le 0$.

If there is such $v$, then clearly the function is unbounded on the feasible set: Take a feasible point $y$, define $y_t:= y + tv$. Then $y_t$ is feasible for all $t>0$, and $y_t^THy_t\to\infty$ for $t\to\infty$.

Conversely, assume the inner problem has no solution for some $z$. Then there is a sequence $(y_n)$ such that $y_n^THy_n\to-\infty$. Hence $y_n$ has to be unbounded. Set $v_n:= \|y_n\|^{-1}y_n$. Then $v_n\to v$ along a subsequence, and the limit $v$ satisfies $v^THv<0$, $Ev=0$, and $Av\le 0$.

$\endgroup$
4
  • $\begingroup$ Do you mean $Av\leq \bar{b}+\bar{d}z$? If not, I don't get it. $\endgroup$
    – VGD
    Aug 17, 2018 at 10:37
  • $\begingroup$ Also, isn't it also solvable if there is a vector $v$ from the feasible set for which $v^T\bar{H}v<0$ but the feasible set is bounded? Then there is a minimum, correct? $\endgroup$
    – VGD
    Aug 17, 2018 at 10:43
  • $\begingroup$ If the feasible set is bounded, then solutions exist. $\endgroup$
    – daw
    Aug 17, 2018 at 11:45
  • $\begingroup$ So did you intend to write $Av\leq0$ instead of $\bar{A}v\leq \bar{b}+\bar{d}z$? $\endgroup$
    – VGD
    Aug 17, 2018 at 13:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .