1
$\begingroup$

The problem is as follows:

$\max_x f(x) \enspace , \enspace \text{s.t.} \enspace g(x) \leq \alpha $

We can not assume that either $f$ nor $g$ are convex, on the contrary - we can assume they are strictly non-convex.

The functions are unknown, but we have access to the values and gradient (e.g. given an $x$ we know what $f(x), \nabla f(x)$ are). We solve this using gradient descent.

We can assume that:

  1. $f$ and $g$ are bounded.
  2. $f$ and $g$ are differentiable and Lipschitz.

The question is - what additional assumptions are required from $f$ and $g$ such that convergence to a feasible solution $g(x^*) \leq \alpha$ is ensured? I was thinking something along the lines of:

  1. every local minima of $g$ is a feasible solution.

Is there any weaker assumption than (3) that may ensure convergence? are you aware of previous works which tackled such a problem (I believe someone has, yet I have yet to find it) and may have talked about this?

I am grateful for any help given!

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ These are far from minimal requirements. I suppose the answer must depend on exactly what you mean by a "gradient algorithm." For instance, what will your algorithm do upon encountering (or crossing) the boundary? And what exactly do you mean by "gradient (first order)" for a function that, although Lipschitz continuous, might fail to be differentiable? And surely you don't intend to impose any conditions on $g$ except in a neighborhood of the set $g(x)=\alpha,$ right? Likewise, is there any point to imposing requirements on $f$ outside the region $g(x)\le\alpha$? $\endgroup$
    – whuber ♦
    Commented Sep 21, 2018 at 12:20
  • 1
    $\begingroup$ Sorry, I didn't phrase the problem properly, what I mean is that we can assume the functions are continuous, bounded. I assume we also require Lipschitz and something along the lines of 3. $\endgroup$
    – Chen
    Commented Sep 21, 2018 at 13:32
  • 2
    $\begingroup$ Please try to refine and narrow your question. As it stands it is very broad and admits many different answers. Could you tell us what problem in statistics or machine learning you are trying to solve? That might narrow the scope sufficiently. $\endgroup$
    – whuber ♦
    Commented Sep 21, 2018 at 13:34
  • $\begingroup$ Refined the question. The question is in machine learning, given parameters $x$ of the network you know $f(x), \nabla f(x), g(x), \nabla g(x)$. A gradient descent algorithm for example is to use Lagrange multipliers method with a 2 timescale scheme ($\lambda$ is updated slowly as opposed to $x$). The question is essentially: what properties must $g$ possess in order to ensure that from any starting point $x_0$ the algorithm will converge to a feasible solution. $\endgroup$
    – Chen
    Commented Sep 21, 2018 at 13:46
  • $\begingroup$ I am puzzled why you are focused on $g,$ since the properties of $f$ are just as important. Are there perhaps typographical errors in your question, such as switching the roles of $f$ and $g$ in some places? $\endgroup$
    – whuber ♦
    Commented Sep 21, 2018 at 14:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.