Date: 21 Dec 1998 10:20:00 GMT
From: tilo.schwarz@dbag.ulm.DaimlerBenz.COM (Tilo Schwarz)
Subject: Q: Complex Algorithm from M. B. Box
NOTE: FOLLOWUPS TO SCI.OP-RESEARCH
Hello,
I have a question concerning the 'Complex' algorithm by M. B. Box as described in 'The computer Journal', Vol. 8 (1965). Do I understand it right, that it may not converge in the following situation:
The goal should be to minimize f(x,y) = sqrt(x) + sqrt(y) subject to the constraints that x and y be in [0,1].
Now suppose, we had three points in the complex:
x0 = .2, y0 = 0 f(x0,y0) = 0.447
x1 = 0, y1 = .2 f(x1,y1) = 0.447
x2 = 0, y2 = .22 f(x2,y2) = 0.469
Now we exchange the worst point (x2,y2) and reflect it through the centroid of the remaining points with a reflection factor of 1.3: Centroid: (.1,.1), new point: xn = 0.23, yn = -0.056
Now reset yn to the boundary: xn = 0.23, yn = 0, which gives f(xn,yn) = 0.479. This trial point is also the worst, thus we move it halfway to the centroid of the remaining points: xn = 0.165, yn = 0.05 and f(xn,yn) = 0.629, which is even worse than the first trial point.
Therefore we move the trial point over and over again halfway to the centroid of the remaining points. But the centroid lies at (.1,.1) with f(.1,.1) = 0.632, thus all the following trial points are worse than (x0,y0) and (x1,y1) and the algorithm continues to move the trial point halfway to the centroid, never stopping. That is, what I observed in my implementation of the Complex algorithm.
So in general the problem occurs, if the centroid is located at a (local) maximum, but the points of the complex have a lower function value and the first reflection can not get rid of the worst point.
Does anybody out there have an idea what may be wrong? Is there a workaround?
Thanks for any help!
Please send an additional email to my address, because our newsserver sometimes does strange things...
Bye
Tilo
hope this helps
peter
Date: 01 Dec 1998 15:03:14 -0200
From: rsilva@ime.usp.br (Paulo J. da Silva e Silva)
Subject: Open Problems.
Hello,
My name is Paulo Silva and I am a PhD student in Applied Math. I am working with continous optimization, mainly the convex case.
I got a friend who walks around with a book in the hand called: "Open Problems in Topology" (or something similar). I am getting a little jealous... So I decided to ask here: is there a "Open Problems in Nonlinear Programming" book or some collection of open problems worth looking?
Thank you all.
Paulo
PS: I hope my English was not that bad :-)
peter
Date: Thu, 03 Dec 1998 22:03:51 +0000
From: "P.B.Nair" <P.B.Nair@NOSPAM.soton.ac.uk>
Subject: Open Problems.
You might find this article which appears in Optima of
interest.
http://www.ise.ufl.edu/~optima/op57fvth.html
Prasanth
Date: 28 Nov 1998 00:22:44 GMT
From: C. A. La Varre <alavarre@tiac.net>
Subject: "The Best" text on Non Linear Programming?
I had a course a while back which used
Garth P. McCormick, Nonlinear Programming, John Wiley & Sons, 1983, ISBN 0-471-09309-2
It was pretty good. Unfortunately I lost it at the end of the semester, and now seek to replace it. It is now 15 years old. Any opinions on a better, equivalent, etc. "bible"?
(I've still got a TASC manual on Optimal Estimation, Hillier & Lieberman's OR Intro, and Samuelson Economics floating around somewhere, so newer ain't necessarily better...)
Andy La Varre
I think a recent 'bible' is:
Nonlinear Programming, by D. Bertsekas (Athena Publ.) 1995. This is a very comprehensive book with lots of theory, algorithms - and - one of the best collection of problems that I know of; theoretical as well as practical (engineering) problems.
Date: Mon, 02 Nov 1998 12:16:21 -0500
From: Jayant Rajgopal <rajgopal@engrng.pitt.edu>
Subject: Solution to this simple system:
Date: Sat, 31 Oct 1998 18:31:26 -0500
From: Phiroze Parakh <phiroze@asha.eecs.umich.edu>
Subject: Solution to this simple system:
I would like to known if a solution to the following system exists
-- Thanks
Date: Sun, 1 Nov 1998 20:23:40 -0600
From: "chandra" <chandra@isource.net>
Subject: Solution to this simple system:
If a(i) are nonnegative, then you can reverse the roles of the objective and
the constraint and solve the problem:
R. Chandrasekaran
UT Dallas
chandra@utdallas.edu
Date: 2 Nov 1998 11:37:19 GMT
From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
I assume T>0
the nonlinear constraint is convex (Hessian positive definite) if all a_i are strictly positive. if all a_i are positive and a_i/k > T, then you have a convex optimization problem and since the no point with s_i = k can be feasible the feasible set is closed , and there exists an unique optimal solution, to be found from the kuhn-tucker-conditions
peter
Date: Sun, 18 Oct 1998 12:28:58 -0700
From: Mark Cooke <lucky@sj.bigger.net>
Subject: Needed: Test problems for linearly constrained NLP
I am looking for optimization test problems (preferably tough ones) with
nonlinear objective functions and linear constraints. The objective
function need not be differentiable and the variables may be bounded. I
would greatly appreciate any suggestions or pointers.
Date: Sun, 18 Oct 1998 14:36:08 -0700
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: Needed: Test problems for linearly constrained NLP
Hi,
a simple search for your desired problem class at
http://fb0445.mathematik.tu-darmstadt.de:8081/opti/select.html
revealed that 291 problems in the CUTE collection fall into it. You
could write a CUTE interface to your solver which is not that difficult.
Another collection with nearly 400 problems is
ftp://plato.la.asu.edu/pub/donlp2/testenviron.tar.gz
Again, you can write an interface (there are instructions) and try all the linearly constrained testcases.
Date: Fri, 26 Jun 1998 09:06:23 +0200
From: Thomas Muche <tm3@rcs.urz.tu-dresden.de>
Subject: I need help!
Hallo!
I developed a model for company valuation. Unfortunatly, in the contraints of the model I have to multiply a binary variable z(t) with a endogenous variable V(t-1) (t is a time index: t = 1...T), so the problem is not longer linear. In order to solve the problem I set all the binary variables 0 OR 1 and solve each resulting linear problem. Unfortunatly it takes a long time, because with only 5 periods I have 15 binary variables and therefore 2^15 linear problems to solve.
Without details the constraints have the following shape:
Any suggestions to the problem?
Thanks Thomas
Date: 26 Jun 1998 10:54:11 GMT
From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: I need help!
you have a mixed integer nonlnear problem and presently solve it by
total enumeration. however, a properly applied branch and bound method may do that at much lower cost. unfortunately, branch and bound methods for mixed integer problems are available in the public domain for linear cases only, as far as i know. but there are some "semicommercial" solutions. contact e.g. sleyffer@mcs.dundee.ac.uk or fletcher@mcs.dundee.ac.u
peter
Date: 26 Jun 1998 11:51:38 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: I need help!
I gather that you don't have a binary quadratic solver available. You might try the following branch and cut algorithm. Add endogenous variables U and the following constraints.
Otherwise each branch should be on a z-variable. Fixing a z-variable enables adding the corresponding quadratic constraint as if it were linear.
Date: Wed, 27 May 1998 14:23:35 -0500
From: "Manish C. Tayal" <tayal@cray.com>
Subject: Confidence intervals for black box optimization routine ?
To: tayal@cray.com
Hi Karl,
I have recently solved a black-box optimization problem in heat exchanger design using Genetic Algorithms and Simulated annealing. Here also we didn't had any kind of derivative or hessian information. We have just submitted our work for publication. If you are interested I can give you more details ... although you will have to tune up to your kind of problem. But it works and saves significant computational effort. !!
For sampling to get various confidence intervals, u can try Latin Hypercube, Median LHC and Hammerseley sampling techniques ... U will have to first generate these samples .. then pass them through the black box and do stochastic analysis on the ouput data values... to get various confidence intervals.
Hope this helps...
-Manish
--------------------------------------------- MANISH C. TAYAL Process Engineering Group 655E CRAY Research, Eagan, Minnesota Email: tayal@cray.com Phone: 612-683-3415 ---------------------------------------------Date: Wed, 27 May 1998 16:18:01 -0700
An asymptotically correct covariance matrix of the parameters of a constrained requires special methods described in Hartmann and Hartwig, "Computing the Moore-Penrose inverse for the covariance matrix in constrained nonlinear estimation", SAS Institute, Cary NC, 1995 (Actually I think this paper has since come out in one of the SIAM journals).
This covariance matrix, however, is only of limited usefullness in computing confidence limits. And bootstrapping and jacknifing do not work either. See Andrews D.W.K, "A simple counterexample to the bootstrap", Cowles FoundationDiscussion Paper #1153, Yale.
Confidence limits in constrained models can be computed by inverting the likelihood ratio statistic (i.e., profile likelihood), or by inverting the Wald statistic. However, the circumstances under which these methods work are limited. See my paper in Computational Economics, "Constrained Maximum Likelihood", Vol 10, No 3. August 1997, 251-266. The methods described there are implemented in a program I've written in Gauss called CML (a commerical product available from Aptech Systems).
Andrews describes methods that produce conservative limits, "Estimation when a parameter is on a boundary", Cowles Foundation paper, Yale, but I don't know of an implementation.
John Geweke describes methods for Bayesian limits in "Posterior Simulators in Econometrics", Federal Reserve Bank of Minneapolis Working Paper 555, 1995. This paper may be published somewhere by now.
There doesn't appear to be any way to compute generally correct confidence limits for inequality constrained models using frequentist methods. Most modern models of any interest contain constrained parameters and so this might seem to be an indictment of frequentist methods. However, it is not clear that the Bayesian methods will work in general either. They are usually computer intensive to an extreme magnitude, and it is not clear that the current methods properly handle ill-defined solutions. That is, a naive method that rejects solutions that fail to converge may generate the same biases in outcome that frequentists methods encounter.
Date: Fri, 22 May 1998 11:26:02 -0700
From: Karl Young <kyoung@itsa.ucsf.edu>
Subject: Confidence intervals for black box optimization routine ?
I'm just beggining to use a black box nonlinear optimization routine
(it comes with the language I'm currently using, IDL, and allows
for bound constraints on the parameters as well as nonlinear constraint
functions, both of which I need). My problem is figuring out how to get
confidence intervals for the output parameters. I don't have access to
things like the Hessian or other such quantities, as the source code is
unavailable. I can think of some obvious things to try, e.g. Monte Carlo
simulations for fits of particular data sets but I was wondering if
anyone could suggest places to look for systematic approaches to this
problem (e.g. books, papers, web sites, code repositories,...)
Thanks for any tips, -- KY ------------------------------------------------------------------- Karl Young Phone: (415) 750-2158 lab UCSF (415) 750-9463 home VA Medical Center, MRS Unit (114M) FAX: (415) 668-2864 4150 Clement Street Email:kyoung@itsa.ucsf.edu San Francisco, CA 94121 -------------------------------------------------------------------Date: Sat, 23 May 1998 07:24:27 GMT
Date: 4 May 1998 08:55:27 GMT
From: "Florent GUHL" <florent.guhl@engees.u-strasbg.fr>
Subject: Problem with FREE variables in MPL with Cplex
Hi,
Is anybody know the technique for declaring a variable possibly negative in Mpl ? I tried to declare a section called "VARIABLES" with the names of all variables and a section called "FREE" with the name of the variable (the same name in the first section) which is possibly negative.
This solution didn't work.
Florent
------------------------------
Date: Mon, 27 Apr 1998 22:51:23 +0100
From: Robin Becker <robin@jessikat.demon.co.uk>
Subject: product form optimisation
has anyone any idea under what conditions the box constrained
optimisation
min [min { f*c'g }]
fL<=f<=fU gL<=g<=gU
can be reduced to
min f*[min { c'g }]
fL<=f<=fU gL<=g<=gU
here c is a known constant n-vector and f is a scalar. I've an idea the
f & g intervals must satisfy ?L>=0 or ?U<=0 and the solution is then an
extreme point of the feasible region.Robin Becker
Date: 28 Apr 1998 07:32:55 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: product form optimisation
If you write down the Kuhn-Tucker conditions, which in this case are necessary
since the constraints satisfy the regularity condition, then it turns out
that for every feasible f the solution of min_g f*(c'g)
must be a vertex of the g-box and strict complementarity holds.
in this case the derivative of the solution g(f) with respect to f is zero
hence the kuhn-Tucker-conditions of the two problems are identical.
the general condition would be f_opt * ( c' (d/df) g_opt(f)) =0 where g_opt(f) is the solution of min_g f*(c'g), gu<=g<=go.
hope this helps
peter
Date: 29 Apr 1998 08:55:01 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: product form optimisation
snip (question regarding sign condition on g)
no: the result depends on the sign of f.
consider the problem
min_g d'g , with gL <= g <=gU .
the necessary and sufficient conditons for the solution are
d-z1+z2=0 z1_i(g_i - gL_i) =0 , i=1,...,n z2_i(gU_i-g_i) = 0, i=1,...,n z1>=0, z2>=0.clearly the solution point g_opt does not depend on the norm of d. Hence replacing d by d/||d|| changes the length of z1 and z2 only, nothing else. Now setting d=f*c, with f a real parameter, you see that the optimal value is multiplied by f and nothing else changes, as long as f >0. for f=0 the whole box of g's is the solution set, and optimal value is 0. but if f<0, the solution point g_opt changes unsteadily, whereas the optimal solution value is continuous but nondifferentiable, it has a kink at zero. Hence as long as fL>0 or fU<0, the reduction is possible and trivial, whereas for a possible sign change in f it isn't.
hope this helps
peter
Date: Tue, 28 Apr 1998 23:09:31 +0100
From: Robin Becker <robin@jessikat.demon.co.uk>
Subject: product form optimisation
Thanks. Does this depend on whether 0 is inside the g_box? My intuitive
approach is based on showing a non disimproving direction for each g & f
if f & g are single signed.
Robin Becker
Date: Wed, 29 Apr 1998 23:13:56 +0100
From: Robin Becker <robin@jessikat.demon.co.uk>
Subject: product form optimisation
yes this does. You mentioned previously that min f min c'g has the same
KT conditions as min min f*c'z, but I can't seem to get my head around
the implicit inner min function which seems to eliminate the variable
g. Is there a simple way to understand min functions (at least in this
simple case). I know this sort of thing is possible as the recourse
methods seem to use it. I'm actually using the min/f min/g as a worst
case function inside a max/c. I'm splitting c = c+ + c- to determine
signs etc and then am able under constant signs on f&g to write down the
optimal of the inner worst case as a function of the bounds, but I don't
seem to have a calculus for the transformations which I'm allowed to do
to preserve the overall solvability. Again a gut feeling is that I
destroy the external solvability if f changes sign ie induces the wrong
shape in the optimal as a function of c. Thanks ++ for valuable insight.
Robin Becker
Date: 30 Apr 1998 09:59:57 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: product form optimisation
the kuhn-tucker conditions of the two problems above are identical under special
conditions only which exclude a sign change in f.
generally, the min-function is not easy to analyze, the min-value of a convex
problem is generally not differentiable with respect to parameters
nor necessarily convex or concave if a parameter of the problem
changes. even worse is the situation with respect to the solution set.
see the case f=0 for the problem above. but there is a restricted calculus
for max (or min)functions and a look at
F.H.Clarke: Optimization and nonsmooth analysis, SIAM
might help.
as far as i understand your question your "true" problem is to estimate max _c min _{f: fL<=f<=fU} [ min_{g: gL<=g<=gU} (fc)'g ]
with c , g in R^n and f in R. (Of course, there must be also some restrictions concerning c) since max_{c1+c2}F <= max_c1 F + max_c2 F you might indeed succeed in decompsing c has indicated by you and observing the solution of your problem (by considering the possible cases with respect to f as already discussed). but I am a little afraid that the bound obtained this way might be quite crude.
hope this helps
peter
Date: 11 Mar 1998 22:38:19 GMT
From: badari@cs.tamu.edu (Badari Devalla)
Subject: Request info on a simple non-linear programming problem
Howdy !
I am a computer science grad student with very little insight into nonlinear programming. As part of my research, I am trying to solve this maximization problem
Max (N) such that
Sum e^(-l)l^(m)/m! <= p
0<=m<=N
where 0<=p<=1
ie find the max N for the Poisson CDF with parameter l to be less than
probability "p".On the face of it, it looks like a fairly standard problem in nonlinear programming - does anyone have pointers to where (textbook/paper) I can find a solution ?
Thanks much
badari
PS : For specific values on l,p, I can use the Poisson CDF tables and find out but I am looking for an analytical solution.
SCI.OP-RESEARCH Digest Mon, 12 Jan 98 Volume 5: Issue 2Date: Tue, 06 Jan 1998 11:48:44 -0700
From: Robert Dodier <dodier@colorado.edu>
Subject: Maximizing a function F(x,y) one variable at a time
Hello all,Here's one scheme for maximizing a function of more than one variable. I'm sure this scheme has a name, but I don't know it -- can someone enlighten me?
Suppose we need to maximize F(x,y). (In general F could have more than two arguments, but let's stick with two.) Let's say F is smooth. From some starting point (x0,y0) we apply this algorithm:
x1 = arg max_x F(x,y0) y1 = arg max_y F(x1,y) x2 = arg max_x F(x,y1) y2 = arg max_y F(x2,y)... etc etc. I think it's clear that this process must always increase F unless (x_k,y_k) is a stationary point of F. So if we start from "close enough" to a local maximum, we should get closer and closer to it.I know this may not necessarily be a smart idea -- for quadratics, for instance, the basis vectors for x and y won't be the best search directions -- but I just need to know (a) what is the name for this, and (b) am I correct to believe that this process will lead to a local maximum, if one exists?
Thanks in advance,
Robert DodierDate: 6 Jan 1998 19:25:23 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: Maximizing a function F(x,y) one variable at a time
......... snipthis is coordinatewise ascent. If x and y are vectors , then it is called blockwise coordinate ascent. Some analysis is in Ortega&Rheinboldt (for the minimization case, that is the same ) and much more in Blum & Oettli: Mathematische Optimierung (Springer). If F is strictly concave on the level set corresponding to (x0,y0) then the process converges indeed. It is however slow. If F is quadratic i.e.
F(Z) = -(1/2) Z^T A Z + b^T Z, (Z a vector and A a positive definite symmetric matrix, .^T means transposition) then you can consider this also as a solution method for grad F =0, which is exactly the Gauss-Seidel iterative solution technique for A Z = b . error reduction for one full cycle will be of order 1- OO(1/cond(A)), hence very slow for illconditioned A. hope this helps
peter
Crawl back to front page.