Non-proprietary Optimization - Revision history

Jpye at 04:36, 25 July 2010

2010-07-25T04:36:38Z

← Older revision		Revision as of 04:36, 25 July 2010
Line 4:		Line 4:

	We are trying to locate a suitable non-commercial optimizer to build into ASCEND. This would alleviate the current dependence on the proprietary [[CONOPT]] optimizer.		We are trying to locate a suitable non-commercial optimizer to build into ASCEND. This would alleviate the current dependence on the proprietary [[CONOPT]] optimizer.

	~~This task is currently being worked on by a [http://socghop.appspot.com/org/home/google/gsoc2009/ascend Google Summer of Code student].~~

	== Requirements for New Optimizer ==		== Requirements for New Optimizer ==

Jpye at 10:21, 21 July 2010

2010-07-21T10:21:39Z

← Older revision		Revision as of 10:21, 21 July 2010
Line 1:		Line 1:
	{{~~task~~}}		{{outdated}}

			'''See [[IPOPT]] for our recently-implemented connection to the free, open-source IPOPT solver.'''

	We are trying to locate a suitable non-commercial optimizer to build into ASCEND. This would alleviate the current dependence on the proprietary [[CONOPT]] optimizer.		We are trying to locate a suitable non-commercial optimizer to build into ASCEND. This would alleviate the current dependence on the proprietary [[CONOPT]] optimizer.

Jpye at 10:20, 21 July 2010

2010-07-21T10:20:53Z

← Older revision		Revision as of 10:20, 21 July 2010
Line 4:		Line 4:

	This task is currently being worked on by a [http://socghop.appspot.com/org/home/google/gsoc2009/ascend Google Summer of Code student].		This task is currently being worked on by a [http://socghop.appspot.com/org/home/google/gsoc2009/ascend Google Summer of Code student].



	== Requirements for New Optimizer ==		== Requirements for New Optimizer ==

	Mathematical/algorithm requirements:		Mathematical/algorithm requirements:


	* Must be able to handle 'box constraints', eg <math>a \le x \le b</math> for each variable.		* Must be able to handle 'box constraints', eg <math>a \le x \le b</math> for each variable.
Line 19:		Line 16:

	Open questions:		Open questions:


	* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?		* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?
Line 27:		Line 23:

	Supporting information requirements:		Supporting information requirements:


	* Should be known to solve a range of comparable problems to those which we expect to encounter		* Should be known to solve a range of comparable problems to those which we expect to encounter
Line 36:		Line 31:

	Pedantic legal stuff:		Pedantic legal stuff:


	* Must be freely available to academics		* Must be freely available to academics
Line 50:		Line 44:

	Related stuff:		Related stuff:


	* [http://en.wikipedia.org/wiki/Hessian_matrix Hessian matrix]		* [http://en.wikipedia.org/wiki/Hessian_matrix Hessian matrix]
Line 60:		Line 53:

	We have done our own cursory [[survey of optimisation software]]		We have done our own cursory [[survey of optimisation software]]


	== TRON ==		== TRON ==
Line 74:		Line 66:

	The following are observations:		The following are observations:


	* TRON requires that you write your own iteration loop ''outside'' TRON itself.		* TRON requires that you write your own iteration loop ''outside'' TRON itself.
Line 95:		Line 86:

	It is emphasised that solving equality constraints is done just by setting elements of <math>\mathbf{c}_L</math> and <math>\mathbf{c}_U</math> equal to each other.		It is emphasised that solving equality constraints is done just by setting elements of <math>\mathbf{c}_L</math> and <math>\mathbf{c}_U</math> equal to each other.


	IPOPT supports a number of linear solvers including the HSL routine MA27, but also MUMPS, which is a free open source solver. So it is now possible to distribute a full working copy of IPOPT with ASCEND. It is also possible to have 'drop-in' support for HSL, because IPOPT can detect and dlopen HSL at runtime, if present.		IPOPT supports a number of linear solvers including the HSL routine MA27, but also MUMPS, which is a free open source solver. So it is now possible to distribute a full working copy of IPOPT with ASCEND. It is also possible to have 'drop-in' support for HSL, because IPOPT can detect and dlopen HSL at runtime, if present.
Line 101:		Line 91:
	Download/build instructions are here:		Download/build instructions are here:
	[http://www.coin-or.org/Ipopt/documentation/node18.html]		[http://www.coin-or.org/Ipopt/documentation/node18.html]


	== MOOCHO / rSQP++ ==		== MOOCHO / rSQP++ ==
Line 111:		Line 100:

	The support for generic linear algebra routines is also now deprecated, and they are going for all-out integration with the other Trilinos packages. That means there's quite a lot to learn about. It's a bit daunting -- if anyone else fancies helping out, by all means, please do.		The support for generic linear algebra routines is also now deprecated, and they are going for all-out integration with the other Trilinos packages. That means there's quite a lot to learn about. It's a bit daunting -- if anyone else fancies helping out, by all means, please do.





	~~[[Category:Proposed]]~~

Jpye: Reverted edits by VerlieBoss (Talk) to last revision by UploadBot

2010-07-21T10:19:43Z

Reverted edits by VerlieBoss (Talk) to last revision by UploadBot

← Older revision		Revision as of 10:19, 21 July 2010
Line 21:		Line 21:


	* [http://www.superiorpapers.com/ custom papers]
	* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?		* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?
	* Should ''not'' assume convex problem?		* Should ''not'' assume convex problem?

VerlieBoss: /* Requirements for New Optimizer */

2010-07-20T14:31:18Z

Requirements for New Optimizer

← Older revision		Revision as of 14:31, 20 July 2010
Line 21:		Line 21:


			* [http://www.superiorpapers.com/ custom papers]
	* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?		* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?
	* Should ''not'' assume convex problem?		* Should ''not'' assume convex problem?

UploadBot: Restored page from Google Cache, uploaded by John Pye

2010-05-13T14:00:45Z

Restored page from Google Cache, uploaded by John Pye

New page

{{task}}

We are trying to locate a suitable non-commercial optimizer to build into ASCEND. This would alleviate the current dependence on the proprietary [[CONOPT]] optimizer.

This task is currently being worked on by a [http://socghop.appspot.com/org/home/google/gsoc2009/ascend Google Summer of Code student].

== Requirements for New Optimizer ==

Mathematical/algorithm requirements:

* Must be able to handle 'box constraints', eg <math>a \le x \le b</math> for each variable.
* Must be able to handle equality constrains, eg <span class="texhtml">''g''(''x'',''y'',''z'') = 0</span> and <span class="texhtml">''x'' = ''f''(''y'',''z'',''a'',''b'')</span>
* Must be able to handle non-linear problems
* If matrix algebra is required, should use sparse methods rather than dense
* Should be able to make use of derivatives

Open questions:

* Should be able to handle general inequality constraints, eg <math>g(x,y,z) \le 0</math> ?
* Should ''not'' assume convex problem?
* Should ''not'' require second derivatives/Hessian matrix?
* Should be able to handle non-linear constraints?

Supporting information requirements:

* Should be known to solve a range of comparable problems to those which we expect to encounter
* Must be accompanied by a set of solvable problems for which exact solutions are known, for testing purposes.
* Should have a published algorithm
* Must have a user's manual
* Should have a freely-available user's manual

Pedantic legal stuff:

* Must be freely available to academics
* All requirement dependencies must be freely available to academics
* Should be freely available to everybody
* Should be redistributable in unmodified source form
* Should be redistributable in modified source form
* Should be redistributable in binary (compiled) form
* Documentation should be redistributable in original form
* Documentation should be redistributable in modified/repackaged form

== Background info ==

Related stuff:

* [http://en.wikipedia.org/wiki/Hessian_matrix Hessian matrix]
* [http://en.wikipedia.org/wiki/Karush-Kuhn-Tucker_conditions Karush-Kuhn-Tucker conditions]
* [http://en.wikipedia.org/wiki/Interior_point_method Interior point method]
* [http://en.wikipedia.org/wiki/Sequential_quadratic_programming Sequential quadratic programming]
* A [http://en.wikipedia.org/wiki/Category:Optimization_algorithms list of optimisation algorithms].
* A [http://orion.uwaterloo.ca/~hwolkowi/mirror.d/glossary/index.php glossary of Mathematical Programming (i.e. optimisation) terms].

We have done our own cursory [[survey of optimisation software]]

== TRON ==

Some work was done to investigate possible adding support for [[TRON]] in ASCEND. TRON can only solve the limited optimisation problem:

<math>
\begin{align}
\min f(\mathbf{x}) \\
\mathbf{x}_{lower} \le \mathbf{x} \le \mathbf{x}_{upper}
\end{align}
</math>

The following are observations:

* TRON requires that you write your own iteration loop ''outside'' TRON itself.
* TRON requires that you evaluate the function value and Hessian matrix (in a special compressed form that involves a vector of diagonal values then compressed column form for the off diagonal values, which being symmetric only need to cover half the matrix (so compressed column == compressed row?).
* TRON updates the variable vector and tells you when an optimum has been found.
* It's up to you to count iterations and terminate if it's taking too long etc.
* It seems fairly conceivable that solving more general systems with TRON might be possible by performing a separate NLA problem solution each iteration. But we're hesitant about trying that, because we're not completely comfortable with the maths involved in doing that at this stage, and not sure if it will mess up considerations of feasibility/optimality from TRON's PoV.

== IPOPT ==

IPOPT solves a more useful type of problem that includes equality constraints:

<math>
\begin{align}
\min f(\mathbf{x}) \\
\mathbf{c}_L \le \mathbf{c}(\mathbf{x}) \le \mathbf{c}_U \\
\mathbf{x}_L \le \mathbf{x} \le \mathbf{x}_U
\end{align}
</math>

It is emphasised that solving equality constraints is done just by setting elements of <math>\mathbf{c}_L</math> and <math>\mathbf{c}_U</math> equal to each other.

IPOPT supports a number of linear solvers including the HSL routine MA27, but also MUMPS, which is a free open source solver. So it is now possible to distribute a full working copy of IPOPT with ASCEND. It is also possible to have 'drop-in' support for HSL, because IPOPT can detect and dlopen HSL at runtime, if present.

Download/build instructions are here:
[http://www.coin-or.org/Ipopt/documentation/node18.html]

== MOOCHO / rSQP++ ==

The way that MOOCHO is packaged for download is as part of the big '''Trilinos''' bundle. This is a huge download that takes more than an hour to build on my system.

An RPM has been built for the Trilinos bundle, including MOOCHO. Get it from:
[http://software.opensuse.org/download/home:/jdpipe/]

The support for generic linear algebra routines is also now deprecated, and they are going for all-out integration with the other Trilinos packages. That means there's quite a lot to learn about. It's a bit daunting -- if anyone else fancies helping out, by all means, please do.

[[Category:Proposed]]