TomSym - Revision history

Elias at 12:43, 11 August 2011

2011-08-11T12:43:05Z

← Older revision		Revision as of 07:43, 11 August 2011
Line 11:		Line 11:
	For example, here we find a minimum to a second degree polynomial in two variables		For example, here we find a minimum to a second degree polynomial in two variables

	<~~nowiki~~>		<pre>
	>> toms a b		>> toms a b
	>> ezsolve(a^2 + 4b^2 + 3a - 2b - ab)		>> ezsolve(a^2 + 4b^2 + 3a - 2b - ab)
Line 34:		Line 34:
	a: -1.4667		a: -1.4667
	b: 0.0667		b: 0.0667
			</pre>

	</~~nowiki~~>

	Looking at the output from the solver, we see that <tt>ezsolve</tt> determined the problem type to be QP (quadratic programming) and selected CPLEX at the solver. The problem was then solved numerically and the solution is returned as a matlab structure with fields corresponding to the symbol names.		Looking at the output from the solver, we see that <tt>ezsolve</tt> determined the problem type to be QP (quadratic programming) and selected CPLEX at the solver. The problem was then solved numerically and the solution is returned as a matlab structure with fields corresponding to the symbol names.
Line 48:		Line 46:
	Symbolic matrices can be manipulated just like normal MATLAB matrices. For example, <tt></tt> gives the matrix product, and <tt>.</tt> gives the element-wise product of two matrices.		Symbolic matrices can be manipulated just like normal MATLAB matrices. For example, <tt></tt> gives the matrix product, and <tt>.</tt> gives the element-wise product of two matrices.

			<pre>
	>> A = tom('A',2,2)		>> A = tom('A',2,2)

Line 66:		Line 64:

	A*b		A*b
			</pre>


Line 73:		Line 71:
	Taking the derivative of a vector expression with respect to a vector symbol gives the so-called Jacobian matrix.		Taking the derivative of a vector expression with respect to a vector symbol gives the so-called Jacobian matrix.

			<pre>
	>> derivative(y,b)		>> derivative(y,b)

Line 79:		Line 77:

	A		A
			</pre>


	Derivatives involving matrices are computed as if the matrices were vectors, with elements taken in column-first order.		Derivatives involving matrices are computed as if the matrices were vectors, with elements taken in column-first order.

			<pre>
	>> derivative(y,A)		>> derivative(y,A)

Line 90:		Line 88:

	kron(b',eye(2))		kron(b',eye(2))
			</pre>


	A consequence of this definition is that the derivative of a matrix with respect to itself is the identity matrix.		A consequence of this definition is that the derivative of a matrix with respect to itself is the identity matrix.

			<pre>
	>> full(derivative(A,A))		>> full(derivative(A,A))

Line 104:		Line 101:
	0 0 1 0		0 0 1 0
	0 0 0 1		0 0 0 1
			</pre>


	==Vectorized code==		==Vectorized code==
Line 112:		Line 108:

	tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.		tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.


	[[Category:tomSym]]		[[Category:tomSym]]

Per: /* Interfaces */ moved to TomSym Interfaces

2011-07-28T07:28:56Z

Interfaces: moved to TomSym Interfaces

← Older revision		Revision as of 02:28, 28 July 2011
Line 112:		Line 112:

	tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.		tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.

	~~==Interfaces==~~

	TOMSYM is most commonly used for setting up optimization problems for the TOMLAB suite of numeric solvers. However, it is also possible to use it by itself to generate m-code or to interface it with your own code.

	~~===Generating m-code with TOMSYM===~~

	It is possible to convert any TOMSYM object into MATLAB code via the <tt>mcode</tt> and <tt>mfile</tt> commands. This makes it possible, for example, to use derivatives computed by TOMSYM in your own applications outside of TOMLAB.

	Because it is very inefficient to store large matrices as code, the <tt>mcode</tt>/<tt>mfile</tt> commands also return a cell array named <tt>tempD</tt> which contains the numeric data from the TOMSYM object. The <tt>tempD</tt> array must be provided whenever the code is executed.

	~~===Connection to TOMLAB===~~

	When TOMLAB is used without TOMSYM, optimization problems are represented via a <tt>Prob</tt> structure, which typically contain function handles to the objective and constraint functions, and ideally also their derivatives. TOMSYM uses a symbolic representation of the objective and constraints to create this <tt>Prob</tt> structure, including the m-code needed, and pass it directly to the solver. This and enables the user to focus on the modelling task rather than tedious implementation details such as coding up the derivative for each nonlinear constraint.

	Advanced users may extract the <tt>Prob</tt> structure from TOMSYM using the <tt>sym2prob</tt> function, and then manipulate this structure further before calling the solver. This makes it possible, for example, to optimize the autogenerated code, or set special solver flags.

	When the same problem needs to be re-solved many times for varying values of a parameter, the fastest way is usually to create the <tt>Prob</tt> structure once, and then change the parameter value using <tt>setparameter</tt>

	~~===Connection to PROPT===~~

	PROPT is a solver for dynamic optimization problems which uses a collocation mehtod. PROPT is based on TOMSYM, and uses the same symbolic engine. The output of PROPT's <tt>collocate</tt> family of functions is ordinary TOMSYM arrays which means that PROPT and TOMSYM code can be mixed freely.


	[[Category:tomSym]]		[[Category:tomSym]]

