MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

6 added 4 characters in body

You can use second-order cone optimization (SOCO) for this. SOCO generalizes linear optimization and allows for a linear objective, for constraints that are either the usual linear equations or inequalities, but also for constraints of the form $\|x\|\leq t$, where $x\in\mathbb{R}^n$ and $t\in\mathbb{R}$. Your problem becomes:

$$\min\{ t\mid \|u\|\leq t, \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m, t\in\mathbb{R}\}.$$

The standard SOCO solvers should have no problems with this.

But actually the quadratic problem $$\min\{ u^Tu\mid \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m\}.$$ should also yield to your quadratic solver.

EDIT: so $m$, the number of $F_i(x)$, is huge. Consider the following auxiliary problem: $$\min\{ \sum_{i\in I} a_i F_i(x)^2\mid Ax\leq b, x\in\mathbb{R}^n\}$$ for a subset $I\subseteq \{1,\ldots, m\}$. If the optimal $x^*$ of this problem satisfies $$F_i(x^*)>0 F_i(x^*)\geq 0 \Longleftrightarrow i\in I$$

then $x^*$ is an optimal solution to the original problem. Such an optimal $I$ can be found by applying the Dantzig-Wolfe method for quadratic optimization (http://pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf) to the original quadratic problem. If done with care, you can avoid the explicit enumeration of all the constraints $F_i(x)\leq u_i$ - they can be kept implicit in the quadratic form $\sum_{i\in I} a_i F_i(x)^2$ throughout.

5 deleted 2 characters in body

You can use second-order cone optimization (SOCO) for this. SOCO generalizes linear optimization and allows for a linear objective, for constraints that are either the usual linear equations or inequalities, but also for constraints of the form $\|x\|\leq t$, where $x\in\mathbb{R}^n$ and $t\in\mathbb{R}$. Your problem becomes:

$$\min\{ t\mid \|u\|\leq t, \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m, t\in\mathbb{R}\}.$$

The standard SOCO solvers should have no problems with this.

But actually the quadratic problem $$\min\{ u^Tu\mid \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m\}.$$ should also yield to your quadratic solver.

EDIT: so $m$, the number of $F_i(x)$, is huge. Consider the following auxiliary problem: $$\min\{ \sum_{i\in I} a_i F_i(x)^2\mid Ax\leq b, x\in\mathbb{R}^n\}$$ for any a subset $I\subseteq \{1,\ldots, m\}$. If the optimal $x^*$ of this problem satisfies $$F_i(x^*)>0 \Longleftrightarrow i\in I$$

then $x^*$ is an optimal solution to the original problem. Such an optimal $I$ can be found by applying the Dantzig-Wolfe method for quadratic optimization (http://pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf) to the original quadratic problem. If done with care, you can avoid the explicit enumeration of all the constraints $F_i(x)\leq u_i$ - they can be kept implicit in the quadratic form $\sum_{i\in I} a_i F_i(x)^2$ throughout.

4 edited body

You can use second-order cone optimization (SOCO) for this. SOCO generalizes linear optimization and allows for a linear objective, for constraints that are either the usual linear equations or inequalities, but also for constraints of the form $\|x\|\leq t$, where $x\in\mathbb{R}^n$ and $t\in\mathbb{R}$. Your problem becomes:

$$\min\{ t\mid \|u\|\leq t, \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m, t\in\mathbb{R}\}.$$

The standard SOCO solvers should have no problems with this.

But actually the quadratic problem $$\min\{ u^Tu\mid \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m\}.$$ should also yield to your quadratic solver.

EDIT: so $m$, the number of $F_i(x)$, is huge. Consider the following auxiliary problem: $$\min\{ \sum_{i\in I} a_i F_i(x)^2\mid Ax\leq b, x\in\mathbb{R}^n\}$$ for any subset $I\subseteq \{1,\ldots, n\}$m\}$. If the optimal$x^*$of this problem satisfies $$F_i(x^*)>0 \Longleftrightarrow i\in I$$ then$x^*$is an optimal solution to the original problem. Such an optimal$I$can be found by applying the Dantzig-Wolfe method for quadratic optimization (http://pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf) to the original quadratic problem. If done with care, you can avoid the explicit enumeration of all the constraints$F_i(x)\leq u_i$- they can be kept implicit in the quadratic form$\sum_{i\in I} a_i F_i(x)^2\$ throughout.

3 added 754 characters in body
2 deleted 16 characters in body
1