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
0answers
12 views

Designing an aggregate weighted cost function

In my undergraduate thesis, I am trying to solve a problem which finds an optimal POI (e.g. a restaurant) for a group of users. Each user $q_i$ is assigned a cost $c_{ij}$ with respect to a POI $o_j$. ...
0
votes
0answers
16 views

Travelling Salesperson MTZ

I have been solving a $10$ city travelling salesperson problem. Having solved the assignment based relaxation problem, I have $5$ subtours: $1 \rightarrow 10 \rightarrow 1$ $2 \rightarrow 8 ...
1
vote
0answers
10 views

Estimation of binomial probabilities $f(r)$ over $r \in [0,\frac{1}{2}]$

I want to fit a (decreasing) univariate function, \begin{equation} f(r), \end{equation} over $r \in [0,\frac{1}{2}]$ to a series ($r =\frac{1}{100}, \frac{2}{100}, \frac{3}{100} ,\ldots,\frac{1}{2}$) ...
0
votes
1answer
28 views

Proving f cannot be convex

The following question I encountered in a convex optimization course and I can't seem to understand the solution.
0
votes
1answer
16 views

Maximize two variables function subject to quadratic constraint

Two mariners end up on a island, with 1800 pounds of food to share, i.e. $F1 + F2 = 1800$. I'm expected to maximize the social welfare function given by $W=U1^{0.25}*U2^{0.75}$ where $U1=\sqrt{F1}$ ...
1
vote
2answers
40 views

Solving the devil's penny puzzle

I was reading an article about the devil's penny puzzle. We are given $n$ boxes, one of which contains the devil's penny while the others contain an amount of money $a_1,\ldots,a_{n-1}$. These numbers ...
0
votes
0answers
12 views

What star rating is representative of this distribution? [on hold]

100 people vote. They can vote 1, 2, 3, or 4 stars. Distribution: 1 = 33, 2 = 26, 3 = 12, and 4 = 28. What star rating would you say is "representative" of these 100 people: 2.36 (2), the average, ...
1
vote
1answer
16 views

Signed angle difference without conditions

I've got two angles in $0 \leqslant a < 360$ and I need to find the signed difference between them which should be $-180 < \Delta < 180$. Is there a way to calculate the difference with ...
-1
votes
0answers
18 views

Effects of degenerate basic feasible solutions in the simplex algorithm? [on hold]

Let $P$ =$\{x\in \mathbb{R}^n :Ax=b,x\geq 0\}$,where $A$ is a $d×n$ matrix of rank $d$. Suppose that all basic feasible solutions are nondegenerate. Let $x \in P$ have exactly $d$ positive entries. ...
0
votes
1answer
37 views

why are the Bisection and Newton Method for finding roots complementary to each other?

my lecture note states that the bisection and newton method for finding roots are most of the time complementary to each other but I can not figure out why. I have basic understanding of both of the ...
2
votes
2answers
31 views

Am I allowed to do this chain-rule type thing when optimizing wrt to a functional?

So we have a function $f(x) = g(x)h(y(x))$ that is convex in $y$ which we want to optimize by choosing the appropriate $y(x)$. I have seen the following done in engineering books, but it just looks so ...
0
votes
0answers
30 views

minimize this objective function

I have a function to minimize and I don't understand how I should proceed. The function is coming from a publication. Background: In a 2D image, $P_1$ and $P_2$ represents 2 patches of colors (RGB) ...
1
vote
2answers
52 views

Find the smallest positive value taken by $a^3+b^3+c^3-3abc$

Find the smallest positive value taken by $a^3+b^3+c^3-3abc$ for positive integers $a,b,c$. Find all integers $a,b,c$ which give the smallest value. Since it is generally hard to find the minimum ...
0
votes
0answers
19 views

Maximization over minimum function

I want to solve the following optimization problem. Suppose we are given $p_r^i \in [0,1]$ for $r={1,2,...,N}$ and $i={1,2}$ such that $\sum_{r=1}^N p_r^i =1$ for i={1,2}. We want to find $x_r \in ...
0
votes
1answer
29 views

Optimizing the area of a rectangle with one side against a wall using the am-gm inequality

Given 300 meters of fence, how can I find the dimensions of a rectangle that is built against a wall the encloses the maximum area. I found this question in a calculus book and saw a simple solution ...
0
votes
0answers
12 views

Using the Fourier Series in Variational Optimization Problems

Say I have a functional $L(f)$ which takes as input the function $f:\mathbb{R}\to\mathbb{R}$, and I want to find the function that optimizes $L$. Unfortunately, there's no way to define a functional ...
0
votes
1answer
17 views

