Т-экзистенциалды жай йонсондық теория болсын. Онда келесідей шарттар эквивалентті

1) Fr(X) -кемел.

2) E_n(Fr(X)) әлсіз толықтырған 3) E_n(Fr(X)) Стоун алгебрасы.

Дәлелдеуі:

Айтарлық Fr(X) йонсондық жиынның фрагменті болсын.

1) –ден 2) дәлелдейік. Т йонсондық теория кемел болсын, онда ол компаньоныне ие. Демек, бұл жағдайда біз тұжырымның шарты бойынша бізде, Fr^М(X)Fr⁰(X), мұндағы

) ( )

0(

EТ

Th X

Fr   -йонсондық теорияның Кайзерлік қабықшасы. Осылайша Fr^М(X) модельді

компоньонның анықтамасына сәйкес модельді толық, бізде онда қарастырылып отырған тілде сәйкесінше әрбір формулаішкі моделіне ModFr^М(X) қатысты тұрақты болады. Сәйкесінше, осы тілдің әрбір экзистенциалды формула ModFr^М(X) ішкі моделіне қатысты тұрақты, және сәйкесінше анықтама бойынша әрбір экзистенциалды формула ModFr^М(X)инвариантты болып келеді. Осыдан біз әрбір экзистенциалды формула әлсіз толықтыруы болатынын аламыз. Осылайша,

әлсіз толықтырылу.

2) =>1) дәлелдейік. Егер E_n(Fr(X)) әлсіз толықтыруы болса, онда Fr(X) теориясының модельді компанионы бар болады. Онда Fr(X)теориясы кемел және оның моделінің компаньоны Fr*(X) болады. Сондықтанда, Fr*(X)теориясы модельді толық. Сонымен, 1)-2) эквивалентті.

1)-ден 3) бойынша дәлелдейік. Айталық Fr(X) кемел болсын. Онда Тйонсондық теориясы кемел жәнеFr(X) теориясының модельді компаньоны бар болады. Теоремаға сәйкес йонсондық теорияның модельді компаньоны оның модельді толықтырылуы болып табылады. Онда, Т теориясының кемелділігінен E_n(Fr(X))-Стоун алгебрасы болады.

3) =>1) дәлелдейік. Егер де E_n(Fr(X))-Стоун алгебрасы болса, онда Т модельді компаньонға ие және де теорема бойынша Т кемел.

Келесі теоремада формулалар торы терминдерінде йонсондық теорияның йонсондық центрлер үшін қажетті және жеткілікті шарттары бар.

Теорема 2. Т-экзистенциалды жай йосондық теория, Х Т теориясының йонсондық жиыны олсын. Онда келесі шарттар эквивалентті:

1) Fr^*(X) -йонсондық теория, 2) әрбір ^TE_n(Fr(X)) кванторсыз әлсіз толықтыруға ие.

Дәлелдемелер үшін келесідей факті қажет:

Факт (*). [11] Егер де модельді компаньоны анықталған болса, онда модельді компаньоны де анықталған (T_)^M және T^M=(T_)^M тең.

Дәлелдеуі.

Айтарлық Fr(X) йонсондық жиынның фрагменті болсын.

1)-ден 2) дәлелдейік Fr(X)– йонсондық теория болсын, онда оның центрі Fr*(X)Th(C) жәнеFr(X) йонсондық теорияны қарастырамыз. Онда [11] Fr(X) теориясы кемел болып табылады.

Онда Fr(X)модельді компаньонға ие жәнеFr^*(X) -Fr(X) теориясының модельді толықтыруы болып табылады. Fr(X) теориясының кемелдігіне қарай,

Fr

_

( X )

-Т теориясының барлық универсалды қорытындысы болып табылады. Демек, *( ))

( )) (

(Fr X En Fr X

En  болсын. Онда

сәйкесінше ^T E_n(Fr(X)) әлсіз кванторсыз толықтыруға ие.

2)–ден 1) дәлелдейік. Әрбір



E_n(Fr(X)) әлсіз кванторсыз толықтыруға ие болсын.

