commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alexander Sehlström (JIRA) <j...@apache.org>
Subject [jira] [Updated] (MATH-966) Native support for upper and lower bound for SimplexSolver
Date Tue, 09 Apr 2013 09:48:18 GMT

     [ 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

Mime
View raw message