4
$\begingroup$

This might be a very basic question for this community. I am reading an article and I think I have some confusion about formulating a problem. My understanding is that all decision variables should be present in the objective function. For any continuous function, the first derivative of the function is zero at the minima or maxima and the value of the variable for which we get the derivative equal to zero is the solution of the problem. However, the article I am reading formulated the problem as follows where some decision variables are present only in the constraints:

enter image description here

The decision variables are $x_a$ ,$v_\pi$, and $y_s$. However, only $x_a$ is present in the objective function. Is it because the coefficients of the absent decision variables might be $0$ in the objective function? If we modify the problem and add the constraints to the objective function like the Lagrange method we will be able to include all variables.

I would really appreciate any comments and answers.

$\endgroup$
4
  • $\begingroup$ Would you like a more complicated example or is the one i presented sufficient? $\endgroup$ Oct 20 at 18:39
  • 2
    $\begingroup$ "For any continuous function, the first derivative of the function is zero at the minima or maxima and the value of the variable for which we get the derivative equal to zero is the solution of the problem." That is true for unconstrained problems, but definitely not true for constrained problems. $\endgroup$
    – prubin
    Oct 20 at 21:08
  • $\begingroup$ @prubin, That's right. II mixed up optimality conditions of constrained and unconstrained problems. $\endgroup$
    – mars
    Oct 20 at 23:24
  • $\begingroup$ @worldsmithhelper No, thanks so much for clearing up my confusion with the example you provided. $\endgroup$
    – mars
    Oct 20 at 23:26
8
$\begingroup$

This answer complements that by @worldsmithhelper .

Not only does an objective function not have to include all the decision variables, it need not include any of them. An "optimization" problem having a constant (zero) objective function, which is equivalent to not having an objective function, is called a feasibility problem.

Your understanding of the optimality conditions is incorrect when there are constraints. When there are constraints (and suitable differentiability and constraint qualification), the first order optimality conditions are the Karush–Kuhn–Tucker (KKT) conditions, which tie together the gradients of the objective and constraints. In unconstrained problems, the KKT conditions reduce to the condition with which you are familiar; namely, that the gradient of the objective function equals zero.

Edit:Any optimization problem can be transformed, via an epigraph formulation, to an equivalent problem containing only one decision variable in the objective function. This is accomplished by introducing a new decision variable, $t$, making $t$ the objective function, keeping all the original constraints and decision variables, while (in the case of minimization), adding an additional constraint, $\text{original_objective_function} \le t$. By virtue of the minimization, at an optimal solution, $t = \text{original_objective_function}$, hence making the transformation correct. Everything is the same for maximization, except the added constraint is $\text{original_objective_function} \ge t$

$\endgroup$
2
  • 1
    $\begingroup$ Good idea to bring up feasibility problems and being more rigorous what constraints put in the objective can actually tell us. $\endgroup$ Oct 20 at 18:39
  • $\begingroup$ Thanks Mark, your comments clears up some confusion I had. $\endgroup$
    – mars
    Oct 20 at 23:33
5
$\begingroup$

NO

Not all decision variables need to be present in the objective. They can be often used to handle constraints or express other things. Consider this simple problem: $$\min_{x,y_1,y_2,y_3,y_4,y_5 \in \mathbb{N}} x \text{ subject to }$$ $$\forall i \in \{1,2,3,4,5\}: \ 0 \leq y_i \leq x$$ $$y_1+y_2+y_3+y_4+y_5 = 12$$

Which might answer the question how much people should come in every week day, when we need to reserve a parking spot for them but only can book parking spots for the complete week.

In this case how many people come in each day is a decision, but they don't appear in the objective because we only care about how many we need at most on a single day as we would need to book that many parking spots for the week.

Note that if a variable appears in the constraints and in the objective they have the same value.

If we modify the problem and add the constraints to the objective function like the Lagrange method we will be able to include all variables.

You are correct that this is an approach to solve problems, however it enforcing integrality (some decision variable being an integer) is a constraint that is hard to enforce. In general for many constraints it is advisable to handle them separately and not put them in the objective to better exploit structure. Putting constraints in the objective can turn problems non-linear or non convex, so a global non-linear optimizer would be needed to give guarantees about the quality of the solution which is often more computationally expensive than handling the constraints separately.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you so much! Your comment equally helped me like the comments by Mark L. Stone but I just learned I can only select one comment as an answer :( $\endgroup$
    – mars
    Oct 20 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.