Per: /* What tomSym cannot do */ moved to What tomSym cannot do

2011-07-26T14:33:06Z

What tomSym cannot do: moved to What tomSym cannot do

← Older revision		Revision as of 09:33, 26 July 2011
Line 112:		Line 112:

	tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.		tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.

	~~==What tomSym cannot do==~~

	~~There are a few things that are possible in Matlab code, but which tomSym currently cannot do. Below we list the most common issues, and their work-arounds.~~

	~~===Variable-size matrixes===~~

	The size of a tomSym object cannot depend on the value of another tomSym object. This has to do with the fact that numeric solvers typically allocate memory only at the start of an optimization run, and then expect the number of unknowns to remain constant. (This may change in the future.)

	~~===Indexes into double arrays===~~

	~~===Replacing values in arrays===~~

	~~===Conditional execution===~~

	~~===N-dimensional arrays for N > 2===~~

	TOMSYM works with scalars, vectors, and two-dimensional matrices. Although Matlab can handle arrays of any dimension, TOMSYM cannot. The work-around is to use tomArray, which transforms tomSym symbols into arrays of any dimension. (TomArray also allows for a GAMS-style indexing which is a bit different from Matlab syntax, but convenient when formulating optimization problems involving high-dimension arrays.)

	~~Note that TOMSYM supports <tt>interpn</tt> with high-dimensional numeric data, although the symbolic inputs must be of dimension less than two.~~

	~~===Limits===~~

	TOMSYM evaluates expressions by generating matlab code. (It does some mathematical simplification to improve efficiency, but only to a limited extent.) If an expression evaluates to 0/0 or 0*Inf, then NaN (Not a Number) will be returned. When the solver encounters a NaN, it will often just quit (although some solvers include back-tracking algorithms.)

	This means that expressions such as <tt>a*log(a)</tt> can not be used if <tt>a</tt> might become zero. In this case it might be prudent to add a constraint <tt>a >= 1e-8</tt> (or similar) to help the solver stay out of trouble.

	==Interfaces==		==Interfaces==

Per: /* Improving speed */ moved to Improving the speed of tomSym

2011-07-26T14:26:10Z

Improving speed: moved to Improving the speed of tomSym

