Constrained optimization

In mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.

Relation to constraint-satisfaction problems

The constrained-optimization problem (COP) is a significant generalization of the classic constraint-satisfaction problem (CSP) model.[1] COP is a CSP that includes an objective function to be optimized. Many algorithms are used to handle the optimization part.

General form

A general constrained minimization problem may be written as follows:[2]

where and are constraints that are required to be satisfied (these are called hard constraints), and is the objective function that needs to be optimized subject to the constraints.

In some problems, often called constraint optimization problems, the objective function is actually the sum of cost functions, each of which penalizes the extent (if any) to which a soft constraint (a constraint which is preferred but not required to be satisfied) is violated.

Solution methods

Many constrained optimization algorithms can be adapted to the unconstrained case, often via the use of a penalty method. However, search steps taken by the unconstrained method may be unacceptable for the constrained problem, leading to a lack of convergence. This is referred to as the Maratos effect.[3]

Equality constraints

Substitution method

For very simple problems, say a function of two variables subject to a single equality constraint, it is most practical to apply the method of substitution.[4] The idea is to substitute the constraint into the objective function to create a composite function that incorporates the effect of the constraint. For example, assume the objective is to maximize subject to . The constraint implies , which can be substituted into the objective function to create . The first-order necessary condition gives , which can be solved for and, consequently, .

Lagrange multiplier

If the constrained problem has only equality constraints, the method of Lagrange multipliers can be used to convert it into an unconstrained problem whose number of variables is the original number of variables plus the original number of equality constraints. Alternatively, if the constraints are all equality constraints and are all linear, they can be solved for some of the variables in terms of the others, and the former can be substituted out of the objective function, leaving an unconstrained problem in a smaller number of variables.

Inequality constraints

With inequality constraints, the problem can be characterized in terms of the geometric optimality conditions, Fritz John conditions and Karush–Kuhn–Tucker conditions, under which simple problems may be solvable.

Linear programming

If the objective function and all of the hard constraints are linear and some hard constraints are inequalities, then the problem is a linear programming problem. This can be solved by the simplex method, which usually works in polynomial time in the problem size but is not guaranteed to, or by interior point methods which are guaranteed to work in polynomial time.

Nonlinear programming

If the objective function or some of the constraints are nonlinear, and some constraints are inequalities, then the problem is a nonlinear programming problem.

Quadratic programming

If all the hard constraints are linear and some are inequalities, but the objective function is quadratic, the problem is a quadratic programming problem. It is one type of nonlinear programming. It can still be solved in polynomial time by the ellipsoid method if the objective function is convex; otherwise the problem may be NP hard.

KKT conditions

Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers. It can be applied under differentiability and convexity.

Branch and bound

Constraint optimization can be solved by branch-and-bound algorithms. These are backtracking algorithms storing the cost of the best solution found during execution and using it to avoid part of the search. More precisely, whenever the algorithm encounters a partial solution that cannot be extended to form a solution of better cost than the stored best cost, the algorithm backtracks, instead of trying to extend this solution.

Assuming that cost is to be minimized, the efficiency of these algorithms depends on how the cost that can be obtained from extending a partial solution is evaluated. Indeed, if the algorithm can backtrack from a partial solution, part of the search is skipped. The lower the estimated cost, the better the algorithm, as a lower estimated cost is more likely to be lower than the best cost of solution found so far.

On the other hand, this estimated cost cannot be lower than the effective cost that can be obtained by extending the solution, as otherwise the algorithm could backtrack while a solution better than the best found so far exists. As a result, the algorithm requires an upper bound on the cost that can be obtained from extending a partial solution, and this upper bound should be as small as possible.

A variation of this approach called Hansen's method uses interval methods.[5] It inherently implements rectangular constraints.

First-choice bounding functions

One way for evaluating this upper bound for a partial solution is to consider each soft constraint separately. For each soft constraint, the maximal possible value for any assignment to the unassigned variables is assumed. The sum of these values is an upper bound because the soft constraints cannot assume a higher value. It is exact because the maximal values of soft constraints may derive from different evaluations: a soft constraint may be maximal for while another constraint is maximal for .

This method[6] runs a branch-and-bound algorithm on problems, where is the number of variables. Each such problem is the subproblem obtained by dropping a sequence of variables from the original problem, along with the constraints containing them. After the problem on variables is solved, its optimal cost can be used as an upper bound while solving the other problems,

