What is Minimization: Definition and 96 Discussions

In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.

View More On Wikipedia.org
Recent contents Top users
  1. M

    Minimization and least squares/ridge regression

    Homework Statement f(x;a) = x_o + (a_1,a_2,a_3,...a_d)*x min a (Xa - Y)^t o^(-1) (Xa - Y) a = (a_0 a_1 a_2 a_3 a_4 . . . a_d)^t Homework Equations Y = (y_1 y_2 y_ 3 ... y_k) X = Dsign Matrix The Attempt at a Solution to minimize write (X(a+ (delta a) - Y )^t o^(-1) (X (a+ delta a) - Y)...
  2. Z

    Ridge Regression Minimization Proof

    Homework Statement Linear family: [tex]f(x;a) = a_{o} + (a_{1}.a_{2},a_{3},...,a_{k}) \cdot x[\tex] [tex] (Xa - Y)^t \sigma^{-1} (Xa-Y) + \lambda (a^t a-a^2_{o} [\tex] [tex] a = (X^t \sigma^{-1} X + \lamda I_{o})^{-1} x^t \sigma^{-1} Y [\tex] Homework Equations[tex] Y_{i} = f(x_{i}) +...
  3. P

    Energy minimization (level set)

    Hi Does anyone know what calculations should be used to minimize an energy functional (level set and active contour method): E(\phi)=\mu\int p(|grad(\phi)|)dx+\lambda\int g\delta(\phi)|grad(\phi)|dx+\alpha \int gH(-\phi)dx (I) According to Chunming Li and Chenyang Xu "Distance Regularized...
  4. O

    MHB Solving Minimization Problem Involving Variance & Covariance

    Hello Everyone! What $b$ minimizes $E[(X-b)^2]$ where $b$ is some constant, isn't it $b=E[X]$? Is it right to go about the proof as follows: $E[(X-b)^2] = E[(X^2+b^2-2bX)] = E[X^2] + E[b^2]-2bE[X]$, but $E[b] = b$, we differentiate with respect to $b$ and set to zero, we obtain that $b=E[X]$...
  5. A

    MATLAB 2D discrete function minimization if extreme points are known, using Matlab

    Hello everyone. I would like to hear some suggestions on minimizing a function. I have discrete 2D function (a grid, where each (x,y) point have some value), where I know only extreme points (more specifically - ridges. http://en.wikipedia.org/wiki/Ridge_detection). I want to reconstruct...
  6. T

    Optimization problem (minimization)

    Homework Statement I have a sector of a circle with area 12 square meters. If radius r and angle \theta are chosen so that the that perimeter of the sector is the smallest possible, then what is the radius? Homework Equations I have area of sector as A=\frac{\theta r^2}{2} which is 12...
  7. A

    Minimizing Chi-Squared Function in MATLAB

    Homework Statement I am using MATLAB to minimize a sum of squares (chi-squared) function. My model has a definite integral (from zero to data values).The model has three parameters w.r.t which I need to minimize. [b]2. relevant equations *I need to integrate (1+x).^(b-a-2).* exp(-b.*x) from...
  8. J

    Fock Operator for minimization

    Hi everyone, I have a question about the application of the Fock operator when we want to optimize, for example, an atomic orbital written as a product of Slater Orbitals. I know that the appeareance of the Fock operator is due to the minimization of the <E> with respect to each wavefunction...
  9. S

    What algorithm can solve a linear minimization problem with given constraints?

    Hi all, does anyone know what type of problem this would be classified as, and what kind of algorithm I could use to get a solution? minimize: P=60w1+30w2+10w3+100w4 subject to: P ≥ 50 0 < wi ≤ 1 thanks very much
  10. Y

    Solving a PDE with Boundary Conditions: A Minimization Problem

    Homework Statement Let Ω\subsetR2 be a region with boundary \Gamma=\Gamma1\bigcup\Gamma2. On Ω we must solve the PDE -{div}(\frac{h^{3}}{12\mu}{grad} p+\frac{h}{2}{u})+kp=f with h and f functions of the spatial coordinates, \mu and k given constants, u a given constant velocity...
  11. T

    Cost of Manufacturing X Items (average cost minimization)

    Homework Statement If the cost of manufacturing x items is: C(x) = (x^3)+21(x^2)+110x+20 Homework Equations All right, so the first few questions asked for total cost of producing 100 items, and marginal cost. I understood those well. Then it asked for the average cost function...
  12. G

    Relative Velocity-Boat Problem and Minimization

    Homework Statement Fred's friends are in a boat. If they could travel perpendicularly to the shore, they could land at his position. However, a strong current vc is greater than the maximum vm of the motor. Find the magnitude of the angle, measured relative to the straight-across direction, at...
  13. D

    Minimization Problem (using Projection)

    Homework Statement Minimize ||cos(2x) - f(x)|| where f(x) is a a function in the span of {(1,sin(x),cos(x)} Where the inner produect is defined (1/pi)(integral from -pi to pi of f(x)g(x) dx) Homework Equations I found f(x) to be zero. Is this correct I am uneasy about this...
  14. S

    Nonlinear Least Squares Minimization

    How should I go about solving this problem? This is only to get a better understanding of how NLLS works. F(x;a) = (1+a1*x)/(a2+a3*x) (so n = 3) I am choosing a1,a2,a3 to be 2,3,5 respectively. I am also picking 6 data points (so m = 6): (0, 0), (-1/4, 1/4), (-1/2, 1/10), (1/4, 1/4)...
  15. S

    Linear Least Squares Minimization

    I'm going through some methods to solve the LLS method of minimization and have come upon 3 general methods to solve the problem. The 3 methods I am looking at are normal equations, QR factorization, and SVD. I've come upon a fact that I can't find an explanation for: Can anyone explain why...
  16. F

    How do I minimize a function with a constraint using Lagrange-Euler method?

    I am working on a functional and I need to find its minimum, the conventional procedure is to use Lagrange-Euler method and find the minimum state of the function, but if I need to impose a constraint to the function, I don't know what I need to do J=int(F(t, f(t), a, b)) minimize(f) and...
  17. C

    Minimization of a Multi Output Circuit

    Hi all. I have a 4 input circuit (ABCD). I have 7 outputs that accompany this circuit. Now, I have tools (like Karnaugh maps) to solve for Standard Sum of Products (or Product of Sum) form for individual outputs. I have the minimum of each output based on the Karnaugh map. However, I want...
  18. C

    Efficient Boolean Minimization Techniques: Simplifying Y = \bar{X}_1+\bar{X}_0

    This is just a general question regarding Boolean minimization. Expression: Y=\bar{X}_1\bar{X}_0+\bar{X}_1X_0+X_1\bar{X}_0 Minimized expression: Y=\bar{X}_1+\bar{X}_0 My first attempt was to minimize it algebraically. I factored \bar{X}_1 from the first two terms, then the \bar{X}_0+X_0...
  19. Somefantastik

    Minimization and Variational Problems

    I just jumped into a finite element methods course, and we are finding minimization problems and variational problems for various PDE's. However, the book never really explains what these guys are and their purpose and what they do, and before I continue, I'd like to understand this. I googled...
  20. K

    How can I optimize a function on a non-linear set with unknown points?

    Hey all, I'm doing some research on computing optimal controls in quantum mechanics, and need a numerical algorithm that I can try to adapt to my problem. I'm hoping that if I describe the problem, someone out there can point me in a good direction. Consider a function f: \mathbb R^n \to...
  21. H

    Understanding KKT Conditions for Minimization Problems with Constraints

    what does it mean to write out the kkt conditions and find x* for the following problem: minimize f(x) = \sum x_i subject to \prod x_i = 1 and x_i \geq 0 for 1<= i <= n. the bounds on the sum and product are from i = 1 to n.
  22. J

    Can This Boolean Equation Be Simplified Further?

    Homework Statement I came to an equation which looks like this: AB'D' + AC'D' + CD' I know I can simplify out the C to this AB'D' + AD' + D' Any further simplification available (And am I simplifying properly so far?) Thanks Homework Equations The Attempt at a Solution
  23. H

    Average distance minimization algorithm

    This could be a well-known problem, but I looked around and I don't see anything. Suppose there is a set of points p_1, p_2, ... p_N. For simplicity, assume Euclidean space of arbitrary dimensionality, but this could be any metric space. I need to find a new set q_1, q_2, ... q_n of n...
  24. S

    Minimization - optimization alg. or equation alg.?

    Hello everybody! I guess my question is mainly concerned with numerical algorithms... Given a problem of the form min w = f(x) subject to g1(x)=0 : : gn(x)=0 where x is a m x 1 vector, n < m. From a numerical standpoint, how can I know whether it is preferably to solve it by setting up the...
  25. D

    Minimizing Area of 2 Triangles Problem

    Homework Statement The line joining P and Q crosses two parallel lines that are 8 units apart (thus, if I drew a vertical line from the top line to the bottom line, that would equal eight). The point R is 10 units from point P (as shown). How far from point Q should the point S be chosen so...
  26. 3

    Solving Minimization Problem: Find Smallest Beam Length

    Homework Statement An 8 foot tall wall is 27 feet from a building. What is the smallest sized beam that could be placed against the wall, sit on top of the 8 foot wall, and touch the ground on the other side of the wall? Homework Equations I want to minimize the beam length, so will...
  27. T

    What Is the Minimum Time for a Sportscar to Travel 1/2 Mile from Standstill?

    Homework Statement a A sportscar can accelerate uniformly to 120 mi/h in 30s. Its maximum braking rate cannot exceed 0.7g. what is the minimum time required to go 1/2 mi, assuming it begins and ends at rest? Homework Equations I drew a graph of v(t) vs t. where the initial acc. goes up...
  28. D

    Mathematical Economics, Minimization

    Homework Statement Consider the following general form of a constant elasticity of substitution production function: y = [SLp + (1 - S)Kp]1/p Assume a firm is trying to minimize the cost of producing any given y. Cost are given by C = wL + rK Find the firm's cost minimizing demand...
  29. R

    Kinematics - Minimization of a period

    Homework Statement A mass is released from rest atop an incline angled at Θ relative to the horizon, from a certain distance up the incline (Not height), x_0. This point up the incline is denoted P. The mass then travels along a horizontal path of length S. The mass then goes up an incline...
  30. C

    Ax + b Least Squares Minimization Standard Form

    All - Given a set of data {(xi, yi)| i = 1,2,...,m} and the regression equation f(x) = ax + b, I want to use the simplex method to minimize the equation Sigma [(yi - f(xi))/f(xi)]^2. However, I am stuck on how to initially organize the problem. I am not sure whether the equation, Sigma [(yi -...
  31. D

    Minimization of losses in a piston compressor

    Hello. I need to minimize all types of manageable losses (mechanical and thermodynamic) in a reciprocating compressor. Does anyone have more suggestions besides having a high efficiency motor, no loss tank drain and high efficiency dual controller?
  32. Q

    Mathematica Minimization help in mathematica

    Hi i am finding difficulty in minimzing the following in mathematica. Can someone try it out and share with me the results. Its urgent. Its a constrained minimization problem in 8 variables c2,c3...c9 Can it be tried out in MATLAB or maple? NMinimize[{1.383` c2^2 + 1.377` c3^2 + 1.2618` c4^2 +...
  33. M

    Constrained Minimization Problem(HELP )

    Homework Statement A closed rectangular box is made with two kinds of materials. The top and bottom are made with heavy-duty cardboard costing $0.36 per square foot, and the sides are made with lightweight cardboard costing $0.06 per square foot. Given that the box is to have a capacity of...
  34. F

    Entropy minimization - maximum energy delivered

    I noticed a lot of articles discussing entropy generation minimization (which is, according to Gouy-Stodola theorem, equal to exergy maximization) of certain processes. The process/machine which is exergy-maximized/entropy-minimized will, according to definition of exergy, produce a maximum...
  35. I

    Predicting Contact Surface of Pressurized Balloons: Energy Minimization Method

    let's suppose i have two differently pressurized balloons and i push them together. how can i predict what that contact surface will look like? to make this simpler let's say i have two disjoint hemispheres which contain a pressurized gas each, again at different pressures, and i push them...
  36. B

    Variational methods - minimization problem proof

    Consider the minimization problem Inf (u E D) F(u) where F(u) = 1/2 integ(0->T) |u (with circle on top)|^2 dt + 1/2 integ(0->T) |u|^2 dt + 1/2 integ(0->T) f(t)u(t) dt, f E L^2 [0,T], and H = {u:[0,T]->R, uEL^2[0,T], u(circle on top) E L^2 [0,T]} is a Hilbert space equipped with the norm...
  37. S

    Minimization of the square of the gradient in a volume

    Homework Statement Find an expression involving the function \phi(x_1, x_2, x_3) that has a minimum average value of the square of its gradient within a certain volume V of space. Homework Equations We are studying functionals, though so far it has only been of one variable. We're...
  38. S

    Minimization using first differential equation - help

    Hi all I am trying to minimize a function by setting the first derivative equal to 0. The strange thing is that I end up with a negative result, which cannot be true (for the application). Any ideas on how this could happen? Do I have an error in my equation somewhere...
  39. F

    Finding the Closest Point on a Parabola: How Can We Minimize Distance?

    Find the point P on the parabola y = x^2 closest to the point (1,0). To solve for P... I used the distance formula, and then took the derivate. Using points (x, x^2) and (1,0)... however, while taking the derivative I get a really nasty 4th power equation, which I am not sure I can...
  40. M

    Minimization with a binary to seven segment decoder in Verilog

    Hey guys, I have two questions about something I'm trying to minimize. I'm making a binary to seven segment decoder in Verilog, and I have a truth table set up. The board I'm going to be placing this on is active low. My questions: I want to reduce, or minimize, this truth table, I was...
  41. D

    Optimizing Rank p Matrix V for Symmetric Matrices with SVD Using Frobenius Norm

    I have this matrix problem: Given R_1, R_2, R_3\in\mathbb{R}^{N\times N} are symmetric matrices with rank p<N. Their SVD are U_1\Sigma_1 U_1^T, U_2\Sigma_2 U_2^T and U_3\Sigma_3 U_3^T, respectively. I want to find a rank p matrix V such that J = \|V\Sigma_1 V^T - U_1\Sigma_1 U_1^T\|_F^2 +...
  42. S

    Multivariable Minimization Question

    I got this question as a take home exam question, and I can't figure it out for the life of me: The temperature T(x,y,z) throughout a region in space is given by: T(x,y,z) = 3*x^2*y*2+z^2 An insect is confined to move on the surface S : x^2 + y^2 = z. The insect is at the point...
  43. C

    Comparing Baseball & Climbing Helmets: Design & Force Minimization

    i have to do this project where i have to compare and contrast a Baseball helmet and a Rock climbing helmet and describe how each is appropriately designed to its use. - have to make reference to each of Sir Isaac Newtons 3 laws - describe how force is minimized - describe several features of...
  44. J

    How can I find the minimum value for the sum of absolute values?

    Hello, I have been having problems finding the way to minimize the sum of absolute values. Specificaly I am looking for the value of X that will minimize the sum|Xi-V|<-- i=1,...n . I know that V should be equal to the mean value of X. But I do not know the correct approach to finding this...
  45. S

    Optimizing Boom Length for Oil Spill Containment: A Calculus Approach

    To contain oil spills, rectangular booms that have a cross-link to provide stability are used. The cross-link joins the long sides and is parallel to the short sides. What is the minimum total length of boom required to enclose an oil spill covering 100 000 m^2 of water if it can only be...
  46. G

    Minimize Heating and Cooling Costs w/ Partial Derivatives

    Hey, This problem i need to use partial derivatives to solve but not Lagrange mulitpliers. My main problem is just setting it up: A building in the shape of a rectangular box is to have a volume of 12,000 cubic feet. It is estimated that the annual heating and cooling costs will...
Back
Top