← Older revision		Revision as of 09:26, 26 July 2011
Line 161:		Line 161:
	PROPT is a solver for dynamic optimization problems which uses a collocation mehtod. PROPT is based on TOMSYM, and uses the same symbolic engine. The output of PROPT's <tt>collocate</tt> family of functions is ordinary TOMSYM arrays which means that PROPT and TOMSYM code can be mixed freely.		PROPT is a solver for dynamic optimization problems which uses a collocation mehtod. PROPT is based on TOMSYM, and uses the same symbolic engine. The output of PROPT's <tt>collocate</tt> family of functions is ordinary TOMSYM arrays which means that PROPT and TOMSYM code can be mixed freely.

	~~==Improving speed==~~

	Speed is often important when solving optimization problems. The main advantage of tomSym is that it allows for high overall speed. The time it takes from the moment you start coding until the solution presented should be as short as possible. Often, much more time is spent coding than numerically solving the problem, so emphasis should be placed on writing code that is easy to read and debug. Sometimes, however, the time used by the numerical solver is critical, and this section gives som hints on how to make it run faster.

	~~===Pre-process the symbolic problem===~~

	~~See <tt>tomsym_mpc.m</tt>~~

	~~===Avoid loops===~~

	~~Manipulating tomSym expressons inside a loop can be very slow. For example, the following loop generates a long symbolic expression.~~


	~~>> v = tom('v',1,10);~~
	~~>> s = 0;~~
	~~>> for i = 1:length(v); s = s+v(i); end~~
	~~>> disp(s);~~
	~~((((((((v(1)+v(2))+v(3))+v(4))+v(5))+v(6))+v(7))+v(8))+v(9))+v(10)~~



	~~In this case, the loop can simply be replaced by <tt>s = sum(v)</tt>, which will run much faster.~~

	~~===Use separate symbols for separate things===~~

	It is common in some optimization frameworks to use a single vector <tt>x</tt> for all the optimization variables, and then using indexes to represent different things. (<tt>x(1)</tt> is position in m, <tt>x(2)</tt> is speed in m/s, etc.)

	Doing this in tomSym is a bad idea for several reasons. The generated code will be less efficient, because tomSym tries to generated derivatives with respect to the whole vector but it is only used one element at a time. Automatic scaling will not work as expected, becuase tomSym tries to scale the entire vector by one factor, when the individual elements may have different magnintude.

	~~Also, it is much easier to read code that uses <tt>x</tt> for position and <tt>v</tt> for speed, than code that uses <tt>x</tt> for both.~~

	~~===Don't vectorize expressions that don't belong together===~~

	~~It is faster say <tt>{ x >= 0, cos(x) >= 0.5 }</tt> than [<tt>x; cos(x)</tt>]<tt> >= </tt>[<tt> 0; 0.5 </tt>].~~

	Here we have one linear constraint and one nonlinar constraint. Normally, the solver will handle these separately, and linear constraints are treated much more efficiently than nonlinear ones. But if they are combined into a nonlinear constraint with two components, then both are handled by the nonlinear part of the solver.

	~~===Avoid using <tt>abs</tt> and <tt>max</tt>===~~

	It is much more efficient to say <tt>{ v >= -1, v <= 1 }</tt> than <tt>{ max(abs(v)) <= 1 }</tt>. Again, this is because linear constraints are treated more efficiently than nonlinear ones. For the same reason it is faster to minimize <tt>y</tt> under the constraint <tt>{ v >= -y, v <= y }</tt> than to minimize <tt>max(abs(x))</tt>.

	~~The <tt>rewriteV</tt> function (called by <tt>ezsolve</tt>) attempts to get rid of instances of <tt>abs</tt> and <tt>max</tt>, but it is only able to handle simple cases.~~

	~~===Don't put equations in the objective===~~

	Using an objective that requires solving equations, such as <tt>sum((Ab).^2))</tt> is very inefficient. A better way to handle this is to rewrite the objective as <tt>sum(x.^2)</tt> and add the constraint <tt>A*x==b</tt>. This formulation gives much more information to the solver, and avoids having to compute the derivative of the solution to an equation (which is numerically unstable.)

	~~For this reason, functions like <tt>fzero</tt> should never be used with tomSym. The function <tt>tomfzero</tt> can often be used in its place.~~

	~~===Balance the scale===~~

	~~Equations like <tt>a/1000000 + b ==1</tt> don't work well with numeric solvers, because <tt>a</tt> and <tt>b</tt> will have very different magnitudes in the solution.~~

	One way to overcome this problem is to set <tt>OPTIONS.scale = 'auto'</tt>, which will cause <tt>ezsolve</tt> to try to guess a scaling factor for each unknown. This works best if each variable has been given reasonable upper and lower bounds.

	Another way to fix the problem is to use scaled variable from the start. For example, if we use the scaled variable <tt>as</tt>, and let <tt>a</tt> equal <tt>1000000*as</tt>, then the equation becomes <tt>as + b ==1</tt>, which is well-scaled.

	~~===Multiply rather than divide===~~

	Multiplication is "less nonlinear" than division. Hence, equations like <tt>mx ==f</tt> typically result in better convergence than <tt>x ==f/m</tt>. This is particularly true for matrices: <tt>Mx ==f</tt> can be much faster than <tt>x ==Mf</tt>.

	~~This method also prevents the problem where the solver shuts down because of a division-by-zero. (However, if <tt>m</tt> is zero then <tt>f==</tt> is a solution, so watch out!)~~

	[[Category:tomSym]]		[[Category:tomSym]]

Per: /* Don't vectorize expressions that don't belong together */

2011-07-26T14:15:03Z

Don't vectorize expressions that don't belong together

← Older revision		Revision as of 09:15, 26 July 2011
Line 196:		Line 196:
	It is faster say <tt>{ x >= 0, cos(x) >= 0.5 }</tt> than [<tt>x; cos(x)</tt>]<tt> >= </tt>[<tt> 0; 0.5 </tt>].		It is faster say <tt>{ x >= 0, cos(x) >= 0.5 }</tt> than [<tt>x; cos(x)</tt>]<tt> >= </tt>[<tt> 0; 0.5 </tt>].

	~~In the first case~~ we have one linear constraint and one nonlinar constraint. ~~The~~ solver will handle these separately, and linear constraints are treated much more efficiently than nonlinear ones. ~~In the second case we have~~ a nonlinear constraint with two components~~. TomSym is unable to separate the linear component~~, so both are handled by the nonlinear part of the solver.		Here we have one linear constraint and one nonlinar constraint. Normally, the solver will handle these separately, and linear constraints are treated much more efficiently than nonlinear ones. But if they are combined into a nonlinear constraint with two components, then both are handled by the nonlinear part of the solver.

	===Avoid using <tt>abs</tt> and <tt>max</tt>===		===Avoid using <tt>abs</tt> and <tt>max</tt>===

Per at 14:10, 26 July 2011

2011-07-26T14:10:23Z

← Older revision		Revision as of 09:10, 26 July 2011
Line 223:		Line 223:

	This method also prevents the problem where the solver shuts down because of a division-by-zero. (However, if <tt>m</tt> is zero then <tt>f==</tt> is a solution, so watch out!)		This method also prevents the problem where the solver shuts down because of a division-by-zero. (However, if <tt>m</tt> is zero then <tt>f==</tt> is a solution, so watch out!)

			[[Category:tomSym]]

Per: /* Supported functions */ moved to TomSym - Supported Functions

2011-07-26T14:09:40Z

Supported functions: moved to TomSym - Supported Functions

Show changes

Per: /* Complex numbers */ moved to TomCmplx

2011-07-26T14:02:44Z

Complex numbers: moved to TomCmplx

← Older revision		Revision as of 09:02, 26 July 2011
Line 112:		Line 112:

	tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.		tomSym is intended for use with vectorized code. It supports all the functions that are typically needed to generated vectorized expressions, such as <tt>sum</tt>, <tt>diff</tt>, <tt>repmat</tt>, <tt>sparse</tt>, etc.

	~~==Complex numbers==~~

	~~The solvers in the TOMLAB suite work with real numbers. Still, some equations are more easily expressed using complex numbers.~~

	~~The tomCmplx class makes it possible to represent symbolic complex expressions as pairs of ordinary tomSym expressions. For example:~~


	~~>> toms a b~~
	~~>> z = tomCmplx(a,b)~~

	~~z = tomCmplx(1x1):~~
	~~Real part:~~
	a

	~~Imaginary part:~~
	b

	~~>> z2 = z.*z~~

	~~z2 = tomCmplx(1x1):~~
	~~Real part:~~
	~~aa-bb~~

	~~Imaginary part:~~
	~~ab+ba~~



	The set of operations allowed for tomCmplx expressions is currently very limited. Element-wise addition, subtraction, multiplication, division and exponentiation are supported, as are <tt>real()</tt>, <tt>imag()</tt>, <tt>abs()</tt> and <tt>angle()</tt> which return real-valued tomSym expressions.

	If a tomCmplx is used in an equation, then a cell array of two equations is generated; One for the real and one for the imaginary component. A complex number can never be used in an inequality, so <tt><=</tt> and <tt>>=</tt> are not supported for tomCmplx. (But inequalities can be used on the real and imaginary parts, as those are normal tomSym expressions.)

	==What tomSym cannot do==		==What tomSym cannot do==

Per: /* Complex numbers */

2011-07-26T14:01:39Z

Complex numbers

