One of the mathematical necessary conditions for maximization, used routinely in solving economic models. Typically, it consists of setting equal to zero the derivative of the function being maximized (or its Lagrangian) with respect to a variable that can be controlled.

first-order conditions The conditions for a function to take a stationary value. If y = f (x), the first-order condition for a stationary value is dy/dx = f_x = 0.

http://glossary.computing.society.informs.org/second.php?page=F.html
First-order conditions. This descends from classical optimization, using Taylor's Theorem. For unconstrained optimization, this is simply that grad_f(x*)=0. (In variational calculus, it is the Euler-Lagrange equation.) For constrained optimization, the first-order conditions of a regular mathematical program is given by the Lagrange Multiplier Rule.

 用于求解OLS估计值的一组线性方程。

 

Label correcting algorithm. Arises in labeling algorithms for shortest path problem. Each iteration a label is set to an estimate of the shortest path from a given node. All labels become exact values at termination.

Label setting algorithm. Arises in labeling algorithms for shortest path problem. Each iteration a label becomes the actual shortest path from some node. (Termination occurs when the destination node(s) are permanently lablelled.)

Labeling algorithm. A class of algorithms for path-related problems on graphs and networks. To illustrate, consider a network [V,A] with arc values c.

The Ford-Fulkerson max flow labeling algorithm (c = capacity).

Input. source (s), destination (t), capacities (c).

Output. max flow from s to t.

• Initialize all flows to be zero and assign the label (-,inf) to the source. All other nodes are unlabeled, and all nodes (including the source) are unscanned.
• Labeling process: Select any labeled, unscanned node, say k with label (a,b). If node j is an unlabeled neighbor and x(k, j) < c(k, j), assign the label (k+,b*) to node j, where b* = Min{b, c(k,j)-x(k,j)}. If node j is an unlabeled neighbor and x(j, k) > 0, assign the label (k-,b*) to node j, where b* = Min{b, x(j,k)}. (In either case, define node j as labeled, but unscanned, while node k is now labeled and scanned.) Repeat this until either the sink is labeled and unscanned, or until no more labels can be assigned. In the latter case terminate; in the former case, go to the flow change step.
• Flow change: Let the sink (t) have label (a,b). If a is k+, replace x(k,t) by x(k,t)+b; if it is (k-,b), replace x(k,t) by x(k,t)-b. In either case, apply the flow change (b or -b) along the path back to the source. The result is a new flow that is b more than it was. Erase labels, except on the source, and go to the labeling process.

  (See technical note, with an example.)

Dijkstra's shortest path algorithm (c = distance).

Input. source (s), destinations (T not Ø), distances (c).

Output. shortest path from s to each node in T.

• Initialize labels: L(v)=inf for v not= s and L(s)=0. Set S=Ø.
• Label: select u in argmin{L(v): v in VS} (terminate if S=V). Then, update S := S/{u}, and for v in VS: if L(u) + c(u,v) < L(v), set L(v) := L(u) + c(u,v).

Terminate when T is a subset of S (i.e., all destination nodes are labeled with their shortest distance from node s).

A generic shortest path labeling algorithm from all nodes to destination node t (c = distance).

Input. destination (t), distances (c).

Output. shortest path from each node to t.

• Initialize labels, L(v) = estimate of shortest path length from node v to node t, with L(t) = 0.
• Label: Find an arc, say (i, j), that violates the distance equations, say L(j) > L(i) + c(i, j). If none, terminate; otherwise, update the label: L(j) = L(i) + c(i, j).

The labeling step is repeated until there are no violations. At termination, L(j) = length of shortest path from node j to node t.

Another type of labeling algorithm occurs in simplicial subdivision, used to compute a fixed point that represents an economic equilibrium.

Lagrange conditions. The optimality equation (plus feasibility conditions) in Lagrange's multiplier theorem.

Lagrange Multiplier Rule (LMR). From the extension to Lagrange's multiplier theorem:

Suppose x* is in argmax{f(x): g(x) <= 0, h(x) = 0}, where f, g, h are in C^1. Then, there exist multipliers (u, v) for which the following conditions hold:

1. grad_x_[f(x*) - ug(x*) - vh(x*)] = 0;
2. u >= 0;
3. ug(x*)=0.

转载本文请联系原作者获取授权，同时请注明本文来自赵晓锋科学网博客。
链接地址：https://wap.sciencenet.cn/blog-285749-354302.html

上一篇：Happy Face Math
下一篇：2010年度国家自然科学基金项目评审结果通告