Application of a Satisfactory Approximation of an Admissible Set for Solving Optimization Problems

A. A. Andrianova

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 154 (2012) no. 3, pp. 190-201

Résumé

This work deals with the properties and construction principles of a satisfactory approximation of a set of admissible solutions for a conditional optimization problem. The replacement of an initial admissible set by its satisfactory approximation allows one to construct finite algorithms for the methods of internal and external points (methods of penalty functions or methods of centers) with the stopping criterion which ensures the required accuracy of the solution. Necessary and sufficient conditions for producing external and internal satisfactory approximations of an admissible set are proved. One of the feasible ways for setting a satisfactory approximation of an admissible set is formulated. This way can be used for the development of algorithms that ensure the required accuracy in a finite number of iterations.

Détail

Keywords: methods of sequential unconstrained minimization, penalty function method, method of centers, solution of an optimization problem with a given accuracy, satisfactory approximation of an admissible set, feasible stopping criteria.

Bibliographie

[1] Grossman K., Kaplan A. A., Nelineinoe programmirovanie na osnove bezuslovnoi minimischatsii, Nauka, Novosibirsk, 1981, 183 pp.

[2] Evtushenko Yu. G., Zhadan V. G., K voprosu o sistematizatsii chislennykh metodov nelineinogo programmirovaniya, VTs AN SSSR, M., 1988, 66 pp. | MR

[3] Zhadan V. G., Chislennye metody lineinogo i nelineinogo programmirovaniya. Vspomogatelnye funktsii v uslovnoi minimizatsii, VTs im. A. A. Dorodnitsyna RAN, M., 2002, 160 pp.

[4] Zabotin Ya. I., Fukin I. A., “Ob odnoi modifikatsii metoda sdviga shtrafov dlya zadach nelineinogo programmirovaniya”, Izv. vuzov. Matem., 2000, no. 12, 49–54

[5] Zabotin Ya. I., Fukin I. A., “Algoritmy v metode shtrafov s approksimatsiei dopustimogo mnozhestva”, Izv. vuzov. Matem., 2004, no. 1, 36–47 | MR | Zbl

[6] Zabotin Ya. I., Andrianova A. A., “Algoritmy v metode tsentrov s approksimatsiei dopustimogo mnozhestva”, Izv. vuzov. Matem., 2001, no. 12, 41–45 | MR | Zbl

[7] Andrianova A. A., Zabotin Ya. I., “Upravlenie protsessom minimizatsii v parametrizovannom metode tsentrov”, Izv. vuzov. Matem., 2002, no. 12, 3–10

[8] Andrianova A. A., “Parametrizatsiya metoda tsentrov dlya minimizatsii yavno kvazivypuklykh funktsii”, Issledovaniya po prikladnoi matematike i informatike, 26, Izd-vo Kazan. matem. o-va, Kazan, 2006, 3–12 | MR

[9] Andrianova A. A., “Printsipy postroeniya approksimatsii dopustimogo mnozhestva pri reshenii zadach uslovnoi optimizatsii s zadannoi tochnostyu”, Metody optimizatsii i ikh prilozheniya, Trudy XV Baikalskoi mezhdunar. shkoly-seminara, v. 2, Matematicheskoe programmirovanie, RIO IDSTU SO RAN, Irkutsk, 2011, 35–38

[10] Sukharev A. G., Timokhov A. V., Fedorov V. V., Kurs metodov optimizatsii, Fizmatlit, M., 2005, 368 pp.

[11] Zabotin Ya. I., Danshin I. N., “Algoritmy s kombinirovaniem, parametrizatsiei i dvustoronnim priblizheniem v metode tsentrov”, Izv. vuzov. Matem., 1998, no. 12, 40–48

[12] Zabotin Ya. I., “Minimaksnyi metod resheniya zadachi matematicheskogo programmirovaniya”, Izv. vuzov. Matem., 1975, no. 6, 36–43 | MR

[13] Fukin I. A., “$\rho$-approksimiruemost vypuklykh funktsii”, Algoritmicheskii analiz neustoichivykh zadach, Tez. dokl. Vseros. konf. (Ekaterinburg, 2–6 fevr. 2004), Izd-vo Ural. un-ta, Ekaterinburg, 2004, 306–307 | Zbl

[14] Korablev A. I., “O relaksatsionnykh metodakh minimizatsii psevdovypuklykh funktsii”, Issledovanie po prikladnoi matematike, 8, Izd-vo Kazan. un-ta, Kazan, 1980, 3–8