Онда әрбір



E_n(Fr(X)) әлсіз толықтыруға ие, яғни



E_n(Fr(X)) әлсіз толықтыру болады.

Яғни [11] Дереккөзден шығатыны – йонсондық теория болып табылады.

Б) Айтарлық Fr(X) йонсондық теория емес болсын.

1. 1)-ден 2) дәлелдейік. Fr^*(X)– йонсондық теория болсын, онда ^*( )

)

*( ModFr X

EFr X  . Осыдан

біз,

)

*( X

EFr -ModFr^*(X) қамтитынын көреміз. Бірақ біз  

)

) ( 0(

X

EFr

X

Fr Кейзер қабықшасы

болатынын білеміз, осыдан шығатыны ModFr⁰(X)E_Fr(X) ModFr(X) бізге белгілі. Осыдан біз )

(X

Fr теориясы кемел болатынын көрдік. Демек, 1 теорема бойынша әрбір



E_n(Fr(X)) әлсіз кванторсыз толықтыруы бар. Онда, әрбір



E_n(Fr(X)) әлсіз кванторсыз толықтыруы барын көрдік. Әрбір



E_n(Fr(X)) әлсіз кванторсыз толықтыруға ие болсын. Онда, әрбір



E_n(Fr(X)) әлсіз кванторсыз толықтыруға ие әлсіз толықтыруы болады. Онда 2-теорема бойынша Fr(X)

теориясы кемел болады. Демек, Fr^*(X) теориясында кемел. Бұл дегеніміз Fr^*(X) теория екенін білдіреді.

Осылайша, теорема дәлелденді.

Пайданылған әдебиеттер тізімі:

1 Volker Weispfenning. The model-theoretic significance of complemented existential formulas. - The Journal of Symbolic Logic, Volume 46, Number 4, Dec. 1981, p.p. 843 – 849.

2 Мустафин Т.Г. Обобщенные условия Йонсона и описание обобщенно-йонсоновских теорий булевых алгебр. - Математические труды, Новосибирск, Изд. Инстит. Мат., 1998, т.1, №2, с.135-197.

3 Ешкеев А.Р., Оспанов Р.М. Связь йонсоновских теорий с теоремой Линдстрема. - Труды V-Казахско- Французского коллоквиума по теории моделей. Сборник научных трудов. – Караганда: Изд-во КарГУ, 2001, стр. 65-75.

4 Ешкеев А.Р., Оспанов Р.М. Йонсоновские теории и их компаньоны. - Материалы 10-й Межвузовской конференции по математике и механике. – т. 1, - Алматы: 2005. – с. 185-190.

5 Ешкеев А.Р., Оспанов Р.М. Некоторые свойства решетки формул йонсоновских теорий. - Международная конференция «Проблемы современной математики и механики», Алматы, 20-22 сентября, 2005, с.134.

6 Справочная книга по математической логике: В 4-х частях/ Под ред. Дж.Барвайса.-Ч.1. Теория моделей: пер. с англ. – М.: Наука. Главная редакция физико-математической литературы, 1982 г., с. 126.

7 Кейслер, Чэн. Теория моделей. – пер. с англ., М., Мир, 1977.

8 Биркгоф Г. Теория решеток. – пер. с англ. Салий В.Н., М.:Наука, 1984.

9 A.Macintyre. Model-completeness for sheaves of structures. – Fundamenta Mathematicae, vol.81 (1973), pp.73- 89.

10 Yerulan Mustafin. Quelques proprietes des theories de Jonsson. - The Journal of Symbolic Logic, Volume 67, Number 2, June 2002, p.p. 528 – 536.

11 Ешкеев А.Р., Касыметова М.Т. «Йонсоновские теории и их классы моделей» монография-Караганда:

Изд-во КарГУ, 2016-370 б. монография

12 Ешкеев А.Р., Шаматаева Н.К. Дөңес экзистенцианалды жай йонсондық теориялардың компьондарының қасиеттері//Хабаршы-Вестник Абай атындағы ҚазҰПУ .физ.мат.сер.-2016. -№3 (55).-Б. 77-83.

УДК 517.938 ГРНТИ 27.37.17

A.A. Kabidoldanova¹, A.K. Kalibekova²

1Cand. Sci.(Phys-Math), Acting Associate Professor of the Al-Farabi Kazakh National University, Almaty, Kazakhstan

2 Student of Master Programme in Mathematics, Al-Farabi Kazakh National University, Almaty, Kazakhstan AN ITERATIVE METHOD FOR CONVEX OPTIMIZATION

Abstract

In this work an algorithm for solving convex programming problem is proposed. The specific feature of the considered problem is that its constrains contain only linear equalities. This feature is a basis for the replacement the nonlinear objective function in the neighborhood of the tested point by a linear one, due to what solving an original problem is reduced to sequential solving linear programming problem. The obtained linear programming problem is solved by sequential correction the value of a objective function on the set of admissible solution and an admissible as well as optimal solutions are found. Further values of an objective function at the found admissible and optimal points are calculated and an auxiliary approach is determined. The next approach is defined as a convex combination of a previous and an auxiliary approach. Note that unlike the Lagrange multipliers method the developed method is applied to problems with the Lagrange function which hasn’t saddle point. The work contains a description of the method, a proof of its convergence, scheme of algorithm.

Key words: convex programming, linear constrains, linearization, admissible point, auxiliary approximation, optimal solution, optimization problem.

Аннотация

А.А. Кабидолданова¹, А.Қ. Қалибекова²

1 к.ф.-м.н., и.о. доцента Казахского национального университета им. аль-Фараби

2 магистрант Казахского национального университета им. аль-Фараби ИТЕРАЦИОННЫЙ МЕТОД ДЛЯ ВЫПУКЛОЙ ОПТИМИЗАЦИИ

В данной работе предлагается подход к решению задачи выпуклого программирования. Характерной особенностью рассматриваемой задачи является то, что ее система ограничений содержит только линейные равенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной целевой функции функцией линейной, благодаря чему решение исходной задачи сводится к последовательному решению задач линейного программирования. Полученная задача линейного программирования решается путем корректировки значения целевой функции на множестве допустимых решений и определяются допустимые и оптимальное решения. Далее вычисляются и сравниваются значения исходной целевой функции в найденных допустимых и оптимальной точках и определяется вспомогательное приближение. Следующее приближение определяется как выпуклая комбинация предыдущего и вспомогательного приближений. Следует отметить, что, в отличие от метода множителей Лагранжа, разработанный метод может быть применен и к задачам, для которых соответствующая функция Лагранжа не имеет седловой точки. Работа содержит описание метода, обоснование его сходимости, схемы алгоритмов и результаты экспериментов.

Ключевые слова: выпуклое программирование, линейные ограничения, линеаризация, допустимое решение, вспомогательное приближение, оптимальное решение, оптимизационная задача.

Аңдатпа

А.А. Кабидолданова¹, А.Қ. Қалибекова²

ДӨҢЕС ТИІМДІЛЕУ ҮШІН ИТЕРАЦИЯЛЫҚ ӘДІС

1ф.-м.ғ.к., әл-Фараби атындағы Қазақ ұлттық университетінің доцент міндетін атқарушысы

2 әл-Фараби атындағы Қазақ ұлттық университетінің 2- курс магистранты

Жұмыста дөңес программалау есебiн шешу жолы ұсынылады. Қарастырылып отырған есептiң ерекшелiгi оның шектеулерiнiң жүйесi тек сызықты теңдiктерден тұратындығында. Осы ерекшелiгi сызықты емес

мақсатты функцияны зерттелiп отырған нүктенiң маңайында сызықты функциямен ауыстыруға негiз болып табылады. Нәтижесiнде қойылған есеп сызықты программалау есептерiн шешуге әкелiнедi. Алынған есеп сызықты программалау есебi мүмкiн болатын шешiмдердiң жиынында мақсатты функцияның мәнiн түзету аркылы шешiлiп, мүмкiн болатын және тиiмдi шешiмдер табылады. Табылған мүмкiн болатын және тиiмдi нүктелерде максатты функцияның мәндерi есептелiп, көмекшi жуықтау анықталады. Келесi жуықтау алдынғы және көмекшi жуықтаулардың комбинациясы ретінде анықталады. Лагранж көбейткiштерi әдiсiмен салыстырғанда ұсынылып отырған әдiспен сәйкес Лагранж функциясының қайқы нүктесi жоқ болатын есептердi де шешуге болады. Жұмыста әдiстiң сипаттамасы, оның жинақталуының дәлелдеуi, алгоритмдер келтiрiлген.

Tүйiн сөздер: дөңес программалау, сызықты шектеулер, линеаризациялау, мүмкiн болатын шешiм, көмекшi жуықтау, тиiмдi шешiм, тиiмдiлеу есебi.

1. Introduction

The problems of mathematical programming are used in various fields of human activity where it is necessary to choose one of the possible modes of action (action programs). For example, in solving problems of management and planning of production processes, designing and prospective planning, in military affairs, etc. Section of mathematical programming, where problems with nonlinear objective function and (or), when at least one of the functions of the constraint system is nonlinear, is called nonlinear programming. Methods of non-linear programming have been widely used in the calculation of economically viable parties for launching components into production, in determining the economically advantageous supply line, the delivery set, the size of the reserves, the distribution of limited resources, the location of the productive forces, in the tare economy, in solving many production and economic tasks, etc. A wide class of mathematical programming problems is related to the minimization of convex functions of several variables defined on a convex set. Such problems are called convex programming problems. The method of Lagrange multipliers is a classical method for solving mathematical programming problems (in particular convex problems). Unfortunately, in the practical application of the method, considerable computational difficulties can occur, narrowing the field of its use [3]. The solution of the problem by the Lagrange method is obtained at the price of an increase in its dimension due to the introduction of indefinite Lagrange multipliers, the number of which is equal to the number of coupling equations. Therefore, with increasing number of variables and constraints, it is expediently to proceed to numerical methods of mathematical programming.

In addition, the method of Lagrange multipliers reduces the solution of the original problem to the search for a saddle point of the Lagrange function. However, there are problems of non-linear programming that have a solution, but their Lagrange function does not have saddle points.

In recent years, a large number of papers devoted to numerical methods for solving mathematical programming problems, based on the construction of modified Lagrange functions, have appeared. The method of modified Lagrange functions makes it possible to extend the scope of the Lagrange multiplier method and has as its goal to improve the efficiency of computational processes for finding saddle points.

However, just as the classical Lagrange multiplier method, for solvable problems, the corresponding modified Lagrange functions of which do not have saddle points, this method is not applicable. The numerical realization of the method of modified Lagrange functions involves the calculation of second derivatives that are not defined everywhere for many known modified Lagrange functions [4]. The method of gradient projection is applied on a set of such a type that the problem of finding the projection of a point is simple enough from the point of view of its numerical realization, since the solution of this problem determines the direction of descent. In the methods of penalty and barrier functions, the objective function is replaced by some generalized function whose values coincide with the values of the original function inside the admissible region, but when approaching the boundary of the domain, and even more so when leaving it sharply increase due to the second term of the generalized function. The search for a minimum point by the methods of penalty and barrier functions becomes more complicated if the extremum is reached at the boundary of the domain. Since the values of the generalized function as they approach the boundary of the domain are determined mainly by the magnitude of the second term, the extremum can not always be calculated with a given accuracy [3]. Attempts have been made to construct penalty functions, the parameters of which remain finite. Unfortunately, such penalty functions, as a rule, are either non-differentiable [5-7], or only locally differentiate [8];their use often does not make it possible to reduce the solution of the minimization problem with constraints to solving problems of unconditional minimization and is associated with the need to find a stationary or saddle point for a given penalty function [9-14]. A modification of the method of logarithmic barrier functions, based on the idea of a parametric displacement of the constraints of the original problem, was proposed.

It is known that the most common algorithmic apparatus of linear programming is the simplex method developed by J. Dancing [15]. The simplex method is simple for both mathematical intuitive understanding and implementation. The disadvantage of the simplex method is its sensitivity to the degeneracy of the problem, which can lead to an infinite number of iterations and the impossibility of constructing a sequence of control actions. System of solvability constraints and construction of a solution to the linear programming problem, developed by S.A. Aisagaliev [2], can be applied to both degenerate and non-degenerate linear programming problems.

2. Statement of the problem

Consider the problem of the following form inf

) (u 

J (1)

} 0 )

