333:
763:, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem.
142:
328:{\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}
708:
147:
947:
827: â optimization problem with a finite number of variables and an infinite number of constraints, or an infinite number of variables and a finite number of constraints
940:
933:
610:
748:
that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from
1137:
812: â Cognitive heuristic of searching for an acceptable decision â the optimum need not be found, just a "good enough" solution.
1037:
1129:
887:
862:
1142:
783:
1376:
1162:
1079:
772:
726:
96:
1182:
906:
1147:
466:
460:
1187:
1177:
824:
20:
786: â theorem that asserts that there exist nearly optimal solutions to some optimization problems
1167:
1152:
994:
439:, the problem is an unconstrained optimization problem. By convention, the standard form defines a
385:
136:
117:
1237:
1214:
1108:
1032:
849:
760:
108:
1355:
1316:
1232:
1157:
1084:
1069:
1022:
567:
62:
1301:
1293:
1289:
1285:
1281:
1277:
1089:
587:
581:
559:
79:
47:
1094:
960:
925:
8:
1027:
1017:
1012:
803:
778:
113:
84:
66:
756:
that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.
1256:
974:
354:
1074:
883:
858:
501:
70:
55:
1227:
1172:
1063:
1058:
792:
713:
448:
61:
Optimization problems can be divided into two categories, depending on whether the
35:
1247:
1218:
1192:
1113:
1098:
1007:
979:
956:
344:
1334:
1242:
1103:
1002:
815:
131:
1370:
1118:
798:
100:
806: â Discipline concerning the application of advanced analytical methods
1339:
716:
that asks whether there is a feasible solution for some particular measure
348:
1329:
1324:
1208:
809:
570:
92:
31:
27:
1252:
1222:
984:
818: â type of computational problem represented by a binary relation
712:
For each combinatorial optimization problem, there is a corresponding
39:
1261:
1042:
88:
77:
An optimization problem with discrete variables is known as a
955:
703:{\displaystyle m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.}
740:, an optimization problem might be "find a path from
613:
454:
145:
829:
Pages displaying wikidata descriptions as a fallback
820:
Pages displaying wikidata descriptions as a fallback
788:
Pages displaying wikidata descriptions as a fallback
702:
327:
124:
106:A problem with continuous variables is known as a
907:"How Traffic Shaping Optimizes Network Bandwidth"
1368:
847:
848:Boyd, Stephen P.; Vandenberghe, Lieven (2004).
941:
16:Problem of finding the best feasible solution
857:. Cambridge University Press. p. 129.
595:The goal is then to find for some instance
948:
934:
203:
871:
877:
19:For broader coverage of this topic, see
1038:Locally convex topological vector space
878:Ausiello, Giorgio; et al. (2003),
1369:
929:
795: â Type of computational problem
775: â Type of computational problem
579:is the goal function, and is either
112:, in which an optimal value from a
13:
455:Combinatorial optimization problem
207:
204:
200:
197:
194:
191:
188:
185:
182:
14:
1388:
899:
528:is the set of feasible solutions;
882:(Corrected ed.), Springer,
116:must be found. They can include
1143:Ekeland's variational principle
784:Ekeland's variational principle
603:, that is, a feasible solution
299:
242:
125:Continuous optimization problem
841:
689:
683:
663:
646:
629:
617:
287:
281:
230:
224:
173:
167:
1:
834:
773:Counting problem (complexity)
725:. For example, if there is a
880:Complexity and Approximation
7:
1163:HermiteâHadamard inequality
766:
10:
1393:
467:combinatorial optimization
461:Combinatorial optimization
458:
18:
1348:
1315:
1270:
1201:
1127:
1051:
993:
967:
825:Semi-infinite programming
358:to be minimized over the
21:Mathematical optimization
1349:Applications and related
1153:Fenchel-Young inequality
761:approximation algorithms
732:which contains vertices
535:and a feasible solution
451:the objective function.
139:optimization problem is
120:and multimodal problems.
1109:Legendre transformation
1033:Legendre transformation
109:continuous optimization
1377:Computational problems
1356:Convexity in economics
1290:(lower) ideally convex
1148:FenchelâMoreau theorem
1138:Carathéodory's theorem
704:
329:
1278:Convex series related
1178:ShapleyâFolkman lemma
705:
566:, which is usually a
330:
99:must be found from a
80:discrete optimization
1168:KreinâMilman theorem
961:variational analysis
611:
445:maximization problem
441:minimization problem
406:equality constraints
143:
118:constrained problems
44:optimization problem
1158:Jensen's inequality
1028:Lagrange multiplier
1018:Convex optimization
1013:Convex metric space
851:Convex Optimization
804:Operations research
779:Design Optimization
114:continuous function
1286:(cs, bcs)-complete
1257:Algebraic interior
975:Convex combination
700:
531:given an instance
507:given an instance
447:can be treated by
355:objective function
325:
323:
159:
56:feasible solutions
54:solution from all
1364:
1363:
889:978-3-540-65431-5
864:978-0-521-83378-3
362:-variable vector
152:
1384:
1282:(cs, lcs)-closed
1228:Effective domain
1183:RobinsonâUrsescu
1059:Convex conjugate
950:
943:
936:
927:
926:
922:
920:
918:
893:
892:
875:
869:
868:
856:
845:
830:
821:
793:Function problem
789:
759:In the field of
755:
751:
747:
743:
739:
735:
731:
724:
714:decision problem
709:
707:
706:
701:
696:
692:
676:
662:
606:
601:optimal solution
598:
590:
584:
578:
565:
557:
542:
538:
534:
527:
516:
499:
492:
472:
438:
423:
416:
403:
381:
365:
361:
351:
334:
332:
331:
326:
324:
280:
279:
269:
268:
267:
223:
222:
212:
210:
179:
162:
160:
149:
36:computer science
1392:
1391:
1387:
1386:
1385:
1383:
1382:
1381:
1367:
1366:
1365:
1360:
1344:
1311:
1266:
1197:
1123:
1114:Semi-continuity
1099:Convex function
1080:Logarithmically
1047:
1008:Convex geometry
989:
980:Convex function
963:
957:Convex analysis
954:
916:
914:
905:
902:
897:
896:
890:
876:
872:
865:
854:
846:
842:
837:
828:
819:
787:
769:
753:
749:
745:
741:
737:
733:
729:
723:
717:
669:
655:
642:
638:
612:
609:
608:
604:
596:
586:
580:
576:
563:
544:
540:
536:
532:
518:
508:
497:
474:
473:is a quadruple
470:
463:
457:
429:
418:
411:
396:
391:
374:
369:
363:
359:
339:
322:
321:
275:
271:
265:
264:
218:
214:
211:
181:
177:
176:
161:
151:
146:
144:
141:
140:
127:
50:of finding the
24:
17:
12:
11:
5:
1390:
1380:
1379:
1362:
1361:
1359:
1358:
1352:
1350:
1346:
1345:
1343:
1342:
1337:
1335:Strong duality
1332:
1327:
1321:
1319:
1313:
1312:
1310:
1309:
1274:
1272:
1268:
1267:
1265:
1264:
1259:
1250:
1245:
1243:John ellipsoid
1240:
1235:
1230:
1225:
1211:
1205:
1203:
1199:
1198:
1196:
1195:
1190:
1185:
1180:
1175:
1170:
1165:
1160:
1155:
1150:
1145:
1140:
1134:
1132:
1130:results (list)
1125:
1124:
1122:
1121:
1116:
1111:
1106:
1104:Invex function
1101:
1092:
1087:
1082:
1077:
1072:
1066:
1061:
1055:
1053:
1049:
1048:
1046:
1045:
1040:
1035:
1030:
1025:
1020:
1015:
1010:
1005:
1003:Choquet theory
999:
997:
991:
990:
988:
987:
982:
977:
971:
969:
968:Basic concepts
965:
964:
953:
952:
945:
938:
930:
924:
923:
913:. 12 July 2016
901:
900:External links
898:
895:
894:
888:
870:
863:
839:
838:
836:
833:
832:
831:
822:
816:Search problem
813:
807:
801:
796:
790:
781:
776:
768:
765:
721:
699:
695:
691:
688:
685:
682:
679:
675:
672:
668:
665:
661:
658:
654:
651:
648:
645:
641:
637:
634:
631:
628:
625:
622:
619:
616:
593:
592:
574:
529:
505:
459:Main article:
456:
453:
426:
425:
409:
394:
389:
372:
367:
320:
317:
314:
311:
308:
305:
302:
298:
295:
292:
289:
286:
283:
278:
274:
270:
266:
263:
260:
257:
254:
251:
248:
245:
241:
238:
235:
232:
229:
226:
221:
217:
213:
209:
206:
202:
199:
196:
193:
190:
187:
184:
180:
178:
175:
172:
169:
166:
163:
158:
155:
150:
148:
126:
123:
122:
121:
104:
83:, in which an
15:
9:
6:
4:
3:
2:
1389:
1378:
1375:
1374:
1372:
1357:
1354:
1353:
1351:
1347:
1341:
1338:
1336:
1333:
1331:
1328:
1326:
1323:
1322:
1320:
1318:
1314:
1307:
1305:
1299:
1297:
1291:
1287:
1283:
1279:
1276:
1275:
1273:
1269:
1263:
1260:
1258:
1254:
1251:
1249:
1246:
1244:
1241:
1239:
1236:
1234:
1231:
1229:
1226:
1224:
1220:
1216:
1212:
1210:
1207:
1206:
1204:
1200:
1194:
1191:
1189:
1186:
1184:
1181:
1179:
1176:
1174:
1173:Mazur's lemma
1171:
1169:
1166:
1164:
1161:
1159:
1156:
1154:
1151:
1149:
1146:
1144:
1141:
1139:
1136:
1135:
1133:
1131:
1126:
1120:
1119:Subderivative
1117:
1115:
1112:
1110:
1107:
1105:
1102:
1100:
1096:
1093:
1091:
1088:
1086:
1083:
1081:
1078:
1076:
1073:
1071:
1067:
1065:
1062:
1060:
1057:
1056:
1054:
1050:
1044:
1041:
1039:
1036:
1034:
1031:
1029:
1026:
1024:
1021:
1019:
1016:
1014:
1011:
1009:
1006:
1004:
1001:
1000:
998:
996:
995:Topics (list)
992:
986:
983:
981:
978:
976:
973:
972:
970:
966:
962:
958:
951:
946:
944:
939:
937:
932:
931:
928:
912:
908:
904:
903:
891:
885:
881:
874:
866:
860:
853:
852:
844:
840:
826:
823:
817:
814:
811:
808:
805:
802:
800:
799:Glove problem
797:
794:
791:
785:
782:
780:
777:
774:
771:
770:
764:
762:
757:
728:
720:
715:
710:
697:
693:
686:
680:
677:
673:
670:
666:
659:
656:
652:
649:
643:
639:
635:
632:
626:
623:
620:
614:
602:
589:
583:
575:
572:
569:
561:
555:
551:
547:
530:
525:
521:
515:
511:
506:
504:of instances;
503:
496:
495:
494:
490:
486:
482:
478:
468:
462:
452:
450:
446:
442:
436:
432:
421:
414:
410:
407:
401:
397:
390:
388:
387:
379:
375:
368:
357:
356:
350:
346:
342:
338:
337:
336:
318:
315:
312:
309:
306:
303:
300:
296:
293:
290:
284:
276:
272:
261:
258:
255:
252:
249:
246:
243:
239:
236:
233:
227:
219:
215:
170:
164:
156:
153:
138:
134:
133:
132:standard form
119:
115:
111:
110:
105:
102:
101:countable set
98:
94:
90:
86:
82:
81:
76:
75:
74:
72:
68:
64:
59:
57:
53:
49:
45:
41:
37:
33:
29:
22:
1340:Weak duality
1303:
1295:
1215:Orthogonally
915:. Retrieved
910:
879:
873:
850:
843:
758:
718:
711:
600:
594:
558:denotes the
553:
549:
545:
523:
519:
513:
509:
488:
484:
480:
476:
465:Formally, a
464:
444:
440:
434:
430:
427:
419:
412:
405:
399:
392:
383:
377:
370:
353:
340:
130:
128:
107:
78:
60:
51:
43:
25:
1330:Duality gap
1325:Dual system
1209:Convex hull
917:13 February
810:Satisficing
404:are called
386:constraints
384:inequality
382:are called
93:permutation
87:such as an
32:engineering
28:mathematics
1253:Radial set
1223:Convex set
985:Convex set
835:References
137:continuous
67:continuous
1238:Hypograph
678:∈
313:…
256:…
234:≤
63:variables
40:economics
1371:Category
1262:Zonotope
1233:Epigraph
767:See also
674:′
660:′
568:positive
493:, where
469:problem
449:negating
343: :
154:minimize
71:discrete
1317:Duality
1219:Pseudo-
1193:Ursescu
1090:Pseudo-
1064:Concave
1043:Simplex
1023:Duality
560:measure
352:is the
89:integer
48:problem
46:is the
1300:, and
1271:Series
1188:Simons
1095:Quasi-
1085:Proper
1070:Closed
886:
861:
335:where
85:object
1128:Main
855:(pdf)
727:graph
607:with
500:is a
408:, and
402:) = 0
380:) †0
135:of a
97:graph
42:, an
1248:Lens
1202:Sets
1052:Maps
959:and
919:2017
884:ISBN
859:ISBN
736:and
571:real
443:. A
417:and
129:The
65:are
52:best
38:and
1302:(Hw
911:IPC
752:to
744:to
599:an
588:max
585:or
582:min
562:of
539:of
502:set
437:= 0
428:If
422:â„ 0
415:â„ 0
95:or
73::
69:or
26:In
1373::
1294:(H
1292:,
1288:,
1284:,
1221:)
1217:,
1097:)
1075:K-
909:.
552:,
543:,
517:,
512:â
487:,
483:,
479:,
433:=
347:â
91:,
58:.
34:,
30:,
1308:)
1306:)
1304:x
1298:)
1296:x
1280:(
1255:/
1213:(
1068:(
949:e
942:t
935:v
921:.
867:.
754:v
750:u
746:v
742:u
738:v
734:u
730:G
722:0
719:m
698:.
694:}
690:)
687:x
684:(
681:f
671:y
667::
664:)
657:y
653:,
650:x
647:(
644:m
640:{
636:g
633:=
630:)
627:y
624:,
621:x
618:(
615:m
605:y
597:x
591:.
577:g
573:.
564:y
556:)
554:y
550:x
548:(
546:m
541:x
537:y
533:x
526:)
524:x
522:(
520:f
514:I
510:x
498:I
491:)
489:g
485:m
481:f
477:I
475:(
471:A
435:p
431:m
424:.
420:p
413:m
400:x
398:(
395:j
393:h
378:x
376:(
373:i
371:g
366:,
364:x
360:n
349:â
345:â
341:f
319:p
316:,
310:,
307:1
304:=
301:j
297:,
294:0
291:=
288:)
285:x
282:(
277:j
273:h
262:m
259:,
253:,
250:1
247:=
244:i
240:,
237:0
231:)
228:x
225:(
220:i
216:g
208:o
205:t
201:t
198:c
195:e
192:j
189:b
186:u
183:s
174:)
171:x
168:(
165:f
157:x
103:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.