Method and apparatus for optimizing system operational parameters
First Claim
1. Apparatus for optimizing the operating state of a communications network comprising:
- a plurality of sensors for developing signals representative of present operating state of said network, said signals being related to controllable parameters of said network;
first processor, responsive to said sensors, for transforming said signals onto a multi-dimensional space such that said operational state of said communications network is at essentially the center of said multi-dimensional space and said constraints form a polytope in said space;
second processor, responsive to said first processor, for computing a path in said space characterized by a power series of order greater than one, along which values of said signals in said space represent a state of said communications network that is monotonically improving with distance from said center; and
third processor, reponsive to said second processor, for selecting a point on said curve, developing a modified set of signals corresponding to said selected point and controlling said parameters of said communication network in accordance with said modified set of signals.
1 Assignment
0 Petitions
Accused Products
Abstract
Method and apparatus for optimizing the operational state of a system employing iterative steps that approximately follow a projective scaling trajectory or an affine scaling trajectory, or curve, in computing from its present state, x0 to a next state x1 toward the optimum state. The movement is made in a transformed space where the present (transformed) state of the system is at the center of the space, and the curve approximation is in the form of a power series in the step size. The process thus develops a sequence of tentative states x1, x2, xn . . . . It halts when a selected suitable stopping criterion is satisfied, and assigns the most recent tentative state as the optimized operating state of the system.
-
Citations
12 Claims
-
1. Apparatus for optimizing the operating state of a communications network comprising:
-
a plurality of sensors for developing signals representative of present operating state of said network, said signals being related to controllable parameters of said network; first processor, responsive to said sensors, for transforming said signals onto a multi-dimensional space such that said operational state of said communications network is at essentially the center of said multi-dimensional space and said constraints form a polytope in said space; second processor, responsive to said first processor, for computing a path in said space characterized by a power series of order greater than one, along which values of said signals in said space represent a state of said communications network that is monotonically improving with distance from said center; and third processor, reponsive to said second processor, for selecting a point on said curve, developing a modified set of signals corresponding to said selected point and controlling said parameters of said communication network in accordance with said modified set of signals.
-
-
2. Apparatus for optimizing the operational state of a system in accordance with a preselected operational criterion by adjusting values of operational parameters controlling said state of said system, said operational parameters being adjustable within a preselected set of linear constraints, comprising:
-
a first processor portion for developing signal representations of said operational parameters and for developing, a preselected representational form of said operational state of said system, based on said representations, said constraints and said criterion, with said representational form comprising a two dimensional array of values related to said set of constraints and to said state of said system, and a one dimensional array of signals related to said operational criterion; and
said two dimensional array defining a polytope in a multidimensional space, with said operational parameters being the variables of said space and said one dimensional array defining a direction in said space;a second processor portion, responsive to said first processor portion, for transforming said operational parameters, said two dimensional array, and said one dimensional array, onto a transformed space where said state of said system is essentially at the center of said space, and computing a power series function in said transformed space, of order greater than one, that approximates a trajectory curve in consonance with said operational criterion; and third processor portion, responsive to said second processor portion, for setting said operational parameters of said system at values corresponding to a point in said transformed space and along said curve.
-
-
3. Apparatus for allocating resources of a commercial enterprise in accordance with a preselected operational criterion by adjusting values of operational parameters describing said state of said enterprise, said operational parameters being adjustable within a preselected set of linear constraints, characterized by:
-
sensors for developing said representations of said values of said operational parameters; a first processing portion, responsive to said signal representations, for projecting said signal representations onto a transformed space to place said state of said enterprise at essentially the center of said transformed space; a second processing portion, responsive to said first portion, for computing a power series function in said transformed space, of order greater than one, that approximates a trajectory curve in consonance with said operational criterion; and a controller for setting said operational parameters of said enterprise at values corresponding to a point in said transformed space and along said curve.
-
-
4. Apparatus for optimizing operational state of a system described by a set of operational parameters, with said optimizing accomplished by adjusting values of said operational parameters within a preselected set of constraints to minimize a set of preselected operational criterion values, comprising:
-
sensors for developing signal representations of said values of said operational parameters; a first processor portion, responsive to said signal representations of said sensors, to applied values of said constraints and to said operational criterion, for developing a canonical form signal representation of said operational state of said system, such that said minimizing is effected by ##EQU23## where x is a vector related to said operational parameters, c is a vector related to said set of preselected criterion values, n is the number of said operational parameters, A=(a11, a12, . . . , aij, . . . , amn) is an m by n matrix of coefficients related to said preselected set of constraints, and e is a vector of all 1'"'"'s;
said canonical signal representation forming a multidimensional space, with said operational parameters being the variables of said space, said matrix defining a polytope in said space, and said c vector specifying a direction in said space;a second processor portion, responsive to said first processor portion, for projecting said operational parameters, said matrix, and said c vector unto a transformed space where said state of said system is at essentially a center of said transformed space; a third processor portion, responsive to said second processor portion, for computing a power series function in said transformed space of order greater than one that approximates a trajectory curve in consonance with said operational criterion; and a controller, responsive to said third processor portion, for setting said operational parameters of said system at values corresponding to a point in said transformed space and along said curve.
-
-
5. Apparatus for optimally scheduling resources of a commercial enterprise in accordance with a preselected operational criterion by adjusting values of operational parameters describing said state of said enterprise, said operational parameters being adjustable within a preselected set of constraints, characterized by:
-
first means for developing a tentative state-of-the-system representation based on said values of said operational parameters, and for developing a canonical form representation of the operational state of said enterprise corresponding to said tentative state-of-the-system, said constraints and said criterion; second means, responsive to said first means, for projecting said canonical form representation of said tentative state-of-the-system in response to a "true" activation signal, onto a transformed space to place said state-of-the-system at essentially the center of said space, and computing a power series function in said transformed space, of order greater than one, that approximates a trajectory curve in consonance with said operational criterion; third means responsive to said second means for modifying said tentative state-of-the-system to correspond to a point in said transformed space and along said curve; fourth means responsive to said second means for developing said activation control signal, and setting said control signal to "true" state when said tentative state-of-the-system is not within a preselected stopping region, and set to a "false" state when said tentative state-of-the-system is within said preselected stopping region; and fifth means, responsive to said fourth means, for setting said operational parameters of said enterprise in accordance with said tentative state-of-the-system when said activation control signal is "false".
-
-
6. In an electronic resource allocation optimizing apparatus, a method for assigning values to a plurality of controllable parameters of a system, x, where said parameters are linearly related to each other through inequality and equality constraint relationships, and where said assigning values aims to maximize a benefit specified by a linear objective relationship of said parameters characterized by:
-
a step of transforming said parameters, x, of said system to a domain containing a vector field describing the steepest descent to an optimum allocation, wherein said system parameters are described by a vector signal y; and a step of passing from a first set of values for said transformed parameters, y(1), that satisfy said constraint relationships to a second set of values for said transformed parameters, y(2), that also satisfy said constraint relationships, in correspondence with the equation ##EQU24## where each of said vk vector coefficients is related to said first set of values and to said objective relationship, where m is a preselected integer, and t is a preselected step size. - View Dependent Claims (7)
-
-
8. A method for assigning values to a plurality of controllable parameters of a system, subject to constraints, and where said assigning values aims to maximize a benefit specified by a linear objective relationship of said parameters characterized by:
-
a step of selecting a starting set of values x for said parameters that satisfy said constraint relationships; a step of converting said set of values and said objective relationship in accordance with a conversion process that smooths the benefit function in the space of said converted set of values; a step of developing an m plurality of coefficient sets vk, where at least one of said coefficients for k>
1 is not zero, related to said converted starting set of values and to said converted objective relationship, where m is a preselected integer;a step of selecting a step size t; and a step of obtaining a second set of values for said parameters, y in accordance with the equation ##EQU25## - View Dependent Claims (9, 10)
-
-
11. A method for assigning values to controllable parameters of a system, where said parameters are linearly related to each other and where said assigning values aims to maximize a benefit specified by a preselected linear relationship of said parameters characterized by
a step of selecting a starting set of values for said parameters that satisfy said constraint relationships; - and
a step of moving from said starting set of values of said parameters by a step of preselected size, t, in accordance with a function that is at least of second order in t, to a new set of values of said parameters.
- and
-
12. In a system including resources and users of said resources where allocation of said resources to said users is subject to linear constraints, a method for allocating said resources to said users so as to minimize a given objective function comprising the steps of:
-
treating said resources as variables;
iteratively reassigning said resources from a present tentative allocation to a new tentative allocation in accordance with a polynomial approximation of a curve of order greater than one that is related to said present tentative allocation and is a member of a family of curves that describe a generalized steepest descent to an optimum allocation in accordance with said objective function;terminating said step of iteratively reassigning said resources when said given objective function is minimized; and allocating said resources in accordance with the last of said tentative resource reassignments.
-
Specification