diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java
index 3e16d7b..bd1f938 100644
--- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/BaseOptimizer.java
@@ -23,8 +23,10 @@
 /**
  * Base class for implementing optimizers.
  * It contains the boiler-plate code for counting the number of evaluations
- * of the objective function and the number of iterations of the algorithm,
- * and storing the convergence checker.
+ * of the objective function and the number of iterations of the algorithm.
+ * It also stores a {@link ConvergenceChecker convergence checker}, as well
+ * as {@link Tolerance default tolerances} (how the checker and tolerances
+ * are used is determined by subclasses).
  * <em>It is not a "user" class.</em>
  *
  * @param <PAIR> Type of the point/value pair returned by the optimization
@@ -48,6 +50,10 @@
     private IntegerSequence.Incrementor evaluations;
     /** Iterations counter. */
     private IntegerSequence.Incrementor iterations;
+    /** Relative tolerance. */
+    private double relativeTolerance = 1e-6;
+    /** Absolute tolerance. */
+    private double absoluteTolerance = 1e-6;
 
     /**
      * @param checker Convergence checker.
@@ -69,6 +75,16 @@
         this.maxIterations = maxIter;
     }
 
+    /** @return the relative tolerance. */
+    protected double getRelativeTolerance() {
+        return relativeTolerance;
+    }
+
+    /** @return the absolute tolerance. */
+    protected double getAbsoluteTolerance() {
+        return absoluteTolerance;
+    }
+
     /**
      * Gets the maximal number of function evaluations.
      *
@@ -142,6 +158,7 @@
      *  <li>{@link MaxEval}</li>
      *  <li>{@link MaxIter}</li>
      *  <li>{@link ConvergenceChecker}</li>
+     *  <li>{@link Tolerance}</li>
      * </ul>
      * @return a point/value pair that satisfies the convergence criteria.
      * @throws TooManyEvaluationsException if the maximal number of
@@ -230,6 +247,12 @@
                 checker = (ConvergenceChecker<PAIR>) data;
                 continue;
             }
+            if (data instanceof Tolerance) {
+               final Tolerance tol = (Tolerance) data;
+               relativeTolerance = tol.getRelativeTolerance();
+               absoluteTolerance = tol.getAbsoluteTolerance();
+               continue;
+            }
         }
     }
 
diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/Tolerance.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/Tolerance.java
new file mode 100644
index 0000000..de115cf
--- /dev/null
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/Tolerance.java
@@ -0,0 +1,53 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math4.legacy.optim;
+
+/**
+ * Default tolerances values.
+ *
+ * @since 4.0
+ */
+public class Tolerance implements OptimizationData {
+    /** Relative tolerance. */
+    private final double relativeTolerance;
+    /** Absolute tolerance. */
+    private final double absoluteTolerance;
+
+    /**
+     * @param relative Relative tolerance.
+     * @param absolute Abolute tolerance.
+     */
+    public Tolerance(double relative,
+                     double absolute) {
+        relativeTolerance = relative;
+        absoluteTolerance = absolute;
+    }
+
+    /**
+     * @return the retlative tolerance.
+     */
+    public double getRelativeTolerance() {
+        return relativeTolerance;
+    }
+
+    /**
+     * @return the absolute tolerance.
+     */
+    public double getAbsoluteTolerance() {
+        return absoluteTolerance;
+    }
+}
diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java
index 6e674c3..0cc8e59 100644
--- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearch.java
@@ -32,7 +32,12 @@
  * direction.
  *
  * @since 3.3