Find the positions of $A$ and $B$ which minimizes the length $AB$.

The line $AB$ joins the points $A(a, 0 )$, $B(0, b)$ on the $x$ and $y$ axes respectively and passes through the points $(8, 27)$. Find the positions of $A$ and $B$ which minimizes the length $AB$. ...
0
votes
1answer
10 views

Softmax Regression Derivative

This website, http://deeplearning.stanford.edu/wiki/index.php/Softmax_Regression, claims the derivative of a multinomial regression: $$ J(\theta) = -\frac{1}{m}\sum_{i=1}^m \sum_{j=1}^k 1\{y^i =j\} ...
0
votes
0answers
16 views

Singularities of composite function

Given a smooth, compact manifold $M$ (of dimension much less than $n$) and two maps $f:\mathbb{R}^n \rightarrow M$, $g:M\rightarrow \mathbb{R}$, I want to understand the topology of the critical set ...
0
votes
0answers
12 views

Derivation of SVM algorithm (Lagrangian)

I have a question about the derivation of the SVM algorithm (for example, page 3 here ). The question is about the math, so that's why I'm asking this here. Suppose I have the following optimization ...
5
votes
2answers
199 views

Set is Convex regardless of b

Let the function $f$ be convex, $f :\Bbb R^n \rightarrow \Bbb R$ and let $$S = \{x : f(x) \le b\}$$ The proposition states that the set $S$ is convex regardless of $b$. Can someone explain to me how ...
0
votes
1answer
52 views

Maximum of polynomial [on hold]

I was studying statics and came across this problem: Find the value $\beta$ such that $P$ has a maximum value in $R^2 - 1000^2 = P^2 + 2000P\cos(75^{\circ}+\beta)$. When $R$ is constant, the ...
3
votes
1answer
26 views

How do you find $∠XPC$ + $∠XPB$ such that $PB+PC$ is maximum where $P$ is a point on $f(x) = (x-1)(x-3)(x-5)$?

Problem: $f(x) = (x-1)(x-3)(x-5)$ intersects the x axis at $A(1,0)$, $B(3,0)$ and $C(5,0)$. A point $P(t,f(t))$ is selected on the curve such that $PB+PC$ is maximum and $t \in (3,5).$ Let $PX$ be ...
0
votes
0answers
8 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
0
votes
1answer
25 views

How can we solve this system of linear inequalities?

Let $c_i$ be a given non-negative integer for all $i\in\{1,\ldots,n\}$. I would like to find the non-negative integers $a_i$ and $b_i$ for all $i\in\{1,\ldots,n\}$ such that: \begin{align} ...
0
votes
0answers
23 views

Local maximum of $(2^{xy}{z \choose y})^{z+1}$

I have an optimization problem where I need to calculate the maximum of the following function $$ f(x,y,z) = (2^{xy}{z \choose y})^{z+1} $$ where $$ (z+1)(a+y(\lceil{\log_2{(z+1)}}\rceil+x))\leq C $$ ...
0
votes
0answers
8 views

ADMM Formulation for fractional programs?

I have a fractional program $$ \min \frac{f(x)}{g(x)} $$ where $f(x)$ and $g(x)$ are both quadratic functions (i.e. they are convex). It has been shown that this can be alternatively represented by ...
1
vote
1answer
50 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + ...
2
votes
0answers
42 views

How to prove that the following function has a unique mode?

I am trying to prove that the function $$f(\alpha)=n\ln \alpha-n\ln\Big(\sum_{i=1}^{n}t_i^\alpha+\int_{a}^{b}x^{\alpha+\beta-1}e^{-\lambda x^\beta}\,dx\Big)+(\alpha-1)\sum_{i=1}^{n}\ln t_i,$$ where ...
0
votes
2answers
26 views

SVD with Sparisty Penalties

I am trying to solve a problem like $$\min_{u,v} \Vert X-uv^T \Vert_F^2 + \beta \Vert v \Vert_1 \mbox{ s.t. } \Vert u \Vert_2 \le 1$$ where $X \in \mathbb{R}^{N\times N}$, $u, v \in ...
1
vote
0answers
29 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
0
votes
0answers
13 views

Optimizing functions with a complex domain and a real codomain

