Discussion between Siong Thye Goh and a06e

Feeds

08:24

Let $x$ be $n$ dimensional. Let $S = \{-1, 1\}^n$, we can rewrite our optimization problem as follows: $$\min_{s \in S} \min _x \sum_i \lambda_i s_ix_i + \frac12x^TAx$$ subject to $$s_i x_i \ge 0, \forall i \in \{1, \ldots n\}$$ That is we can solve a quadratic programming problem in each orthant...

a06e

Let $x(s)$ be a solution to the inner convex minimization problem (with given $s$). If some coordinates vanish, $x_i(s)=0$, it does not necessarily follow that this $x(s)$ is a local minimum in the original problem. Do you agree? This is the point I'm missing (otherwise I agree with your answer).

Siong Thye Goh

ah, I misinterpreted your question as you are trying to find all global minimum. Hmm.... thanks for raising the good point. I haven't figured that part as well.

a06e

Regarding the optimality condition you wrote ... doesn't this assume that the objective function is convex? My objective function fails to be convex at the hyperplanes $x_i=0$ whenever the corresponding $\lambda_i<0$.

Siong Thye Goh

I think it is similar to the concept of stationary point. convexity is not required.

a06e

Yes, stationarity is ok. The problem is with the assumption that "stationarity" implies it is a local minimizer.

Siong Thye Goh

08:24

true, that is a good point.

a06e

On second thought I now believe your stationarity condition is actually sufficient for having a local minima.

Though I'm not sure how to (exhaustively) search for all solutions ...

Siong Thye Goh

if we go through each orthant, we would have found all the candidates right?

a06e

08:51

It seems to me one would need to search through all $3^N$ vectors $\mathbf{s}\in\{-1,0,+1\}^{N}$. So not just orthants

(Too bad LaTeX is not supported in this chat!)

Please take a look at the answer I have just posted: math.stackexchange.com/a/4910031/10063. I'm not sure if we can get around this somehow and do a faster search over 2^N orthants instead ...

Siong Thye Goh

09:46

my initial thought of using those conditions is to comb through 2^N region and use the condition that it is indeed a stationary point. I don't have a proof yet but I wonder if all solution found is a local minimum.

4 hours later…

Siong Thye Goh

13:23

I think a mystery that I haven't figure out is if $x$ is in two orthant, $O_1$ and $O_2$, and if $x$ is the optimal solution in $O_1$, is it optimal in $O_2$ as well?

a06e

13:36

Not sure what you mean by:

if $x$ is in two orthant, $O_1$ and $O_2$

?

Ah I think my answer fails because when $\lambda_i<0$, I can't do $\partial\lambda_{i}|x_{I}| \ne \lambda_{i}\partial|x_{I}|$

Ok I figured out what's missing. If $\lambda_i < 0$ then $x_i$ cannot be zero at a local minimum.

Siong Thye Goh

14:39

for example orthant 1 is x1>=0, x2>=0, x3>=0
orthant 2 is x1 <= 0, x2>=0, x3>=0

Suppose the optimal solution in orthant 1 is (0,0,3)
note that this point also resides in orthant 2. Now my question is is it also optimal in orthant 2?

I don't have a solution for that yet. but I think of another information that perhaps we can use.

if x resides in two orthant and it is optimal in orthant 1, suppose we find a better solution in orthant 2, then x is not a local minima

next day → last day (16 days later) »

all rooms