+ * @deprecated as of 4.0-beta2.
+ * Class is now encapsulated in {@link MultivariateOptimizer}.
+ * Subclasses should call {@link MultivariateOptimizer#createLineSearch()}
+ * and {@link MultivariateOptimizer#lineSearch(double[],double[])} instead.
  */
+@Deprecated
 public class LineSearch {
     /**
      * Value that will pass the precondition check for {@link BrentOptimizer}
diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearchTolerance.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearchTolerance.java
new file mode 100644
index 0000000..e6df1e7
--- /dev/null
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/LineSearchTolerance.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math4.legacy.optim.nonlinear.scalar;
+
+import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException;
+import org.apache.commons.math4.legacy.optim.Tolerance;
+
+/**
+ * Tolerances for line search.
+ *
+ * @since 4.0
+ */
+public class LineSearchTolerance extends Tolerance {
+    /** Range. */
+    private final double initialBracketingRange;
+
+    /**
+     * @param relative Relative tolerance.
+     * @param absolute Absolute tolerance.
+     * @param range Extent of the initial interval used to find an interval
+     * that brackets the optimum.
+     * If the optimized function varies a lot in the vicinity of the optimum,
+     * it may be necessary to provide a value lower than the distance between
+     * successive local minima.
+     */
+    public LineSearchTolerance(double relative,
+                               double absolute,
+                               double range) {
+        super(relative, absolute);
+
+        if (range <= 0) {
+            throw new NotStrictlyPositiveException(range);
+        }
+
+        initialBracketingRange = range;
+    }
+
+    /** @return the initial bracketing range. */
+    public double getInitialBracketingRange() {
+        return initialBracketingRange;
+    }
+}
diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java
index 2cd72d8..35a954b 100644
--- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultivariateOptimizer.java
@@ -17,10 +17,19 @@
 package org.apache.commons.math4.legacy.optim.nonlinear.scalar;
 
 import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
+import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
 import org.apache.commons.math4.legacy.optim.BaseMultivariateOptimizer;
 import org.apache.commons.math4.legacy.optim.ConvergenceChecker;
 import org.apache.commons.math4.legacy.optim.OptimizationData;
 import org.apache.commons.math4.legacy.optim.PointValuePair;
+import org.apache.commons.math4.legacy.optim.MaxEval;
+import org.apache.commons.math4.legacy.optim.univariate.BracketFinder;
+import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer;
+import org.apache.commons.math4.legacy.optim.univariate.SearchInterval;
+import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker;
+import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction;
+import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer;
+import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair;
 
 /**
  * Base class for a multivariate scalar function optimizer.
@@ -33,6 +42,14 @@
     private MultivariateFunction function;
     /** Type of optimization. */
     private GoalType goal;
+    /** Line search relative tolerance. */
+    private double lineSearchRelativeTolerance = 1e-8;
+    /** Line search absolute tolerance. */
+    private double lineSearchAbsoluteTolerance = 1e-8;
+    /** Line serach initial bracketing range. */
+    private double lineSearchInitialBracketingRange = 1d;
+    /** Line search. */
+    private LineSearch lineSearch;
 
     /**
      * @param checker Convergence checker.
@@ -50,6 +67,7 @@
      * <ul>
      *  <li>{@link ObjectiveFunction}</li>
      *  <li>{@link GoalType}</li>
+     *  <li>{@link LineSearchTolerance}</li>
      * </ul>
      * @return {@inheritDoc}
      * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
@@ -70,6 +88,7 @@
      * <ul>
      *  <li>{@link ObjectiveFunction}</li>
      *  <li>{@link GoalType}</li>
+     *  <li>{@link LineSearchTolerance}</li>
      * </ul>
      */
     @Override
@@ -95,13 +114,45 @@
                     };
                 continue;
             }
+            if (data instanceof LineSearchTolerance) {
+                final LineSearchTolerance tol = (LineSearchTolerance) data;
+                lineSearchRelativeTolerance = tol.getRelativeTolerance();
+                lineSearchAbsoluteTolerance = tol.getAbsoluteTolerance();
+                lineSearchInitialBracketingRange = tol.getInitialBracketingRange();
+                continue;
+            }
         }
     }
 
     /**
+     * Intantiate the line search implementation.
+     */
+    protected void createLineSearch() {
+        lineSearch = new LineSearch(this,
+                                    lineSearchRelativeTolerance,
+                                    lineSearchAbsoluteTolerance,
+                                    lineSearchInitialBracketingRange);
+    }
+
+    /**
+     * Finds the number {@code alpha} that optimizes
+     * {@code f(startPoint + alpha * direction)}.
+     *
+     * @param startPoint Starting point.
+     * @param direction Search direction.
+     * @return the optimum.
+     * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
+     * if the number of evaluations is exceeded.
+     */
+    protected UnivariatePointValuePair lineSearch(final double[] startPoint,
+                                                  final double[] direction) {
+        return lineSearch.search(startPoint, direction);
+    }
+
+    /**
      * @return the optimization type.
      */
