565:
Consider the problem of
Linearly Constrained Convex Quadratic Programming. Under reasonable assumptions (the problem is feasible, the system of constraints is regular at every point, and the quadratic objective is strongly convex), the active-set method terminates after finitely many steps, and
464:, as the solution is not necessarily on one of the edges of the bounding polygon, an estimation of the active set gives us a subset of inequalities to watch while searching the solution, which reduces the complexity of the search.
130:
50:
constraints. The active constraints are then expressed as equality constraints, thereby transforming an inequality-constrained problem into a simpler equality-constrained subproblem.
452:
The active set is particularly important in optimization theory, as it determines which constraints will influence the final result of optimization. For example, in solving the
369:
289:
206:
443:
400:
320:
240:
161:
626:
697:
541:
678:
636:
535:
566:
yields a global solution to the problem. Theoretically, the active-set method may perform a number of iterations exponential in
529:
59:
650:
35:
553:
547:
53:
An optimization problem is defined using an objective function to minimize or maximize, and a set of constraints
47:
43:
461:
325:
631:. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.
495:
245:
169:
405:
453:
604:
674:
632:
646:
378:
298:
218:
670:
642:
136:
571:
146:
28:
691:
457:
17:
472:
In general an active-set algorithm has the following structure:
504:
a subset of the constraints with negative
Lagrange multipliers
488:
the equality problem defined by the active set (approximately)
574:. However, its practical behaviour is typically much better.
628:
Linear complementarity, linear and nonlinear programming
408:
381:
328:
301:
248:
221:
172:
149:
62:
125:{\displaystyle g_{1}(x)\geq 0,\dots ,g_{k}(x)\geq 0}
437:
394:
363:
314:
283:
234:
200:
155:
143:to search for the optimal solution. Given a point
124:
27:"Active set" redirects here. For the band, see
590:
446:
8:
371:Equality constraints are always active. The
42:is an algorithm used to identify the active
665:Nocedal, Jorge; Wright, Stephen J. (2006).
460:that intersect at the solution point. In
426:
413:
407:
386:
380:
346:
333:
327:
306:
300:
266:
253:
247:
226:
220:
177:
171:
148:
101:
67:
61:
605:"Optimization III: Convex Optimization"
583:
542:Sequential linear-quadratic programming
445:that are active at the current point (
163:in the feasible region, a constraint
7:
698:Optimization algorithms and methods
554:Generalized reduced gradient method
669:(2nd ed.). Berlin, New York:
456:problem, the active set gives the
364:{\displaystyle g_{i}(x_{0})>0.}
25:
521:Methods that can be described as
536:Sequential quadratic programming
402:is made up of those constraints
603:Nemirovsky and Ben-Tal (2023).
476:Find a feasible starting point
432:
419:
352:
339:
284:{\displaystyle g_{i}(x_{0})=0}
272:
259:
201:{\displaystyle g_{i}(x)\geq 0}
189:
183:
113:
107:
79:
73:
1:
530:Successive linear programming
438:{\displaystyle g_{i}(x_{0})}
714:
510:for infeasible constraints
139:, that is, the set of all
26:
591:Nocedal & Wright 2006
447:Nocedal & Wright 2006
548:Reduced gradient method
667:Numerical Optimization
439:
396:
365:
316:
285:
236:
202:
157:
126:
625:Murty, K. G. (1988).
462:quadratic programming
440:
397:
395:{\displaystyle x_{0}}
366:
317:
315:{\displaystyle x_{0}}
286:
237:
235:{\displaystyle x_{0}}
203:
158:
127:
496:Lagrange multipliers
406:
379:
326:
299:
246:
219:
170:
147:
60:
593:, pp. 467–480
523:active-set methods
468:Active-set methods
454:linear programming
435:
392:
361:
312:
281:
232:
198:
153:
122:
680:978-0-387-30303-1
498:of the active set
482:"optimal enough"
156:{\displaystyle x}
40:active-set method
16:(Redirected from
705:
684:
661:
659:
658:
649:. Archived from
612:
611:
609:
600:
594:
588:
449:, p. 308).
444:
442:
441:
436:
431:
430:
418:
417:
401:
399:
398:
393:
391:
390:
370:
368:
367:
362:
351:
350:
338:
337:
321:
319:
318:
313:
311:
310:
290:
288:
287:
282:
271:
270:
258:
257:
241:
239:
238:
233:
231:
230:
207:
205:
204:
199:
182:
181:
162:
160:
159:
154:
135:that define the
131:
129:
128:
123:
106:
105:
72:
71:
34:In mathematical
21:
713:
712:
708:
707:
706:
704:
703:
702:
688:
687:
681:
671:Springer-Verlag
664:
656:
654:
639:
624:
621:
616:
615:
607:
602:
601:
597:
589:
585:
580:
563:
470:
422:
409:
404:
403:
382:
377:
376:
342:
329:
324:
323:
302:
297:
296:
262:
249:
244:
243:
222:
217:
216:
173:
168:
167:
145:
144:
137:feasible region
97:
63:
58:
57:
32:
23:
22:
15:
12:
11:
5:
711:
709:
701:
700:
690:
689:
686:
685:
679:
662:
637:
620:
617:
614:
613:
595:
582:
581:
579:
576:
572:simplex method
562:
559:
558:
557:
551:
545:
539:
533:
519:
518:
513:
512:
511:
505:
499:
489:
477:
469:
466:
434:
429:
425:
421:
416:
412:
389:
385:
360:
357:
354:
349:
345:
341:
336:
332:
309:
305:
280:
277:
274:
269:
265:
261:
256:
252:
229:
225:
209:
208:
197:
194:
191:
188:
185:
180:
176:
152:
133:
132:
121:
118:
115:
112:
109:
104:
100:
96:
93:
90:
87:
84:
81:
78:
75:
70:
66:
29:The Active Set
24:
14:
13:
10:
9:
6:
4:
3:
2:
710:
699:
696:
695:
693:
682:
676:
672:
668:
663:
653:on 2010-04-01
652:
648:
644:
640:
638:3-88538-403-5
634:
630:
629:
623:
622:
618:
606:
599:
596:
592:
587:
584:
577:
575:
573:
569:
560:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
527:
526:
524:
517:
514:
509:
506:
503:
500:
497:
493:
490:
487:
484:
483:
481:
478:
475:
474:
473:
467:
465:
463:
459:
455:
450:
448:
427:
423:
414:
410:
387:
383:
374:
358:
355:
347:
343:
334:
330:
307:
303:
294:
278:
275:
267:
263:
254:
250:
227:
223:
214:
195:
192:
186:
178:
174:
166:
165:
164:
150:
142:
138:
119:
116:
110:
102:
98:
94:
91:
88:
85:
82:
76:
68:
64:
56:
55:
54:
51:
49:
45:
41:
37:
30:
19:
666:
655:. Retrieved
651:the original
627:
619:Bibliography
598:
586:
567:
564:
522:
520:
515:
507:
501:
491:
485:
480:repeat until
479:
471:
451:
372:
292:
212:
210:
140:
134:
52:
46:in a set of
39:
36:optimization
33:
570:, like the
561:Performance
458:hyperplanes
44:constraints
657:2010-04-03
578:References
516:end repeat
373:active set
211:is called
48:inequality
18:Active set
525:include:
193:≥
117:≥
92:…
83:≥
692:Category
293:inactive
647:0949214
492:compute
677:
645:
635:
544:(SLQP)
508:search
502:remove
291:, and
213:active
38:, the
608:(PDF)
556:(GRG)
538:(SQP)
532:(SLP)
486:solve
675:ISBN
633:ISBN
550:(RG)
494:the
356:>
375:at
322:if
295:at
242:if
215:at
694::
673:.
643:MR
641:.
359:0.
683:.
660:.
610:.
568:m
433:)
428:0
424:x
420:(
415:i
411:g
388:0
384:x
353:)
348:0
344:x
340:(
335:i
331:g
308:0
304:x
279:0
276:=
273:)
268:0
264:x
260:(
255:i
251:g
228:0
224:x
196:0
190:)
187:x
184:(
179:i
175:g
151:x
141:x
120:0
114:)
111:x
108:(
103:k
99:g
95:,
89:,
86:0
80:)
77:x
74:(
69:1
65:g
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.