In general I want to understand if it makes sense to optimize a function of the following form $f: \mathbb{C} → \mathbb{R}$ for my specific problem $f(z) = | z | ^{2} $ (wich I is not analytic since ...
-1
votes
0answers
12 views

Removing variables from convex linear program

I am solving linear program (possibly non-convex). Then we know that dual is always convex. Then I noticed that depending on objective functional I can sometimes remove particular variables from this ...
0
votes
0answers
19 views

Negative eigenvalue of a hessian matrix entails a local decrease in function value?

I was reading up on non-convex optimization, and I can across this sentence: "Since Hessian(f(w)) has a negative eigenvalue, there is always a point that is near w which has smaller function value" ...
7
votes
3answers
156 views

How do you find the maximum value of $|z^2 - 2iz+1|$ given that $|z|=3$, using triangle inequality?

Problem: How do you find the maximum value of $|z^2 - 2iz+1|$ given that $|z|=3$, using triangle inequality? My attempt: $$|z^2 - 2iz+1|\le|z|^2+2|i||z|+1$$ $$\implies |z^2 - 2iz+1|\le16$$ ...
2
votes
1answer
25 views

Win/Lose ratios and selection strategies

Imagine the following scenario: You're on a TCG tournament which allowed you to bring N decks with you. After each game, you might select another deck for your next game. You are allowed to keep ...
1
vote
0answers
67 views

Making a Matrix singular

During my research I came across the following problem. Intuitively this should be an easy one. However, the simplest version of it looks like this: Let $C \geq \frac{1}{2}$ be some fixed ...
1
vote
1answer
28 views

Inequality with three unknowns

Consider: \begin{equation} \Big(e^x-1\Big)\mathbb{1}_{(x\geq0)} \leq \lambda_1+\lambda_2e^x + \lambda_3x^2 \end{equation} where $\lambda_1$, $\lambda_2$, $\lambda_3$ are three unknown constants. By ...
0
votes
0answers
10 views

Gradient Descent with multiplication term

Say I have the objective: $\arg \min_{R, T} \|y - RTx\|^2_2$ where, R and T are matrices (not necessarily square) and y and x are known vectors. I wish to try and optimize R and T using Gradient ...
0
votes
0answers
29 views

Understanding ADMM: how is it applied to this particular problem?

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
0
votes
1answer
24 views

Continuity of Parameterized Optimal Solution

Suppose for every $y$, $f(x,y)$ is strictly convex in $x$. Further, $f(x,y)$ is continuous in $y$. Let $\mathcal X$ be compact (in my problem, $\mathcal X$ is an interval). Can anyone suggest any ...
0
votes
0answers
13 views

Setting the right restriction in a simple linear optimization task

here is the task: One factory produces 3 types of cars: small, midsize and big. There are 6000 tons of steel and 60000 total time available. For each type of car produced, there must be 1000 cars of ...
0
votes
1answer
19 views

What is the maximum of the following function?

Let $f(x,y) = \frac{xy^\alpha}{x+y},\alpha\in(0,\infty)$. How to compute $$\sup_{(x,y)\in[a,b]\times [0,c]}\frac{xy^\alpha}{x+y},$$ with $b>a>0$?
0
votes
0answers
16 views

One-dimensional deblurring

I just begun studying image deblurring on my own, and I have a question. Most books I found say that I can see the images as arrays, and that I can "vectorize" the arrays of the images by stacking the ...
0
votes
1answer
16 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
0
votes
0answers
5 views

Biorthogonal (discrete wavelet) noise bases?

I am slightly interested in discrete wavelet transforms (DWT), but so far I have mostly used already-derived and existing well-known wavelets, such as Daubechies, Cohen-Daubechies-Faveau, Symlets and ...
0
votes
3answers
55 views

How to do a regression which includes reciprocals?

I'm trying to find an interpolating formula for a set of coefficients (I have $80$ at the moment). I tried first to find an interpolating polynomial, but that was not useful: using the first ...
1
vote
0answers
54 views
+100

Interpolation and mapping between scattered vectors in two unequally dimensioned spaces

Imagine two spaces: An ‘input’ space with dimension $m$. An ‘output’ space with dimension $n$. $m \geq n$ There are points in each of these spaces defined such that some characteristic is ...
1
vote
0answers
35 views

Basic optimization question

A teacher put this problem up the other day and I'm confused about how he got to the answer. Can you explain it to me? Job $X$ provides $20$ vacation days and $143,000$ euro annual salary. Job $Y$ ...
0
votes
0answers
20 views

What the minimum of infinite tetration divided by $\sqrt{x}$?

For some values of $x$ the limit of infinite tetration converges. For example when $x=\sqrt{2}$ this is fixed point $$\lim_{n\rightarrow \infty} \sqrt{2} \uparrow \uparrow n = ...