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.

learn more… | top users | synonyms (5)

0
votes
1answer
18 views

Question about separability of convex envelopes

Given a function $f(\boldsymbol{x})$ defined on the hypercube $\boldsymbol{x} \in [0,1]^n$. Suppose $f(\boldsymbol{x})$ can be expressed as $f(\boldsymbol{x})=c(\boldsymbol{x})+g(\boldsymbol{x})$, ...
1
vote
1answer
101 views

Recovering the optimal primal solution from dual solution

I'm having trouble finding the optimal primal solution of a particular problem from its dual solution. Primal: $\texttt{Maximize} \ \ 10 x_1 + 24 x_2 + 20 x_3 + 20 x_4 + 25 x_5$ Subject to $x_1 + ...
14
votes
3answers
4k views

Why are additional constraint and penalty term equivalent in ridge regression?

Tikhonov regularization (or ridge regression) adds a constraint that $\|\beta\|^2$, the $L^2$-norm of the parameter vector, is not greater than a given value (say $c$). Equivalently, it may solve an ...
0
votes
0answers
13 views

optima; value of a function

Suppose we have the following function $$Err(f) = \frac{1}{2}E|Y-f(X)| = P(Y=1,f(X)=-1) + P(Y=-1,f(X)=1),$$ where $Y, f(X) \in \{-1, 1\}$. How can find the optimal value of the above function, Err? I ...
0
votes
2answers
89 views

Minimize a non-convex function subject to linear dynamics constraint

I want to solve the following problem: $$\min\limits_{\bf u} \frac{\bf c^T {\bf x} (T_f)}{\| \bf c\|\|{\bf x} (T_f)\|}$$ subject to $$\dot{\bf x} (t) = A {\bf x}(t) + B {\bf u}(t)$$ $$x(0) = x_0$$ ...
2
votes
1answer
75 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
2
votes
4answers
250 views

Longest chord in the intersection n disks (circle areas)

Given n disks that intersect, there is a shape in the space where they intersect. Given that, what is the longest chord, more generally longest line, that can be drawn in this space? For n=1, this is ...
0
votes
5answers
566 views

I am trying to maximize an exponential function [closed]

I am looking for the value of $x$ that will maximize $y$ in the following equation $$ y=e^{-(x-a)^2/b} $$ where $a$ and $b$ are constants. Any help is appreciated
0
votes
1answer
88 views

If g(x) is the maximum value of f(t)

