850:
133:
508:
36:
145:
685:
of the function being optimized is equated to zero, and any values of the choice variable(s) that satisfy this equation are viewed as candidate solutions (while those that do not are ruled out as candidates). There are several ways in which a candidate solution might not be an actual solution. First,
470:
feasible set is one in which a line segment connecting any two feasible points goes through only other feasible points, and not through any points outside the feasible set. Convex feasible sets arise in many types of problems, including linear programming problems, and they are of particular
649:. Algorithms for solving various types of optimization problems often narrow the set of candidate solutions down to a subset of the feasible solutions, whose points remain as candidate solutions while the other feasible solutions are henceforth excluded as candidates.
884:
is selected as the initial candidate solution and is tested for optimality; if it is rejected as the optimum, an adjacent vertex is considered as the next candidate solution. This process is continued until a candidate solution is found to be the optimum.
652:
The space of all candidate solutions, before any feasible points have been excluded, is called the feasible region, feasible set, search space, or solution space. This is the set of all possible solutions that satisfy the problem's constraints.
640:
of possible solutions in the feasible region of a given problem. A candidate solution does not have to be a likely or reasonable solution to the problem—it is simply in the set that satisfies all
561:
If the feasible set is unbounded, there may or may not be an optimum, depending on the specifics of the objective function. For example, if the feasible region is defined by the constraint set {
136:
A problem with five linear constraints (in blue, including the non-negativity constraints). In the absence of integer constraints the feasible set is the entire region bounded by blue, but with
811:
527:≥ 0} is unbounded because in some directions there is no limit on how far one can go and still be in the feasible region. In contrast, the feasible set formed by the constraint set {
352:
319:
415:
244:
745:
840:
857:
constraints on two variables produce a region of possible values for those variables. Solvable two-variable problems will have a feasible region in the shape of a
491:
If the constraints of an optimization problem are mutually contradictory, there are no points that satisfy all the constraints and thus the feasible region is the
287:
264:
694:, at which a temporary pause in the local rise or fall of the function occurs. Such candidate solutions may be able to be ruled out by use of the
686:
it might give a minimum when a maximum is being sought (or vice versa), and second, it might give neither a minimum nor a maximum but rather a
698:, the satisfaction of which is sufficient for the candidate solution to be at least locally optimal. Third, a candidate solution may be a
511:
A bounded feasible set (top) and an unbounded feasible set (bottom). The set at the bottom continues forever towards the right.
100:
943:
864:
if it is bounded. In an algorithm that tests feasible points sequentially, each tested point is in turn a candidate solution.
72:
551:
435:
1012:
79:
913:
748:
119:
53:
419:
In many problems, the feasible set reflects a constraint that one or more variables must be non-negative. In pure
754:
86:
475:
that is to be maximized, it will generally be easier to solve in the presence of a convex feasible set and any
57:
68:
17:
1007:
324:
613:
161:
292:
642:
188:
184:
377:
654:
449:
209:
46:
669:, the candidate solutions are the individuals in the population being evolved by the algorithm.
960:
695:
543:≤ 4} is bounded because the extent of movement in any direction is limited by the constraints.
192:
903:
678:
633:
93:
720:
816:
180:
8:
461:
420:
269:
983:
873:
854:
424:
371:
249:
200:
149:
137:
939:
909:
877:
849:
666:
637:
443:
987:
975:
691:
682:
625:
621:
370:
is at least 5 and at most 12. The feasible set of the problem is separate from the
165:
554:
for the feasible set to be bounded is that the number of constraints be at least
472:
179:
is the set of all possible points (sets of values of the choice variables) of an
132:
423:
problems, the feasible set is the set of integers (or some subset thereof). In
869:
861:
710:
703:
577:
has no optimum since any candidate solution can be improved upon by increasing
480:
374:, which states the criterion to be optimized and which in the above example is
933:
1001:
699:
476:
687:
617:
516:
439:
979:
858:
467:
428:
153:
27:
Mathematical constraints that define ways of finding the best solution
492:
203:
to the problem, before the set of candidates has been narrowed down.
507:
35:
881:
714:
431:
196:
519:. For example, the feasible set defined by the constraint set {
495:. In this case the problem has no solution and is said to be
206:
For example, consider the problem of minimizing the function
452:
is the process of finding a point in the feasible region.
144:
905:
Optimisation and
Stability Theory for Economic Analysis
813:
This candidate solution is in fact correct except when
657:
is the process of finding a point in the feasible set.
759:
502:
819:
757:
723:
677:
In calculus, an optimal solution is sought using the
380:
327:
295:
272:
252:
212:
908:. New York: Cambridge University Press. p. 32.
60:. Unsourced material may be challenged and removed.
932:Boyd, Stephen; Vandenberghe, Lieven (2004-03-08).
834:
805:
739:
409:
346:
313:
281:
258:
238:
999:
931:
366:is at least 1 and at most 10 and the value of
596:, then there is an optimum (specifically at (
901:
806:{\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.}
558:+ 1 (as illustrated by the above example).
354:Here the feasible set is the set of pairs (
343:
152:problem with three variables is a convex
120:Learn how and when to remove this message
848:
506:
199:constraints. This is the initial set of
143:
131:
958:
471:interest because, if the problem has a
14:
1000:
455:
844:
607:
569:≥ 0}, then the problem of maximizing
927:
925:
660:
552:necessary but insufficient condition
546:In linear programming problems with
58:adding citations to reliable sources
29:
503:Bounded and unbounded feasible sets
24:
902:Beavis, Brian; Dobbs, Ian (1990).
486:
25:
1024:
922:
347:{\displaystyle 5\leq y\leq 12.\,}
427:problems, the feasible set is a
34:
645:; that is, it is in the set of
438:whose boundaries are formed by
45:needs additional citations for
961:"A genetic algorithm tutorial"
952:
938:. Cambridge University Press.
895:
749:Cavalieri's quadrature formula
314:{\displaystyle 1\leq x\leq 10}
246:with respect to the variables
148:A closed feasible region of a
13:
1:
888:
747:the candidate solution using
410:{\displaystyle x^{2}+y^{4}.}
7:
672:
585:; yet if the problem is to
239:{\displaystyle x^{2}+y^{4}}
183:that satisfy the problem's
10:
1029:
459:
140:it is the set of red dots.
1013:Mathematical optimization
959:Whitley, Darrell (1994).
473:convex objective function
162:mathematical optimization
968:Statistics and Computing
362:) in which the value of
187:, potentially including
655:Constraint satisfaction
450:Constraint satisfaction
865:
836:
807:
741:
740:{\displaystyle x^{n},}
696:second derivative test
616:and other branches of
512:
442:and whose corners are
436:multidimensional space
411:
348:
315:
283:
260:
240:
157:
141:
852:
837:
835:{\displaystyle n=-1.}
808:
742:
679:first derivative test
515:Feasible sets may be
510:
412:
349:
316:
284:
261:
241:
147:
135:
817:
755:
721:
517:bounded or unbounded
378:
325:
293:
270:
250:
210:
181:optimization problem
54:improve this article
935:Convex Optimization
665:In the case of the
462:Convex optimization
456:Convex feasible set
421:integer programming
201:candidate solutions
138:integer constraints
980:10.1007/BF00175354
874:linear programming
866:
855:linear programming
845:Linear programming
832:
803:
776:
737:
647:feasible solutions
630:candidate solution
608:Candidate solution
513:
425:linear programming
407:
372:objective function
344:
311:
282:{\displaystyle y,}
279:
256:
236:
158:
150:linear programming
142:
1008:Optimal decisions
945:978-0-521-83378-3
775:
667:genetic algorithm
661:Genetic algorithm
622:search algorithms
259:{\displaystyle x}
130:
129:
122:
104:
69:"Feasible region"
16:(Redirected from
1020:
992:
991:
965:
956:
950:
949:
929:
920:
919:
899:
880:of the feasible
841:
839:
838:
833:
812:
810:
809:
804:
793:
792:
777:
774:
760:
746:
744:
743:
738:
733:
732:
692:inflection point
683:first derivative
626:computer science
416:
414:
413:
408:
403:
402:
390:
389:
353:
351:
350:
345:
320:
318:
317:
312:
288:
286:
285:
280:
265:
263:
262:
257:
245:
243:
242:
237:
235:
234:
222:
221:
170:feasible region,
166:computer science
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
1028:
1027:
1023:
1022:
1021:
1019:
1018:
1017:
998:
997:
996:
995:
963:
957:
953:
946:
930:
923:
916:
900:
896:
891:
847:
818:
815:
814:
782:
778:
764:
758:
756:
753:
752:
728:
724:
722:
719:
718:
711:antiderivatives
675:
663:
610:
505:
489:
487:No feasible set
479:will also be a
464:
458:
398:
394:
385:
381:
379:
376:
375:
326:
323:
322:
294:
291:
290:
271:
268:
267:
251:
248:
247:
230:
226:
217:
213:
211:
208:
207:
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
1026:
1016:
1015:
1010:
994:
993:
951:
944:
921:
914:
893:
892:
890:
887:
870:simplex method
862:simple polygon
846:
843:
831:
828:
825:
822:
802:
799:
796:
791:
788:
785:
781:
773:
770:
767:
763:
736:
731:
727:
704:global optimum
674:
671:
662:
659:
609:
606:
504:
501:
488:
485:
481:global optimum
457:
454:
434:: a region in
406:
401:
397:
393:
388:
384:
342:
339:
336:
333:
330:
310:
307:
304:
301:
298:
278:
275:
255:
233:
229:
225:
220:
216:
177:solution space
128:
127:
42:
40:
33:
26:
9:
6:
4:
3:
2:
1025:
1014:
1011:
1009:
1006:
1005:
1003:
989:
985:
981:
977:
973:
969:
962:
955:
947:
941:
937:
936:
928:
926:
917:
915:0-521-33605-8
911:
907:
906:
898:
894:
886:
883:
879:
875:
871:
863:
860:
856:
851:
842:
829:
826:
823:
820:
800:
797:
794:
789:
786:
783:
779:
771:
768:
765:
761:
750:
734:
729:
725:
716:
712:
707:
705:
701:
700:local optimum
697:
693:
689:
684:
680:
670:
668:
658:
656:
650:
648:
644:
639:
635:
631:
627:
624:(a topic in
623:
619:
615:
605:
604:) = (0, 0)).
603:
599:
595:
591:
588:
584:
580:
576:
572:
568:
564:
559:
557:
553:
550:variables, a
549:
544:
542:
538:
534:
530:
526:
522:
518:
509:
500:
498:
494:
484:
482:
478:
477:local optimum
474:
469:
463:
453:
451:
447:
445:
441:
437:
433:
430:
426:
422:
417:
404:
399:
395:
391:
386:
382:
373:
369:
365:
361:
357:
340:
337:
334:
331:
328:
308:
305:
302:
299:
296:
276:
273:
253:
231:
227:
223:
218:
214:
204:
202:
198:
194:
190:
186:
182:
178:
174:
173:feasible set,
171:
167:
163:
155:
151:
146:
139:
134:
124:
121:
113:
110:November 2018
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: –
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
974:(2): 65–85.
971:
967:
954:
934:
904:
897:
876:problems, a
872:for solving
867:
853:A series of
717:of the form
708:
688:saddle point
676:
664:
651:
646:
629:
614:optimization
611:
601:
597:
593:
589:
586:
582:
578:
574:
570:
566:
562:
560:
555:
547:
545:
540:
536:
532:
528:
524:
520:
514:
496:
490:
465:
448:
418:
367:
363:
359:
355:
205:
189:inequalities
176:
172:
169:
159:
116:
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
18:Feasible set
643:constraints
618:mathematics
440:hyperplanes
289:subject to
185:constraints
1002:Categories
889:References
709:In taking
702:but not a
497:infeasible
460:See also:
193:equalities
154:polyhedron
80:newspapers
827:−
751:would be
715:monomials
620:, and in
493:empty set
338:≤
332:≤
306:≤
300:≤
882:polytope
673:Calculus
587:minimize
444:vertices
432:polytope
988:3447126
868:In the
636:of the
197:integer
94:scholar
986:
942:
912:
878:vertex
859:convex
690:or an
681:: the
634:member
468:convex
429:convex
195:, and
96:
89:
82:
75:
67:
984:S2CID
964:(PDF)
632:is a
628:), a
565:≥ 0,
535:≥ 0,
531:≥ 0,
523:≥ 0,
101:JSTOR
87:books
940:ISBN
910:ISBN
321:and
266:and
168:, a
164:and
73:news
976:doi
713:of
638:set
612:In
581:or
539:+ 2
341:12.
175:or
160:In
56:by
1004::
982:.
970:.
966:.
924:^
830:1.
706:.
600:,
592:+
573:+
499:.
483:.
466:A
446:.
358:,
309:10
191:,
990:.
978::
972:4
948:.
918:.
824:=
821:n
801:.
798:C
795:+
790:1
787:+
784:n
780:x
772:1
769:+
766:n
762:1
735:,
730:n
726:x
602:y
598:x
594:y
590:x
583:y
579:x
575:y
571:x
567:y
563:x
556:n
548:n
541:y
537:x
533:y
529:x
525:y
521:x
405:.
400:4
396:y
392:+
387:2
383:x
368:y
364:x
360:y
356:x
335:y
329:5
303:x
297:1
277:,
274:y
254:x
232:4
228:y
224:+
219:2
215:x
156:.
123:)
117:(
112:)
108:(
98:·
91:·
84:·
77:·
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
