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)

1
vote
1answer
32 views

Prove that the following function has a unique maximum?

I was working on a problem and reduced it to showing $$f(\alpha)=n\ln \alpha-\ln \left(\sum_{i=1}^n t_i^\alpha+\int_a^b x^{\alpha+\beta-1} e^{-\lambda x^\beta} \, dx \right) + (\alpha-1)\sum_{i=1}^n ...
0
votes
0answers
7 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
1
vote
0answers
10 views
3
votes
2answers
51 views

Turn off the ovens! An optimization problem

The problem is more abstract, but can be illustrated nicely using ovens. A oven can produce any heat, but is most efficient when it produces $c$ heat. The inefficency increases quadratically as one ...
0
votes
2answers
37 views

Maximize the function $x+y$ on the closure of the unit ball

Find the maximum of $\{x +y : (x,y) \in closure [B(0,1)] \}$. Here $B(0,1)=\{(x,y) \in \mathbb{R}^2 : x^2+y^2 \leq 1\}$ I can't proceed in this as to how to maximize this value. Will it lie on ...
1
vote
1answer
11 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
1
vote
1answer
26 views

Find minimum number of coins with Largest value coins?

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find ...
0
votes
0answers
14 views

For any three integers $n$, $x<n$, and $y<n$, minimize the integer $xy-n>0$

I have some intuition that this is an integer programming problem, but I'm not sure exactly how to solve it that way. The alternative is brute force, which I'm sure can be outdone by better solutions. ...
1
vote
1answer
18 views

Maximizing symmetric functions on the unit cube

Let $f:[0,1]^n \to \mathbb{R}$. We say that $f$ is symmetric, if for every permutation $\sigma \in S_n$ and every $(x_1,..,x_n) \in [0,1]^n$ we have that $$f(x_1,..,x_n) = ...
12
votes
2answers
9k views

What is the best strategy for Cookie-Clicker-esque games?

Today, I stumbled across the game Cookie Clicker, which I recommend you avoid until you have at least a few hours of time to waste. The basic idea behind the game is this: You have a large stash of ...
0
votes
0answers
11 views

convex optimization with multiple nonsmooth terms

Is there a general algorithm for solving $$ \min f(x) + g(x) + h(x) $$ where all three functions are convex and proximable, $f(x)$ is smooth, and $g(x)$ and $h(x)$ are both nonsmooth? Note that if ...
0
votes
1answer
20 views

Maximum hyperrectangle

Is there a way to determine the coordinates of the maximum hyper-rectangle in n-D space subject to linear constraints and $x_i\ge0$ ? Example: Argument Maximum of $x_1 x_2 x_3$ Given ...
0
votes
1answer
21 views

Is my proof correct? Convex optimization

There's a theorem that says that if $C \subset \mathbb R^n$ is a convex set, then $x^* \in C$ is the closest point in $C$ to $y \notin C$ if and only if $(y-x^*)\cdot(x-x^*)\leq 0$ for all $x \in C$. ...
0
votes
0answers
14 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 ...
0
votes
1answer
17 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
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.
1
vote
2answers
42 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 ...
2
votes
0answers
145 views

Prove an artificial variable that leaves the basis will never return.

Prove an artificial variable that leaves the basis will never return. Edit: This is for the simplex method (I think). I have no idea how to start this. Anyone know any books with these kinds of ...
2
votes
1answer
758 views

How to see that K-means objective is convex?

I'm trying to proof that the objective of the K-means clustering algorithm is non-convex. The objective is given as $J(U,Z) = \|X-UZ\|_F^2$, with $X \in\mathbb{R}^{m\times n}, U\in ...
0
votes
0answers
13 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
418 views

How to solve nonlinear constrained optimization in Matlab?

I have to solve a nonlinear constrained function in matlab, and I am not familiar with it's commands. the problem is: minimize $E(b,c)$ constraints: $k1< c\sqrt{b}< k2 ; c/6>k3$ Note: E(b,c) ...
1
vote
1answer
17 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
39 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
32 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
1answer
53 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 ...
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
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
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
1answer
31 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
13 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$. ...
3
votes
1answer
103 views

Is this limit finite, or infinite?

Is $$\lim_{x\uparrow 1}\left(\frac{1-x}{x}\max\{nx^n|n\in\mathbb{N}\} \right)$$ infinite, or finite? ($\mathbb{N}$ is the set of the natural numbers). According to Mathematica, it looks like ...
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
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 ...
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 ...
2
votes
1answer
502 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
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} ...
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 + ...
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 ...
0
votes
2answers
707 views

Optimization, rectangle inscribed inside arch of the curve.

A rectangle is to be inscribed under the arch of the curve $y = 4\cos(0.5x)$ from $x = \pi$ to $x = -\pi$. What are the dimensions of the rectangle with largest area, and what is the largest area? ...
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$$ ...
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.