📄 optimization.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"><!--NewPage--><HTML><HEAD><!-- Generated by javadoc (build 1.5.0_10) on Fri Jan 26 16:34:49 NZDT 2007 --><TITLE>Optimization</TITLE><META NAME="keywords" CONTENT="weka.core.Optimization class"><LINK REL ="stylesheet" TYPE="text/css" HREF="../../stylesheet.css" TITLE="Style"><SCRIPT type="text/javascript">function windowTitle(){ parent.document.title="Optimization";}</SCRIPT><NOSCRIPT></NOSCRIPT></HEAD><BODY BGCOLOR="white" onload="windowTitle();"><!-- ========= START OF TOP NAVBAR ======= --><A NAME="navbar_top"><!-- --></A><A HREF="#skip-navbar_top" title="Skip navigation links"></A><TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY=""><TR><TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1"><A NAME="navbar_top_firstrow"><!-- --></A><TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY=""> <TR ALIGN="center" VALIGN="top"> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A> </TD> <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> <FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="http://www.cs.waikato.ac.nz/ml/weka/" target="_blank"><FONT CLASS="NavBarFont1"><B>Weka's home</B></FONT></A> </TD> </TR></TABLE></TD><TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM></EM></TD></TR><TR><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../weka/core/NoSupportForMissingValuesException.html" title="class in weka.core"><B>PREV CLASS</B></A> <A HREF="../../weka/core/Option.html" title="class in weka.core"><B>NEXT CLASS</B></A></FONT></TD><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../index.html?weka/core/Optimization.html" target="_top"><B>FRAMES</B></A> <A HREF="Optimization.html" target="_top"><B>NO FRAMES</B></A> <SCRIPT type="text/javascript"> <!-- if(window==top) { document.writeln('<A HREF="../../allclasses-noframe.html"><B>All Classes</B></A>'); } //--></SCRIPT><NOSCRIPT> <A HREF="../../allclasses-noframe.html"><B>All Classes</B></A></NOSCRIPT></FONT></TD></TR><TR><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2"> SUMMARY: NESTED | FIELD | <A HREF="#constructor_summary">CONSTR</A> | <A HREF="#method_summary">METHOD</A></FONT></TD><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">DETAIL: FIELD | <A HREF="#constructor_detail">CONSTR</A> | <A HREF="#method_detail">METHOD</A></FONT></TD></TR></TABLE><A NAME="skip-navbar_top"></A><!-- ========= END OF TOP NAVBAR ========= --><HR><!-- ======== START OF CLASS DATA ======== --><H2><FONT SIZE="-1">weka.core</FONT><BR>Class Optimization</H2><PRE>java.lang.Object <IMG SRC="../../resources/inherit.gif" ALT="extended by "><B>weka.core.Optimization</B></PRE><DL><DT><B>All Implemented Interfaces:</B> <DD><A HREF="../../weka/core/TechnicalInformationHandler.html" title="interface in weka.core">TechnicalInformationHandler</A></DD></DL><HR><DL><DT><PRE>public abstract class <B>Optimization</B><DT>extends java.lang.Object<DT>implements <A HREF="../../weka/core/TechnicalInformationHandler.html" title="interface in weka.core">TechnicalInformationHandler</A></DL></PRE><P>Implementation of Active-sets method with BFGS update to solve optimization problem with only bounds constraints in multi-dimensions. In this implementation we consider both the lower and higher bound constraints. <p/> Here is the sketch of our searching strategy, and the detailed description of the algorithm can be found in the Appendix of Xin Xu's MSc thesis:<p/> Initialize everything, incl. initial value, direction, etc.<p/> LOOP (main algorithm):<br/> 1. Perform the line search using the directions for free variables<br/> 1.1 Check all the bounds that are not "active" (i.e. binding variables) and compute the feasible step length to the bound for each of them<br/> 1.2 Pick up the least feasible step length, say \alpha, and set it as the upper bound of the current step length, i.e. 0<\lambda<=\alpha<br/> 1.3 Search for any possible step length<=\alpha that can result the "sufficient function decrease" (\alpha condition) AND "positive definite inverse Hessian" (\beta condition), if possible, using SAFEGUARDED polynomial interpolation. This step length is "safe" and thus is used to compute the next value of the free variables .<br/> 1.4 Fix the variable(s) that are newly bound to its constraint(s).<p/> 2. Check whether there is convergence of all variables or their gradients. If there is, check the possibilities to release any current bindings of the fixed variables to their bounds based on the "reliable" second-order Lagarange multipliers if available. If it's available and negative for one variable, then release it. If not available, use first-order Lagarange multiplier to test release. If there is any released variables, STOP the loop. Otherwise update the inverse of Hessian matrix and gradient for the newly released variables and CONTINUE LOOP.<p/> 3. Use BFGS formula to update the inverse of Hessian matrix. Note the already-fixed variables must have zeros in the corresponding entries in the inverse Hessian.<p/> 4. Compute the new (newton) search direction d=H^{-1}*g, where H^{-1} is the inverse Hessian and g is the Jacobian. Note that again, the already- fixed variables will have zero direction.<p/> ENDLOOP<p/> A typical usage of this class is to create your own subclass of this class and provide the objective function and gradients as follows:<p/> <pre> class MyOpt extends Optimization { // Provide the objective function protected double objectiveFunction(double[] x) { // How to calculate your objective function... // ... } // Provide the first derivatives protected double[] evaluateGradient(double[] x) { // How to calculate the gradient of the objective function... // ... } // If possible, provide the index^{th} row of the Hessian matrix protected double[] evaluateHessian(double[] x, int index) { // How to calculate the index^th variable's second derivative // ... } } </pre> When it's the time to use it, in some routine(s) of other class... <pre> MyOpt opt = new MyOpt(); // Set up initial variable values and bound constraints double[] x = new double[numVariables]; // Lower and upper bounds: 1st row is lower bounds, 2nd is upper double[] constraints = new double[2][numVariables]; ... // Find the minimum, 200 iterations as default x = opt.findArgmin(x, constraints); while(x == null){ // 200 iterations are not enough x = opt.getVarbValues(); // Try another 200 iterations x = opt.findArgmin(x, constraints); } // The minimal function value double minFunction = opt.getMinFunction(); ... </pre> It is recommended that Hessian values be provided so that the second-order Lagrangian multiplier estimate can be calcluated. However, if it is not provided, there is no need to override the <code>evaluateHessian()</code> function.<p/> REFERENCES (see also the <code>getTechnicalInformation()</code> method):<br/> The whole model algorithm is adapted from Chapter 5 and other related chapters in Gill, Murray and Wright(1981) "Practical Optimization", Academic Press. and Gill and Murray(1976) "Minimization Subject to Bounds on the Variables", NPL Report NAC72, while Chong and Zak(1996) "An Introduction to Optimization", John Wiley & Sons, Inc. provides us a brief but helpful introduction to the method. <p/> Dennis and Schnabel(1983) "Numerical Methods for Unconstrained Optimization and Nonlinear Equations", Prentice-Hall Inc. and Press et al.(1992) "Numeric Recipe in C", Second Edition, Cambridge University Press. are consulted for the polynomial interpolation used in the line search implementation. <p/> The Hessian modification in BFGS update uses Cholesky factorization and two rank-one modifications:<br/> Bk+1 = Bk + (Gk*Gk')/(Gk'Dk) + (dGk*(dGk)'))/[alpha*(dGk)'*Dk]. <br/> where Gk is the gradient vector, Dk is the direction vector and alpha is the step rate. <br/> This method is due to Gill, Golub, Murray and Saunders(1974) ``Methods for Modifying Matrix Factorizations'', Mathematics of Computation, Vol.28, No.126, pp 505-535. <p/><P><P><DL><DT><B>Version:</B></DT> <DD>$Revision: 1.7 $</DD><DT><B>Author:</B></DT> <DD>Xin Xu (xx5@cs.waikato.ac.nz)</DD><DT><B>See Also:</B><DD><A HREF="../../weka/core/Optimization.html#getTechnicalInformation()"><CODE>getTechnicalInformation()</CODE></A></DL><HR><P><!-- ======== CONSTRUCTOR SUMMARY ======== --><A NAME="constructor_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Constructor Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD><CODE><B><A HREF="../../weka/core/Optimization.html#Optimization()">Optimization</A></B>()</CODE><BR> </TD></TR></TABLE> <!-- ========== METHOD SUMMARY =========== --><A NAME="method_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Method Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> double[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../weka/core/Optimization.html#findArgmin(double[], double[][])">findArgmin</A></B>(double[] initX, double[][] constraints)</CODE><BR> Main algorithm.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> double</CODE></FONT></TD><TD><CODE><B><A HREF="../../weka/core/Optimization.html#getMinFunction()">getMinFunction</A></B>()</CODE><BR> Get the minimal function value</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> <A HREF="../../weka/core/TechnicalInformation.html" title="class in weka.core">TechnicalInformation</A></CODE></FONT></TD><TD><CODE><B><A HREF="../../weka/core/Optimization.html#getTechnicalInformation()">getTechnicalInformation</A></B>()</CODE><BR> Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> double[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../weka/core/Optimization.html#getVarbValues()">getVarbValues</A></B>()</CODE><BR> Get the variable values.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> double[]</CODE></FONT></TD><TD><CODE><B><A HREF="../../weka/core/Optimization.html#lnsrch(double[], double[], double[], double, boolean[], double[][], weka.core.Optimization.DynamicIntArray)">lnsrch</A></B>(double[] xold, double[] gradient, double[] direct, double stpmax, boolean[] isFixed, double[][] nwsBounds, weka.core.Optimization.DynamicIntArray wsBdsIndx)</CODE><BR> Find a new point x in the direction p from a point xold at which the value of the function has decreased sufficiently, the positive ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -