Existence of (sequential) feasible direction

In summary: Oh, I see now. I had a look at the chapter, and indeed: it seems that the author has not yet reached the point where he can apply the definitions he has given to prove the desired properties of critical points. (In particular, he has not yet proved that ##X## is a convex set.)My impression is that the author is working up to making the statement "if ##X## is convex and ##x^{\ast}## is a local minimum of ##f## on ##X##, then the directional derivative of ##f## at ##x^{\ast}## vanishes in all directions ##h \in \mathbb{R}^n## that are sequentially feasible at ##x^{\ast}
  • #1
nuuskur
Science Advisor
857
910
Having trouble with something that's likely too trivial, but here goes..

In Optimization theory and nonlinear programming [Sun, Yuan] the following is discussed at section 8.2.

Consider the optimisation of [itex]f:\mathbb R^n\to\mathbb R[/itex] with constraints [itex]g_j:\mathbb R^n\to\mathbb R, g_j(x) = 0, j=1,\ldots , m[/itex].

A feasible set [itex]X[/itex] is a subset of [itex]\mathbb R^n[/itex] which contains all those points that satisfy the system of constraints. The following definition is given.

A feasible direction at [itex]x^*\in X[/itex] is a straight line section containing [itex]x^*[/itex] that consists of ONLY feasible points. Formally, there exists a direction [itex]h\in\mathbb R^n\setminus\{0\}[/itex] (may assume to be normed) with
[tex]
\exists \delta >0, \forall \eta (0\leq \eta\leq \delta \implies x^* + \eta h\in X)
[/tex]
Only this definition is given, so one naturally asks, do such feasible directions even exist, in general?

Further development is done via the language of sequences.
Call a direction [itex]h\neq 0[/itex] to be a sequential feasible direction at [itex]x^*\in X[/itex] if there exist sequences [itex]h_k\to h[/itex] such that for every vanishing sequence [itex]\eta _k >0[/itex] it holds that [itex]x^* + \eta_k h_k\in X[/itex].
Evidently, the sequence converges to [itex]x^*[/itex], but the following is problematic for me.
Set [itex]x_k := x^* + \eta_kh_k[/itex]. If we set [itex]\eta _k := \|x_k-x^*\|[/itex] then
[tex]
\frac{x_k-x^*}{\|x_k-x^*\|} \xrightarrow[k\to\infty]{} h?!\tag{E}
[/tex]
What I understand is that we have a sequence of normed elements, so if it converges to anything, the limit has to be nonzero, but why does it converge?

Let's give some context. Suppose [itex]x^*\in X[/itex] is not a local maximum point (subject to said constraints), then by definition
[tex]
\forall k\in\mathbb N,\exists x_k\in X : \|x^*-x_k\|\leq \frac{1}{k}\quad \&\quad f(x_*) < f(x_k)
[/tex]
So, we can construct a sequence of feasible points that converges to [itex]x^*[/itex]. May we assume without loss of generality, this sequence has a limiting direction? More formally, if we write [itex]x_k = x^* + \eta_ kh_k, k\in\mathbb N[/itex], may we assume [itex]\exists \lim _k h_k\in\mathbb R ^n\setminus\{0\}[/itex]?

So, like I said, probably something trivial, but I really don't understand why we may assume the argument that culminates in (E).
 
  • Like
Likes S.G. Janssens
Mathematics news on Phys.org
  • #2
nuuskur said:
Only this definition is given, so one naturally asks, do such feasible directions even exist, in general?
No, at the level of generality of your presentation, I do not see why they should exist. What excludes the possibility of ##X## being a finite set?
nuuskur said:
Further development is done via the language of sequences.
Call a direction [itex]h\neq 0[/itex] to be a sequential feasible direction at [itex]x^*\in X[/itex] if there exist sequences [itex]h_k\to h[/itex] such that for every vanishing sequence [itex]\eta _k >0[/itex] it holds that [itex]x^* + \eta_k h_k\in X[/itex].
Evidently, the sequence converges to [itex]x^*[/itex], but the following is problematic for me.
Set [itex]x_k := x^* + \eta_kh_k[/itex]. If we set [itex]\eta _k := \|x_k-x^*\|[/itex] then
Sorry, but this confuses me. You took ##(\eta_k)_k## to be a vanishing sequence (of real numbers), then used it to define ##x_k##, but now you use ##x_k## in turn to define ##\eta_k##? Could you perhaps clarify this?

Without this (unnecessary?) re-definition, I would imagine that (E) follows because
$$
\frac{x_k - x^{\ast}}{\|x_k - x^{\ast}\|} = \frac{\eta_k}{|\eta_k|}\frac{h_k}{\|h_k\|} = \frac{h_k}{\|h_k\|} \to \frac{h}{\|h\|} = h,
$$
where it was used that ##\eta_k > 0## and ##h## is normalized.
 
Last edited:
  • Like
Likes nuuskur
  • #3
Right, but it assumes ##h_k\to h ##. For the example I've given about the maximal point, I'd like to explicitly show which direction is sequentially feasible. So far, all I've seen in the chapter is a slew of definitions, but there's no lemma or proposition of the form "a (sequentially) feasible direction exists".

I'm kind of getting the vibe as in algebra - we describe a structure with a whole number of properties, prove a lot of equivalent statements and then when it comes to exhibiting examples of said structure, we're left empty-handed.
 
  • #4
nuuskur said:
Right, but it assumes ##h_k\to h ##.
Indeed. What I did is: I read your definition of ##h \neq 0## being a sequentially feasible direction at ##x^{\ast} \in X##. So, I took the involved sequence ##(h_k)## that the definition assumes exists and converges to ##h##. Then I picked an arbitrary vanishing sequence ##(\eta_k)## of positive numbers and checked that the sequence ##(x_k)## defined in terms of ##(h_k)## and ##(\eta_k)## has the behavior (E).

At this point, we are just verifying a simple consequence of the definition of "sequential feasibility". Does this clarify how (E) is obtained from the definition?
nuuskur said:
For the example I've given about the maximal point, I'd like to explicitly show which direction is sequentially feasible.

Ok, let's return to your example in your first post. (I did not comment on it before, because I thought your issue was mainly with (E).)
nuuskur said:
Let's give some context. Suppose [itex]x^*\in X[/itex] is not a local maximum point (subject to said constraints), then by definition
[tex]
\forall k\in\mathbb N,\exists x_k\in X : \|x^*-x_k\|\leq \frac{1}{k}\quad \&\quad f(x_*) < f(x_k)
[/tex]
So, we can construct a sequence of feasible points that converges to [itex]x^*[/itex].
Yes, that looks correct.
nuuskur said:
May we assume without loss of generality, this sequence has a limiting direction? More formally, if we write [itex]x_k = x^* + \eta_ kh_k, k\in\mathbb N[/itex], may we assume [itex]\exists \lim _k h_k\in\mathbb R ^n\setminus\{0\}[/itex]?
Sorry if I am slow, but I am confused again. Where do the ##h_k## and ##\eta_k## come from? I thought they are provided by the definition of "sequential feasibility", together with the direction ##h## itself. Also, it seems to me that this definition as such does not make any reference to extrema.

For me, the intuition behind the definitions is as follows. In order to solve local optimization problems, we need a way to compare points ##x^{\ast}## to other points nearby. Ideally, in a sense, we would want to be able to approach ##x^{\ast}## in a continuous fashion from all directions, but this requires ##x^{\ast}## to be an interior point of ##X##.

Depending on the constraints that define ##X##, this may not be possible. For example, ##X## may have corners (such that it is only possible to approach corner points from within ##X## along certain directions, but not along others) or ##X## may be a discrete set. I believe that your two definitions ("feasible" and "sequentially feasible") cater for such cases, respectively.
nuuskur said:
So far, all I've seen in the chapter is a slew of definitions, but there's no lemma or proposition of the form "a (sequentially) feasible direction exists".
One trivial way in which (sequentially) feasible directions exist at any point of ##X##, is of course when ##X## is open. On a more interesting level, I do expect your book (which I unfortunately do not know myself) to formulate certain conditions on the constraints ##g_j## that ensure such existence. Maybe it will still come in a later section?
nuuskur said:
I'm kind of getting the vibe as in algebra - we describe a structure with a whole number of properties, prove a lot of equivalent statements and then when it comes to exhibiting examples of said structure, we're left empty-handed.
Yes, I know that feeling, although I think that (what I consider) good abstract algebra study books motivate the definitions and properties from the examples, not the other way around. (For monographs or encyclopedic works it may be different, of course.)
 
  • Like
Likes nuuskur
  • #5
Krylov said:
Where do the ##h_k## and ##\eta_k## come from?
When we pick a sequence that violates the maximum condition, we can write every sequence element as a sum [itex]x^* +\eta _kh_k[/itex], where [itex]\eta _k >0[/itex] is vanishing and wo.l.o.g [itex]\|h_k\|=1[/itex]. Simply put, the vector ##h_k ## points at the direction where ##x_k## is taken from and the scalar ##\eta_k## scales ##h_k## appropriately.

If [itex]X[/itex] is open, or, at the very least, for some [itex]\delta >0[/itex] [itex]B(x^*,\delta)\subseteq X[/itex], then we can of course pick an arbitrary straight line section and obviously it also provides a sequentially feasible direction, but then does the non-interior point case become something vacuous?

For instance, if [itex]x^*[/itex] is isolated, formally, for some [itex]\delta >0, B(x^*,\delta)\cap X = \{x^*\}[/itex], does [itex]x^*[/itex] automatically become a constrained extremum point?

What happens if it's not an interior point, but, say, an accumulation point i.e there exist sequences of ##X ## that converge to it. So let ##x_k\to x^* ##. Write every ##x_k = x^* +\eta_kh_k \in X## for reasons mentioned earlier. Is it safe to assume the sequence of directions ##h_k ## converges?

I've tried exhibiting some trivial counter-examples. For instance in 2-dimensional case, suppose ##x^* = 0 ## and we can set [itex]x_k = \frac{((-1)^k,0)}{2^k}[/itex], that means the sequence itself converges, but the sequence of directions keeps oscillating, but we can extract a converging subsequence (constant actually) of directions, so that doesn't work.

*lightbulb moment*

We are picking directions in a compact set (the unit sphere). We can immediately extract a converging subsequence, consequently a nonzero sequentially feasible direction.

As said, probably too trivial, which it is :sorry:
 
Last edited:
  • Like
Likes S.G. Janssens
  • #6
nuuskur said:
When we pick a sequence that violates the maximum condition, we can write every sequence element as a sum [itex]x^* +\eta _kh_k[/itex], where [itex]\eta _k >0[/itex] is vanishing and wo.l.o.g [itex]\|h_k\|=1[/itex]. Simply put, the vector ##h_k ## points at the direction where ##x_k## is taken from and the scalar ##\eta_k## scales ##h_k## appropriately.

Ok, now I understand what you meant earlier, thank you.
nuuskur said:
*lightbulb moment*

We are picking directions in a compact set (the unit sphere). We can immediately extract a converging subsequence, consequently a nonzero sequentially feasible direction.

As said, probably too trivial, which it is :sorry:

I don't find it that trivial. Sorry for insisting, what you do here is that you start with a sequence ##(x_k)## converging to ##x^{\ast}## and then you define ##(h_k)## and ##(\eta_k)## using ##(x_k)##. Finally, you use compactness to extract a (sub)sequence ##(h_k)## converging to a unit vector ##h##.

Now, I take it that this ##h## should then be a sequentially feasible direction at ##x^{\ast}##. However - if you want to check your definition of sequential feasibility - you would still need to prove that for every vanishing positive sequence ##(\eta_k)## (not necessarily the same sequence that you used to get to ##h## in post #5) the points ##x^{\ast} + \eta_k h_k## all lie in ##X## (are all feasible).
 
  • #7
In addition, here are some trivial counterexamples to show that - at least at the great level of generality of your OP - sequentially feasible directions may not exist for any point of ##X##.

1. ##X## is a finite set.
2. ##X = \mathbb{Q}##.

(For 2, select any rational ##x^{\ast}## and let ##(h_k)## be a normalized sequence in ##\mathbb{R}## converging to ##h = \pm 1##. Then ##h_k = 1## or ##h_k = -1## identically, beyond any sufficiently large ##k##. Let ##(\eta_k)## be a vanishing sequence of positive, irrational numbers. Then ##x^{\ast} + \eta_k h_k = x^{\ast} \pm \eta_k## for ##k## sufficiently large, and this is not in ##X##.)

I really don't think that there is a problem, though: It seems to me that the authors of your book have continuous optimization in mind, and I think the definitions that you gave are chosen on that basis.
 
  • Like
Likes nuuskur
  • #8
Krylov said:
I really don't think that there is a problem, though: It seems to me that the authors of your book have continuous optimization in mind, and I think the definitions that you gave are chosen on that basis.
My mistake. Not only continuous, but even continuously (twice) differentiable.
 
  • Like
Likes S.G. Janssens
  • #9
nuuskur said:
My mistake. Not only continuous, but even continuously (twice) differentiable.

Ok, very good. Let's review your earlier sequential definition:
nuuskur said:
Call a direction [itex]h\neq 0[/itex] to be a sequential feasible direction at [itex]x^*\in X[/itex] if there exist sequences [itex]h_k\to h[/itex] such that for every vanishing sequence [itex]\eta _k >0[/itex] it holds that [itex]x^* + \eta_k h_k\in X[/itex].
From what you wrote afterwards, we also assume that ##h## and the ##h_k## are normalized. I also think that after "it holds that..." it is probably meant to write "eventually" (i.e. for ##k## large enough).

Related to what I said at the end of post #6,
Krylov said:
Now, I take it that this ##h## should then be a sequentially feasible direction at ##x^{\ast}##. However - if you want to check your definition of sequential feasibility - you would still need to prove that for every vanishing positive sequence ##(\eta_k)## (not necessarily the same sequence that you used to get to ##h## in post #5) the points ##x^{\ast} + \eta_k h_k## all lie in ##X## (are all feasible).

you could consider the following.

If the ##g_j## are linear functionals such that the hyperplanes defined by them intersect nontrivially, then every point in ##X## admits a feasible direction, so it certainly admits a sequentially feasible direction.

If we admit nonlinear functionals, then I think it gets more complicated. As an example, take ##\mathbb{R}^2## with the single constraint ##g(x) = \|x\|^2 - 1##, so ##X## is just the unit sphere. Take a point ##x^{\ast} \in X## and let ##h## be a normalized direction, so in fact ##h \in X## as well. Consider a sequence ##(h_k)## of normalized vectors such that ##h_k \to h##. For every positive and sufficiently small ##\eta_k## the vector ##x^{\ast} + \eta_k h_k## lies outside the unit sphere, so outside ##X##. Therefore ##x^{\ast}## does not have a sequentially feasible direction.

Are you definitions aimed at problems with linear equality (and perhaps inequality) constraints?
 
  • #10
Constraints are usually sufficiently smooth, say, once or twice continuously differentiable. In the general case, yes, inequality constraints can also be considered, but I'm trying to work my way through constraints with equalities for now.
 
  • #11
nuuskur said:
Constraints are usually sufficiently smooth, say, once or twice continuously differentiable.
Ok, but the nonlinear example of ##g## in post #9 satisfies that requirement, so it makes me wonder (maybe like you?) what good the definition of a (sequentially) feasible direction from your book does in the context of smooth, non-linear constraints.

(You could add the requirement that the ##g_1,\ldots,g_m## define an ##(n - m)## dimensional smooth manifold (i.e. additionally require that the derivative of ##x \mapsto (g_1(x), \ldots, g_m(x))## has maximal rank ##m## at each point), but that does not seem to help, as the same example shows.)
 

1. What is a sequential feasible direction?

A sequential feasible direction is a vector in the feasible region of a problem that can be used to improve the objective function at each iteration of an optimization algorithm. It is a direction that satisfies the constraints of the problem and leads to a better solution.

2. How is the existence of sequential feasible direction determined?

The existence of sequential feasible direction is determined by checking if the constraints of the problem are satisfied at each iteration of the optimization algorithm. If a direction is found that satisfies the constraints and leads to a better solution, then a sequential feasible direction exists.

3. What is the significance of the existence of sequential feasible direction?

The existence of sequential feasible direction is important in optimization algorithms because it guarantees that the algorithm will converge to a feasible and optimal solution. Without a sequential feasible direction, the algorithm may get stuck at a non-feasible or non-optimal solution.

4. Can the existence of sequential feasible direction be proved?

Yes, the existence of sequential feasible direction can be proved using mathematical optimization theory and techniques such as convexity and duality. These proofs ensure that the algorithm will always have a feasible direction to move towards a better solution.

5. What happens if a problem does not have a sequential feasible direction?

If a problem does not have a sequential feasible direction, it means that the constraints are too restrictive and there is no feasible direction that can improve the objective function. In this case, the problem may be infeasible and the optimization algorithm will not be able to find a solution.

Similar threads

Replies
7
Views
1K
  • General Math
Replies
21
Views
3K
  • General Math
Replies
13
Views
7K
Replies
1
Views
2K
Replies
7
Views
2K
Replies
5
Views
221
  • Calculus and Beyond Homework Help
Replies
13
Views
882
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
26
Views
804
  • General Math
Replies
1
Views
1K
Back
Top