The method of steepest descent or following the gradient is only one of many methods for locating extrema (minima or maxima) of nonlinear functions. Before getting too complicated, you can simply try random points within the domain, keeping the most promising ones. Once you get close to a solution, steepest descent may work to tighten it up. You could even use a more systematic approach of splitting the domain into ever smaller parts, much like the quick sort algorithm. I often use Broyden's method or the Davidon-Fletcher-Powel method. Plus there are a variety of evolutionary methods. Send me A and b and I'll solve it for you. I wouldn't waste my time with MATLAB. My book on the subject is free today (4/14) https://www.amazon.com/dp/B07FL7JR1J The accompanying software is always free.

A few questions. What is A and what spaces does A act between? What is the functions space for x? It may be that you need to tighten up the formulation. Even after you do that, optimizations methods such as Gradient descent and Newton's method, only find critical points of the cost function. It may very well be that the cost function have more than one critical points. In which case the these methods will converge to the "closest" critical point. There is no guarantee that this will be the global min or max. You need to have a starting point that lies within the basin of attraction.

Truman is exactly right. It is not at all uncommon for nonlinear problems to have more than one local minimum or maximum, which may lie surprisingly far from the global extremum. The Web is full of interesting plots showing complex residual functions in multi-colors. My book on complex variables is free on next Wednesday (4/29) https://www.amazon.com/dp/B07MW6782P If A is some nxn square matrix and x is nx1 you can easily implement the problem in C++. Microsoft's complex "container" is a real mess, so I wrote my own that works fine.

Dear Nima Saliani

Norms kill imaginary parts.

So where is your problem?

Regards

You may have moved on but someone else reading this post may need a solution for a similar problem. I have made up a problem to illustrate how to minimize(|Ax-b|+|x|), where A is a 2x2 complex matrix and b and x are 2x1 complex vectors. Because each element of x has a real and imaginary part, this problem has 4 degrees of freedom. This is perhaps the least efficient solution but it serves to illustrate how to accomplish a more elegant solution, such as steepest descent. I create a residual function using A, b, and x. I then step through one million sets of 4 random values, which takes no more than a second. This finds an approximate solution. I then iteratively and sequentially refine the solution for each of the 4 elements of x using Brent's method. The whole process takes about 2 seconds. Everything is in the attached zip file, including the output and a batch file to compile the code.

Have you solved this problem? Nima Saliani