0
$\begingroup$

I have a professor in optimization class who says that, in the interior point method, we of course cannot use the gradient to determine that we are at the minimum point. This is because the problem is constrained by $Ax=b$.

Instead, we use the fact that "being at the minimum implies the weaker condition that the gradient of the objective function is perpendicular to the constraints $Ax=b$".

I'm having trouble following that reasoning...as I can think of many LP problems where the gradient is not perpendicular to the constraints at the minimizer. How is this true?

$\endgroup$
  • 1
    $\begingroup$ Can you be more specific about the type of problem you are considering, and what the interior point method is? $\endgroup$ – Chappers Jun 2 '17 at 15:35
  • 1
    $\begingroup$ Very (I mean very!) broadly speaking, many unconstrained gradient based algorithms can handle convex constraints by projecting the gradient on to the constraint set. In the case of an affine set like $\{x | Ax=b\}$ this means projecting the gradient (perpendicularly) on to this set. Hence at an optimum the projected gradient will be zero, which is tantamount to the gradient being perpendicular to the constraint (or the tangent space thereof). $\endgroup$ – copper.hat Jun 2 '17 at 16:31
  • $\begingroup$ This is similar to what I am getting at: youtube.com/watch?v=78sNnf3pOYs around minutes 28 to 30 $\endgroup$ – jaja Jun 4 '17 at 2:44
2
$\begingroup$

I'm not sure you're claim is accurate. In any case, what we know in general is this: Given a function $f: \mathcal H \rightarrow (-\infty,+\infty]$, recall the definition of its sub-differential at a point $x \in \mathcal H$, namely

$$ \partial f(x) := \{v \in \mathcal H | f(z) \ge f(x) + v^T(z-x)\}. $$ An element of $\partial f(x)$ is called a sub-gradient of $f$ at $x$. The following classical result is immediate. Viz,

First-order optimality condition: $x^* \in \text{argmin }f \iff 0 \in \partial f(x^*).$

Now, minimizing $h(x)$ subject to $x \in C$ is equivalent to minimizing $\;f(x):= h(x) + i_C(x)$ without any constraints. Thus,

$$ \begin{split} x^* \in \text{argmin }h|_{\mathcal C} &\iff x^* \in \text{argmin }h + i_{\mathcal C} \iff 0 \in \partial (h + i_{\mathcal C}) \iff -\nabla h(x^*) \in \partial i_{\mathcal C} \\ &\iff \langle \nabla h(x^*), z - x^*\rangle \ge 0\; \forall z \in \mathcal C, \end{split} $$ which gives something which roughly amounts to your claim, when the constraint set $\mathcal C$ is affine.

N.B.: $i_C$ denotes the indicator function of $C$ defined by $i_C(x)= 0$ if $x \in C$ and $i_C(x) = \infty$ otherwise.

$\endgroup$
  • $\begingroup$ hm. i see thanks for this.... $\endgroup$ – jaja Jun 4 '17 at 0:29
  • $\begingroup$ can you please break this down for me a little more specifically? For example, what is $i_c(x)$? Also, for this to be totally convincing, you would have to prove that "minimizing $h(x)$ subject to $x \in C$ is equivalent to minimizing $f(x):=h(x)+i_c(x)$ without any constraints". $\endgroup$ – jaja Apr 8 '18 at 1:03
  • 1
    $\begingroup$ $i_C$ is the indicator function of $C$ defined by $i_C(x)= 0$ if $x \in C$ and $i_C(x) = \infty$ otherwise. With this understanding, your other questions have trivial answers. Right ? $\endgroup$ – dohmatob Apr 8 '18 at 11:15
  • $\begingroup$ I'm sorry...still having a little bit of trouble (excuse my brain please). Is sub-gradient the same as $\nabla$ here? I'm also wondering if instead of $0 \in \partial (h+i_c) \iff - \nabla h(x^*) \in \partial i_c$ I can write $0 = \nabla (h+i_c) \iff - \nabla h(x^*) = \partial i_c$ ? $\endgroup$ – jaja Apr 8 '18 at 14:31
  • 1
    $\begingroup$ First, $\partial f(x)$ is a set, which is always defined whether $f$ is differentiable at $x$ or not. $\nabla f$ doesn't always make sense. For example: $\nabla i_C(x)$ doesn't make sense, as $i_C$ is not diff'ble. However, if $f$ is differentiable at $x$, then $\partial f(x) = \{\nabla f(x)\}$. Second, under some special conditions (relative interior qualification), the subdifferential of a sum of 2 functions is the sum set of their subdifferentials. Lookup subdifferentlal. $\endgroup$ – dohmatob Apr 8 '18 at 14:49
1
$\begingroup$

I believe a more precise term would be the gradient is perpendicular to a supporting hyperplane of the feasible set.

When the feasible set is a smooth manifold (without "corners"), then the supporting hyperplane is a tangent and in this case the gradient is indeed perpendicular.

When the feasible set has a corner, there are many supporting hyperplanes. For example, basic feasible solutions in LP problems are "corners", and thus at the optimum the objective gradient is perpendicular to one of the infinite set of supporting hyperplanes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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