[
https://issues.apache.org/jira/browse/MATH-966?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alexander Sehlström updated MATH-966:
-------------------------------------
Description:
The SimplexSolver (import org.apache.commons.math3.optim.linear.SimplexSolver)
do not support lower and upper bounds as input arguments. It would be
convenient to have this support since this would be very helpful when dealing
with unconstrained problems (no Ax = c present) that has bounds on x (x_l <= x
<= x_u).
Attached is a piece of code in need for such a feature where a lot of fiddeling
is needed in order to convert the bounds (x_l <= x <= x_u) to constraints (Ax =
c).
was:
Using the SimplexSolver takes about twice as long as using Matlab's linprog to
solve s in min g'*s. Can it perhaps be related to the lack of support for lower
and upper bounds and thus the need to translate these into linear constraints?
In my simple test the number of elements in g is 640 making the number of
needed constraints at least 1280.
Test code below.
-------------------------
import java.util.ArrayList;
import java.util.Collection;
import org.apache.commons.lang3.time.StopWatch;
import org.apache.commons.math3.optim.MaxIter;
import org.apache.commons.math3.optim.PointValuePair;
import org.apache.commons.math3.optim.linear.LinearConstraint;
import org.apache.commons.math3.optim.linear.LinearConstraintSet;
import org.apache.commons.math3.optim.linear.LinearObjectiveFunction;
import org.apache.commons.math3.optim.linear.NonNegativeConstraint;
import org.apache.commons.math3.optim.linear.Relationship;
import org.apache.commons.math3.optim.linear.SimplexSolver;
public class simplextest {
/**
* Test of SimplexSolver.
*
* The code is the core part of an SLP solver implementation, see [1].
*
* The solution of the linear programming problem g( x )'*s takes around
* 7900-8000 ms to solve in Matlab using the method linprog. This code,
* using Apache Commons Math SimplexSolver, takes about twice that
amount
* of time to solve.
*
* [1] F. A. Gomes and T. A. Senne. An slp algorithm and its
application
* to topology optimization. Computational & Applied Mathematics,
* 30(1):53–89, 2011.
* @param args
*/
public static void main(String[] args) {
double delta = 1.0;
double xmax = 1.0;
double xmin = 0.0;
double[] x = new double[640];
for (int i = 0; i < x.length; i++) {
x[i] = 1.0;
}
double[] zeros = new double[x.length];
for (int i = 0; i < x.length; i++) {
zeros[i] = 0;
}
/*
----------------------------------------------------------------
* Starting from s_n, determine s_c, the solution of:
*
* min g( x )' * s
* s
* A * s = -c , (1)
* s.t.
* s_l <= s <= s_u
*
* where g( x ) is the vector of first order derivatives of f(
x ) with
* respect to xi, s is the step length to use for update of x,
A is
* a matrix of constraint coefficients and c a constraint
vector.
* The lower and upper bounds of s are defined as:
*
* s_l = max( -delta, xmin - x ),
(2)
* s_u = min( delta, xmax - x ),
(3)
*
* respectively.
*
*
----------------------------------------------------------------
*/
// Gradient g( x ) of objective function f( x ) at point x
LinearObjectiveFunction lof = new LinearObjectiveFunction(g, 0);
// Constraints A and -c
// - none present
// Boundaries s_l and s_u
double[] s_l = x;
double[] s_u = x;
for (int i = 0; i < x.length; i++) {
s_l[i] = Math.max(-delta, xmin-x[i]);
s_u[i] = Math.min( delta, xmax-x[i]);
}
Collection<LinearConstraint> constraints = new ArrayList();
for (int i = 0; i < s_l.length; i++) {
double[] coef = zeros;
coef[i] = 1;
constraints.add(new LinearConstraint(coef,
Relationship.GEQ, s_l[i]));
constraints.add(new LinearConstraint(coef,
Relationship.LEQ, s_u[i]));
}
LinearConstraintSet lcs = new LinearConstraintSet(constraints);
// We do allow negative values for of s_c.
NonNegativeConstraint nnc = new NonNegativeConstraint(false);
System.out.println("SIMPLEX start");
StopWatch timer = new StopWatch();
timer.start();
PointValuePair simplexresult = new SimplexSolver().optimize(new
MaxIter(10000), lof, lcs, nnc);
timer.stop();
System.out.println("SIMPLEX end. Time to run SimplexSolver: " +
timer.getTime() + " ms.");
double[] s_c = simplexresult.getPoint();
System.out.println("Value at s_c: " + simplexresult.getValue());
System.out.println("Length of s_c: " + s_c.length);
}
/** Dummy array (640 elements) representing the derivatives g( x )=df(
x )/dxi
* of the non-linear function f( x ) with respect to xi. */
static double[] g = new double[]{-0.00179316125791547,
-0.00186599920194353, -0.00178664129013447, -0.00172834318988362,
-0.00165493551015620, -0.00156954474458443, -0.00147547661946697,
-0.00137596812632366, -0.00127399344705111, -0.00117213674243999,
-0.00107253125613632, -0.000976854461020823, -0.000886364038180068,
-0.000801958844577927, -0.000724251400639756, -0.000653642381614435,
-0.000590392009466253, -0.000534687512440864, -0.000486709890166037,
-0.000446707576452747, -0.000415090362253781, -0.000392566321271314,
-0.000380361911386747, -0.000380600178293745, -0.000396987502358782,
-0.000436123675155918, -0.000510220276570089, -0.000642977980859036,
-0.000886484725177957, -0.00135679509189717, -0.00562276819635794,
-0.0191595618032286, -0.00151307608499047, -0.00153237469339673,
-0.00147805952938475, -0.00143273372829592, -0.00137541820877165,
-0.00130839745789250, -0.00123411650097137, -0.00115500449079890,
-0.00107333098575238, -0.000991105478058508, -0.000910021922839421,
-0.000831443101844780, -0.000756415569155893, -0.000685704654002937,
-0.000619839883536613, -0.000559163340282699, -0.000503876065214330,
-0.000454080075987688, -0.000409815561930811, -0.000371094174169918,
-0.000337929856875494, -0.000310367811313847, -0.000288508225582478,
-0.000272509711756259, -0.000262524099995362, -0.000258427571700508,
-0.000258987560113066, -0.000259821066494665, -0.000254390835493420,
-0.000425974629508607, -0.00255534143883473, -0.0109620233534384,
-0.00112264580308360, -0.00114537650292274, -0.00110630598199877,
-0.00107496368620859, -0.00103512135484872, -0.000988228992281026,
-0.000935861637210484, -0.000879610351846248, -0.000820988604990319,
-0.000761361916668301, -0.000701903743221047, -0.000643576149503307,
-0.000587130704636343, -0.000533123558920592, -0.000481938617542103,
-0.000433813635765152, -0.000388865373732924, -0.000347111209372436,
-0.000308485489701601, -0.000272849167178933, -0.000239990686770463,
-0.000209614391854502, -0.000181309905309488, -0.000154494452778694,
-0.000128335398892890, -0.000101781459644301, -7.45142971230458e-05,
-5.35671182621995e-05, -9.64926014247001e-05, -0.000484021608978086,
-0.00204706667090334, -0.00507046218262815, -0.000842355651835186,
-0.000860063875611195, -0.000832174854893145, -0.000810615332832421,
-0.000783047472712686, -0.000750368517191638, -0.000713571042684545,
-0.000673676357063250, -0.000631673158262868, -0.000588467914384774,
-0.000544850694472543, -0.000501477037723462, -0.000458863852762312,
-0.000417395832627965, -0.000377338503425087, -0.000338854506645859,
-0.000302020657587691, -0.000266844419940828, -0.000233279573314524,
-0.000201242182489371, -0.000170630143151868, -0.000141354390427814,
-0.000113402533926538, -8.69920997027506e-05, -6.29823434481471e-05,
-4.40749253337381e-05, -3.85280804682352e-05, -7.22236246367860e-05,
-0.000220969684538997, -0.000658393097919020, -0.00166792592022495,
-0.00287748054057287, -0.000619989705341423, -0.000633614326603474,
-0.000614439487893152, -0.000600420082684275, -0.000582327216795691,
-0.000560647447086371, -0.000535943839005291, -0.000508819472051920,
-0.000479877966011965, -0.000449687537327614, -0.000418753683378604,
-0.000387502912824729, -0.000356277314609483, -0.000325338055109085,
-0.000294875337928105, -0.000265022737807541, -0.000235874786118415,
-0.000207508017197561, -0.000180007426009980, -0.000153502885797583,
-0.000128224685899104, -0.000104596669252579, -8.34059266165646e-05,
-6.61356430532566e-05, -5.56628442110547e-05, -5.77958391736976e-05,
-8.47352956100101e-05, -0.000161968262169211, -0.000337267124727625,
-0.000677858016118388, -0.00125352288801923, -0.00181727839387283,
-0.000445822710572410, -0.000456279588722645, -0.000444002651372491,
-0.000435970442655630, -0.000425373247051020, -0.000412368630033536,
-0.000397189427761258, -0.000380129966611525, -0.000361519732337454,
-0.000341693261795331, -0.000320964284666239, -0.000299608925682763,
-0.000277859293155462, -0.000255906429060323, -0.000233910736454109,
-0.000212018326799110, -0.000190382774680734, -0.000169193224260711,
-0.000148711652298881, -0.000129324703081130, -0.000111619689486204,
-9.65017152463037e-05, -8.53824965173667e-05, -8.04969685044249e-05,
-8.54479479733677e-05, -0.000106139379780647, -0.000152205774088313,
-0.000238481204022165, -0.000384382729588834, -0.000607397699060511,
-0.000929157440629259, -0.00121239764021950, -0.000312810421983766,
-0.000320998103215957, -0.000314271079095216, -0.000311157439442976,
-0.000306637394078426, -0.000300575428266377, -0.000292936722527807,
-0.000283790437286008, -0.000273286501439029, -0.000261620874153266,
-0.000249002996990063, -0.000235633653217983, -0.000221695759190875,
-0.000207356950201331, -0.000192781499963858, -0.000178149429257919,
-0.000163681770092783, -0.000149672290065569, -0.000136527320242122,
-0.000124816678158331, -0.000115340143256491, -0.000109215557660088,
-0.000107995998775064, -0.000113822571744427, -0.000129609717280922,
-0.000159217921734550, -0.000207458920405824, -0.000279611898229467,
-0.000380197903268815, -0.000511492288073054, -0.000686672787185558,
-0.000830505140542277, -0.000215968898796825, -0.000222789177409525,
-0.000220616975845585, -0.000221704057851805, -0.000222219633444194,
-0.000221732795787804, -0.000219980875173261, -0.000216881582560336,
-0.000212497191039452, -0.000206979388657387, -0.000200518551400212,
-0.000193309936281498, -0.000185539298387848, -0.000177384830730118,
-0.000169030721394106, -0.000160688303422911, -0.000152622183571759,
-0.000145179960061244, -0.000138824764819668, -0.000134169695446436,
-0.000132011983570516, -0.000133361940522023, -0.000139456258535997,
-0.000151735523885414, -0.000171750205265864, -0.000200944045275930,
-0.000240282368585295, -0.000289838272007114, -0.000348789101813630,
-0.000416639984875088, -0.000505108733398081, -0.000573402215475515,
-0.000152002934108395, -0.000158396885083856, -0.000160070399012003,
-0.000164903330847974, -0.000169645787635637, -0.000173536918593667,
-0.000176121207725333, -0.000177250358565008, -0.000177006057860697,
-0.000175599899761348, -0.000173289934165475, -0.000170329625548041,
-0.000166948054294878, -0.000163352844422019, -0.000159746649012804,
-0.000156350159364635, -0.000153426973024077, -0.000151307123702159,
-0.000150406337858546, -0.000151237115888528, -0.000154405539946921,
-0.000160584285573442, -0.000170447975202046, -0.000184553364868932,
-0.000203149817592269, -0.000225930782734992, -0.000251814599094906,
-0.000278993851824329, -0.000305665876556779, -0.000331831600885956,
-0.000368094271102843, -0.000393433444851468, -0.000119141129544974,
-0.000126146349745362, -0.000131213389043487, -0.000139535366042881,
-0.000147786793125235, -0.000154823302608506, -0.000160059467808987,
-0.000163412273329558, -0.000165128409845619, -0.000165603428377815,
-0.000165251554658937, -0.000164437901120078, -0.000163459426595022,
-0.000162555132182854, -0.000161929564023584, -0.000161779301576029,
-0.000162316317789098, -0.000163784238509612, -0.000166463917057153,
-0.000170663919861244, -0.000176690087528617, -0.000184787123747788,
-0.000195045677972806, -0.000207273646913470, -0.000220846043821830,
-0.000234582221238297, -0.000246758263951231, -0.000255435057877523,
-0.000259318086352855, -0.000259264005550595, -0.000264297226977716,
-0.000265013613052089, -0.000117188969198881, -0.000126030407670937,
-0.000134295664628016, -0.000145971573196831, -0.000156906789102328,
-0.000165541546572207, -0.000171318154104493, -0.000174449968023966,
-0.000175557940464540, -0.000175366088647555, -0.000174523603134196,
-0.000173537140426740, -0.000172770693903743, -0.000172475802747864,
-0.000172829078783733, -0.000173965218003348, -0.000176000037748028,
-0.000179040780599975, -0.000183181527884962, -0.000188481333583791,
-0.000194922729153867, -0.000202349760041355, -0.000210389189203054,
-0.000218367673056281, -0.000225252941719306, -0.000229667647142815,
-0.000230045913657279, -0.000225015267454717, -0.000214078614482417,
-0.000198628893961797, -0.000185872463311066, -0.000173158637956436,
-0.000147892014069409, -0.000160128998490414, -0.000171661702318161,
-0.000186510679549303, -0.000198825119262455, -0.000206739849791212,
-0.000210110186204654, -0.000209851331660638, -0.000207238623146419,
-0.000203460624747153, -0.000199434567242435, -0.000195787688602216,
-0.000192909206399886, -0.000191017839132533, -0.000190220324964639,
-0.000190552915254540, -0.000192004621751627, -0.000194523049445504,
-0.000198003844654925, -0.000202264885440200, -0.000207007512163429,
-0.000211770262808443, -0.000215886283619821, -0.000218463364694338,
-0.000218412927901465, -0.000214556435101174, -0.000205829901249999,
-0.000191592336516339, -0.000172040392754460, -0.000148766828327793,
-0.000127193507584790, -0.000108321582019239, -0.000215870796690931,
-0.000233637114480792, -0.000248705204028062, -0.000266021765194871,
-0.000277127101273729, -0.000280421082375007, -0.000277029510504363,
-0.000269200599148399, -0.000259149258576067, -0.000248559135566648,
-0.000238531094218419, -0.000229701193537468, -0.000222384574739214,
-0.000216692040967536, -0.000212609597310620, -0.000210045048600296,
-0.000208848605300504, -0.000208813554296741, -0.000209661829970611,
-0.000211019151989214, -0.000212385958651043, -0.000213113870984506,
-0.000212402272633745, -0.000209333595230468, -0.000202964678154909,
-0.000192479637340578, -0.000177385555598506, -0.000157708374328803,
-0.000134157041553359, -0.000108314867909231, -8.40250827241755e-05,
-6.38730177020263e-05, -0.000330821856344745, -0.000357206540551032,
-0.000375801903679430, -0.000392940950043812, -0.000397143254423475,
-0.000388936548675663, -0.000372320853208807, -0.000351612929423879,
-0.000329970687014895, -0.000309299386116558, -0.000290582804647813,
-0.000274230047315910, -0.000260322210762756, -0.000248765327500168,
-0.000239374714148867, -0.000231914048284921, -0.000226105405237082,
-0.000221620873985684, -0.000218063209881626, -0.000214942284006475,
-0.000211655589247692, -0.000207484199691991, -0.000201618935228267,
-0.000193232055488450, -0.000181602777937830, -0.000166285363601067,
-0.000147277034863148, -0.000125115600815023, -0.000100853394870755,
-7.59710623272496e-05, -5.30246416578345e-05, -3.48078818074257e-05,
-0.000512975680264810, -0.000552461305583454, -0.000572133365646328,
-0.000580177709143267, -0.000564809101619692, -0.000533131164043702,
-0.000494402290438159, -0.000454845101774525, -0.000417666589473746,
-0.000384154719177542, -0.000354607572402909, -0.000328863597958817,
-0.000306581699223565, -0.000287373100420547, -0.000270853365808412,
-0.000256652201975826, -0.000244401254203445, -0.000233710859670152,
-0.000224142731660755, -0.000215184903905946, -0.000206236858539179,
-0.000196615569549442, -0.000185595534497415, -0.000172494727371384,
-0.000156809319422269, -0.000138378583870714, -0.000117528048987877,
-9.51079664290892e-05, -7.23540873648158e-05, -5.06119605775484e-05,
-3.14656679909297e-05, -1.70773381194177e-05, -0.000808300399244480,
-0.000866423690975748, -0.000871934550719600, -0.000843851293868146,
-0.000781339995813371, -0.000708146375110106, -0.000637499980490829,
-0.000574267761912054, -0.000519144580539970, -0.000471410082882976,
-0.000429965221522905, -0.000393749181640639, -0.000361867170424658,
-0.000333604427608985, -0.000308397304999710, -0.000285790954493627,
-0.000265394951614831, -0.000246841152195775, -0.000229746160297961,
-0.000213681523580232, -0.000198157038389392, -0.000182625472826614,
-0.000166519230376127, -0.000149328530362341, -0.000130722877840143,
-0.000110698884135798, -8.97066082373598e-05, -6.86721175985059e-05,
-4.88267895755548e-05, -3.13396140211478e-05, -1.71058549885329e-05,
-7.27526766985759e-06, -0.00134039901438356, -0.00141039994368175,
-0.00133300478177251, -0.00118491245843665, -0.00102958350486794,
-0.000896700534416294, -0.000789442890275047, -0.000702373154028037,
-0.000630373395990932, -0.000569414746837330, -0.000516589457649305,
-0.000469864697619275, -0.000427843465612414, -0.000389575039609661,
-0.000354414783951609, -0.000321921583443453, -0.000291781563827201,
-0.000263749641196686, -0.000237603687500172, -0.000213109339086861,
-0.000189996807533486, -0.000167954411077583, -0.000146646302772159,
-0.000125762482969541, -0.000105104978785547, -8.47015180583889e-05,
-6.49141031672829e-05, -4.64761107464792e-05, -3.03648206620035e-05,
-1.74533232662803e-05, -8.13379086441613e-06, -2.55159954089266e-06,
-0.00258627180457405, -0.00250137618458324, -0.00195484255121130,
-0.00153662238120018, -0.00125285448654837, -0.00106610254000956,
-0.000932284617726192, -0.000830107222964506, -0.000747462504860635,
-0.000677308827177823, -0.000615433157637744, -0.000559276936423189,
-0.000507281888773497, -0.000458512289360706, -0.000412428992925543,
-0.000368749287110940, -0.000327356215564530, -0.000288236512367131,
-0.000251434872298830, -0.000217017572618179, -0.000185042383196102,
-0.000155535232590640, -0.000128477497848929, -0.000103810524558320,
-8.14645433680479e-05, -6.14148705352320e-05, -4.37554633569646e-05,
-2.87548014972114e-05, -1.68229038326958e-05, -8.30052889245658e-06,
-3.10958090180413e-06, -6.72770895716317e-07, -0.00832255001108606,
-0.00424274442193861, -0.00247638718358205, -0.00171195662219939,
-0.00138817098112561, -0.00119748960629682, -0.00106724693089786,
-0.000967563934983282, -0.000884402193450427, -0.000810623372006699,
-0.000742412453540962, -0.000677696742710702, -0.000615374255627124,
-0.000554913951414177, -0.000496137979033326, -0.000439099014275024,
-0.000384009018008954, -0.000331195479582187, -0.000281070498825992,
-0.000234102748478256, -0.000190785256135679, -0.000151594660563358,
-0.000116941136217137, -8.71130169003498e-05, -6.22259834691107e-05,
-4.21919850235240e-05, -2.67244991270777e-05, -1.53884240690709e-05,
-7.67616641495416e-06, -3.04218086154891e-06, -8.16422345010389e-07,
-1.14831259829150e-07, -0.0196459292020271, -0.00671402038753640,
-0.00199059067873166, -0.00152369118511831, -0.00132304835587322,
-0.00120232622596864, -0.00111302282623110, -0.00103694392461811,
-0.000966548099501448, -0.000898390859751910, -0.000830899483427770,
-0.000763429292186035, -0.000695834159018391, -0.000628254817428942,
-0.000561012290923371, -0.000494555798795701, -0.000429440069959419,
-0.000366317267239957, -0.000305932667932765, -0.000249114402185169,
-0.000196747842860280, -0.000149726099194342, -0.000108870863274605,
-7.48238810418816e-05, -4.79193843069165e-05, -2.80615562404801e-05,
-1.46460044001636e-05, -6.57452098992910e-06, -2.40728437267621e-06,
-6.55802427409389e-07, -1.13844669352587e-07, -2.26070381807107e-08};
}
> Native support for upper and lower bound for SimplexSolver
> ----------------------------------------------------------
>
> Key: MATH-966
> URL: https://issues.apache.org/jira/browse/MATH-966
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 4.0, 3.1.1
> Reporter: Alexander Sehlström
> Priority: Minor
>
> The SimplexSolver (import
> org.apache.commons.math3.optim.linear.SimplexSolver) do not support lower and
> upper bounds as input arguments. It would be convenient to have this support
> since this would be very helpful when dealing with unconstrained problems (no
> Ax = c present) that has bounds on x (x_l <= x <= x_u).
> Attached is a piece of code in need for such a feature where a lot of
> fiddeling is needed in order to convert the bounds (x_l <= x <= x_u) to
> constraints (Ax = c).
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
