0
$\begingroup$

Suppose I have a convex program which has only two variables, the objective function is strictly convex, and the constraints are linear functions.

I think removing all non-tight constraints doesn't change the optimal solution.

However, when there are more than 2 tight constraints, I am not sure if removing all other tight constraints but only leaving two of them still keep the optimal solution unchanged.

Any advice would be appreciated!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

In convex optimization, a local optimum is a global one. So if you do not change the neighbourhood of the optimal solution, you do not change the optimal solution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer, J! Would you please tell me more details? Do you mean that removing n-2 tight constraints and leaving only 2 tight constraints there doesn't change the neighbourhood of the optimal solution? I can not see this clearly... $\endgroup$
    – Ann
    Commented Jan 4, 2015 at 11:40
  • $\begingroup$ You can safely remove a constraint if it does not enlarge the convex set in a small neighbourhood of the optimal solution. In your case, the neighbourhood of the optimal solution (or an appropriately chosen one) is a point in which two half-lines meet which locally determine the convex set. If you keep these half-lines you can safely remove all other constraints. $\endgroup$
    – J Fabian Meier
    Commented Jan 4, 2015 at 14:41
2
$\begingroup$

No, you can't. Even in linear optimization with only two variables you may have several linear constraints that form a corner of your feasible domain. Removing some constraints may make the corner less sharp and lead to an unbounded objective. Imagine that removing some constraint adds new feasible directions at the corner (it's simple to draw a picture...).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hello Dirk, in my case the convex program only has two variables. Maybe you didn't notice my description? $\endgroup$
    – Ann
    Commented Jan 4, 2015 at 16:38
  • $\begingroup$ Jupp, this is also true in two variables. $\endgroup$
    – Dirk
    Commented Jan 4, 2015 at 21:04
  • $\begingroup$ Hello Dirk, I was thinking of the following argument. Please let me know where it goes wrong. The problem is to minimize a convex function f(x_1,x_2) over a set of linear constraints. Call this convex program (i). I think it is true that removing the non-tight constraints doesn't matter. Then I remove all other tight constraints but two of them (like eliminate redundant equations). Call this program (ii). I think the optimal solution (x^*_1, x^*_2) of (ii) is a feasible solution of (i). So (x^*_1, x^*_2) should also be the optimal solution of (i), because objective functions are the same. $\endgroup$
    – Ann
    Commented Jan 4, 2015 at 21:33

Not the answer you're looking for? Browse other questions tagged .