In particular, the cost estimate of a solution having as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved. More precisely, the cost of soft constraints containing both assigned and unassigned variables is estimated as above (or using an arbitrary other method); the cost of soft constraints containing only unassigned variables is instead estimated using the optimal solution of the corresponding problem, which is already known at this point.

There is similarity between the Russian Doll Search method and dynamic programming. Like dynamic programming, Russian Doll Search solves sub-problems in order to solve the whole problem. But, whereas Dynamic Programming directly combines the results obtained on sub-problems to get the result of the whole problem, Russian Doll Search only uses them as bounds during its search.

Bucket elimination

The bucket elimination algorithm can be adapted for constraint optimization. A given variable can be indeed removed from the problem by replacing all soft constraints containing it with a new soft constraint. The cost of this new constraint is computed assuming a maximal value for every value of the removed variable. Formally, if is the variable to be removed, are the soft constraints containing it, and are their variables except , the new soft constraint is defined by:

Bucket elimination works with an (arbitrary) ordering of the variables. Every variable is associated a bucket of constraints; the bucket of a variable contains all constraints having the variable has the highest in the order. Bucket elimination proceed from the last variable to the first. For each variable, all constraints of the bucket are replaced as above to remove the variable. The resulting constraint is then placed in the appropriate bucket.

See also