( , /

{   ₀   



U U R u U g u Au b

u ⁿ (2)

where J(u)C¹(U₀) is a convex function, defined on a convex set U₀,bR^m is a given vector, A is a given matrix of order mn,U₀uRⁿ/u_j 0, jI,I{1,2,,n}.

Let u₀ U be an arbitrary point. Define auxiliary approach u_kU,k0,1,2,..from the condition )

( min )

(u_k J u^m_dk

J  , m0,1,2,, (3)

where u_dk^m,m0,1,2,.., are admissible solutions of .

inf, ),

( )

(u J u u u u U

J_k   _k  _k   (4)

Note, that among admissible solutions u_dk^m,m0,1,2,..of the problem (4) there are also its optimal solutions.

Next approximation is constructed by the formula ),

1 k k( k k

k u u u

u_    (5)

here _k is defined from the condition

)).

( ( ) ( ], 1 , 0 [ ), ( min )

( _{k k k k k k}

k f f J u u u

f         (6)

3. Determination of the auxiliary approach

As it follows from (3), for determining auxiliary approach u_k U,k0,1,2,..,it is necessary to find admissible solutionsu_dk^m,m0,1,2,..,of the problem (4). Admissible solutions of the problem (4) are points of set U.

3.1. Optimization problem

Problem (4) is solved by reducing it to the problem of the following form



^{( )}

    

^inf,

) ,

( ^{2 *}

1 u  J u   Aub Aub 

J_k  _k  (7)



/



,

,

, ¹

0 Гk Гk R dk

U

u      (8)

here dk ^Jk

 

^ud ,^ud^Uis arbitrary point.

Consider the problem (7), (8) for fixed values of k and  _kГ_k. Now the problem (7), (8) has the form



( )

    

inf, )

, ( )

(u J₁ u  J u  ² Aub^* Aub 

F _k _{k k} _k (9)

U0

u . (10)

Lemma 1. Let inf ( ) ( ) 0.

0



  dk

U

u F u F u Then u_dkU₀ are admissible solutions of the problem (4).

Proof. Let inf ( ) ( ) 0

0



  dk

U

u F u F u , i.e.



J_k(u_dk)_k

 

² Au_dkb

 

^* Au_dk b



0,u_dkU₀. It follows from this that J_k(u_dk)_k, Au_dk b,u_dkU₀. That is u_dkU. In other words, u_dk is an admissible solution of problem (4). Lemma is proved.

As it follows from lemma 1, to construct admissible solutions of the problem (4) it is necessary to solve the problem (7), (8) for different values of _k and determine such values of



u,_k



, in which



,



inf

 

0. inf

0

0 1  



 J u Fu

U k u U k

u  If inf



,



inf

 

0

0

0 1  



 J u F u

U k u U k

u  , then there is no any point on the set U, which

gives the objective function ^Jk

 

^u the given value _k.

3.2. Properties of auxiliary objective functions

Lemma 2. The function F(u) is convex on the convex set U . ₀

Proof. We note, that the set U₀ is convex ,i.e. u¹(1)u²U₀ u₁,u₂U₀, [0,1].The function F(u)C²(U₀), partial derivatives

], [

2 ] ) ( )[

( 2 )

(u J u J u A Au b

F   _{k k} _k  ^ 

. 0 2

)) ( )(

( 2 )

(     

u J u J u ^ A^A

F _{k k}

Then, according to convexity criterion for smooth functions on a convex set, function F(u) is convex on U0. The lemma is proved.

In document №3(59) (бет 93-98)