Let f be continuous on [a,b] and define a function g(x) on [a,b] as follows g(a)=f(a) and for a $\lt\ $x $\le\ $b then g(x) be the maximum value of f(t) on [a,x]. Prove that g(x) is continuous of [a,...
0
votes
1answer
663 views

Solving non-linear optimization using generalized reduced gradient (GRG) method

Consider the following elementary maximization problem: \begin{align} f{=}\mathrm{argmax}_{y_{l,c}, p_{l,c}}~\sum_{l=1}^{L}\sum_{c=1}^{C} y_{l,c}\text{log}_2\left(1+\frac{p_{l,c}}{I_{l,c}}\right) \end{...
0
votes
1answer
78 views

The meaning of 'worst case'

When giving bound on convergence rate, complexity and so on, people sometimes will specify it by 'worst case'. What is the meaning of 'worst case'?
1
vote
0answers
42 views

Optimization problem with variables in the subscript

I want to solve a optimization problem, which mimics the actions between a seller and several buyers. A seller has several goods, 1, 2, ... J, with prices $p_j$ and quantity $q_j$. A buyer can only ...
0
votes
1answer
308 views

The Euler-Poisson equation

$$\int_{0}^\pi (x''^2+4x^2) dt$$ $$ x(0)=x'(0)=0; x(\pi)=0;x'(\pi)=sinh(\pi)$$ This is The Euler-Poisson equation, i found: $$\frac {\partial f}{\partial x}-\frac {d}{dt} \frac{\partial f}{\partial x'}...
3
votes
1answer
46 views

Rate of Convergence of complicated sequence with interactions

I have been working on a problem where the sequence turns out to be so complex that i am unable to find its convergence rate with necessary and sufficient conditions on the parameters.After working ...
0
votes
2answers
132 views

How to maximize shipping box volume

Earlier last week I realized I needed to ship a large volume of things domestically. Of course, I decided that I wanted to do so as cheaply as possible. I first looked at USPS standard post rates. I ...
1
vote
0answers
74 views

Hammersley–Chapman–Robbins bound for Rice distribution

I am trying to evaluate the Hammersley–Chapman–Robbins bound for the variance of an unbiased estimate $\hat{\alpha}$ of $\alpha$ (for a given $\sigma$) for the Rice distribution: $$p(x|\alpha,\sigma) =...
1
vote
2answers
187 views

What is the derivative of this?

I have a function of the following form: $J = \|W^TW-I\|_F^2$ Where, $W$ is a matrix and $F$ is the Frobenius Norm. How can I find the derivative of $\frac{\partial J}{\partial W}$ ?
0
votes
1answer
36 views

Finding Maximum and Minimum for f(x,y)

The problem I am working on is: Find the maximum and minimum values of the function: $f(x,y) = -3x^2 - 14xy - 3y^2 -8$ on the disk: $x^2 + y^2 \leq 4$ The $-14xy$ term is severely throwing me for a ...
5
votes
2answers
83 views

How to minimize $x^2+4xy+5y^2-4x-6y+7$ without using calculus

I would like to find the smallest possible value of the function $$f(x,y)=x^2+4xy+5y^2-4x-6y+7$$ without taking any derivatives. My thoughts were to complete the square on both $x$ and $y$ and ...
1
vote
4answers
230 views

Maximizing the area of a triangle with its vertices on a parabola.

So, here's the question: I have the parabola $y=x^2$. Take the points $A=(-1.5, 2.25)$ and $B=(3, 9)$, and connect them with a straight line. Now, I am trying find out how to take a third point on ...
1
vote
0answers
36 views

Quasiconcavity of $g(x)=xf(K-x)$

The function $f(x)$ is strictly increasing, finite, positive and twice continuously differentiable on the compact interval $[0,K]$, and $f(0)=0$. I'm trying to either find a counterexample to, or a ...
1
vote
1answer
84 views

Find max/min of $f(x,y,z)$ on closed unit ball $B$ in $\mathbb{R^3}$

$f(x,y,z) = 3x - 2y + z$ Let $B$ be a closed unit ball in $\mathbb{R^3}$, find the max/min of f on $B$. We first need to observe $(a)$ the behavior of $f$ in $B^0$ $(b)$ the behavior of $f$ on $\...
1
vote
1answer
58 views

Question of proof of maxima related to quadratic form

Suppose $\bf{A}$ is a symmetric positive-definite matrix and now we want to maximize function $f(\bf{x})=\bf{x}^\rm{T}\bf{A}\bf{x}$ with restriction $\bf{x}^\rm{T}\bf{x}=\rm{1}$. Using Lagrange ...
0
votes
1answer
43 views

Showing CP-rule is not optimal for $P \mid p_j = 1, \text{ intree} \mid \sum C_j$.

We are asked to find a counterexample that shows that the Critical Path rule is not optimal for $P \mid p_j = 1, \text{ intree} \mid \sum C_j$. However, after trying for two hours, I don't think I'll ...
0
votes
1answer
24 views

Simply function F and find alpha for which F will be min

I have point coordinates like [x, y], where x and y are positive natural numbers. I need to ...
1
vote
1answer
79 views

Find minimum of $P=\frac{\sqrt{3(2x^2+2x+1)}}{3}+\frac{1}{\sqrt{2x^2+(3-\sqrt{3})x +3}}+\frac{1}{\sqrt{2x^2+(3+\sqrt{3})x +3}}$

For $x\in\mathbb{R}$ find minimum of $P$. $P=\dfrac{\sqrt{3(2x^2+2x+1)}}{3}+\dfrac{1}{\sqrt{2x^2+(3-\sqrt{3})x +3}}+\dfrac{1}{\sqrt{2x^2+(3+\sqrt{3})x +3}}$ Source : Viet Nam national test for high ...
2
votes
2answers
65 views

Find all minima and maxima of $f(x) = (x+1)^{1/3}(x^2-2x+1)^{1/5}$

Find all minima and maxima of : $f(x) = (x+1)^{1/3}(x^2-2x+1)^{1/5}$ I feel kind of ashamed by posting such a question but I am not able to get the right answer. I've tried to do it the Fichtenholtz ...
4
votes
0answers
109 views

StackEgg optimal algorithm

What is the minimum number of days that is needed to complete the StackEgg game? (It's on the right if anyone didn't notice.) There are four markers (Questions, Answers, Users, Quality) I believe each ...
2
votes
3answers
51 views

Can we not determine the minimum and maximum value of a function by just obtaining the value of the function at the critical points?

Can we do the above or is it neccessary to find the sign of the second derivative. I find no problem with any of the above but the answer of the following question left me confused. "The real number ...
1
vote
0answers
35 views

Combinatorics : Minimization of the number of common objects between subsets

Let's consider the following setup. I have access to $N$ objects. Thanks to these objects, I can build up sub-packets containing $k$ such objects. I know that there exists a total of $\displaystyle N\...
1
vote
0answers
66 views

find min max of function on unit ball

$g(a,b,c)=3a-2b+c$, B is a closed unit ball in $\mathbb R^3$. Find the max/min of g on B. What is the behavior of $g$ on the open unit ball, and the boundary of the unit ball? I think the unit ball ...
0
votes
2answers
167 views

What is the derivative of a matrix w.r.t itself?

what is the derivative of \begin{equation}\partial \frac{x^TVx}{\partial V} \end{equation} where V is a matrix and x is a vector. In general what is the right way to calculate matrix derivatives w.r.t ...
2
votes
1answer
64 views

Optimal solutions of x and y for $\max_{x,y}~\min (f(x,y),~g(x,y))$

Can someone help me to find analytical solutions for optimal values of $x$ and $y$ which satisfy the following optimization problem? \begin{align} \max_{x,y}~\min & \left[a\left(\frac{1-x}{2-x}\...
2
votes
1answer
250 views

Proximal mapping of $f(U) = -\log \det(U)$

This is an assignment problem which I failed to solve in a couple of days. Denote the set of all $n \times n$ symmetric matrices and the set of all $n \times n$ symmetric positive definite matrices ...
0
votes
1answer
30 views

If $x = \operatorname{argmin}_{x \in X} \lvert Ax - y\rvert^2$ does it mean that $Ax = \operatorname{Proj}_X(Ay)$?

Suppose that $A$ is an invertible matrix and $$x = \operatorname{argmin}_{x \in X}\lvert Ax - y\rvert^2,$$ then does it mean that $Ax = \operatorname{Proj}_X(y)$ like in the definition of ...
1
vote
2answers
149 views

Triangle containing most points from a set

Given a point set in $\mathbb{R}^2$, I need to find a triangle connecting three points of the set that contains the most points of the set. Points that lie on the connecting lines don't count. The ...
0
votes
1answer
44 views

Is this function jointly convex in its variables?

I have a function which I suspect is jointly convex, but have a difficult time proving it, especially since the Hessian is messy. The function is $f(y_i,i=1.2,\ldots,N)=\sum_i l_i w_i + y_i$, where $$...
0
votes
0answers
70 views

Equivalence of Two Statements (Duality Theory, Optimization)

Let $a$ and $a_{1}, ... , a_{m}$ be given vectors in $\mathbb{R^{n}}$. Prove that the following two statements are equivalent. $a)$ For all $x \geq 0$ we have $a^tx \leq\max\limits_{i}(a_{i}^tx)$. $...
1
vote
2answers
45 views

Another optimization problem

I am having trouble figuring out a next step in an optimization problem the question is to find the max and min values of $f(x,y)=\frac{x+y}{2+x^2+y^2}$ I calculated $f_x$ and $f_y$ and set both ...
1
vote
2answers
88 views

How to minimize the function $f(x,y) = x^2 + \frac{9}{4}y^2 + 3xy -2x-2y \;\;\;$ s.t. $x,y \geq 0$

My task is to minimize the function $$f(x,y) = x^2 + \frac{9}{4}y^2 + 3xy -2x-2y \;\;\;$$ subject to $x,y \geq 0$. Do I need to use Lagrange multipliers in this problem? I tried simply taking the ...
-1
votes
1answer
53 views

Minimize the cost of a 3 cubic unit volume box, given the price of each of six sides per unit area

I was wondering if anyone could help verify my answer of a question, or if it is incorrect to maybe let me know my mistake? The questions asks to minimize the cost of a 3 cubic unit volume rectangle ,...
1
vote
1answer
32 views

Conditions for global max of symmetric function to lie on diagonal

Assume $f:[0,1] \times [0,1]$ is symmetric, i.e. $f(x,y) = f(y,x) \;\;\forall x,y \in [0,1]$. Assume further that $f$ is smooth, and that for every $x \in [0,1]$ the map $\phi_{x}(y):=f(x,y)$ attains ...
0
votes
1answer
33 views

How to set up matrix to compute best coefficients

Suppose we're given a non-linear spring with the following relationship between the applied weight ($x$) and displacement ($y$): $y = ax + bx^3$. I've done a sequence of $m$ tests measuring the ...
1
vote
0answers
12 views

Approximation for the minimal test cover / minimal group test problem

There are multiple approximation methods I find for the minimal test cover, where approximation is with respect to the size of the test set. However I am looking for approximation which starts with a ...
3
votes
0answers
371 views

Real approximation to the maximum using Laplace's method integral

The Laplace's Method states that under some conditions, it holds that: $ \sqrt{\frac{2\pi}{M(-g''(x_0))}} h(x_0) e^{M g(x_0)} \approx \int_a^b\! h(x) e^{M g(x)}\, dx \text { as } M\to\infty$ Where $...
1
vote
2answers
2k views

Optimization, find the dimensions of the poster with the smallest area

The top and bottom margins of a poster are 4 cm and the side margins are each 2 cm. If the area of printed material on the poster is fixed at 380 square centimeters, find the dimensions of the poster ...
-2
votes
1answer
59 views

Modelling Problem in Linear Programming Standard Form

I'm having a hard time setting this up, so that's what I need help with. The solving I understand. We’re making a drink with the following requirements: at least 500 calories, at least 20 mg. of ...
0
votes
3answers
112 views

Spectral Theorem / Quadratic Form Minimization Problem

Here is the problem: Let $A$ be an $n \times n$ symmetric matrix. Let $S = \{ \mathbf x \in \mathbb R^n : ||\mathbf x|| = 1 \} $ denote the unit sphere. Let $Q(\mathbf x) = \mathbf x ^TA\mathbf x $ ...
0
votes
1answer
37 views

Confirmation of maximization problem

Hey all I am working on a problem, and my numbers are coming out not so nice so I think It is possible that I am making a mistake and if so Id be really interested in learning how to do it correctly. ...