References

  1. ^ Rossi, Francesca; van Beek, Peter; Walsh, Toby (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Chapter 1 – Introduction", Foundations of Artificial Intelligence, Handbook of Constraint Programming, vol. 2, Elsevier, pp. 3–12, doi:10.1016/s1574-6526(06)80005-2, retrieved 2019-10-04
  2. ^ Martins, J. R. R. A.; Ning, A. (2021). Engineering Design Optimization. Cambridge University Press. ISBN 978-1108833417.
  3. ^ Wenyu Sun; Ya-Xiang Yuan (2010). Optimization Theory and Methods: Nonlinear Programming, Springer, ISBN 978-1441937650. p. 541
  4. ^ Prosser, Mike (1993). "Constrained Optimization by Substitution". Basic Mathematics for Economists. New York: Routledge. pp. 338–346. ISBN 0-415-08424-5.
  5. ^ Leader, Jeffery J. (2004). Numerical Analysis and Scientific Computation. Addison Wesley. ISBN 0-201-73499-0.
  6. ^ Verfaillie, Gérard, Michel Lemaître, and Thomas Schiex. "Russian doll search for solving constraint optimization problems." AAAI/IAAI, Vol. 1. 1996.

Further reading

Read other articles:

Der Titel dieses Artikels ist mehrdeutig. Zum Landkomtur siehe Johann Philipp von und zum Steinkallenfels. Steinkallenfels Die Burgen Stein und Kallenfels Die Burgen Stein und Kallenfels Staat Deutschland Ort Kirn, Stadtteil Kallenfells Entstehungszeit um 1200 Burgentyp Höhenburg Erhaltungszustand Ruine Geographische Lage 49° 48′ N, 7° 27′ O49.7973333333337.4423166666667Koordinaten: 49° 47′ 50,4″ N, 7° 26′ 32,3″ O p3w1 St...

Fränkische Saale in Bad Kissingen Die Liste der Fließgewässer im Flusssystem Fränkische Saale umfasst, im Gegensatz zur sortierbaren Tabelle Liste von Zuflüssen der Fränkischen Saale, neben den direkten Zuflüssen der Fränkischen Saale auch Nebenflüsse höherer Ordnung, soweit sie namentlich auf der Topographischen Karte 1:10000 Bayern Nord (DK 10) oder im Kartenservicesystem des Bayerischen Landesamts für Umwelt (LfU) aufgeführt werden. Namenlose Zuläufe und Abzweigungen werden ni...

Raja Kerajaan Amanuban Kerajaan Amanuban (Banam) adalah sebuah kerajaan yang terletak di pulau Timor bagian barat, wilayah Indonesia. Di era kemerdekaan, Kerajaan Amanuban bersama Kerajaan Molo (Oenam) dan Kerajaan Amanatun membentuk Kabupaten Timor Tengah Selatan (dalam bahasa Belanda disebut Zuid Midden Timor) di Provinsi Nusa Tenggara Timur dengan ibu kota So'E. Cikal bakal Kerajaan Amanuban (Banam) diawali dengan kehadiran Olak Mali, leluhur Raja Nope, dengan istrinya di Gunung Tunbes. Ol...

Besi,  26FeKubus dan potongan besi murni Garis spektrum besiSifat umumNama, lambangbesi, FePengucapan/bêsi/[1] Alotroplihat alotrop besiPenampilanmetalik berkilau dengan semburat kelabuBesi dalam tabel periodik Hidrogen Helium Lithium Berilium Boron Karbon Nitrogen Oksigen Fluor Neon Natrium Magnesium Aluminium Silikon Fosfor Sulfur Clor Argon Potasium Kalsium Skandium Titanium Vanadium Chromium Mangan Besi Cobalt Nikel Tembaga Seng Gallium Germanium Arsen Selen Bromin...

National Historic Site of Tanzania Kizimkazi Dimbani MosqueKizimkazi Mosque in late 19th CenturyShown within TanzaniaLocationKusini District, Unguja South Region, TanzaniaCoordinates6°26′9.96″S 39°27′44.64″E / 6.4361000°S 39.4624000°E / -6.4361000; 39.4624000TypeSettlementHistoryMaterialCoral ragFounded1107 CECulturesSwahiliSite notesOwnershipTanzanian GovernmentManagementAntiquities Division, Ministry of Natural Resources and Tourism [1]Archit...

البطولة الكندية لكرة القدم 2016 تفاصيل الموسم البطولة الكندية لكرة القدم  النسخة 9  البلد كندا  التاريخ بداية:11 مايو 2016  نهاية:29 يونيو 2016  المنظم اتحاد كندا لكرة القدم  البطل نادي تورونتو  مباريات ملعوبة 8   عدد المشاركين 5   أهداف مسجلة 20   الحضور الجما�...

French politician and businessman Augustin Thomas Pouyer-Quertier, (2 September 1820 – 2 April 1891) was Minister for Finance of France. He was born in Étouteville-en-Caux (Seine-Maritime) and died in Rouen. He developed a cotton factory and cotton agriculture in Algeria. He was one of the founders of Compagnie française du télégraphe de Paris à New-York, the French Telegraph Company, in 1879. Authority control databases International ISNI VIAF National France BnF data Germany United S...

Cataloging of published recordings by Eddie Money Eddie Money discographyMoney performing in 2006Studio albums11Live albums2Compilation albums7EPs4Singles28 The discography of American rock musician Eddie Money consists of 11 studio albums, two live albums, four EPs, and 28 singles. He also released seven compilation albums. Money's self-titled debut album was released in late 1977. The album spawned three singles, all of which charted on the Billboard Hot 100. However, only the first two: Ba...

Airport in Western Australia Mount Keith AirportIATA: WMEICAO: YMNESummaryAirport typePrivateOperatorBHPLocationMount Keith MineElevation AMSL1,792 ft / 546 mCoordinates27°17′07″S 120°32′59″E / 27.28528°S 120.54972°E / -27.28528; 120.54972MapYMNELocation in Western AustraliaRunways Direction Length Surface m ft 11/29 1,797 5,896 Sources: Australian AIP and aerodrome chart[1] Mount Keith Airport (IATA: WME, ICAO: YMNE) is located at Mo...

Комуто́вана лі́нія зв'язку́ (англ. Dial-up link) — лінія зв'язку, встановлювана лише на час з'єднання пристрою-передавача і пристрою-приймача. Для зв'язку з інтернетом, як правило, у даних лініях використовується модем і телефонна лінія. У комп'ютерних мережах використовують�...

American multi-level marketing company This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Sunrider – news · newspapers · books · scholar · JSTOR (March 2009) (Learn how and when to remove this template message) Sunrider InternationalTypePrivately held companyIndustryDirect sellingFoundedOrem, Utah in 1982FoundersTei-Fu Chen and Oi-Lin ChenHeadquartersTorra...

Cryptocurrency and Ethereum token ChainlinkDenominationsPluralChainlinkCodeLINKDevelopmentOriginal author(s)Sergey Nazarov, Steve Ellis, Dr. Ari Juels[1][2]White paperchain.link/whitepaperCode repositorygithub.com/smartcontractkit/chainlinkWritten inSolidity, GoOperating systemBlockchain-agnosticSource modelOpen sourceLicenseMIT LicenseLedgerSupply limit1,000,000,000WebsiteWebsitechainlinklabs.com Chainlink is a decentralized blockchain oracle network built on Ethereum.[3&...

Paco Muñoz Paco Muñoz en 2008Información personalNombre de nacimiento Francisco Muñoz Martínez Nacimiento 5 de enero de 1939 (84 años)Valencia (España) Nacionalidad EspañolaInformación profesionalOcupación Escritor y cantante Movimiento Nova cançó Instrumento Voz y guitarra Discográfica Movieplay [editar datos en Wikidata] Paco Muñoz (Valencia, 1939) es un cantante y escritor español de vocación tardía que, como Labordeta, empezó a cantar espoleado por Ovidi Montll...

American politician (1867–1931) George W. HarrisonNorth Dakota Insurance CommissionerIn office1899–1900Preceded byFrederick B. FancherSucceeded byFerdinand Leutz Personal detailsBornGeorge W. Harrison(1867-09-15)September 15, 1867Political partyRepublicanSpouseMyrtie E. Allen George W. Harrison (1867–1931) was a prominent journalist, newspaper editor and publisher, and North Dakota Republican Party politician who served as the fourth insurance commissioner of North Dakota from 1899 to 1...

Football clubOlney TownFull nameOlney Town Football ClubNickname(s)The NurserymenFounded1903Dissolved2018GroundEast Street, Olney Home colours Away colours Olney Town Football Club was a football club based in Olney, Buckinghamshire, England. History They were established in 1903 and were founder members of the North Bucks League in 1911. Following World War I they joined the South East Northants League, but returned to the North Bucks League in the 1930s, winning its second division in 1932�...

Icelandic Forest Service (Skógræktin)English logo of the Icelandic Forest ServiceEstablished2016 (Originally 1907)[1]HeadÞröstur Eysteinsson, directorStaff~ 70Formerly calledSkógrækt RíkisinsAddressMiðvangur 2 - 4, 700 Egilsstaðir, IcelandWebsitehttps://www.skogur.is/en The Icelandic Forest Service (Icelandic: Skógræktin [ˈskouː(ɣ)ˌraixtɪn]) (IFS) is a subordinate agency to the Ministry for the Environment and Natural Resources of the Government of Iceland. Thi...

United States historic placeSocialist HallU.S. National Register of Historic PlacesU.S. National Historic Landmark DistrictContributing Property Socialist Hall, Butte, MontanaShow map of MontanaShow map of the United StatesLocation1957 Harrison Ave., Butte, MontanaCoordinates45°59′39″N 112°30′45″W / 45.99417°N 112.51250°W / 45.99417; -112.51250Arealess than one acreBuilt1916ArchitectJ. Frank MabieArchitectural styleWestern CommercialNRHP reference...

Lukisan Manjuśrīkīrti, Raja Shambala. Menurut kepercayaan Buddhis dan Hindu, Shambala adalah sebuah kerajaan misterius yang tersembunyi di antara Gunung Himalaya dan Gurun Gobi.[1] Di Shambala, seluruh penduduknya telah mencapai pencerahan spiritual sehingga para pengikut Budhisme Tibet mengatakan bahwa para penduduk Shambala merupakan perwujudan dari kesempurnaan, Shambala juga dikenal dengan sebutan Tanah Suci.[1] Referensi ^ a b Szczepanski, Kallie. Where is Shambala. As...

ReokKecamatanNegara IndonesiaProvinsiNusa Tenggara TimurKabupatenManggaraiPopulasi • Total20,799 jiwa (BPS 2.018) jiwaKode Kemendagri53.10.11 Kode BPS5313140 Luas236,80 km²Desa/kelurahan6 desa4 kelurahan Perahu di pelabuhan Reo pada masa Hindia Belanda Reok (disebut juga Reo) adalah sebuah kecamatan di Kabupaten Manggarai, Nusa Tenggara Timur, Indonesia. Kecamatan ini terletak sekitar 60 Kilometer ke arah utara dari ibukota Kabupaten Manggarai. Pusat pemerintahannya berada d...

Administrative division of Syria Not to be confused with Hamas Government. Governorate in SyriaHama مُحافظة حماةḤamāGovernorateMap of Syria with Hama highlightedCoordinates (Hama): 35°12′N 37°12′E / 35.2°N 37.2°E / 35.2; 37.2Country SyriaCapitalHamaManatiq (Districts)5Government • GovernorMahmoud Zanubua[1]Area • Total8,883 km2 (3,430 sq mi) Estimates range between 8,844 km² and 8,...