← Older revision		Revision as of 09:01, 26 July 2011
Line 141:		Line 141:


	The set of operations allowed for tomCmplx expressions is currently very limited. Element-wise addition, subtraction, multiplication and ~~division~~ are supported, as are <tt>real()</tt>, <tt>imag()</tt>, <tt>abs()</tt> and <tt>angle()</tt> which return real-valued tomSym expressions.		The set of operations allowed for tomCmplx expressions is currently very limited. Element-wise addition, subtraction, multiplication, division and exponentiation are supported, as are <tt>real()</tt>, <tt>imag()</tt>, <tt>abs()</tt> and <tt>angle()</tt> which return real-valued tomSym expressions.

	If a tomCmplx is used in an equation, then a cell array of two equations is generated; One for the real and one for the imaginary component. A complex number can never be used in an inequality, so <tt><=</tt> and <tt>>=</tt> are not supported for tomCmplx.		If a tomCmplx is used in an equation, then a cell array of two equations is generated; One for the real and one for the imaginary component. A complex number can never be used in an inequality, so <tt><=</tt> and <tt>>=</tt> are not supported for tomCmplx. (But inequalities can be used on the real and imaginary parts, as those are normal tomSym expressions.)

	==What tomSym cannot do==		==What tomSym cannot do==

Per: /* Frequently Asked Questions */ moved to TomSym FAQ

2011-07-26T13:59:13Z

Frequently Asked Questions: moved to TomSym FAQ

← Older revision		Revision as of 08:59, 26 July 2011
Line 255:		Line 255:

	This method also prevents the problem where the solver shuts down because of a division-by-zero. (However, if <tt>m</tt> is zero then <tt>f==</tt> is a solution, so watch out!)		This method also prevents the problem where the solver shuts down because of a division-by-zero. (However, if <tt>m</tt> is zero then <tt>f==</tt> is a solution, so watch out!)

	~~==Frequently Asked Questions==~~

	~~===Can I be sure that TOMLAB will always return a solution to my optimization problem?===~~

	-No. Although there are certain subclasses of problems, such as Linear Programming (LP) and Quadratic Programming (QP), where convergence is guaranteed (with upper bounds on the computation time), in the general case there is no guarantee that a given problem can be solved in any reasonable amount of time, nor that the returned solution is a global optimum.

	However, TOMLAB has a large collection of powerful solvers, and is often able to solve problems that are considered extremely hard as long as the optimization parameters are choosen correctly. (If you run into problems, don't hesitate to contact our support team. See our website http://tomopt.comor contact info.)

	~~===TOMSYM says that "the returned solution may be incorrect". What's wrong?===~~

	~~TOMSYM gives this warning message whenever the numeric solver returned any kind of error or warning. Look at the output from the solver for clues.~~

	If the solver says that the problem was ïnfeasible", then there is likely a problem with the constraints. Try removing or relaxing constraints one at a time to pinpoint the problem. The <tt>feasibilitycheck</tt> function can also be useful in diagnosing the problem and finding a feasible initial point.

	If the solver determines that the problem is ünbounded", then there are either not enough constraints, or the objective function is incorrect. Remember that TOMSYM alwasy assumes a minimization problem, so for maximization problems a minus sign must be put in front of the objective.

	If the solver stoped because the maximum number of iterations was exceeded, then there is likely something wrong with the scaling of the problem. Are some variables/equations thousands of times larger than others? Setting <tt>options.scale = 'auto'</tt> might help. Another likely cause of the problem is that the initial guess is not good enough. Try supplying a better guess.

	If the solver "terminated during ... evaluation" then your objective or equations (or their derivatives) has a numeric problem, such as division by zero. Try to rewrite your code to avoid division by zero, set stricter bounds so that this does not occur, or switch to a more robust solver.

	~~===How can I know when tomSym is used instead of Matlab's own routines?===~~

	TomSym routines are ''overloaded'' which means that they will be used whenever a tomSym object is part of a function call. For example, if <tt>x</tt> is a tomSym symbol (or expression), then a function call such as <tt>sin(x)</tt> will use the tomSym version of the <tt>sin</tt> function, and the returned object will be another tomSym expression.

	~~On the other hand, calling <tt>sin(0.5)</tt> will use Matlab's own <tt>sin</tt> function, even if TOMLAB is installed.~~

	==Supported functions==		==Supported functions==