Di-linyar na programming

Nonlinear na Programming (NLP) — ito ay isang sangay ng mathematical programming at operations research na nagtatrabaho sa mga problema ng optimization, kung saan ang objective function at/o kahit isa sa mga hadlang ay nonlinear na mga function ng mga decision variable.

Ang NLP ay isang pangkalahatang anyo ng linear programming at nagbibigay-daan sa pag-modelo ng mas malawak na klase ng mga tunay na sistema at proseso, kung saan ang mga ugnayan sa pagitan ng mga variable ay hindi mahigpit na proporsyonal (ibig sabihin, inilalarawan ng mga kurba, hindi ng mga tuwid na linya).

Paksa at layunin

Ginagamit ang Nonlinear na Programming upang mahanap ang mga pinakamainam na solusyon sa mga sitwasyong kung saan:

• Ang ugnayan ng target na tagapagpahiwatig (kita, gastos, kahusayan, atbp.) sa mga kontroladong parameter ay nonlinear (halimbawa, bumababang kita mula sa sukat, quadratic na gastos).
• Ang mga hadlang sa mga mapagkukunan o teknolohikal na proseso ay inilalarawan ng mga nonlinear na relasyon (halimbawa, mga reaksyong kemikal, mga batas ng pisika, mga ekonomikong ugnayan).

Ang mga problema ng NLP ay lumilitaw sa maraming larangan:

• Inhinyerong disenyo (pag-optimize ng mga istruktura, proseso).
• Ekonomiya at pananalapi (pag-optimize ng portfolio na isinasaalang-alang ang panganib, pagmomodelo ng merkado).
• Teknolohiyang kemikal (pag-optimize ng mga rehimen ng reaktor).
• Machine Learning (pagsasanay ng mga neural network, support vector machine).
• Pamamahala ng mga proseso sa produksyon. Logistics (na isinasaalang-alang ang mga nonlinear na gastos).

Matematikal na pagbabalangkas ng problema ng NLP

Ang pangkalahatang problema ng nonlinear na programming ay binubalangkas tulad ng sumusunod:

Kailangan hanapin ang hanay ng mga halaga ng mga decision variable na nagpapalaki o nagpapaliit ng nonlinear na objective function. Sa gayon, ang mga halaga ng mga variable ay dapat matugunan ang sistema ng mga hadlang, na maaaring ipahayag kapwa sa anyo ng mga hindi pagkakapantay-pantay (halimbawa, "ang halaga A ay dapat mas maliit o katumbas ng B"), at sa anyo ng mga pagkakapantay-pantay (halimbawa, "ang halaga C ay dapat eksaktong katumbas ng D"). Mahalaga na kahit isa sa mga function na naglalarawan ng layunin o mga hadlang ay nonlinear. Madalas na idinaragdag ang mga kondisyon ng hindi negatibidad ng mga variable, ibig sabihin, ang kinakailangang ang kanilang mga halaga ay mas malaki o katumbas ng zero.

Ang hanay ng lahat ng mga kumbinasyon ng mga halaga ng variable na nakakatugon sa mga hadlang ay bumubuo ng feasible region ( FR).

Mga pagkakaiba mula sa linear programming

Ang Nonlinear na Programming ay makabuluhang naiiba mula sa linear programming (LP):

• Nonlinearity: Ang objective function o mga hadlang (o parehong ito) ay naglalaman ng mga nonlinear na ugnayan.
• Mga katangian ng FR: Ang feasible region sa NLP ay maaaring hindi convex (hindi tulad ng LP, kung saan ang FR ay palaging isang convex na polygon).
• Mga katangian ng optimum: Ang pinakamainam na solusyon sa NLP ay hindi kinakailangang nasa sulok ng FR; maaari itong nasa hangganan o sa loob ng rehiyon. Sa NLP ay maaaring may mga lokal na optimum na hindi mga global na optimum.
• Kahirapan ng paglutas: Ang mga problema ng NLP ay karaniwang mas mahirap lutasin kaysa sa mga problema ng LP. Walang iisang unibersal na algorithm, katulad ng simplex method, para sa lahat ng problema ng NLP.

