Skip to main content
7 votes
Accepted

Smooth approximation of $\max(f_1(x),f_2(x),\cdots,f_n(x))$

Indeed, there exists numerous smooth approximations for the max function. One of the most well known approximation is the Kreisselmeier-Steinhauser (KS) functional, that approximates the non-smooth ...
fpacaud's user avatar
  • 1,511
5 votes

What approximation is guarantees when solving an LP with floating-point numbers?

A quick disclaimer regarding I can solve it exactly in polynomial time using e.g. interior-point methods Interior-point algorithms do not solve a problem "exactly": they provide a solution ...
mtanneau's user avatar
  • 4,183
5 votes

Find an upper bound for an objective function

Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.
RobPratt's user avatar
  • 32.7k
3 votes

How to apply smooth approximation to non-linear complementarity constraints?

Read Bintong CHen and Patrick T. Harker, Smooth Approximations to Nonlinear Complementarity Problems, SIAM Journal on Optimization, 7(2), 403-320, 1997
Mark L. Stone's user avatar
3 votes

Normal approximation of Poisson distribution

Context Free Algebra. As pointed out by xd y in the comments, one way to derive this without context (i.e., understanding the Gaussian approximation to the Poisson) is just to apply the quadratic ...
SecretAgentMan's user avatar
2 votes

Find the shortest path connecting some (s,t) - a greedy (?) criterion to a multi-commodity flow problem

Only the outer algorithm is greedy, in the sense of removing the path links in each iteration and never looking back. Use any algorithm (like Dijkstra) to find a shortest path for each remaining $(s_j,...
RobPratt's user avatar
  • 32.7k
2 votes
Accepted

How to apply smooth approximation to non-linear complementarity constraints?

Need to check boundaries for $U$ where $U^{min} \le U\le U^{max}$ and then the first and last if conditions. Still define binary variables $\delta_x, \delta_y$ and so on for each of the expressions. ...
Sutanu Majumdar's user avatar
2 votes

Convex approximation of an expression with fraction for CVX

I assume the given problem is $$ \max \frac{\|ax-b\|^2}{\|cx+b\|^2}, x \in \mathbb{C}^N $$ I may try the following relaxation. The given problem is equivalent to $$ \begin{align} &\max &\|ax-...
xd y's user avatar
  • 1,196
2 votes

Convex approximation of an expression

No approximation is needed if you wish to minimize the expression. For maximization, see the material after "Edit". Due to cyclic permutation invariance of trace, $$\text{trace}(X) = \text{...
Mark L. Stone's user avatar
2 votes

Deriving a lower bound for a two-stage stochastic problem

The following is a valid lower bound for the stochastic programming problem. \begin{align} \mathbb{E}_{\mathbb{\xi} \in \varOmega} \min \limits_{x\in X} \left( c^\top x + \mathcal{Q}(x, \xi) \right) \...
Penghui Guo's user avatar
1 vote

Approximating a convex program

Basically $S(K, \epsilon) = K + \epsilon B$. Thus optimizing a function on $S(K, \epsilon)$ is not easier than optimization over $K$. Those approximate optimality definitions are used to measure the ...
Red shoes's user avatar
  • 153
1 vote

Formulation of a stepwise linear approximation

One approximation possible is to use the tangents of $f(x)$. Assuming you are minimizing $f(x)$, introduce a new variable $z$ to approximate $f(x)$ over a given set $A$ and use constraints: \begin{...
Kuifje's user avatar
  • 13.5k
1 vote
Accepted

Deriving a lower bound for a two-stage stochastic problem

It's a while since I asked this question. I have now came across the answer which is as follows: Yes, if the stochastic problem is solved through the horizon based on the realized scenario, it ...
Mostafa's user avatar
  • 2,104

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