# Tagged Questions

Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

95 views

### Is $f(t)=t^\alpha$ for $\alpha\in(0,1)$ a sub-additive function? [duplicate]

Possible Duplicate: Does $|x|^p$ with $0&lt;p&lt;1$ satisfy the triangular inequality on $\mathbb{R}$? Is the function $$f(t)= t^{\alpha},\quad \alpha\in (0,1)$$ a subadditive ...
3k views

### Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
242 views

608 views

### Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
345 views

### Least Square Method with Positive Parameters

this is my first post here in the Stack Exchange. A friend told me about this forum and I'm giving it a try. I searched a bit past threads, but couldn't find what I wanted, so I'm posting the problem ...
169 views

### Minimizing the cost of a path in a dynamic system

So suppose I want a path from 0 to $c>0$ on the real line, and I am going to use the function $S(t)$ to get there in (discrete) time $T$. That is, my position at time 0 is 0, my position at time $T$ ...
83 views

### Maximum of an expression with four variables

Assume $0 < p_1 \le p_2\le p_3 \le p_4$. What is the maximum of the following expression? $$\frac{\left(p_1+p_4\right)\left(p_2+p_3\right)}{\left(p_1+p_3\right)\left(p_2+p_4\right)}$$ Is that ...
1k views

### Shortest distance between two shapes

This is the scenario of my problem. I have an image of two objects ( of arbitrary shape, not convex, not touching or crossing each other, kept a few space apart). And I am supposed to find the ...
536 views

### How to maximize area of two circles inside a rectangle without overlapping?

Two circles have to be drawn inside a rectangle of dimensions $W\times H$ such that the area of both circles is to be as large as possible without overlapping. Let the radii of the circles be $r_1$ ...
1k views

### How to find the minimum value of the expression?

Let $x$, $y$, $z$ be three nonegative real numbers and $x^2 + y^2 + z^2 = 5.$ Find the minimum of the expression $$E=\dfrac{1}{2}(x^2 y^2 + y^2 z^2 + z^2 x^2) + \dfrac{96}{x + y + z + 1}.$$ What ...
82 views

### How to maximize $\left({a+b \choose a} 2^{-a-b}\right)$?

How can you maximize $\left({a+b \choose a} 2^{-a-b}\right)$ assuming, $a,b \geq 0$ and $0< (a+b) \leq n$, where all the variables are non-negative integers? Is the maximum when $a=b=n/2$, ...
207 views

I am trying to solve the following binary quadratic program. $$\min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma ... 3answers 904 views ### Compute the minimum distance between the centre to the curve xy=4. I wish to solve the following problem: Compute the minimum distance between the center to the curve xy=4. But I don't know where to start from? 4answers 164 views ### Optimization with a constrained function Okay so I understand how to find points of extrema when for example, We have 3x^2 + 2y^2 + 6z^2 subject to the constaint x+y+z=1. I followed the method of the Lagrange multiplier and resulted in ... 2answers 188 views ### How many points to find a polynomial? I would like to fit a formula ax^b + cx^d+ e to a set of points. I have two questions. If my data were perfect, how many points do I need in the worst case to get a,b,c,d,e exactly? If my data ... 6answers 417 views ### Optimizing a+b+c subject to a^2 + b^2 + c^2 = 27 If a,b,c \gt 0 and a^2+b^2+c^2=27, find the maximum and minimum values of a+b+c. How to solve this one? (Here's the source of inspiration for the problem.) 1answer 310 views ### What is the complexity of computing the minimum distance between two convex polyhedra that both have n faces? EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity O(n) (which is what my question is about) ... 0answers 165 views ### Lagrange multiplier expression I would like to solve the following optimization problem using the gradient ascend method: \begin{array}{ll} \text{maximize}_{\theta} & \theta^TQ_1\theta + b_1\\ \text{subject to} & \theta^... 3answers 125 views ### Finding the range of a y=-x^2(x+5)(x-3) without calculus? I was helping a precalculus student with this question. The graph wasn't given. My only idea was to find the inverse and try to find its domain. When trying to find the inverse, I arrived at 0=y^4+2y^... 1answer 140 views ### Formulating an LP problem with vectors We have m vectors v_1,v_2,\dots,v_m\in\mathbb{R}^n and m numbers t_1,t_2,\dots,t_m\in\mathbb{R} and we want to find a vector y\in\mathbb{R}^n such that$$|v_i^Ty-t_i|\leq D$$for i=1,\... 0answers 29 views ### Optimization by Symmetry? Let$$f(x,y,a,b) := \frac{xa+yb}{\sqrt{xa^2+yb^2}},$$where x,y,a,b are all positive. Define$$g(a,b) = \min_{x+y=1,\,x,y\ge 0}f(x,y,a,b).$$How would one solve for g(a,b)? I have solved this by ... 1answer 263 views ### Dual residual for linearized ADMM I am using linearized ADMM for a problem with a (non-smooth) convex loss function f(x), and a hard constraint x \in E, where E is an ellipsoid in R^d. I have encoded the hard constraint as A ... 2answers 39 views ### Question about the constraint in Laplacian eigenmaps When calculating Laplacian Eigenmaps, the original paper mentions about the constraint$$y^TDy=1as "removes an arbitrary scaling factor in the embedding". My understanding is that it prevents y ... 1answer 112 views ### What's wrong in this dual derivation? I have a function in the form \begin{align} f(q,M)=\sup_{0\leq \alpha \leq 1} -\alpha^T (R\odot M)\alpha+\alpha^Tq \end{align} which is a dual of a minimization problem, where R and M are ... 1answer 48 views ### Algebraic Riccati equation (DARE) stabilazability condition I'm Trying to help in this question which involves Algebraic Ricatti equation. Honestly to say I never met this equation before. I'm struggling to understand the conditions stated in the limitations ... 2answers 730 views ### How to maximize an entropy function? I'm very novice in optimization and have a convex optimization function of form \sum_{i,k} p_{k,i}*\log{p_{k,i}}  to minimize with the following constraints: \forall i, a_i = \sum_{k=1}^{m} b_k. ... 1answer 268 views ### Proof of Non-Convexity Am looking for a proof of non-convexity of the quotient of two matrix trace functions as given by \frac{\operatorname{Tr}X^TAX}{\operatorname{Tr}X^TBX}, when TrX^TBX>0 for two different ... 1answer 316 views ### Voronoi diagram with different metric functions Given a metric space (X,d) and finite number of points (x_i)_{i=1}^n the Voronoi diagram (or the Dirichlet cell) C_i is given by C_i = \{x\in X:d(x,x_i)<\min\limits_{j\neq i}d(x,x_j)\}. $... 1answer 258 views ### Extrema of$f:\mathbb{R}^n\rightarrow \mathbb{R}$My question is about finding the extrema of a multidimensional function,$f:\mathbb{R}^n\rightarrow \mathbb{R}$. From lecture I know that$H_f(x_0) < 0 $implies a isolated maximum$H_f(x_0) &...
Background This is a follow-up to this question. The problem statement is the same: Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j < k \le 5} \alpha_i \alpha_j \alpha_k$$ ...