12

While iteratively approximately solving the first order Karush-Kuhn-Tucker conditions, many (nonconvex) nonlinear solvers "roll downhill", i.e., enforce descent (for minimization) of the objective function for algorithms which attain and maintain primal feasibility, or improvement in a merit function (or similarly with filter methods) for algorithms which ...


7

MIP solvers such as CPLEX & Gurobi indicate a gap (in %) between the current best solution and the current best dual bound (which is a lower bound for a minimization problem). In general, the optimum value is not known until, well, the problem is solved. Different solvers may use slightly different definitions: CPLEX: $$ g = \frac{|Z_{dual} - Z_{primal}|...


7

As you are probably aware of, the standard optimality condition for column generation is not valid if not all constraints are included in the master problem, as the dual information of the missing constraints needs to be taken into account in the computation of the reduced costs. Muter et al. (2013) consider this issue and show that if the formulation ...


6

It is possible to apply the notions of stationary points and the second derivative of a function to functionals. For $|\varepsilon|\ll1$ and and a differentiable function $h$, we can write, using Taylor series,$$F(x,y+\varepsilon h,y'+\varepsilon h')=F(x,y,y')+\varepsilon\mathcal{I}(\Delta[y,h])+\frac{\varepsilon^2}2\mathcal I(\Delta_2[y,h])+\mathcal O(\...


6

Coming from the world of optimal control, I tend to view the calculus of variations from a Pontryagin point of view. The conditions stated by Pontryagin are necessary, and sufficient under certain hypotheses (mainly related to the convexity of the function $F$). I used to refer to this article during my PhD: O. L. Mangasarian, Sufficient Conditions for the ...


5

No, an optimal solution need not exist. Take $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = e^{x}$. However if you restrict $S$ to be compact instead of just closed, then you are guaranteed a solution. In fact, convexity is not required. For a simple proof, let $f(x_n) \to \inf_{x \in S} f(x)$. $x_n \in S$ has a convergent subsequence by compactness, and let $...


4

Gaps are typically tied to specific models and solution methods. The gap reflects the difference between the best known bound and the objective value of the best solution produced by a particular algorithm. How that is computed depends in part on whether you are minimizing and maximizing, in part on whether you want the gap as a fraction of the best solution ...


4

If I understand your question correctly, I think you can find your answer by considering the following two primal problems. The first is \begin{alignat*}{2} & \max & x_{1}\\ & \textrm{s.t.} & x_{1}+x_{2} & \le1\\ & & x_{1} & \le1\\ & & x & \ge0 \end{alignat*} and the second is \begin{alignat*}{2} & \max &...


3

In addition to the references already given in the comments, this paper (DOI link) demonstrates that exact solutions to some non-convex quadratic programs are given by semi-definite programming, and whenever the SDP relaxation is tight we can actually solve the SDP via SOCP! In general the SDP relaxation will of course not be tight, but as shown by ...


3

I guess you are assuming that the dual problem was obtained by only dualizing some of the constraints. The answer below makes sense if I am right about my guess. In general, I believe the answer to your problem is no. Take for instance the multi-commodity flow problem. If you dualize the capacity constraints, then the dual problem you will be solving ...


2

For a continuous function, all you need to do is prove that it's (i) non-convex, and (ii) monotonic. (i) can be shown using the eigenvalues of the hessian matrix, and (ii) using the gradient. However, in your case your domain is $\mathbb{Z}$, therefore derivatives are generally not defined, and neither is the concept of (pseudo)convexity. You can show ...


2

From duality theory: At each feasible $x$,$f(x)=\sup_{u>0,v}L(x,u,v)$, and the supremum is taken iff $u\geq 0$ satisfying $u_ih(x)=0,i=1,...,m$. The optimal value of the primal problem, named as $f^*$ satisfies: \begin{equation} f^*=\inf_x\sup_{u>0,v}L(x,u,v) \end{equation} This means that if the dual is feasible, the primal has to be feasible as well. ...


2

With the exception of special cases, this problem is NP-hard. One interesting case is that minimizing a convex or concave function over a simplex can be solved in polynomial time. In other special cases it is also possible to linearise the problem through reformulations. In the general case however this would be solved by relaxing the objective and using ...


Only top voted, non community-wiki answers of a minimum length are eligible