Semi-infinite programming

Last updated December 07, 2019

In optimization theory, semi-infinite programming (SIP) is an optimization problem with a finite number of variables and an infinite number of constraints, or an infinite number of variables and a finite number of constraints. In the former case the constraints are typically parameterized.^[1]

Mathematical formulation of the problem

The problem can be stated simply as:

\min _{x\in X}\;\;f(x)

{\text{subject to: }}

g(x,y)\leq 0,\;\;\forall y\in Y

where

f:R^{n}\to R

g:R^{n}\times R^{m}\to R

X\subseteq R^{n}

Y\subseteq R^{m}.

SIP can be seen as a special case of bilevel programs in which the lower-level variables do not participate in the objective function.

Methods for solving the problem

In the meantime, see external links below for a complete tutorial.

Examples

In the meantime, see external links below for a complete tutorial.

Related Research Articles

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In additions to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem specific branching heuristic.

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within certain bounds, one approach to tackling such problems is called robust optimization. Here the goal is to find a solution which is feasible for all such data and optimal in some sense. Stochastic programming models are similar in style but take advantage of the fact that probability distributions governing the data are known or can be estimated. The goal here is to find some policy that is feasible for all the possible data instances and maximizes the expectation of some function of the decisions and the random variables. More generally, such models are formulated, solved analytically or numerically, and analyzed in order to provide useful information to a decision-maker.

Interior-point methods are a certain class of algorithms that solve linear and nonlinear convex optimization problems.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.

In an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it into an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a non-negativity constraint on the slack variable.

In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.

In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem. A solution to the relaxed problem is an approximate solution to the original problem, and provides useful information.

Robust optimization is a field of optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution.

A geometric program (GP) is an optimization problem of the form

In mathematics, a semi-infinite programming (SIP) problem is an optimization problem with a finite number of variables and an infinite number of constraints. The constraints are typically parameterized. In a generalized semi-infinite programming (GSIP) problem, the feasible set of the parameters depends on the variables.

Bilevel optimization is a special kind of optimization where one problem is embedded (nested) within another. The outer optimization task is commonly referred to as the upper-level optimization task, and the inner optimization task is commonly referred to as the lower-level optimization task. These problems involve two kinds of variables, referred to as the upper-level variables and the lower-level variables.

In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in a linear program is a linear function, the objective function in a linear-fractional program is a ratio of two linear functions. A linear program can be regarded as a special case of a linear-fractional program in which the denominator is the constant function one.

In functional analysis, a branch of mathematics, the algebraic interior or radial kernel of a subset of a vector space is a refinement of the concept of the interior. It is the subset of points contained in a given set with respect to which it is absorbing, i.e. the radial points of the set. The elements of the algebraic interior are often referred to as internal points.

In mathematics, a submodular set function is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.

In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If $is the optimal dual value and is the optimal primal value then the duality gap is equal to . This value is always greater than or equal to 0. The duality gap is zero if and only if strong duality holds. Otherwise the gap is strictly positive and weak duality holds.$

In mathematical optimization, the perturbation function is any function which relates to primal and dual problems. The name comes from the fact that any such function defines a perturbation of the initial problem. In many cases this takes the form of shifting the constraints.

Design optimization is an engineering design methodology using a mathematical formulation of a design problem to support selection of the optimal design among many alternatives. Design optimization involves the following stages:

Variables: Describe the design alternatives
Objective: Elected functional combination of variables
Constraints: Combination of Variables expressed as equalities or inequalities that must be satisfied for any acceptable design alternative
Feasibility: Values for set of variables that satisfies all constraints and minimizes/maximizes Objective.

References

↑
- Bonnans, J. Frédéric; Shapiro, Alexander (2000). "5.4 and 7.4.4 Semi-infinite programming". Perturbation analysis of optimization problems. Springer Series in Operations Research. New York: Springer-Verlag. pp. 496–526 and&nbsp, 581. ISBN 978-0-387-98705-7. MR 1756264.
- M. A. Goberna and M. A. López, Linear Semi-Infinite Optimization, Wiley, 1998.
- Hettich, R.; Kortanek, K. O. (1993). "Semi-infinite programming: Theory, methods, and applications". SIAM Review. 35 (3): 380–429. doi:10.1137/1035089. JSTOR 2132425. MR 1234637.

Edward J. Anderson and Peter Nash, Linear Programming in Infinite-Dimensional Spaces, Wiley, 1987.
Bonnans, J. Frédéric; Shapiro, Alexander (2000). "5.4 and 7.4.4 Semi-infinite programming". Perturbation analysis of optimization problems. Springer Series in Operations Research. New York: Springer-Verlag. pp. 496–526 and&nbsp, 581. ISBN 978-0-387-98705-7. MR 1756264.
M. A. Goberna and M. A. López, Linear Semi-Infinite Optimization, Wiley, 1998.
Hettich, R.; Kortanek, K. O. (1993). "Semi-infinite programming: Theory, methods, and applications". SIAM Review. 35 (3): 380–429. doi:10.1137/1035089. JSTOR 2132425. MR 1234637.
David Luenberger (1997). Optimization by Vector Space Methods. John Wiley & Sons. ISBN 0-471-18117-X.
Rembert Reemtsen and Jan-J. Rückmann (Editors), Semi-Infinite Programming (Nonconvex Optimization and Its Applications). Springer, 1998, ISBN 0-7923-5054-5, 1998

External links

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] 
Bonnans, J. Frédéric; Shapiro, Alexander (2000). "5.4 and 7.4.4 Semi-infinite programming". Perturbation analysis of optimization problems. Springer Series in Operations Research. New York: Springer-Verlag. pp. 496–526 and&nbsp, 581. ISBN 978-0-387-98705-7. MR 1756264.
M. A. Goberna and M. A. López, Linear Semi-Infinite Optimization, Wiley, 1998.
Hettich, R.; Kortanek, K. O. (1993). "Semi-infinite programming: Theory, methods, and applications". SIAM Review. 35 (3): 380–429. doi:10.1137/1035089. JSTOR 2132425. MR 1234637.

[mwNg] Bonnans, J. Frédéric; Shapiro, Alexander (2000). "5.4 and 7.4.4 Semi-infinite programming". Perturbation analysis of optimization problems. Springer Series in Operations Research. New York: Springer-Verlag. pp. 496–526 and&nbsp, 581. ISBN 978-0-387-98705-7. MR 1756264.

[mwRQ] M. A. Goberna and M. A. López, Linear Semi-Infinite Optimization, Wiley, 1998.

[mwRw] Hettich, R.; Kortanek, K. O. (1993). "Semi-infinite programming: Theory, methods, and applications". SIAM Review. 35 (3): 380–429. doi:10.1137/1035089. JSTOR 2132425. MR 1234637.