com.net2plan.utils

Class GradientProjectionUtils

java.lang.Object

com.net2plan.utils.GradientProjectionUtils

public class GradientProjectionUtils
extends Object

Auxiliary static methods to solve some simple optimization problems (e.g. the projection of a vector in some sets defined with simple linear constraints) by means of relatively simple algorithms devised by applying the KKT conditions on the problem. Gradient algorithms can use these methods to solve some projections or regularizations.

Author:

Pablo Pavon-Marino

See Also:

Java Optimization Modeler (JOM) website, JGraphT website, Java Universal Network/Graph Framework (JUNG) website

Constructor Summary

Constructors

Constructor and Description
GradientProjectionUtils()

Method Summary

Modifier and Type	Method and Description
static double	euclideanProjection_boxLike(double x_k, double xMin, double xMax) Projects a value x_0 into an interval [xMin , xMax].
static double	euclideanProjection_boxLikeLowerBound(double x_k, double xMin) Projects a value x_0 into an interval [xMin , inf].
static double	euclideanProjection_boxLikeUpperBound(double x_k, double xMax) Projects a value x_0 into an interval [inf , xMax].
static void	euclideanProjection_sumEquality(DoubleMatrix1D inAndOut_x, double vectorSum) Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k = C, x_k >= 0.
static void	euclideanProjection_sumEquality(DoubleMatrix1D inAndOut_x, int[] coordinatesToConsider, double vectorSum) Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k = C, x_k >= 0.
static void	euclideanProjection_sumInequality(DoubleMatrix1D inAndOut_x, double xMin, double vectorSum) Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k <= C, x_k >= xMin.
static void	euclideanProjection_sumInequality(DoubleMatrix1D inAndOut_x, int[] coordinatesToConsider, double xMin, double vectorSum) Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k <= C, x_k >= xMin.
static void	euclideanProjection_sumInequality(DoubleMatrix1D inAndOut_x, int[] coordinatesToConsider, DoubleMatrix1D xMin_k, double vectorSum) Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k <= C, x_k >= xMin_k.
static DoubleMatrix1D	regularizedProjection_sumEquality(DoubleMatrix1D a_k, int[] coordinatesToConsider, DoubleMatrix1D xMin_k, double vectorSum, double epsilon) Using a simple algorithm, finds the vector x which minimizes \sum_k a_k x_k + epsilon * x_l^2, subject to: x_k >= xMin_k, \sum_k x_k = C.
static double	scaleDown_maxAbsoluteCoordinateChange(double x0, double x, double maxAbsDifference) If x differs in absolute value less than maxAbsDifference, x as it is, is returned.
static void	scaleDown_maxAbsoluteCoordinateChange(DoubleMatrix1D x0_k, DoubleMatrix1D inAndOut_x, int[] coordinateKeysToConsider, double maxAbsDifference) If all the selected coordinates in x_k differ in absolute value less than maxAbsDifference respect to x_0, the vector x_k as it is, is returned.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GradientProjectionUtils

public GradientProjectionUtils()

Method Detail

euclideanProjection_boxLike

public static double euclideanProjection_boxLike(double x_k,
                                                 double xMin,
                                                 double xMax)

Projects a value x_0 into an interval [xMin , xMax].

Parameters:

x_k - The input value to project

xMin - The interval lower value

xMax - The interval upper value

Returns:

the projected value. Equivalent to max(xMin, min (xMax,x_k))

euclideanProjection_boxLikeLowerBound

public static double euclideanProjection_boxLikeLowerBound(double x_k,
                                                           double xMin)

Projects a value x_0 into an interval [xMin , inf].

Parameters:

x_k - The input value to project

xMin - The interval lower value

Returns:

the projected value. Equivalent to max(xMin, ,x_k)

euclideanProjection_boxLikeUpperBound

public static double euclideanProjection_boxLikeUpperBound(double x_k,
                                                           double xMax)

Projects a value x_0 into an interval [inf , xMax].

Parameters:

x_k - The input value to project

xMax - The interval upper value

Returns:

the projected value. Equivalent to min(xMax, ,x_k)

euclideanProjection_sumEquality

public static void euclideanProjection_sumEquality(DoubleMatrix1D inAndOut_x,
                                                   double vectorSum)

Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k = C, x_k >= 0.

Parameters:

inAndOut_x - The input vector x0_k. The euclidean projection (output of the algorithm) is returned writing in this variable.

vectorSum - The C constant.

euclideanProjection_sumEquality

