--- title: "FindMinimum" language: "en" type: "Symbol" summary: "FindMinimum[f, x] searches for a local minimum in f, starting from an automatically selected point. FindMinimum[f, {x, x0}] searches for a local minimum in f, starting from the point x = x0. FindMinimum[f, {{x, x0}, {y, y0}, ...}] searches for a local minimum in a function of several variables. FindMinimum[{f, cons}, {{x, x0}, {y, y0}, ...}] searches for a local minimum subject to the constraints cons. FindMinimum[{f, cons}, {x, y, ...}] starts from a point within the region defined by the constraints." keywords: - conjugate gradient - constrained local optimization - constrained optimization - convex programming - Gauss-Newton algorithm - GNA - gradient - gradient descent - interior point algorithm - Levenberg-Marquardt method - linear fractional programming - linear programming - local minimization - local optimization - minimization - Newton's method - numerical minimization - quadratic programming - quasi-Newton - steepest-descent - argmin - minpos - ConjugateGradient - LevenbergMarquardt - Newton - QuasiNewton - extrema - fminbnd - fminsearch canonical_url: "https://reference.wolfram.com/language/ref/FindMinimum.html" source: "Wolfram Language Documentation" related_guides: - title: "Optimization" link: "https://reference.wolfram.com/language/guide/Optimization.en.md" - title: "Discrete Mathematics" link: "https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md" - title: "Convex Optimization" link: "https://reference.wolfram.com/language/guide/ConvexOptimization.en.md" - title: "Solvers over Regions" link: "https://reference.wolfram.com/language/guide/GeometricSolvers.en.md" - title: "Scientific Models" link: "https://reference.wolfram.com/language/guide/ScientificModels.en.md" - title: "Graph Programming" link: "https://reference.wolfram.com/language/guide/GraphProgramming.en.md" - title: "Matrix Decompositions" link: "https://reference.wolfram.com/language/guide/MatrixDecompositions.en.md" - title: "Symbolic Vectors, Matrices and Arrays" link: "https://reference.wolfram.com/language/guide/SymbolicArrays.en.md" - title: "System Model Analytics & Design" link: "https://reference.wolfram.com/language/guide/SystemModelAnalyticsDesign.en.md" related_functions: - title: "FindMaximum" link: "https://reference.wolfram.com/language/ref/FindMaximum.en.md" - title: "NMinimize" link: "https://reference.wolfram.com/language/ref/NMinimize.en.md" - title: "Minimize" link: "https://reference.wolfram.com/language/ref/Minimize.en.md" - title: "FindArgMin" link: "https://reference.wolfram.com/language/ref/FindArgMin.en.md" - title: "FindMinValue" link: "https://reference.wolfram.com/language/ref/FindMinValue.en.md" - title: "FindFit" link: "https://reference.wolfram.com/language/ref/FindFit.en.md" - title: "FindRoot" link: "https://reference.wolfram.com/language/ref/FindRoot.en.md" - title: "Min" link: "https://reference.wolfram.com/language/ref/Min.en.md" - title: "LinearOptimization" link: "https://reference.wolfram.com/language/ref/LinearOptimization.en.md" - title: "ConvexOptimization" link: "https://reference.wolfram.com/language/ref/ConvexOptimization.en.md" - title: "GeometricOptimization" link: "https://reference.wolfram.com/language/ref/GeometricOptimization.en.md" - title: "D" link: "https://reference.wolfram.com/language/ref/D.en.md" - title: "BayesianMinimization" link: "https://reference.wolfram.com/language/ref/BayesianMinimization.en.md" - title: "RegionDistance" link: "https://reference.wolfram.com/language/ref/RegionDistance.en.md" related_tutorials: - title: "Constrained Optimization" link: "https://reference.wolfram.com/language/tutorial/ConstrainedOptimizationOverview.en.md" - title: "Unconstrained Optimization" link: "https://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationOverview.en.md" - title: "Numerical Mathematics: Basic Operations" link: "https://reference.wolfram.com/language/tutorial/NumericalCalculations.en.md" - title: "Numerical Optimization" link: "https://reference.wolfram.com/language/tutorial/NumericalOperationsOnFunctions.en.md#24524" - title: "Symbolic Evaluation" link: "https://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationSettingUpOptimizationProblems.en.md#147397427" - title: "Implementation Notes: Numerical and Related Functions" link: "https://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.en.md#13028" --- # FindMinimum FindMinimum[f, x] searches for a local minimum in f, starting from an automatically selected point. FindMinimum[f, {x, x0}] searches for a local minimum in f, starting from the point x = x0. FindMinimum[f, {{x, x0}, {y, y0}, …}] searches for a local minimum in a function of several variables. FindMinimum[{f, cons}, {{x, x0}, {y, y0}, …}] searches for a local minimum subject to the constraints cons. FindMinimum[{f, cons}, {x, y, …}] starts from a point within the region defined by the constraints. ## Details and Options * ``FindMinimum`` returns a list of the form ``{fmin, {x -> xmin}}``, where ``fmin`` is the minimum value of ``f`` found, and ``xmin`` is the value of ``x`` for which it is found. * If the starting point for a variable is given as a list, the values of the variable are taken to be lists with the same dimensions. * The constraints ``cons`` can contain equations, inequalities or logical combinations of these. * The constraints ``cons`` can be any logical combination of: | | | | :----------------------- | :------------------- | | lhs == rhs | equations | | lhs > rhs or lhs >= rhs | inequalities | | {x, y, …}∈reg | region specification | * ``FindMinimum`` first localizes the values of all variables, then evaluates ``f`` with the variables being symbolic, and then repeatedly evaluates the result numerically. * ``FindMinimum`` has attribute ``HoldAll``, and effectively uses ``Block`` to localize variables. * ``FindMinimum[f, {x, x0, x1}]`` searches for a local minimum in ``f`` using ``x0`` and ``x1`` as the first two values of ``x``, avoiding the use of derivatives. * ``FindMinimum[f, {x, x0, xmin, xmax}]`` searches for a local minimum, stopping the search if ``x`` ever gets outside the range ``xmin`` to ``xmax``. * Except when ``f`` and ``cons`` are both linear, the results found by ``FindMinimum`` may correspond only to local, but not global, minima. * By default, all variables are assumed to be real. * For linear ``f`` and ``cons``, ``x∈Integers`` can be used to specify that a variable can take on only integer values. * The following options can be given: | | | | | :----------------- | :--------------- | :----------------------------------------------- | | AccuracyGoal | Automatic | the accuracy sought | | EvaluationMonitor | None | expression to evaluate whenever f is evaluated | | Gradient | Automatic | the list of gradient components for f | | MaxIterations | Automatic | maximum number of iterations to use | | Method | Automatic | method to use | | PrecisionGoal | Automatic | the precision sought | | StepMonitor | None | expression to evaluate whenever a step is taken | | WorkingPrecision | MachinePrecision | the precision used in internal computations | * The settings for ``AccuracyGoal`` and ``PrecisionGoal`` specify the number of digits to seek in both the value of the position of the minimum, and the value of the function at the minimum. * ``FindMinimum`` continues until either of the goals specified by ``AccuracyGoal`` or ``PrecisionGoal`` is achieved. * Possible settings for ``Method`` include ``"ConjugateGradient"``, ``"PrincipalAxis"``, ``"LevenbergMarquardt"``, ``"Newton"``, ``"QuasiNewton"``, ``"InteriorPoint"``, and ``"LinearProgramming"``, with the default being ``Automatic``. --- ## Examples (34) ### Basic Examples (4) Find a local minimum, starting the search at $x=2$ : ```wl In[1]:= FindMinimum[x Cos[x], {x, 2}] Out[1]= {-3.28837, {x -> 3.42562}} In[2]:= Plot[x Cos[x], {x, 0, 20}] Out[2]= [image] ``` Extract the value of ``x`` at the local minimum: ```wl In[3]:= x /. Last[FindMinimum[x Cos[x], {x, 2}]] Out[3]= 3.42562 ``` --- Find a local minimum, starting at $x=7$, subject to constraints $1\leq x \leq 15$ : ```wl In[1]:= FindMinimum[{x Cos[x], 1 ≤ x ≤ 15}, {x, 7}] Out[1]= {-9.47729, {x -> 9.52933}} ``` --- Find the minimum of a linear function, subject to linear and integer constraints: ```wl In[1]:= FindMinimum[{x + y, x + 2y ≥ 3 && x ≥ 0 && y ≥ 0 && y∈Integers}, {x, y}] Out[1]= {2., {x -> 1., y -> 1}} ``` --- Find a minimum of a function over a geometric region: ```wl In[1]:= FindMinimum[{x + y, {x, y}∈Disk[]}, {x, y}] Out[1]= {-1.41422, {x -> -0.707108, y -> -0.707108}} ``` Plot it: ```wl In[2]:= Show[ContourPlot[x + y, {x, y}∈Disk[]], Graphics[{Red, PointSize[Large], Point[{x, y} /. Last[%]]}]] Out[2]= [image] ``` ### Scope (12) With different starting points, you may get different local minima: ```wl In[1]:= FindMinimum[x Cos[x], {x, 5}] Out[1]= {-3.28837, {x -> 3.42562}} In[2]:= FindMinimum[x Cos[x], {x, 10}] Out[2]= {-9.47729, {x -> 9.52933}} ``` --- Local minimum of a two-variable function starting from ``x = 2``, ``y = 2`` : ```wl In[1]:= FindMinimum[Sin[x]Sin[2y], {{x, 2}, {y, 2}}] Out[1]= {-1., {x -> 1.5708, y -> 2.35619}} ``` --- Local minimum constrained within a disk: ```wl In[1]:= FindMinimum[{Sin[x]Sin[2y], x ^ 2 + y ^ 2 < 3}, {{x, 2}, {y, 2}}] Out[1]= {-0.0886359, {x -> 0.419679, y -> 1.68044}} ``` --- Starting point does not have to be provided: ```wl In[1]:= FindMinimum[{Sin[x ]Sin[2y], x ^ 2 + y ^ 2 < 3}, {x, y}] Out[1]= {-0.0886359, {x -> 0.419679, y -> 1.68044}} ``` --- For linear objective and constraints, integer constraints can be imposed: ```wl In[1]:= FindMinimum[{x + y, 3x + 2y ≥ 7 && x ≥ 0 && y ≥ 0}, {x, y}] Out[1]= {2.33333, {x -> 2.33333, y -> 0.}} In[2]:= FindMinimum[{x + y, 3x + 2y ≥ 7 && x ≥ 0 && y ≥ 0 && x∈Integers}, {x, y}] Out[2]= {2.5, {x -> 2, y -> 0.5}} ``` --- ``Or`` constraints can be specified: ```wl In[1]:= FindMinimum[{x + y, x ^ 2 + y ^ 2 ≤ 1 || (x + 2) ^ 2 + (y + 2) ^ 2 ≤ 1}, {x, y}] Out[1]= {-5.41421, {x -> -2.70711, y -> -2.70711}} ``` --- Find a minimum in a region: ```wl In[1]:= t = RotationTransform[{{0, 0, 1}, {1, 1, 1}}]; ℛ = TransformedRegion[Ellipsoid[{0, 0, 0}, {1, 2, 3}], t]; In[2]:= FindMinimum[{z, {x, y, z}∈ℛ}, {x, y, z}] Out[2]= {-2.16025, {x -> -1.40386, y -> -0.60208, z -> -2.16025}} ``` Plot it: ```wl In[3]:= Graphics3D[{{Opacity[0.5], Green, GeometricTransformation[Ellipsoid[{0, 0, 0}, {1, 2, 3}], t]}, {Red, PointSize[Large], Point[{x, y, z} /. Last[%]]}}] Out[3]= [image] ``` --- Find the minimum distance between two regions: ```wl In[1]:= Subscript[ℛ, 1] = Disk[]; Subscript[ℛ, 2] = InfiniteLine[{{-2, 0}, {0, 2}}]; In[2]:= FindMinimum[{(x - u)^2 + (y - v)^2, {{x, y}∈Subscript[ℛ, 1], {u, v}∈Subscript[ℛ, 2]}}, {x, y, u, v}] Out[2]= {0.171573, {x -> -0.707107, y -> 0.707107, u -> -1., v -> 1.}} ``` Plot it: ```wl In[3]:= Graphics[{{LightBlue, Subscript[ℛ, 1]}, {Green, Subscript[ℛ, 2]}, {Red, Point[{{x, y}, {u, v}} /. Last[%]]}}] Out[3]= [image] ``` --- Find the minimum $r$ such that the triangle and ellipse still intersect: ```wl In[1]:= Subscript[ℛ, 1] = Triangle[{{0, 0}, {1, 0}, {0, 1}}]; Subscript[ℛ, 2] = Disk[{1, 1}, {2r, r}]; In[2]:= FindMinimum[{r, {x, y}∈Subscript[ℛ, 1] && {x, y}∈Subscript[ℛ, 2]}, {r, x, y}] Out[2]= {0.447214, {r -> 0.447214, x -> 0.2, y -> 0.8}} ``` Plot it: ```wl In[3]:= Graphics[{{LightBlue, Subscript[ℛ, 1], Subscript[ℛ, 2]}, {Red, Point[{x, y}]}} /. Last[%]] Out[3]= [image] ``` --- Find the disk of minimum radius that contains the given three points: ```wl In[1]:= Subscript[ℛ, 3] = Disk[{a, b}, r]; In[2]:= FindMinimum[{r, ({0, 0} | {1, 0} | {0, 1})∈Subscript[ℛ, 3]}, {a, b, r}] Out[2]= {0.707107, {a -> 0.499451, b -> 0.499451, r -> 0.707107}} ``` Plot it: ```wl In[3]:= Graphics[{{LightBlue, Subscript[ℛ, 3]} /. %[[2]], {Red, Point[{{0, 0}, {1, 0}, {0, 1}}]}}] Out[3]= [image] ``` Using ``Circumsphere`` gives the same result directly: ```wl In[4]:= Circumsphere[{{0, 0}, {1, 0}, {0, 1}}]//N Out[4]= Sphere[{0.5, 0.5}, 0.707107] ``` --- Use $x\in \mathcal{R}$ to specify that $x$ is a vector in $\mathbb{R}^3$ : ```wl In[1]:= ℛ = Sphere[]; In[2]:= FindMinimum[{x.{1, 2, 3}, x∈ℛ}, x] Out[2]= {-3.74166, {x -> {-0.267261, -0.534523, -0.801784}}} ``` --- Find the minimum distance between two regions: ```wl In[1]:= Subscript[ℛ, 1] = Triangle[{{0, 0}, {1, 0}, {0, 1}}]; Subscript[ℛ, 2] = Disk[{2, 2}, 1]; In[2]:= FindMinimum[{EuclideanDistance[x, y], {x∈Subscript[ℛ, 1], y∈Subscript[ℛ, 2]}}, {x, y}] Out[2]= {1.12132, {x -> {0.5, 0.5}, y -> {1.29289, 1.29289}}} ``` Plot it: ```wl In[3]:= Graphics[{{LightBlue, Subscript[ℛ, 1], Subscript[ℛ, 2]}, {Red, Point[{x, y}]}} /. %[[2]]] Out[3]= [image] ``` ### Options (7) #### AccuracyGoal & PrecisionGoal (2) This enforces convergence criteria $\left\|x_k-x^*\right\| \leq \max \left(10^{-9},10^{-8}\left\|x_k\right\|\right)$ and $\text{$\triangledown $f}\left(x_k\right)\leq 10^{-9}$ : ```wl In[1]:= FindMinimum[Sin[x / 2], {x, 1}, AccuracyGoal -> 9, PrecisionGoal -> 8] Out[1]= {-1., {x -> -3.14159}} ``` --- This enforces convergence criteria $\left\|x_k-x^*\right\| \leq \max \left(10^{-20},10^{-18}\left\|x_k\right\|\right)$ and $\text{$\triangledown $f}\left(x_k\right)\leq 10^{-20}$ : ```wl In[1]:= FindMinimum[Sin[x / 2], {x, 1}, AccuracyGoal -> 20, PrecisionGoal -> 18] ``` FindMinimum::fmdig: MachinePrecision working digits is insufficient to achieve the requested accuracy or precision. ```wl Out[1]= {-1., {x -> -3.14159}} ``` Setting a high ``WorkingPrecision`` makes the process convergent: ```wl In[2]:= FindMinimum[Sin[x / 2], {x, 1}, AccuracyGoal -> 20, PrecisionGoal -> 18, WorkingPrecision -> 40] Out[2]= {-1.00000000000000000000000000000000000000, {x -> -3.141592653589793238462643383032495226760}} ``` #### EvaluationMonitor (1) Plot convergence to the local minimum: ```wl In[1]:= ListPlot[Last[Reap[FindMinimum[x Cos[x], {x, 2}, EvaluationMonitor :> Sow[x]]]]] Out[1]= [image] ``` #### Gradient (1) Use a given gradient; the Hessian is computed automatically: ```wl In[1]:= FindMinimum[Sin[x]Sin[2 y], {x, y}, Gradient -> {Cos[x] Sin[2 y], 2 Cos[2 y] Sin[x]}, Method -> "Newton"] Out[1]= {-1., {x -> -1.5708, y -> 0.785398}} ``` Supply both gradient and Hessian: ```wl In[2]:= FindMinimum[Sin[x]Sin[2y], {x, y}, Gradient -> {Cos[x] Sin[2 y], 2 Cos[2 y] Sin[x]}, Method -> {"Newton", Hessian -> {{-Sin[x] Sin[2 y], 2 Cos[x] Cos[2 y]}, {2 Cos[x] Cos[2 y], -4 Sin[x] Sin[2 y]}}}] Out[2]= {-1., {x -> -1.5708, y -> 0.785398}} ``` #### Method (1) In this case, the default derivative-based methods have difficulties: ```wl In[1]:= FindMinimum[Abs[x + 1] + Abs[x + 1.01] + Abs[y + 1], {x, y}] Out[1]= {0.01, {x -> -1.00683, y -> -1.}} In[2]:= FindMinimum[Abs[x + 1] + Abs[x + 1.01] + Abs[y + 1], {x, y}, Method -> "ConjugateGradient"] ``` FindMinimum::lstol: The line search decreased the step size to within the tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the function. You may need more than MachinePrecision digits of working precision to meet these tolerances. ```wl Out[2]= {0.01, {x -> -1.00435, y -> -1.}} ``` Direct search methods that do not require derivatives can be helpful in these cases: ```wl In[3]:= FindMinimum[Abs[x + 1] + Abs[x + 1.01] + Abs[y + 1], {x, y}, Method -> "PrincipalAxis"] Out[3]= {0.01, {x -> -1.00671, y -> -1.}} ``` ``NMinimize`` also uses a range of direct search methods: ```wl In[4]:= NMinimize[{Abs[x + 1] + Abs[x + 1.01] + Abs[y + 1], 0 > x > -2}, {x, y}] Out[4]= {0.01, {x -> -1.00182, y -> -1.}} ``` #### StepMonitor (1) Steps taken by ``FindMinimum`` in finding the minimum of a function: ```wl In[1]:= pts = Reap[FindMinimum[(1 - x) ^ 2 + 100(-x ^ 2 - y) ^ 2 + 1, {{x, -1.2}, {y, 1}}, StepMonitor :> Sow[{x, y}]]][[2, 1]]; pts = Join[{{-1.2, 1}}, pts]; In[2]:= ContourPlot[(1 - x) ^ 2 + 100(-x ^ 2 - y) ^ 2 + 1//Log, {x, -1.3, 1.5}, {y, -1.5, 1.4}, Epilog -> {Red, Line[pts], Point[pts]}] Out[2]= [image] ``` #### WorkingPrecision (1) Set the working precision to $20$; by default ``AccuracyGoal`` and ``PrecisionGoal`` are set to $\frac{20}{2}$ : ```wl In[1]:= FindMinimum[Cos[x ^ 2 - 3 y] + Sin[x ^ 2 + y ^ 2], {x, y}, Method -> "Newton", WorkingPrecision -> 20] Out[1]= {-2.0000000000000000000, {x -> 1.3763849724065498629, y -> 1.6786760819521202065}} ``` ### Applications (3) Annual returns (``R``) of long bonds from S&P 500 from 1973 to 1994: ```wl In[1]:= R = {{0.942, 1.02, 1.056, 1.175, 1.002, 0.982, 0.978, 0.947, 1.003, 1.465, 0.985, 1.159, 1.366, 1.309, 0.925, 1.086, 1.212, 1.054, 1.193, 1.079, 1.217, 0.889}, {0.852, 0.735, 1.371, 1.236, 0.926, 1.064, 1.184, 1.323, 0.949, 1.215, 1.224, 1.061, 1.316, 1.186, 1.052, 1.165, 1.316, 0.968, 1.304, 1.076, 1.1, 1.012}}; ``` Compute the mean and covariance from the returns: ```wl In[2]:= μ = Mean[Transpose@R] Out[2]= {1.09291, 1.11977} In[3]:= Σ = Covariance[Transpose[R]] Out[3]= {{0.0231523, 0.0113317}, {0.0113317, 0.0282829}} In[4]:= X = Map[Subscript[x, #]&, {"long T-bond", "SP500"}] Out[4]= {Subscript[x, "long T-bond"], Subscript[x, "SP500"]} ``` Minimize the volatility subject to at least 10% return: ```wl In[5]:= FindMinimum[{X.Σ.X, Total[X] == 1 && μ.X ≥ 1.10 && Apply[And, Thread[X ≥ {0, 0}]]}, X] Out[5]= {0.0182959, {Subscript[x, "long T-bond"] -> 0.588856, Subscript[x, "SP500"] -> 0.411144}} ``` --- Find the smallest square that can contain $n$ circles of given radii $r_i$ for $i=1,\text{...},n$ that do not overlap. Specify the number of circles and the radius of each circle: ```wl In[1]:= n = 20; r = BlockRandom[RandomReal[{0.5, 1.5}, n], RandomSeeding -> 123]; ``` If $c_i$ is the center of circle $i$, then the objective is to minimize $\max _{i = 1,\text{..},n}\left(\left\|c_i\|_{\infty }+ r_i\right.\right)$. The objective can be transformed so as to minimize $s$ and $-s\text{$<$=}\left\|c_i\|_{\infty }+r_i\text{$<$=}s\right., i=1,\text{...},n$ : ```wl In[2]:= objectiveConstraint = Table[-s <= Norm[c[i], Infinity] + r[[i]] <= s, {i, n}]; ``` The circles must not overlap: ```wl In[3]:= nonOverlapConstraint = Table[Norm[c[i] - c[j]] >= r[[i]] + r[[j]], {i, 1, n}, {j, i + 1, n}]; ``` Collect the variables: ```wl In[4]:= vars = Append[Table[Element[c[i], Vectors[2, Reals]], {i, n}], Element[s, Reals]]; ``` Minimize the objective $s$ : ```wl In[5]:= Short[res = FindMinimum[{s, objectiveConstraint, nonOverlapConstraint}, vars], 5] Out[5]//Short= {4.75135, {c[1] -> {1.33505, -3.79563}, c[2] -> {-1.48092, -0.122662}, c[3] -> {3.30814, -2.43116}, c[4] -> {1.45834, -0.190683}, c[5] -> {-3.94901, -2.41447}, «11», c[17] -> {-3.8013, -3.97885}, c[18] -> {-1.80681, -3.00071}, c[19] -> {-1.91823, 2.30122}, c[20] -> {-4.15178, 3.00651}, s -> 4.75135}} ``` The circles are contained in the square $[-s,s] \times [-s,s]$ : ```wl In[6]:= Graphics[{Table[Circle[c[i], r[[i]]], {i, n}], {FaceForm[None], EdgeForm[Black], Rectangle[{-s, -s}, {s, s}]}}] /. res[[2]] Out[6]= [image] ``` Compute the fraction of square covered by the circles: ```wl In[7]:= Sum[Area[Disk[c[i], r[[i]]]], {i, n}] / Area[Rectangle[{-s, -s}, {s, s}]] /. res[[2]] Out[7]= 0.720045 ``` --- Find a path through circular obstacles such that the distance between the start and end points is minimized: ```wl In[1]:= p = {{2, 2}, {7, 6}, {3, 5}, {4, 8}, {8, 9}, {6, 2.5}}; r = {1, 1.3, 1.5, 1, 0.7, 1.5}; {start, end} = {{0, 0}, {10, 10}}; domain = Graphics[{MapThread[Circle[#1, #2]&, {p, r}], {PointSize[0.02], Point[{start, end}]}}, Frame -> True] Out[1]= [image] ``` The path is discretized into $n$ different points with distance of $l/n$ between points, where $l$ is the trajectory length being minimized: ```wl In[2]:= n = 30; distanceConstraints = Table[Inactive[Norm][x[i] - x[i - 1]] <= l / n, {i, n}]; ``` The points cannot be inside the circular objects: ```wl In[3]:= objectConstraints = Table[Inactive[Norm][-p[[j]] + x[i]] >= r[[j]], {i, 1, n}, {j, 1, 6}]; ``` The start and end points are known: ```wl In[4]:= positionConstraints = {x[0] == start, x[n] == end}; ``` Collect the variables: ```wl In[5]:= vars = Append[Table[x[i]∈Vectors[2, Reals], {i, 0, n}], l∈Reals]; ``` Minimize the length $l$ subject to the constraints: ```wl In[6]:= Short[res = FindMinimum[{l, distanceConstraints, objectConstraints, positionConstraints}, vars], 2] Out[6]//Short= {14.5693, {x[0] -> {2.8471636068532425`*^-9, 2.809384453708684`*^-9}, x[1] -> {0.440639, 0.204172}, «28», x[30] -> {10., 10.}, l -> 14.5693}} ``` Visualize the result: ```wl In[7]:= pts = vars[[1 ;; -2, 1]] /. res[[2]]; Show[domain, Graphics[{Red, Point[pts]}]] Out[7]= [image] ``` ### Properties & Relations (2) ``FindMinimum`` tries to find a local minimum; ``NMinimize`` attempts to find a global minimum: ```wl In[1]:= objective = -100 / ((x - 1)^2 + (y - 1)^2 + 1) - 200 / ((x + 1)^2 + (y + 2)^2 + 1); FindMinimum[{$$\text{objective}$$, $$x^2+y^2>3$$ }, {{x, 2}, y}] Out[1]= {-103.063, {x -> 1.23037, y -> 1.21909}} In[2]:= NMinimize[{$$\text{objective}$$, $$x^2+y^2>3$$ }, {x, y}] Out[2]= {-207.16, {x -> -0.994929, y -> -1.99248}} In[3]:= ContourPlot[objective, {x, -3, 2}, {y, -3, 2}, ...] Out[3]= [image] ``` ``Minimize`` finds a global minimum and can work in infinite precision: ```wl In[4]:= Minimize[{$$- 100\left/\left((x-1)^2+(y-1)^2+1\right)\right.-200\left/\left((x+1)^2+(y+2)^2+1\right)\right.$$, $$x^2+y^2>3$$ }, {x, y}] Out[4]= {Root[9450000000000 - 1185300000000*#1 + 39312000000*#1^2 + 1872000000*#1^3 + 18099900*#1^4 + 48841*#1^5 & , 1, 0], {x -> Root[{9450000000000 - 1185300000000*#1 + 39312000000*#1^2 + 1872000000*#1^3 + 18099900*#1^4 + 48841*#1^5 & , -4101256 ... 0*#1^3)*#2^8 - (48942129600*#1^4)*#2^8 & , 1200 + 18*#1 - 200*#2 - (6*#1)*#2 + 300*#2^2 + (5*#1)*#2^2 + #1*#2^4 - ((12*#1)*#2)*#3 + ((2*#1)*#2^2)*#3 + 300*#3^2 + #1*#3^2 + ((2*#1)*#2^2)*#3^2 + (2*#1)*#3^3 + #1*#3^4 & }, {1, 2, 2}]}} In[5]:= N[%] Out[5]= {-207.16, {x -> -0.994861, y -> -1.99229}} ``` --- ``FindMinimum`` gives both the value of the minimum and the minimizer point: ```wl In[1]:= FindMinimum[{x - 2y, x ^ 2 + y ^ 2 ≤ 1}, {x, y}] Out[1]= {-2.23607, {x -> -0.447214, y -> 0.894427}} ``` ``FindArgMin`` gives the location of the minimum: ```wl In[2]:= FindArgMin[{x - 2y, x ^ 2 + y ^ 2 ≤ 1}, {x, y}] Out[2]= {-0.447214, 0.894427} ``` ``FindMinValue`` gives the value at the minimum: ```wl In[3]:= FindMinValue[{x - 2y, x ^ 2 + y ^ 2 ≤ 1}, {x, y}] Out[3]= -2.23607 ``` ### Possible Issues (6) With machine-precision arithmetic, even functions with smooth minima may seem bumpy: ```wl In[1]:= opt = FindMinimum[x Cos[x], {x, 1}] ``` FindMinimum::lstol: The line search decreased the step size to within the tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the function. You may need more than MachinePrecision digits of working precision to meet these tolerances. ```wl Out[1]= {-3.28837, {x -> 3.42562}} In[2]:= yopt = First[opt]; xopt = x /. Last[opt]; In[3]:= Plot[x Cos[x] - yopt, Evaluate[{x, xopt - 1.*^-7, xopt + 1.*^-7}], PlotRange -> All] Out[3]= [image] ``` Going beyond machine precision often avoids such problems: ```wl In[4]:= FindMinimum[x Cos[x], {x, 1}, WorkingPrecision -> 30] Out[4]= {-3.28837139559089648651259645712, {x -> 3.42561845948172814647764787226}} ``` --- If the constraint region is empty, the algorithm will not converge: ```wl In[1]:= FindMinimum[{x + y, x ^ 2 + y ^ 2 ≥ 2 && x ^ 2 + y ^ 2 ≤ 1}, {x, y}] ``` FindMinimum::infeas: Possible infeasibility detected. Returning the best solution found. Setting a different initial point or Method -> InteriorPoint may lead to a better solution. ```wl Out[1]= {1.73514, {x -> 0.868537, y -> 0.8666}} ``` --- If the minimum value is not finite, the algorithm will not converge: ```wl In[1]:= FindMinimum[Tan[x], {x, 2}] ``` FindMinimum::lstol: The line search decreased the step size to within the tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the function. You may need more than MachinePrecision digits of working precision to meet these tolerances. ```wl Out[1]= {-3.058630832723279*^14, {x -> 1.5708}} In[2]:= FindMinimum[{-x ^ 2 - y ^ 2, x ^ 2 + y ^ 2 > 10}, {x, y}] ``` FindMinimum::cvmit: Failed to converge to the requested accuracy or precision within 500 iterations. ```wl Out[2]= {-3.5836016962142324*^9, {x -> 42329.7, y -> 42329.7}} ``` --- The integer linear programming algorithm is only available for machine-number problems: ```wl In[1]:= FindMinimum[{x + y, x + 2y ≥ 3 && x > 1 && y > 1 && x∈Integers}, {x, y}, WorkingPrecision -> 20] ``` FindMinimum::lpip: Warning: Problem specified contains integer variables. Only machine number algorithm is available; the problem will be converted into machine precision. ```wl Out[1]= {2., {x -> 1, y -> 1.}} ``` --- Sometimes providing a suitable starting point can help the algorithm to converge: ```wl In[1]:= FindMinimum[{Cos[x] - Exp[(x - 0.5) y], x ^ 2 + y ^ 2 < 1}, {x, y}] Out[1]= {-0.573452, {x -> 0.927095, y -> 0.374826}} In[2]:= FindMinimum[{Cos[x] - Exp[(x - 0.5) y], x ^ 2 + y ^ 2 < 1}, {{x, -1}, {y, -1}}] Out[2]= {-1.60046, {x -> -0.657219, y -> -0.7537}} ``` --- It can be time-consuming to compute functions symbolically: ```wl In[1]:= f[x_] := Nest[Sin[# + Sin[2#]]&, x, 15] In[2]:= FindMinimum[f[x], {x, 0}]//Timing ``` FindMinimum::lstol: The line search decreased the step size to within the tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the function. You may need more than MachinePrecision digits of working precision to meet these tolerances. ```wl Out[2]= {2.79016, {-0.947747, {x -> -0.00022845}}} ``` Restricting the function definition prevents symbolic evaluation: ```wl In[3]:= g[x_ ? NumericQ] := Nest[Sin[# + Sin[2#]]&, x, 15] In[4]:= FindMinimum[g[x], {x, 0}]//Timing ``` FindMinimum::lstol: The line search decreased the step size to within the tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the function. You may need more than MachinePrecision digits of working precision to meet these tolerances. ```wl Out[4]= {0.002928, {-0.947747, {x -> -0.000228451}}} ``` ## See Also * [`FindMaximum`](https://reference.wolfram.com/language/ref/FindMaximum.en.md) * [`NMinimize`](https://reference.wolfram.com/language/ref/NMinimize.en.md) * [`Minimize`](https://reference.wolfram.com/language/ref/Minimize.en.md) * [`FindArgMin`](https://reference.wolfram.com/language/ref/FindArgMin.en.md) * [`FindMinValue`](https://reference.wolfram.com/language/ref/FindMinValue.en.md) * [`FindFit`](https://reference.wolfram.com/language/ref/FindFit.en.md) * [`FindRoot`](https://reference.wolfram.com/language/ref/FindRoot.en.md) * [`Min`](https://reference.wolfram.com/language/ref/Min.en.md) * [`LinearOptimization`](https://reference.wolfram.com/language/ref/LinearOptimization.en.md) * [`ConvexOptimization`](https://reference.wolfram.com/language/ref/ConvexOptimization.en.md) * [`GeometricOptimization`](https://reference.wolfram.com/language/ref/GeometricOptimization.en.md) * [`D`](https://reference.wolfram.com/language/ref/D.en.md) * [`BayesianMinimization`](https://reference.wolfram.com/language/ref/BayesianMinimization.en.md) * [`RegionDistance`](https://reference.wolfram.com/language/ref/RegionDistance.en.md) ## Tech Notes * [Constrained Optimization](https://reference.wolfram.com/language/tutorial/ConstrainedOptimizationOverview.en.md) * [Unconstrained Optimization](https://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationOverview.en.md) * [Numerical Mathematics: Basic Operations](https://reference.wolfram.com/language/tutorial/NumericalCalculations.en.md) * [Numerical Optimization](https://reference.wolfram.com/language/tutorial/NumericalOperationsOnFunctions.en.md#24524) * [Symbolic Evaluation](https://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationSettingUpOptimizationProblems.en.md#147397427) * [Implementation Notes: Numerical and Related Functions](https://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.en.md#13028) ## Related Guides * [`Optimization`](https://reference.wolfram.com/language/guide/Optimization.en.md) * [Discrete Mathematics](https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md) * [Convex Optimization](https://reference.wolfram.com/language/guide/ConvexOptimization.en.md) * [Solvers over Regions](https://reference.wolfram.com/language/guide/GeometricSolvers.en.md) * [Scientific Models](https://reference.wolfram.com/language/guide/ScientificModels.en.md) * [Graph Programming](https://reference.wolfram.com/language/guide/GraphProgramming.en.md) * [Matrix Decompositions](https://reference.wolfram.com/language/guide/MatrixDecompositions.en.md) * [Symbolic Vectors, Matrices and Arrays](https://reference.wolfram.com/language/guide/SymbolicArrays.en.md) * [System Model Analytics & Design](https://reference.wolfram.com/language/guide/SystemModelAnalyticsDesign.en.md) ## Related Links * [NKS\|Online](http://www.wolframscience.com/nks/search/?q=FindMinimum) * [A New Kind of Science](http://www.wolframscience.com/nks/) ## History * Introduced in 1988 (1.0) \| Updated in 2000 (4.1) ▪ 2003 (5.0) ▪ [2007 (6.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn60.en.md) ▪ [2014 (10.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn100.en.md)