Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

INVESTIGATING SEM-INFINITE PROGPIAAB USING PENALTY FUNCTIONS AND AND LAGRANGLAN METHODS

IP.com Disclosure Number: IPCOM000128268D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 11 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Sven-Ake Gustafson: AUTHOR [+3]

Abstract

In this paper the relations between semi-infinite programs and optimisation problems with finitely many variables and constraints are reviewed. Two classes of convex semi-hifmite programs are defined, one based on the fact that a convex set may be represented as the intersection of closed halfspaces while the other class is defined using the representation of the elements of a convex set as convex combinations of points and directions. Extension to nonconvex problems is given. A common technique of solving a semi-infinite program computationally is to derive necessary conditions for optimality in the form of a nonlinear system of equations with finitely many equations and unknowns. In the three-phase algorithm, this system is constructed from the optimal solution of a discretised version of the given semi-infinite program, i.e. a problem with finitely many variables and constraints. The system is solved numerically, often by means of some finearisation method. One option is to use a direct analog of the familiar SOLVER method.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

INVESTIGATING SEM-INFINITE PROGPIAAB USING PENALTY FUNCTIONS AND AND LAGRANGLAN METHODS

by

Sven-Ake Gustafson

TRITA-NA NVESTIGATING SEMI-INFINITE PROGRAMS USING PENALTY FUNCTIONS AND LAGRANGIAN METHODS

Abstract.

In this paper the relations between semi-infinite programs and optimisation problems with finitely many variables and constraints are reviewed. Two classes of convex semi-hifmite programs are defined, one based on the fact that a convex set may be represented as the intersection of closed halfspaces while the other class is defined using the representation of the elements of a convex set as convex combinations of points and directions. Extension to nonconvex problems is given. A common technique of solving a semi-infinite program computationally is to derive necessary conditions for optimality in the form of a nonlinear system of equations with finitely many equations and unknowns. In the three-phase algorithm, this system is constructed from the optimal solution of a discretised version of the given semi-infinite program, i.e. a problem with finitely many variables and constraints. The system is solved numerically, often by means of some finearisation method. One option is to use a direct analog of the familiar SOLVER method.

1. Introduction

Linear semi-infinite programs were originally defined by generalising linear programs allowing either the number of constraints or the number of variables (but not both) to become infinite. Consider naniely

(Equation Omitted)

Here

(Equation Omitted)

and

(Equation Omitted)

are fixed vectors and A a given n by N matrix

For all values of N (1b) defines a convex subset of R1 (which could possibly be empty) and the generalisation to infinitely many constraints (1b) appears straight-forward. (See e.g. Glashoff- Gustafson, [41). We consider now the dual of the problem (1). (In the sequel we refer to a group

The Royal Institute of Technology Page 1 Dec 31, 1985

Page 2 of 11

INVESTIGATING SEM-INFINITE PROGPIAAB USING PENALTY FUNCTIONS AND AND LAGRANGLAN METHODS

of formulae whose members are distinguished by letters by giving the common element of the formula labels, i.e. the number).

(Equation Omitted)

over all vectors x E R' subject to the constraints

(Equation Omitted)

If Program(LD) has an optimal solution, then it has an optimal solution z with at most n positive components

(Equation Omitted)

Therefore we may reformulate Program(LD) thus t PR,ocRAM(LD), second formulation. Let

(Equation Omitted)

be as in Program(LP). Determine an integer q, a subset j.1 c f N} and reals

(Equation Omitted)

such that the expression

(Equation Omitted)

is rendered a maximum subject to the constraints

(Equation Omitted)

Here the columns of A are denoted

(Equation Omitted)

. We note that Program (LD) is feasible, if c C- Rn can be written as a nonnegative linear combination of the columns of A. If such a representation exists, then it is easy to es...