I have an optimization problem where i need to find an image x, that is very close to x' such that:

  1. monitor(x') is valid but monitor(x) is invalid. (output is valid when the neural network output is inside bounds of specific box).

  2. x is same classified as x' by a neural network(their prediction class is the same).

Note that x is an image with (1,28,28,1) dimension and its transformed to an array with dim 784 in order to pass into a scipy solver.

The optimization problem is represented as follows:

Obj function: minimize L2 norm of (x'- x) with constraints:

  1. prediction( transformed image of x) = prediction( transformed image of x')

  2. monitor(x) = 0 (0 for invalid)

x is the optimization variable to be found and x' is the valid input passed

So I am using scipy to solve my problem, I tried local optimization (COBYLA and SLSQP) and global optimization(Sgho and differential evolution). I think my problem is non linear and non convex according to my constraints. But some resources pointed out that non convex constraints don't necessarily mean non convex problem.

I read in: https://www.researchgate.net/post/Identify-if-optimization-problem-is-convex-or-non-convex

"Depending on the problem, you may also try to solve it with a solver which give you just a local optimum if the problem is non convex (as ipopt, or bonmin if you have integer variables) and then compare the solution with that of a global MINLP solver as Couenne/BARON/SCIP. If the results are very different the problem is probably non convex. It could also be that some solver gives you as output the information about the convexity of the problem, but I am not sure about that."

Actually, local and global optimization gave me different results, and sgho was performing the best out of all. However all aren't always converging to successful solutions, but sgho performs best. I think this is because of my non linear and non convex constraints.

Is my choice for Sgho and differential evolution good? and so my problem is considered non convex right?

  • $\begingroup$ The key question is what kind of functions prediction, transformed and monitor are. Your objective function is simple, but if these functions are complicated/nonlinear/non-convex/discontinuous, then the problem is difficult to solve. $\endgroup$ – Wolfgang Bangerth Feb 17 at 20:35
  • $\begingroup$ So is it in this case nonconvex? yes i think its too compicated especially when having an image of dim 28*28, its hard to converge $\endgroup$ – S i Feb 18 at 22:45
  • $\begingroup$ We don't know. If all of the three functions above are linear, then the problem is convex and easy. You really need to say more about what these functions are to know. $\endgroup$ – Wolfgang Bangerth Feb 19 at 16:09
  • $\begingroup$ monitor is a function that checks if the output at a certain layer of the neural network of x is between a box bound. Transformed is just reshaping an array of 28*28 dimension to a (1,28,28,1) dimension image. Prediction is the predicted label of the image, it is also predicted via a neural network $\endgroup$ – S i Feb 19 at 17:48
  • $\begingroup$ are they in this case linear? $\endgroup$ – S i Feb 22 at 8:44

Your Answer

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

Browse other questions tagged or ask your own question.