-    public GoalType getGoalType() {
+    protected GoalType getGoalType() {
         return goal;
     }
 
@@ -129,4 +180,115 @@
     public double computeObjectiveValue(double[] params) {
         return function.value(params);
     }
+
+    /**
+     * Find the minimum of the objective function along a given direction.
+     *
+     * @since 4.0
+     */
+    private static class LineSearch {
+        /**
+         * Value that will pass the precondition check for {@link BrentOptimizer}
+         * but will not pass the convergence check, so that the custom checker
+         * will always decide when to stop the line search.
+         */
+        private static final double REL_TOL_UNUSED = 1e-15;
+        /**
+         * Value that will pass the precondition check for {@link BrentOptimizer}
+         * but will not pass the convergence check, so that the custom checker
+         * will always decide when to stop the line search.
+         */
+        private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
+        /**
+         * Optimizer used for line search.
+         */
+        private final UnivariateOptimizer lineOptimizer;
+        /**
+         * Automatic bracketing.
+         */
+        private final BracketFinder bracket = new BracketFinder();
+        /**
+         * Extent of the initial interval used to find an interval that
+         * brackets the optimum.
+         */
+        private final double initialBracketingRange;
+        /**
+         * Optimizer on behalf of which the line search must be performed.
+         */
+        private final MultivariateOptimizer mainOptimizer;
+
+        /**
+         * The {@code BrentOptimizer} default stopping criterion uses the
+         * tolerances to check the domain (point) values, not the function
+         * values.
+         * The {@code relativeTolerance} and {@code absoluteTolerance}
+         * arguments are thus passed to a {@link SimpleUnivariateValueChecker
+         * custom checker} that will use the function values.
+         *
+         * @param optimizer Optimizer on behalf of which the line search
+         * be performed.
+         * Its {@link MultivariateOptimizer#getObjectiveFunction() objective
+         * function} will be called by the {@link #search(double[],double[])
+         * search} method.
+         * @param relativeTolerance Search will stop when the function relative
+         * difference between successive iterations is below this value.
+         * @param absoluteTolerance Search will stop when the function absolute
+         * difference between successive iterations is below this value.
+         * @param initialBracketingRange Extent of the initial interval used to
+         * find an interval that brackets the optimum.
+         * If the optimized function varies a lot in the vicinity of the optimum,
+         * it may be necessary to provide a value lower than the distance between
+         * successive local minima.
+         */
+        /* package-private */ LineSearch(MultivariateOptimizer optimizer,
+                                         double relativeTolerance,
+                                         double absoluteTolerance,
+                                         double initialBracketingRange) {
+            mainOptimizer = optimizer;
+            lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED,
+                                               ABS_TOL_UNUSED,
+                                               new SimpleUnivariateValueChecker(relativeTolerance,
+                                                                                absoluteTolerance));
+            this.initialBracketingRange = initialBracketingRange;
+        }
+
+        /**
+         * Finds the number {@code alpha} that optimizes
+         * {@code f(startPoint + alpha * direction)}.
+         *
+         * @param startPoint Starting point.
+         * @param direction Search direction.
+         * @return the optimum.
+         * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
+         * if the number of evaluations is exceeded.
+         */
+        /* package-private */ UnivariatePointValuePair search(final double[] startPoint,
+                                                              final double[] direction) {
+            final int n = startPoint.length;
+            final MultivariateFunction func = mainOptimizer.getObjectiveFunction();
+            final UnivariateFunction f = new UnivariateFunction() {
+                    /** {@inheritDoc} */
+                    @Override
+                    public double value(double alpha) {
+                        final double[] x = new double[n];
+                        for (int i = 0; i < n; i++) {
+                            x[i] = startPoint[i] + alpha * direction[i];
+                        }
+                        return func.value(x);
+                    }
+                };
+
+            final GoalType goal = mainOptimizer.getGoalType();
+            bracket.search(f, goal, 0, initialBracketingRange);
+            // Passing "MAX_VALUE" as a dummy value because it is the enclosing
+            // class that counts the number of evaluations (and will eventually
+            // generate the exception).
+            return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE),
+                                          new UnivariateObjectiveFunction(f),
+                                          goal,
+                                          new SearchInterval(bracket.getLo(),
+                                                             bracket.getHi(),
+                                                             bracket.getMid()));
+        }
+    }
 }
diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java
index f22eaf3..3589fd0 100644
--- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizer.java
@@ -27,8 +27,6 @@
 import org.apache.commons.math4.legacy.optim.PointValuePair;
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType;
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GradientMultivariateOptimizer;
-import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearch;
-
 
 /**
  * Non-linear conjugate gradient optimizer.
@@ -37,6 +35,8 @@
  * update formulas for the conjugate search directions.
  * It also supports optional preconditioning.
  * <br>
+ * Line search must be setup via {@link org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearchTolerance}.
+ * <br>
  * Constraints are not supported: the call to
  * {@link #optimize(OptimizationData[]) optimize} will throw
  * {@link MathUnsupportedOperationException} if bounds are passed to it.
@@ -49,8 +49,6 @@
     private final Formula updateFormula;
     /** Preconditioner (may be null). */
     private final Preconditioner preconditioner;
-    /** Line search algorithm. */
-    private final LineSearch line;
 
     /**
      * Available choices of update formulas for the updating the parameter
@@ -78,50 +76,19 @@
     }
 
     /**
-     * Constructor with default tolerances for the line search (1e-8) and
-     * {@link IdentityPreconditioner preconditioner}.
-     *
-     * @param updateFormula formula to use for updating the &beta; parameter,
-     * must be one of {@link Formula#FLETCHER_REEVES} or
-     * {@link Formula#POLAK_RIBIERE}.
-     * @param checker Convergence checker.
-     */
-    public NonLinearConjugateGradientOptimizer(final Formula updateFormula,
-                                               ConvergenceChecker<PointValuePair> checker) {
-        this(updateFormula,
-             checker,
-             1e-8,
-             1e-8,
-             1e-8,
-             new IdentityPreconditioner());
-    }
-
-    /**
      * Constructor with default {@link IdentityPreconditioner preconditioner}.
      *
      * @param updateFormula formula to use for updating the &beta; parameter,
      * must be one of {@link Formula#FLETCHER_REEVES} or
      * {@link Formula#POLAK_RIBIERE}.
      * @param checker Convergence checker.
-     * @param relativeTolerance Relative threshold for line search.
-     * @param absoluteTolerance Absolute threshold for line search.
-     * @param initialBracketingRange Extent of the initial interval used to
-     * find an interval that brackets the optimum in order to perform the
-     * line search.
      *
-     * @see LineSearch#LineSearch(org.apache.commons.math4.legacy.optim.nonlinear.scalar.MultivariateOptimizer,double,double,double)
      * @since 3.3
      */
     public NonLinearConjugateGradientOptimizer(final Formula updateFormula,
-                                               ConvergenceChecker<PointValuePair> checker,
-                                               double relativeTolerance,
-                                               double absoluteTolerance,
-                                               double initialBracketingRange) {
+                                               ConvergenceChecker<PointValuePair> checker) {
         this(updateFormula,
              checker,
-             relativeTolerance,
-             absoluteTolerance,
-             initialBracketingRange,
              new IdentityPreconditioner());
     }
 