public static void euclideanProjection_sumEquality(DoubleMatrix1D inAndOut_x,
                                                   int[] coordinatesToConsider,
                                                   double vectorSum)

Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k = C, x_k >= 0.

Parameters:

inAndOut_x - The input vector x0_k. The euclidean projection (output of the algorithm) is returned writing in this variable.

coordinatesToConsider - The vector x0_k and x_k to consider is given by the input vector inAndOut_x, restricted to these coordinates. If null all the vector coordinates are selected.

vectorSum - The C constant.

euclideanProjection_sumInequality

public static void euclideanProjection_sumInequality(DoubleMatrix1D inAndOut_x,
                                                     double xMin,
                                                     double vectorSum)

Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k <= C, x_k >= xMin.

Parameters:

inAndOut_x - The input vector x0_k. The euclidean projection (output of the algorithm) is returned writing in this variable.

xMin - The xMin constant.

vectorSum - The C constant.

euclideanProjection_sumInequality

public static void euclideanProjection_sumInequality(DoubleMatrix1D inAndOut_x,
                                                     int[] coordinatesToConsider,
                                                     double xMin,
                                                     double vectorSum)

Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k <= C, x_k >= xMin.

Parameters:

inAndOut_x - The input vector x0_k. The euclidean projection (output of the algorithm) is returned writing in this variable.

coordinatesToConsider - The vector x0_k and x_k to consider is given by the input vector inAndOut_x, restricted to these coordinates. If null all the vector coordinates are selected.

xMin - The xMin constant.

vectorSum - The C constant.

euclideanProjection_sumInequality

public static void euclideanProjection_sumInequality(DoubleMatrix1D inAndOut_x,
                                                     int[] coordinatesToConsider,
                                                     DoubleMatrix1D xMin_k,
                                                     double vectorSum)

Using a simple algorithm, finds the euclidean projection of the input vector x0_k, to the set: sum x_k <= C, x_k >= xMin_k.

Parameters:

inAndOut_x - The input vector x0_k. The euclidean projection (output of the algorithm) is returned writing in this variable.

coordinatesToConsider - The vector x0_k and x_k to consider is given by the input vector inAndOut_x, restricted to these coordinates. If null all the vector coordinates are selected.

xMin_k - The xMin_k vector of constant lower bounds.

vectorSum - The C constant.

regularizedProjection_sumEquality

public static DoubleMatrix1D regularizedProjection_sumEquality(DoubleMatrix1D a_k,
                                                               int[] coordinatesToConsider,
                                                               DoubleMatrix1D xMin_k,
                                                               double vectorSum,
                                                               double epsilon)

Using a simple algorithm, finds the vector x which minimizes \sum_k a_k x_k + epsilon * x_l^2, subject to: x_k >= xMin_k, \sum_k x_k = C.

Parameters:

a_k - The input vector a_k.

coordinatesToConsider - The selected coordinates to consider in the vectors a_k and xMin. If null, all the vector coordinates are selected

xMin_k - The xMin_k vector of constant lower bounds. If null, a vector of zeros

vectorSum - The C constant.

epsilon - The epsilon value

Returns:

The with the solution of the problem

scaleDown_maxAbsoluteCoordinateChange

public static double scaleDown_maxAbsoluteCoordinateChange(double x0,
                                                           double x,
                                                           double maxAbsDifference)

If x differs in absolute value less than maxAbsDifference, x as it is, is returned. If not, x is scaled down by the value which makes the maximum value of |x - x_0| become maxAbsDifference.

Parameters:

x0 - the x0 value

x - the x value

maxAbsDifference - the maximum absoulute value difference

Returns:

the scaled value

scaleDown_maxAbsoluteCoordinateChange

public static void scaleDown_maxAbsoluteCoordinateChange(DoubleMatrix1D x0_k,
                                                         DoubleMatrix1D inAndOut_x,
                                                         int[] coordinateKeysToConsider,
                                                         double maxAbsDifference)

If all the selected coordinates in x_k differ in absolute value less than maxAbsDifference respect to x_0, the vector x_k as it is, is returned. If not, all the selected coordinates of x_k are scaled down by the value which makes the maximum value of |x_k - x_0| become maxAbsDifference.

Parameters:

x0_k - the x0_k vector

inAndOut_x - The vector x_k, used as input. The output is written also here

coordinateKeysToConsider - The vector x0_k and x_k to consider is given by the input vector inAndOut_x, restricted to these coordinates

maxAbsDifference - The maximum absolute difference allowed in the selected coordinates of x_k, respect to x_0