Abstract
A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject tox∈D,g(x)≥0, whereD is a closed convex subset ofR n andf,g are convex finite functionsR n. Under suitable stability hypotheses, it is shown that a feasible point\(\bar x\) is optimal if and only if 0=max{g(x):x∈D,f(x)≤f(\(\bar x\))}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Rosen, J. B.,Iterative Solution of Nonlinear Optimal Control Problems, SIAM Journal on Control, Vol. 4, pp. 223–244, 1966.
Avriel, M., andWilliams, A. C.,Complementary Geometric Programming, SIAM Journal on Applied Mathematics, Vol. 19, pp. 125–141, 1970.
Meyer, R.,The Validity of a Family of Optimization Methods, SIAM Journal on Control, Vol. 8, pp. 41–54, 1970.
Ueing, U.,A Combinatorial Method to Compute a Global Solution of Certain Nonconvex Optimization Problems, Numerical Methods for Nonlinear Optimization, Edited by F. A. Lootsma, Academic Press, New York, New York, pp. 223–230, 1972.
Bansal, P. P., andJacobsen, S. E.,Characterization of Local Solutions for a Class of Nonconvex Programs, Journal of Optimization Theory and Applications, Vol. 15, pp. 549–564, 1975.
Hillestad, R. J., andJacobsen, S. E.,Reverse Convex Programming, Applied Mathematics and Optimization, Vol. 6, pp. 63–78, 1980.
Hillestad, R. J., andJacobsen, S. E.,Linear Programs with an Additional Reverse Convex Constraint, Applied Mathematics and Optimization, Vol. 6, pp. 257–269, 1980.
Tuy, H.,Global Minimization of a Concave Function Subject to Mixed Linear and Reverse Convex Constraints, Proceedings of the IFIP Working Conference on Recent Advances in System Modeling and Optimization, Hanoi, Vietnam, 1983.
Thuong, Ng. V., andTuy, H. A Finite Algorithm For Solving Linear Programs with an Additional Reverse Convex Constraint, Proceedings of the IIASA Workshop on Nondifferentiable Optimization, Sopron, Hungary, 1984.
Zaleesky, A. B.,Nonconvexity of Feasible Domains and Optimization of Management Decisions (in Russian), Ekonomika i Matematitcheskie Metody, Vol. 16, pp. 1069–1081, 1980.
Singer, I.,Minimization of Continuous Convex Functionals on Complements of Convex Sets, Mathematische Operationsforschung und Statistik, Series Optimization, Vol. 11, pp. 221–234, 1980.
Tuy, H., andThuong, Ng. V.,Minimizing a Convex Function over the Complement of a Convex Set, Proceedings of the 9th Symposium on Operations Research, Osnabrück, Germany, 1984.
Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
Polyakova, L. N.,Necessary Conditions for an Extremum of Quasidifferentiable Functions (in Russian), Vestnik Leningrad University, Mathematics, Vol. 13, pp. 241–247, 1981.
Toland, J. F.,On Subdifferential Calculus and Duality in Nonconvex Optimization, Analyse Nonconvexe, Bulletin de la Société Mathématique de France, Mémoire 60, pp. 177–183, 1979.
Hoffman, K. L.,A Method for Globally Minimizing Concave Functions over Convex Sets, Mathematical Programming, Vol. 20, pp. 22–32, 1981.
Horst, R.,An Algorithm for Nonconvex Programming Problems, Mathematical Programming, Vol. 10, pp. 312–321, 1976.
Thieu, T. V., Tam, B. T., andBan, V. T.,An Outer Approximation Method for Globally Minimizing a Concave Function over a Compact Convex Set, Proceedings of the IFIP Working Conference on Recent Advances in System Modeling and Optimization, Hanoi, Vietnam, 1983.
Tuy, H., Thieu, T. V. andThai, Ng. Q.,A Conical Algorithm for Globally Minimizing a Concave Function over a Closed Convex Set, Mathematics of Operations Research, Vol. 10, pp. 498–514, 1985.
Tuy, H.,On Outer Approximation Methods for Solving Concave Minimization Problems, Acta Mathematica Vietnamica, Vol. 8, pp. 3–34, 1983.
Tuy, H.,Concave Programming under Linear Constraints, Soviet Mathematics, Vol. 5, pp. 1437–1440, 1964.
Tuy, H., andThai, Ng. Q.,Minimizing a Concave Function over a Compact Convex Set, Acta Mathematica Vietnamica, Vol. 8, pp. 13–20, 1983.
Tuy, H. Global Minimization of a Difference of Two Convex Functions, Selected Topics in Operations Research and Mathematical Economics, Edited by H. Pallaschlke, Springer-Verlag, Berlin, Germany, pp. 98–118, 1984.
Falk, J. E., andHoffman, K. R.,A Successive Underestimation Method for Concave Minimization Problems, Mathematics of Operations Research, Vol. 1, pp. 251–259, 1976.
Author information
Authors and Affiliations
Additional information
Communicated by A. V. Fiacco
Rights and permissions
About this article
Cite this article
Tuy, H. Convex programs with an additional reverse convex constraint. J Optim Theory Appl 52, 463–486 (1987). https://doi.org/10.1007/BF00938217
Issue Date:
DOI: https://doi.org/10.1007/BF00938217