@@ -131,29 +98,16 @@
      * {@link Formula#POLAK_RIBIERE}.
      * @param checker Convergence checker.
      * @param preconditioner Preconditioner.
-     * @param relativeTolerance Relative threshold for line search.
-     * @param absoluteTolerance Absolute threshold for line search.
-     * @param initialBracketingRange Extent of the initial interval used to
-     * find an interval that brackets the optimum in order to perform the
-     * line search.
      *
-     * @see LineSearch#LineSearch(org.apache.commons.math4.legacy.optim.nonlinear.scalar.MultivariateOptimizer, double, double, double)
      * @since 3.3
      */
     public NonLinearConjugateGradientOptimizer(final Formula updateFormula,
                                                ConvergenceChecker<PointValuePair> checker,
-                                               double relativeTolerance,
-                                               double absoluteTolerance,
-                                               double initialBracketingRange,
                                                final Preconditioner preconditioner) {
         super(checker);
 
         this.updateFormula = updateFormula;
         this.preconditioner = preconditioner;
-        line = new LineSearch(this,
-                              relativeTolerance,
-                              absoluteTolerance,
-                              initialBracketingRange);
     }
 
     /**
@@ -190,6 +144,8 @@
             delta += r[i] * searchDirection[i];
         }
 
+        createLineSearch();
+
         PointValuePair current = null;
         while (true) {
             incrementIterationCount();
@@ -197,12 +153,13 @@
             final double objective = func.value(point);
             PointValuePair previous = current;
             current = new PointValuePair(point, objective);
-            if (previous != null && checker.converged(getIterations(), previous, current)) {
+            if (previous != null &&
+                checker.converged(getIterations(), previous, current)) {
                 // We have found an optimum.
                 return current;
             }
 
-            final double step = line.search(point, searchDirection).getPoint();
+            final double step = lineSearch(point, searchDirection).getPoint();
 
             // Validate new point.
             for (int i = 0; i < point.length; ++i) {
diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java
index 405c703..62cc2c7 100644
--- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java
+++ b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv/PowellOptimizer.java
@@ -25,7 +25,6 @@
 import org.apache.commons.math4.legacy.optim.ConvergenceChecker;
 import org.apache.commons.math4.legacy.optim.PointValuePair;
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType;
-import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearch;
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.MultivariateOptimizer;
 import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair;
 import org.apache.commons.math4.core.jdkmath.JdkMath;
@@ -41,8 +40,6 @@
  * to define a custom convergence checker that might terminate the algorithm
  * earlier.
  * <br>
- * Line search is performed by the {@link LineSearch} class.
- * <br>
  * Constraints are not supported: the call to
  * {@link #optimize(org.apache.commons.math4.legacy.optim.OptimizationData...)} will throw
  * {@link MathUnsupportedOperationException} if bounds are passed to it.
@@ -61,18 +58,14 @@
      * Minimum relative tolerance.
      */
     private static final double MIN_RELATIVE_TOLERANCE = 2 * JdkMath.ulp(1d);
-    /**
-     * Relative threshold.
-     */
+    /** Relative threshold. */
     private final double relativeThreshold;
-    /**
-     * Absolute threshold.
-     */
+    /** Absolute threshold. */
     private final double absoluteThreshold;
-    /**
-     * Line search.
-     */
-    private final LineSearch line;
+    /** Relative threshold. */
+    private final double lineSearchRelativeThreshold;
+    /** Absolute threshold. */
+    private final double lineSearchAbsoluteThreshold;
 
     /**
      * This constructor allows to specify a user-defined convergence checker,
@@ -120,14 +113,11 @@
         if (abs <= 0) {
             throw new NotStrictlyPositiveException(abs);
         }
+
         relativeThreshold = rel;
         absoluteThreshold = abs;
-
-        // Create the line search optimizer.
-        line = new LineSearch(this,
-                              lineRel,
-                              lineAbs,
-                              1d);
+        lineSearchRelativeThreshold = lineRel;
+        lineSearchAbsoluteThreshold = lineAbs;
     }
 
     /**
@@ -168,6 +158,9 @@
     protected PointValuePair doOptimize() {
         checkParameters();
 
+        // Line search optimizer.
+        createLineSearch();
+
         final GoalType goal = getGoalType();
         final double[] guess = getStartPoint();
         final MultivariateFunction func = getObjectiveFunction();
@@ -198,7 +191,7 @@
 
                 fX2 = fVal;
 
-                final UnivariatePointValuePair optimum = line.search(x, d);
+                final UnivariatePointValuePair optimum = lineSearch(x, d);
                 fVal = optimum.getValue();
                 alphaMin = optimum.getPoint();
                 final double[][] result = newPointAndDirection(x, d, alphaMin);
@@ -246,7 +239,7 @@
                 t -= delta * temp * temp;
 
                 if (t < 0.0) {
-                    final UnivariatePointValuePair optimum = line.search(x, d);
+                    final UnivariatePointValuePair optimum = lineSearch(x, d);
                     fVal = optimum.getValue();
                     alphaMin = optimum.getPoint();
                     final double[][] result = newPointAndDirection(x, d, alphaMin);
diff --git a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java
index 2e11372..114c48c 100644
--- a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java
+++ b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/MultiStartMultivariateOptimizerTest.java
@@ -44,10 +44,7 @@
         circle.addPoint(110.0, -20.0);
         circle.addPoint( 35.0,  15.0);
         circle.addPoint( 45.0,  97.0);
-        // TODO: the wrapper around NonLinearConjugateGradientOptimizer is a temporary hack for
-        // version 3.1 of the library. It should be removed when NonLinearConjugateGradientOptimizer
-        // will officially be declared as implementing MultivariateDifferentiableOptimizer
-        GradientMultivariateOptimizer underlying
+        final GradientMultivariateOptimizer underlying
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
                                                       new SimpleValueChecker(1e-10, 1e-10));
         final Supplier<double[]> generator = gaussianRandom(new double[] { 50, 50 },
@@ -62,12 +59,13 @@
                                  circle.getObjectiveFunctionGradient(),
                                  new NelderMeadTransform(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 98.680, 47.345 }));
+                                 new InitialGuess(new double[] { 98.680, 47.345 }),
+                                 new LineSearchTolerance(1e-10, 1e-10, 1));
         Assert.assertEquals(1000, optimizer.getMaxEvaluations());
-        PointValuePair[] optima = optimizer.getOptima();
+        final PointValuePair[] optima = optimizer.getOptima();
         Assert.assertEquals(nbStarts, optima.length);
         for (PointValuePair o : optima) {
-            // we check the results of all intermediate restarts here (there are 10 such results)
+            // Check the results of all intermediate restarts.
             Vector2D center = Vector2D.of(o.getPointRef()[0], o.getPointRef()[1]);
             Assert.assertEquals(69.9597, circle.getRadius(center), 1e-3);
             Assert.assertEquals(96.07535, center.getX(), 1.4e-3);
diff --git a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java
index 9864fcb..29820c2 100644
--- a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java
+++ b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/nonlinear/scalar/gradient/NonLinearConjugateGradientOptimizerTest.java
@@ -31,6 +31,7 @@
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.GoalType;
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.ObjectiveFunction;
 import org.apache.commons.math4.legacy.optim.nonlinear.scalar.ObjectiveFunctionGradient;
+import org.apache.commons.math4.legacy.optim.nonlinear.scalar.LineSearchTolerance;
 import org.junit.Assert;
 import org.junit.Test;
 
@@ -104,15 +105,15 @@
             = new LinearProblem(new double[][] { { 2 } }, new double[] { 3 });
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         optimizer.optimize(new MaxEval(100),
                            problem.getObjectiveFunction(),
                            problem.getObjectiveFunctionGradient(),
                            GoalType.MINIMIZE,
                            new InitialGuess(new double[] { 0 }),
                            new SimpleBounds(new double[] { -1 },
-                                            new double[] { 1 }));
+                                            new double[] { 1 }),
+                           new LineSearchTolerance(1e-3, 1e-3, 1));
     }
 
     @Test
@@ -121,14 +122,14 @@
             = new LinearProblem(new double[][] { { 2 } }, new double[] { 3 });
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0 }));
+                                 new InitialGuess(new double[] { 0 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertEquals(1.5, optimum.getPoint()[0], 1.0e-10);
         Assert.assertEquals(0.0, optimum.getValue(), 1.0e-10);
 
@@ -144,14 +145,14 @@
 
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0, 0 }));
+                                 new InitialGuess(new double[] { 0, 0 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertEquals(7.0, optimum.getPoint()[0], 1.0e-10);
         Assert.assertEquals(3.0, optimum.getPoint()[1], 1.0e-10);
         Assert.assertEquals(0.0, optimum.getValue(), 1.0e-10);
@@ -169,14 +170,14 @@
         }, new double[] { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5 });
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }));
+                                 new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         for (int i = 0; i < problem.target.length; ++i) {
             Assert.assertEquals(0.55 * i, optimum.getPoint()[i], 1.0e-10);
         }
@@ -191,14 +192,14 @@
         }, new double[] { 1, 1, 1});
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0, 0, 0 }));
+                                 new InitialGuess(new double[] { 0, 0, 0 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertEquals(1.0, optimum.getPoint()[0], 1.0e-10);
         Assert.assertEquals(2.0, optimum.getPoint()[1], 1.0e-10);
         Assert.assertEquals(3.0, optimum.getPoint()[2], 1.0e-10);
@@ -234,7 +235,6 @@
         NonLinearConjugateGradientOptimizer optimizer
            = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
                                                      new SimpleValueChecker(1e-13, 1e-13),
-                                                     1e-7, 1e-7, 1,
                                                      preconditioner);
 
         PointValuePair optimum
@@ -242,7 +242,8 @@
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }));
+                                 new InitialGuess(new double[] { 0, 0, 0, 0, 0, 0 }),
+                                 new LineSearchTolerance(1e-7, 1e-7, 1));
 
         final double[] result = optimum.getPoint();
         final double[] expected = {3, 4, -1, -2, 1 + epsilon, 1 - epsilon};
@@ -264,14 +265,14 @@
         }, new double[] { 1, 1, 1 });
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0, 0, 0 }));
+                                 new InitialGuess(new double[] { 0, 0, 0 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertTrue(optimum.getValue() > 0.5);
     }
 
@@ -285,14 +286,14 @@
         }, new double[] { 32, 23, 33, 31 });
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-13, 1e-13),
-                                                      1e-15, 1e-15, 1);
+                                                      new SimpleValueChecker(1e-13, 1e-13));
         PointValuePair optimum1
             = optimizer.optimize(new MaxEval(200),
                                  problem1.getObjectiveFunction(),
                                  problem1.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 0, 1, 2, 3 }));
+                                 new InitialGuess(new double[] { 0, 1, 2, 3 }),
+                                 new LineSearchTolerance(1e-15, 1e-15, 1));
         Assert.assertEquals(1.0, optimum1.getPoint()[0], 1.0e-4);
         Assert.assertEquals(1.0, optimum1.getPoint()[1], 1.0e-3);
         Assert.assertEquals(1.0, optimum1.getPoint()[2], 1.0e-4);
@@ -330,14 +331,14 @@
 
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 7, 6, 5, 4 }));
+                                 new InitialGuess(new double[] { 7, 6, 5, 4 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertEquals(0, optimum.getValue(), 1.0e-10);
     }
 
@@ -352,14 +353,14 @@
         }, new double[] { 3.0, 12.0, -1.0, 7.0, 1.0 });
         NonLinearConjugateGradientOptimizer optimizer
            = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                     new SimpleValueChecker(1e-6, 1e-6),
-                                                     1e-3, 1e-3, 1);
+                                                     new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 2, 2, 2, 2, 2, 2 }));
+                                 new InitialGuess(new double[] { 2, 2, 2, 2, 2, 2 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertEquals(0, optimum.getValue(), 1.0e-10);
     }
 
@@ -373,14 +374,14 @@
 
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 1, 1 }));
+                                 new InitialGuess(new double[] { 1, 1 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertEquals(2.0, optimum.getPoint()[0], 1.0e-8);
         Assert.assertEquals(1.0, optimum.getPoint()[1], 1.0e-8);
     }
@@ -395,14 +396,14 @@
 
         NonLinearConjugateGradientOptimizer optimizer
             = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                      new SimpleValueChecker(1e-6, 1e-6),
-                                                      1e-3, 1e-3, 1);
+                                                      new SimpleValueChecker(1e-6, 1e-6));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 1, 1 }));
+                                 new InitialGuess(new double[] { 1, 1 }),
+                                 new LineSearchTolerance(1e-3, 1e-3, 1));
         Assert.assertTrue(optimum.getValue() > 0.1);
     }
 
@@ -416,14 +417,14 @@
         problem.addPoint( 45.0,  97.0);
         NonLinearConjugateGradientOptimizer optimizer
            = new NonLinearConjugateGradientOptimizer(NonLinearConjugateGradientOptimizer.Formula.POLAK_RIBIERE,
-                                                     new SimpleValueChecker(1e-30, 1e-30),
-                                                     1e-15, 1e-13, 1);
+                                                     new SimpleValueChecker(1e-30, 1e-30));
         PointValuePair optimum
             = optimizer.optimize(new MaxEval(100),
                                  problem.getObjectiveFunction(),
                                  problem.getObjectiveFunctionGradient(),
                                  GoalType.MINIMIZE,
-                                 new InitialGuess(new double[] { 98.680, 47.345 }));
+                                 new InitialGuess(new double[] { 98.680, 47.345 }),
+                                 new LineSearchTolerance(1e-15, 1e-13, 1));
         Vector2D center = Vector2D.of(optimum.getPointRef()[0], optimum.getPointRef()[1]);
         Assert.assertEquals(69.960161753, problem.getRadius(center), 1.0e-8);
         Assert.assertEquals(96.075902096, center.getX(), 1.0e-7);