Mga pangunahing kahirapan at hamon ng NLP

Ang paglutas ng mga problema ng nonlinear na programming ay sinasamahan ng ilang mga kahirapan:

• Pagkakaroon ng mga lokal na ekstremum: Karamihan sa mga paraan ng NLP ay ginagarantiyahan lamang ang paghahanap ng lokal na optimum (isang solusyon na mas mabuti sa isang tiyak na kapaligiran). Ang paghahanap ng global na optimum (ang pinakamainam na solusyon sa buong FR) ay isang kumplikadong gawain, lalo na para sa mga hindi convex na problema.
• Hindi convexity: Kung ang problema ay hindi convex (ang objective function o ang FR ay hindi convex), maaaring mayroon ng maraming lokal na optimum, at ang mga karaniwang gradient na paraan ay maaaring \"matigil\" sa isa sa mga ito.
• Computational complexity: Ang mga algorithm ng paglutas ng NLP ay kadalasang nangangailangan ng mas malaking computational resources kumpara sa LP.

Mahahalagang klase ng mga problema ng NLP

Sa kabila ng pangkalahatang kahirapan, may mga mahahalagang subclass ng mga problema ng NLP kung saan nalinang ang mga epektibong pamamaraan ng paglutas:

• Convex programming: Ang problema ng pagliit ng isang convex na function sa isang convex na hanay ng mga tanggap na solusyon (o pagpapalaki ng isang concave na function). Pangunahing katangian: anumang lokal na minimum ay global na minimum din. Ito ay lubos na nagpapadali sa paghahanap ng pinakamainam na solusyon.
• Quadratic programming: Ang objective function ay quadratic, at lahat ng mga hadlang ay linear.
• Separable programming: Ang objective function at mga hadlang ay maaaring ilarawan bilang mga kabuuan ng mga function, na ang bawat isa ay nakasalalay lamang sa isang variable.

Mga paraan ng paglutas ng mga problema ng NLP

Mga paraan ng paglutas ng mga problema ng nonlinear na programming (NLP)

I. Mga paraan ng walang kondisyong optimization (optimization nang walang mga hadlang):

• Mga gradient na paraan (paraan ng pinakamabilis na pagbaba, paraan ng conjugate gradients);
• Paraan ni Newton at quasi-Newton na mga paraan (halimbawa, BFGS);
• Mga paraan gamit ang approximation ng Hessian.

II. Mga paraan ng may kondisyong optimization (optimization na may mga hadlang):

• Mga paraan ng pagbabago:
  • Paraan ng penalty functions;
  • Paraan ng barrier functions.
• Mga paraan ng direktang paghahanap ng direksyon:
  • Paraan ng mga posibleng direksyon.
• Mga paraan batay sa mga kondisyon ng optimality:
  • Mga paraan ng Karush-Kuhn-Tucker (KKT conditions);
  • Paraan ng Lagrange multipliers.
• Mga iterative na paraan:
  • Sequential Quadratic Programming (SQP);
  • Mga paraan ng interior point.

III. Mga paraan ng global na optimization:

• Mga heuristic at metaheuristic na paraan:
  • Genetic algorithms;
  • Simulated annealing;
  • Tabu search.
• Mga deterministikong paraan:
  • Branch and bound;
  • Mga algorithm ng global na optimization para sa mga problemang may espesyal na istruktura.

Mga sanggunian

• Bazara M., Shetty K. Nonlinear na Programming. Teorya at mga algorithm. — M.: Mir, 1982.
• Fiacco A., McCormick G. Nonlinear na Programming. Mga paraan ng sunud-sunod na walang kondisyong minimization. — M.: Mir, 1972.
• Himmelblau D. Inilapat na Nonlinear na Programming. — M.: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Tingnan din

• Operations Research
• Optimization
• Linear programming
• Convex programming
• Objective function
• Mga hadlang
• Feasible region