Derivative Free Methods Based on a Game Approach to the Solution of Nonlinear Programming Problem
Alexey L. Sadovski
Texas A&M University-Corpus Christi
E-mail: Alexey.Sadovski@tamucc.edu
Keywords: Derivative free method, nonlinear programming, polyhedral game, iterative algorithm.
Abstract. The presentation deals with an application of the class of monotonic iterative algorithms for the solution of noncooperative games, developed by the author [1], to solve nonsmooth problems of mathematical programming without using derivative [2]. Namely, we are looking for the optimal solution of a nonlinear programming problem (NLP) by determining a set of saddle points of the Lagrangian function through solving corresponding polyhedral (matrix) game.
The proposed methods have some advantages, such as the simplicity of the each step and the polynomial convergence of the sequence of approximations to the optimal solution of the problem under consideration. Also, this approach is derivative free, and offers an opportunity to solve mathematical programming problems with pseudo- and quasi-concave (convex) objective functions and constraints without determining gradients or subgradients, if some of the functions does not have derivative. Besides, application of some finite algorithm, such as a simplex-method, to the matrix polyhedral game may solve nonlinear problems. The paper presents polyhedral game of the size (m+1)x(n+1), where m is a number of constraints and n is a number of variables in the given NLP.
Speaking of disadvantages we should mention, that convergence of the proposed algorithms is not as fast as a convergence of gradient methods.
Iterative Algorithms. Let us consider matrix game A=( aij ). There are two main ways to find optimal strategies for both players x*, y* and value of the game v(A): linear programming and iterative methods. To introduce iterative methods we need the following definitions:
These methods present simulation of the game played step by step in such a
way that each player uses ones best response for the accumulated mixed strategy
of the other player.
|
A=(L(ai,bj)) ,i=0,...,n, j=0,...,m |
|
Where ai and bj are vertices of the tetrahedrons for the initial and dual problems respectively:
ao = (0,...,0), ai = (0,...,nM,...,0) in Rn
bo = (0,...,0), bj = (0,...,mM,...,O) in Rm
Theorem: Let us assume that p*
and q* are optimal strategies for both players in
the game A, then optimal solution of the given problem of nonlinear programming
is:
|
x* = |
|
pi* ai |
and
|
f(x*) = |
|
|
pi* L(ai,bj) qi* = max f(x), |
if and only if an objective function f(x)
is a generalized pseudo-concave function, and constraints gk(x) are quasi-concave
functions. In the conclusion of the paper let us outline Linear Programming
(LP) problem, which is congruent to the given NLP problem. Assuming that f(x*)>0,
and letting zi = pi* / f(x*), we
have problem of linear programming:
|
min —> |
|
zi = 1/ f(x), |
such that for any j=1,…m
|
|
zi L(ai,bj) $ 1, i=1,…n. |
If z* is optimal linear plan for above LP, then f(x*)
=1/
zi*,
and optimal solution x* can be determined by the following
formula:
x*
= A (zi* ai) / / zi*.
Now it is easy to see, that the process of obtaining solution of the NLP may be converted to the solution of the matrix game, which, in its turn, is solved by iterative algorithm or by solving corresponding LP problem.
Some Open Problems. There are few open problems for the future research. First one is to compare effectiveness and complexity of proposed game-theoretical approaches for the solution of NLP problem with the more traditional gradient methods. The other open problem is possibility of applying such game based iterative algorithms to the solution of the global optimization.
REFERENCES
[1] Sadovski, A. A Game Approach to the Solution of Mathematical Programming Problems, Soviet Math. Doklady, vol. 20, # 3, p.446 (1979)
[2] Sadovski, A. A Game
Approach to the Solution of Nonlinear Programming Problem, Abstracts Fifth
[3] Belen'kii V., Volkonsii V., Iterative Methods in Game Theory and Programming, NAUKA (1974)