단편 선형 근사법을 이용한 비선형 제약 최적화에 대한 입문서

A general constrained optimization problem is to select real decision variables from a given feasible region in such a way as to optimize (minimize or maximize) a given objective function \[f(x_0,x_1,\dots,x_{n-1}).\] We usually let denote the vector of real decision variables That is, and write the general nonlinear program as: \[\begin{aligned}\text{ Maximize }&f(x)\\\text{ Subject to }&g_i(x)\leq b_i&&\qquad(i=0,1,\dots,m-1)\\&x\in\mathbb{R}^n\end{aligned}\] where each of the constraint functions through is given, and each is a constant (Bradley et al., 1977). This is only one possible way to write the problem. Minimizing is equivalent to maximizing Likewise, an equality constraint can be expressed as the pair of inequalities and Moreover, by adding a slack variable, any inequality can be converted into an equality constraint (Bradley et al., 1977). These types of problems appear across many application areas, for example, in business settings where a company aims to maximize profit or minimize costs while operating on resources or funding constraints (Cherry, 2016). If is a linear function and the constraints are linear, then the problem is called a linear programming problem (LP) (Cherry, 2016). “The problem is called a nonlinear programming problem (NLP) if the objective function is nonlinear and/or the feasible region is determined by nonlinear constraints.” (Bradley et al., 1977, p. 410) The assumptions and approximations used in linear programming can sometimes produce a suitable model for the decision variable ranges of interest. In other cases, however, nonlinear behavior in the objective function and/or the constraints is essential to formulate the application as a mathematical program accurately (Bradley et al., 1977). Nonlinear programming refers to methods for solving an NLP. Although many mature solvers exist for LPs, NLPs, especially those involving higher-order nonlinearities, are typically more difficult to solve (Cherry, 2016). Challenging nonlinear programming problems arise in areas such as electronic circuit design, financial portfolio optimization, gas network optimization, and chemical process design (Cherry, 2016). One way to tackle nonlinear programming problems is to linearize them and use an LP solver to obtain a good approximation. One would like to do that for several reasons. For instance, linear models are usually faster to solve and can be more numerically stable. To move from theory to a working Python model, we will walk through the following sections: - Separable Functions - Example - Special Ordered Sets of Type 2 - On Convex and Concave Functions - Python Implementation - Further Readings - Conclusion - References This text assumes some familiarity with mathematical programming. After defining Separable Functions, we present a separable nonlinear maximization Example and outline an approach based on piecewise linear (PWL) approximations of the nonlinear objective function. Next, we define Special Ordered Sets of Type 2 and explain how they support the numerical formulation. We then introduce the theoretical background in On Convex and Concave Functions, providing tools used throughout the remainder of this work on nonlinear programming (NLP). Finally, we present a Python Implementation procedure that uses Gurobipy and PWL approximations of the nonlinear objective function, enabling LP/MIP solvers to obtain useful approximations for fairly large NLPs. Separable Functions This article’s solution procedure is for separable programs. Separable programs are optimization problems of the form: \[\begin{aligned}\text{ Maximize }&\sum\limits_{j=0}^{n-1}f_j(x_j)\\\text{ Subject to }&\sum\limits_{j=0}^{n-1} g_{ij}(x_j)\leq 0\qquad(i=0,1,\dots,m-1)\\&x\in\mathbb{R}^n\end{aligned}\] where each of the functions and are known. These problems are called separable because the decision variables appear separately: one in each constraint function and one in each objective function (Bradley et al., 1977). Example Consider the following problem from Bradley et al. (1977) that arises in portfolio selection: \[\begin{aligned}\text{ Maximize }&f(x)=20x_0+16x_1-2x_0^2-x_1^2-(x_0+x_1)^2\\\text{ Subject to }&x_0+x_1\leq5\\&x_0\geq0,x_1\geq0.\end{aligned}\] As stated, the problem is not separable because of the term in the objective function. However, nonseparable problems can frequently be reduced to a separable form using various formulation tricks. In particular, by letting we can re-express the problem above in separable form as: \[\begin{aligned}\text{ Maximize }&f(x)=20x_0+16x_1-2x_0^2-x_1^2-x_2^2\\\text{ Subject to }&x_0+x_1\leq5\\&x_0+x_1-x_2=0\\&x_0\geq0,x_1\geq0,x_2\geq 0.\end{aligned}\] Clearly, the linear constraints are separable, and the objective function can now be written as where \[\begin{aligned}f_0(x_0)&=20x_0-2x_0^2\\f_1(x_1)&=16x_1-x_1^2\end{aligned}\] and \[f_2(x_2)=-x_2^2.\] To form the approximation problem, we approximate each nonlinear term by a piecewise linear functio